[Chapter 8. 메모리 관리 전략] 페이징

스택이나 힙 세그먼트가 확장될 때 사용* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

결속 방식에 따른 메모리 경영 기법의 분류

 

분류	공간 크기	사상 단위	적재 단위
분할 방법	논리 = 물리	전체 프로그램	전체 프로그램
페이징 / 세그먼테이션	논리 = 물리	페이지 (세그먼트 기법은 가변 크기)	전체 프로그램
가상 메모리	논리 > 물리	페이지	프로그램 일부 적재

 

분할 방법의 단편화 문제는 프로그램이 연속된 메모리에 탑재되어야 하는 것이 근본적인 문제점이었다.

 

페이징 기법과 세그먼테이션 기법은

연속된 물리 공간이 필요하지 않으며, (프로세스가 적재되는 물리 주소 공간이 연속적이지 않아도 적재를 허용)

실행 시간 주소 결속이 가능하다.

 

페이징 (Paging)

---

페이징 기법에서 물리 메모리는 프레임(frame), 논리 메모리는 페이지(page)라고 불리는 같은 크기의 블록으로 나뉜다.

(프레임의 크기 = 페이지의 크기)

 

프레임과 페이지는 페이지 테이블을 통해서 대응되며,

이를 통해 모든 논리 주소는 페이징 하드웨어에 의해 물리 주소로 사상(mapping)될 수 있다.

* 페이징 그 자체는 동적 재배치의 한 형태

 

 

페이징의 가장 중요한 특징은 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다르다는 것이다.

 

프로그래머는 메모리가 하나의 연속적인 공간이며, 메모리에는 이 프로그램만 있다고 생각한다.

하지만 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램이 메모리에 올라와 있다.

 

페이지 테이블

프레임과 페이지의 대응 관계를 나타내는 주소 변환 테이블로, 주 메모리에서 각 페이지가 점유하는 프레임의 시작 주소를 가지고 있다.

프레임의 시작 주소 + 페이지 내의 상대 주소(offset)를 통해 실제 메모리 상에서의 주소(물리 주소)를 알아낼 수 있다.

 

 

* 주소 표현

 

1. 논리 주소 : (p, d)

p : 페이지 번호 - 페이지 테이블을 액세스 할 때 사용

d : 페이지 변위 (페이지 내의 상대 주소, offset)

 

페이지의 크기는 컴퓨터 구조에 따라 페이지 당 512B에서 16MB 사이이며, 2의 제곱으로 증가한다.

 

만약 논리 주소 공간의 크기가 2^m, 페이지의 크기가 2^n이라면

논리 주소의 상위 m-n 비트는 페이지 번호를 나타내고, 하위 n비트는 페이지 변위를 나타낸다.

 

 

2. 물리 주소 : (f, d) = 프레임의 시작 주소 + 페이지 변위 (offset) = f * S + d

f : 페이지 p에 해당하는 프레임의 번호 (frame number)

S : 프레임의 크기 = 페이지의 크기

 

내부 단편화 (Internal Fragmentation)

페이징 기법에서는 외부 단편화가 일어나지 않는다.

놀고 있는 모든 프레임이 프로세스에게 할당될 수 있기 때문이다.

 

 

하지만 프로세스를 페이지 단위로 나누는 것에서 내부 단편화가 발생한다.

 

할당은 항상 프레임의 정수 배로 할당되는데,

모든 프로그램의 크기는 프레임/페이지의 크기(S)의 정확한 정수배로 되어 있지 않기 때문에

맨 마지막 페이지의 실제 코드 양은 최소 1 byte, 최대 S byte가 될 것이다.

 

평균 S/2 byte가 되기 때문에, 평균적으로 각 프로세스에 대하여 프레임의 절반 크기로 내부 단편화가 일어나게 된다.

 

페이지의 크기가 작은 것이 바람직하겠지만, 이에 반비례해서 페이지 테이블의 크기가 커지게 되어 공간 낭비가 생긴다.

디스크의 입장에서는 페이지의 크기가 클수록 효율적이다. (12장)

 

일반적인 추세는 페이지 크기가 프로세스, 자료, 주 메모리가 커짐에 따라 함께 커져왔으며,

현재 보통 페이지 크기는 2~8 KB이다.

 

Free Frame 리스트

한 프로세스가 실행되기 위해 도착했다면 그 프로세스의 크기가 페이지 몇 개 분에 해당하는지 조사하게 된다.

프로세스가 n개 페이지를 요구한다면 메모리에서 이용할 수 있는 프레임은 n개가 있어야 한다.

 

운영체제는 새로운 프레임 할당을 위해 가용 프레임들을 free frame 리스트로 운용한다.

 

 

프레임 테이블(Frame Table)

운영체제는 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다.

프레임 테이블(frame table)이라는 자료 구조를 통해 프레임 별 할당 상황(할당 여부, 할당 프로세스 등), 총 프레임의 수 등을 관리한다.

 

보호 (Protection)

메모리 접근을 위해서는 페이지 테이블을 반드시 거쳐가야만 하기 때문에 메모리 보호나 기타 유용한 용도로 사용이 가능하다.

 

1. 보호 비트

페이징에서의 메모리 보호는 각 페이지에 붙어있는 보호 비트(protection bit)에 의해서 구현된다.

보호비트는 보통 페이지 테이블에 속해 있으며,

각 비트는 이 페이지가 읽고-쓰기 가능한지 읽기 전용(read-only)인지를 각각 정의할 수 있다.

 

2. 유효/무효 비트

페이지 테이블의 각 엔트리에는 '유효/무효'라는 하나의 비트가 더 있다.

유효(valid) : 관련 페이지가 프로세스의 합법적인 페이지임을 나타낸다.

무효(invalid) : 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.

 

이 비트를 통해 해당 페이지에 대한 접근 허용 유무를 설정할 수 있다.

 

3. PTLR

페이지 테이블 항목에는 모든 페이지를 배정하지 않는다.

따라서 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해

모든 논리 주소 값이 페이지 테이블 길이 레지스터(Page Table Length Register, PTLR)의 값과 비교된다.

 

만약 해당 레지스터의 값을 넘어가는 것으로 판명된다면 트랩을 발생시킨다.

 

공유 페이지 (Shared pages)

페이징은 코드를 쉽게 공유할 수 있도록 한다.

 

만약 재진입 가능 코드(reentrant code, pure code)라면 아래의 그림과 같이 프로세스 사이에서 공유가 가능하다.

 

 

재진입 가능 코드는 수행하는 동안 절대로 변하지 않기 때문에 여러 프로세서들이 동시에 같은 코드를 수행할 수 있다.

따라서 단 하나의 편집기 코드 사본이 물리 메모리에 올라오기만 하면 공유가 가능해진다.

 

 

---

하지만 페이징 기법은 아래의 문제점들을 가진다.

1. 주소 결속까지 걸리는 속도

2. 페이지 테이블의 용량

 

주소 결속 속도를 높이기 위해서 TLB를 사용하며,

페이지 테이블의 용량 문제를 해결하기 위해 페이지 테이블을 구성하는 여러 방법들이 존재한다.

 

TLB(Translation Look-aside Buffers)

페이지 테이블은 크기가 작은 경우, 레지스터의 집합으로 구현할 수 있다.

하지만 대부분의 페이지 테이블 내 항목은 1백만을 초과하기 때문에 테이블 구현을 위해 레지스터를 사용하는 것은 부적절하다.

 

따라서 대부분의 컴퓨터는 페이지 테이블을 주 메모리에 저장하고,

페이지 테이블 기준 레지스터(Page-Table Base Register, PTBR)에 페이지 테이블의 시작 주소를 저장하는 방식을 사용한다.

다른 페이지 테이블을 사용하려면 PTBR의 값만을 변경하면 되는 것이다.

 

하지만 이 방식은 2번의 메모리 접근이 필요하기 때문에 메모리 접근 시간이 2배로 느려진다는 문제점이 있다.

* 메모리 접근 : 1. 페이지 테이블에 대한 접근 / 2. 메모리 자체(물리 주소)에 대한 접근

 

 

 

메모리 접근 시간에 대한 해결책으로, TLB(Translation Look-aside Buffer)라는 소형 하드웨어 캐시를 둔다.

TLB는 16~32개의 연관 레지스터(associative register)를 사용하여 병렬 검색이 가능하다.

 

TLB의 각 레지스터는 <key, value>를 저장한다.

key : 페이지 번호 (= 논리 주소의 p)

value : 프레임 번호 (= 프레임 시작 주소 f)

 

 

운영 방법

1. TLB는 페이지 테이블의 일부분만을 저장한다.

2. CPU가 논리 주소를 생성하면 해당 페이지 번호가 TLB에 전달된다.

3-1. 페이지 번호가 발견되면(TLB hit) 해당 프레임 번호를 즉시 알 수 있다.

3-2. 페이지 번호가 발견되지 않으면(TLB miss) 페이지 테이블에 접근하여 프레임 번호를 얻는다.

        새로운 페이지 번호와 프레임 번호를 TLB에 추가하는 것을 통해 다음 참조 시 빠르게 처리할 수 있게 된다.

4. 프레임 번호가 얻어지면 페이지 변위(offset, 논리 주소의 d)와 더해져서 물리 주소로 변환, 메모리에 접근하는 데 사용된다.

 

* 적중률(hit ratio) : 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율

 

 

만약 TLB가 가득 차게 되면 기존 항목들 중 교체될 항목을 선택해야 하는데,

이때 FIFO, LRU, 라운드 로빈, 무작위 등 다양한 교체 정책이 사용될 수 있다.

 

 

어떤 TLB는 각 항목에 ASID(Address-Space Indentifiers)를 저장하기도 한다.

ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려준다.

 

TLB에서 가상 주소를 변환할 때, 현재 수행 중인 프로세스의 ASID가 TLB 항목에 있는 ASID와 동일한지 검사를 진행하게 되고

만약 동일하지 않다면 TLB miss로 처리하여 프로세스의 정보를 보호한다.

따라서 ASID 지원이 있다면 한 TLB 안에 여러 프로세스들의 정보를 동시에 함께 보관할 수 있다.

 

만약 ASID가 없다면 새로운 페이지 테이블이 선택될 때마다 (ex. 새 프로세스가 문맥 교환해서 실행을 재개하는 경우)

다음 실행 프로세스가 잘못 변환을 하지 않도록 하기 위해 TLB는 전부 flush 되어야 할 것이다.

 

 

페이지 테이블의 구조

페이지 테이블의 속도 측면의 성능뿐만 아니라, 페이지 테이블의 크기도 중요한 이슈이다.

요즘 많은 현대 컴퓨터들은 큰 주소 공간을 가지는데(2^32 ~ 2^64), 이에 따라 페이지 테이블도 상당히 커진다.

 

32비트 주소 체계를 사용(주소 공간의 크기 : 2^32)하는 컴퓨터가 있다고 하자. 

페이지의 크기가 4 KB(2^12)라고 한다면, 페이지 테이블에는 2^20(= 2^32 / 2^12) 개의 주소 변환 정보가 저장되어야 한다.

각 항목은 4 B로 구성되기 때문에, 각 프로세스는 4 MB의 페이지 테이블이 필요하게 될 것이다.

이 큰 공간을 주 메모리에서 연속적으로 할당해주는 것은 어렵다.

 

 

이를 해결하는 방법으로는 모든 페이지 테이블을 주 메모리에서 연속적으로 탑재하기보다는

페이지 테이블을 여러 개의 조각으로 분할하여 운영하는 것이 있다.

 

따라서 페이지 테이블의 크기 문제를 구조 차원에서 해결하는 3가지 방법들에 대하여 알아보도록 하자.

 

1. 계층적 페이징 (Hierarchical paging) (2단계, 다단계 페이징 기법)
2. 해시 페이지 테이블 (Hashed page table) → 클러스터 페이지 테이블 (Clustered Page Tables)
3. 역 페이지 테이블 (Inverted page table)

 

계층적 페이징 (Hierarchical paging)

페이지 테이블 자체가 다시 페이지화되는 것이다.

 

1. 2단계 페이징 기법 (Two-Level Paging Scheme)

논리 주소 상의 페이지 번호(p)를 2단계로 분할한다.

 

논리 주소 : (p1, p2, d)

p1 : 바깥 페이지 테이블(outer page table)의 인덱스

p2 : 안쪽 페이지 테이블(inner page table)의 페이지 내의 변위

d : 페이지 변위 (offset)

 

 

* 더 자세한 운영 방식은 아래와 같다.

 

 

 

(예시)

페이지의 크기가 4 KB인 32비트 주소 체계 컴퓨터가 있다고 하자.

이 컴퓨터에서 논리 주소는 20비트만큼을 페이지 번호가 차지, 나머지 12비트만큼이 페이지 변위로 이루어진다.

 

여기서 페이지 테이블도 페이지로 나누어지기 때문에

페이지 번호를 나타내는 20비트는 10비트짜리 페이지 번호(p1)와 10비트짜리 페이지 변위(p2)로 나누어진다.

 

 

주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오는 식으로 이루어지기 때문에

forward-mapped 페이지 테이블이라고도 부른다.

 

 

2. 다단계 페이징 기법

64비트 주소 체계를 가진 시스템에서는 2단계 페이징 기법도 적절하지 못하다.

 

페이지 크기가 4 KB(2^12)라고 가정하면, 페이지 테이블은 2^52(= 2^64 / 2^12) 항목으로 구성될 것이다.

여기서 2단계 페이징을 사용하게 되면 논리 주소는 아래와 같이 된다.

 

 

바깥 페이지 테이블은 2^42 항목을 가지게 되고, 결국 2^44 바이트의 너무 큰 연속 공간이 필요하게 된다.

 

따라서 바깥 페이지 주소 부분을 다시 둘로 분할한다. 바깥 페이지 테이블을 페이지시키는 것이다. (3단계 페이징 기법)

p1 (32비트) : 바깥 페이지의 인덱스

p2 (10비트) : 바깥 페이지 테이블의 페이지 내의 변위

p3 (10비트) : 안쪽 페이지 테이블의 페이지 내의 변위

 

 

바깥 페이지와 안쪽 페이지는 페이지 단위의 페이징을 해야 하기 때문에 10비트를 초과하기 어렵다.

p1을 32비트로 할 수밖에 없고, 바깥 페이지 테이블은 여전히 2^34 바이트 즉, 16 GB의 크기를 요구한다.

 

 

다음 단계로 2번째 바깥 테이블 자체를 페이징 하는 4단계 페이징 기법을 사용할 수 있을 것이나,

각 논리 주소를 사상하기 위해 너무 많은 메모리 접근을 요구하기 때문에 비현실적이다.

이미 3단계 페이징 기법에서 논리 결속을 위해 물리 메모리를 4번씩이나 접근해야 한다.

 

따라서 주소 공간이 32비트보다 큰 구조에서는 계층적 페이지 테이블이 부적합하다.

 

해시 페이지 테이블 (Hashed Page Table)

위에서 주소 공간이 32비트보다 커지면 계층적 페이징을 사용하기 어렵다는 것을 보았다.

해시 페이지 테이블은 32비트보다 큰 주소 공간을 다루기 위해서 많이 사용된다.

 

 

해시 페이지 테이블에서는 해시 값을 가상 페이지 번호로 활용한다.

이때 해시 함수의 입력 도메인의 크기가 출력 도메인의 크기보다 커서 해시 값이 동일한 경우가 발생하는데,

해시 페이지 테이블의 각 항목에 연결 리스트(linked list)를 두어 해결한다.

 

즉, 해시 충돌이 일어난 논리 주소(가상 페이지 번호)들에 대한 물리 주소 값 쌍들을 연결 리스트로 따로 관리한다.

같은 곳으로 해시되는 원소들이 해당 리스트에 매달리게 되는 것이다.

 

 

해시 테이블의 각 항목은 3개의 필드를 가진다.

1. 가상 페이지 번호(virtual page number) = 논리 주소 상의 페이지 번호 (q)

2. 사상되는 페이지 프레임 번호 = 물리 주소 상의 프레임 번호 (아래의 그림에서 s, r)

3. 연결 리스트 상의 다음 원소 포인터

 

 

운영 방법

1. 가상 페이지 번호(논리 주소 값)를 해시 함수를 통해서 해시 값으로 변환한다.

2. 해싱을 통해 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.

3-1. 둘이 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.

3-2. 일치하지 않으면 연결 리스트를 계속 따라가면서 똑같은 작업을 반복한다.

 

 

 

해시 페이지 테이블의 변형 기법으로, 클러스터 페이지 테이블(Clustered Page Tables) 기법이 있다.

64비트 시스템의 경우 이 기법을 주로 사용한다.

 

해시 페이지 테이블은 각 항목들이 한 개의 페이지만 가리키지만

클러스터 페이지 테이블은 각 항목들이 여러 페이지(ex. 16개)를 가리킨다.

 

따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 변환 정보를 지닐 수 있으며,

메모리 접근이 비연속적이면서 전 주소 공간으로 넓게 퍼져 있는 경우(= 성긴(sparce) 주소 공간)에 유용하다.

 

 

* 성긴 주소 공간

힙(heap)과 스택(stack) 사이의 공백을 말한다.

1. 스택이나 힙 세그먼트가 확장될 때 사용

2. 동적으로 라이브러리를 링크해야할 때 사용

 

역 페이지 테이블 (Inverted Page Table)

페이지 테이블이 엄청난 메모리 공간을 점유하는 것을 해결하는 방법이다.

 

논리 주소 : (PID, p, d)

PID : 프로세스의 ID

p : 페이지 번호

d : 페이지 변위 (offset)

 

역 페이지 테이블의 항목 : <PID, p>

PID : 페이지를 소유하고 있는 프로세스의 ID

p : 페이지 번호

 

메모리 프레임마다 역 페이지 테이블의 한 항목씩을 할당한다.

 

운영 방법

1. 메모리 참조 발생 시 논리 주소의 일부분(PID, p)이 메모리 하부 시스템에 전달된다.

2. 역 페이지 테이블에서 일치하는 것이 있는지 검색한다.

3-1. 일치하는 것이 i번째 엔트리에서 발견되면 물리 주소는 <i, offset>이 된다.

3-2. 일치하는 것이 없다면 잘못된 메모리 접근으로 간주된다.

 

 

역 페이지 테이블은 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에

다른 기법들보다 메모리 공간을 훨씬 작게 점유한다.

 

 

하지만 메모리 공유가 어렵다는 단점이 있다.

메모리 공유는 하나의 물리 영역에 사상되는 여러 개의 가상 주소를 통해 구현되지만

역 페이지 테이블에서는 모든 물리 페이지에 대해서는 하나의 가상(논리) 주소만을 갖기 때문에 메모리 공유가 불가하다.

 

또한 주소 변환을 위해 페이지 테이블을 탐색해야 하기 때문에 주소 변환 시간이 오래 걸릴 수도 있다.

역 페이지 테이블은 물리 주소에 따라 정렬되어 있지만 탐색은 논리 주소를 기준으로 하기 때문에

전체 테이블을 탐색해야 하는 경우도 발생한다.

 

 

이것은 해시 테이블을 사용하는 것으로 해결할 수 있으나,

매 접근마다 해시 테이블을 참조해야 하기 때문에 메모리 참조 횟수를 증가시킨다는 것을 유의해야 한다.

(메모리 참조 - 1. 해시 테이블 2. 페이지 테이블)

 

n 비트의 가상공간과 PID 정보를 해시하여 m 비트의 프레임 번호로 사상(mapping)하는 것이며, (n > m)

해시 오버플로우에 따른 충돌 관리를 위해 체인을 사용한다.

* 체인 포인터 : 다음 항목을 가리키는 인덱스 값, null이면 다음 항목이 없다는 의미이다.