OSTEP 20 Advanced Page Tables

페이징의 두 번째 문제는 페이지 테이블의 크기이다. 어떻게 하면 페이지 테이블이 차지하는 메모리의 크기를 줄일 수 있을까??

1. 간단한 해법: 더 큰 페이지

페이지 크기를 증가시키면, 페이지 테이블의 크기가 줄어든다. 페이지 크기를 4KB에서 16KB로 증가시킨다면, 페이지 테이블의 크기는 4MB에서 1MB로 둘어들 것이다. 페이지 크기의 증가는 부작용이 있다. 바로 내부 단편화이다.

페이지 크기가 너무 크다면, 할당된 페이지 내부에서 낭비가 발생할 것이다. 결국 컴퓨터 시스템의 메모리가 금방 고갈될 것이다. 때문에 일반적으로 4KB 혹은 8KB의 페이지 크기를 사용한다.

2. 하이브리드: 페이징과 세그먼트

1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 들어보자. 이 예제에서 한 개의 코드 페이지(VPN 0)가 물리 페이지 10번, 그리고 한 개의 힙 페이지(VPN 4)가 23번 물리 페이지에 매핑되어 있다. 가상 주소 공간의 끝부분에 두 개의 스택 페이지 (VPN 14, 15)가 물리 페이지 28번과 4번에 매핑되어 있다.

그림에서 보이듯 페이지 테이블 대부분이 비어 있다. 이런 낭비를 막아보자.

프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 논리 세그멘트마다 따로 페이지 테이블을 두면 어떨까? 코드, 힙, 스택 세그멘트에 대해 페이지 테이블을 각각 만들어보자.

세그멘테이션에서는 세그멘트의 물리 주소 시작 위치를 나타내는 베이스 레지스터, 그리고 크기를 나타내는 바운드 또는 리미트 레지스터가 있다.

우리 방식에서, 베이스 레지스터는 세그멘트 시작 주소가 아니라 세그멘트의 페이지 테이블의 시작 주소를 갖는다. 바운드 레지스터는 페이지 테이블의 끝을 나타내기 위해 사용한다.

하드웨어에 세 개의 베이스/바운드 레지스터 쌍이 코드, 힙, 스택을 위해 존재한다고 가정해보자. 이 시스템에서 모든 프로세스는 세 개의 페이지 테이블을 갖는다.

TLB 미스가 발생하면 하드웨어는 세그멘트 비트를 사용하여 어떤 베이스와 바운드 쌍을 사용할지 결정한다. 하드웨어는 그 레지스터에 들어 있는 물리 주소를 VPN과 다음과 같은 형싱으로 조작하여 페이지 테이블 항목 (PTE) 의 주소를 얻는다.

SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

앞에서 살펴본 선형 페이지 테이블과 작동이 거의 동일하다. 세 개의 페이지 테이블 레지스터를 사용하는 것이 차이점이다.

이 방법 역시 문제가 존재한다.

1. 여전히 세그멘테이션을 사용한다. 세그멘테이션은 주소 공간의 사용에 있어 특정 패턴을 사용하기 때문에 유연하지 못하다.
2. 외부 단편화를 유발한다. 페이지 테이블 크기에 제한이 없으며 다양한 크기를 가진다. 따라서 메모리 상에서 페이지 테이블용 공간을 확보하는 것이 더 복잡하다.

3. 멀티 레벨 페이지 테이블

페이지 테이블을 페이지 단위로 자른 뒤, 하나라도 유효한 entry가 없다면, 해당 페이지 테이블을 유지하지 않는 방식이다. 이를 처리하기 위해 멀티 레벨 페이지 테이블에는 페이지 디렉토리 (page directory) 라는 개념을 도입했다. 페이지 테이블의 페이지가 어디에 있는지, 해당 페이지 테이블에 유효한 페이지가 있는지를 알려주는 데 사용한다.

페이지 디렉토리에는 실제로 사용중인 두 개의 페이지 테이블에만 접근할 수 있도록 하여 메모리 낭비를 방지한다.

이렇게 주소 변환에 한 번의 단계가 추가되었기 때문에 멀티 레벨이라고 불린다.

페이지 디렉토리는 페이지당 하니의 entry를 가지고 있다. 페이지 테이블의 시작 부분, 즉 베이스 레지스터 같은 느낌이다. page directory entry가 유효한지 알려주는 valid bit와 page frame number로 구성된다.

이렇게 하면 메모리 낭비를 줄일 수 있지만, TLB 미스가 발생한 경우 메모리에서 페이지 테이블에 접근하기 위해 2번의 메모리 접근이 발생한다. 디렉토리 한 번, 페이지 테이블 한 번.

2단계 이상 사용하기

만약 페이지 디렉터리가 너무 커지면 어떻게 해야 할까? 페이지 디렉터리 자체를 멀티 페이지들로 나누어서, 트리의 단계를 늘리는 방식으로 해결할 수 있다.

4. 역 페이지 테이블

물리 페이지를 가상 주소 상의 페이지로 변환한다. 순차 탐색을 하면 느리기 때문에, 해시 테이블 등을 사용한다. 역 페이지 테이블의 각 항목은 해당 물리페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 갖고 있다.

역 페이지 테이블(Inverted Page Table, IPT)은 일반적인 페이지 테이블과 다르게 동작하는 메모리 관리 방식입니다. 일반적인 페이지 테이블은 각 프로세스에 대해 가상 주소를 물리 주소로 매핑하는 역할을 합니다. 그러나 이런 방식은 테이블의 크기가 가상 메모리의 크기에 비례하기 때문에, 테이블 자체가 매우 큰 메모리를 차지하게 될 수 있습니다.

역 페이지 테이블은 이 문제를 해결하기 위해 만들어진 데이터 구조로, 물리적 메모리의 각 페이지를 가상 주소 공간에 매핑합니다. 이는 물리 메모리의 각 페이지를 인덱스로 하는 배열을 유지함으로써 이루어집니다. 각 엔트리는 해당 물리 페이지를 사용 중인 프로세스의 식별자(ID)와 해당 가상 페이지의 주소를 저장합니다. 따라서 역 페이지 테이블은 모든 프로세스에 대한 정보를 한 곳에서 관리합니다.

역 페이지 테이블을 사용하면 전체 시스템에 대한 페이지 테이블의 크기가 물리 메모리의 크기에 비례하게 됩니다. 이는 가상 메모리 주소 공간이 물리 메모리보다 훨씬 클 수 있기 때문에, 메모리 사용량을 크게 줄일 수 있습니다.

그러나 역 페이지 테이블을 사용하면 가상 주소를 물리 주소로 변환하는 과정이 복잡해집니다. 주어진 가상 주소와 프로세스 ID를 가진 물리 페이지를 찾기 위해 전체 테이블을 검색해야 할 수 있습니다. 이를 해결하기 위해, 일반적으로 빠른 검색을 가능하게 하는 해시 테이블이나 다른 방식의 인덱싱이 사용됩니다.

5. 페이지 테이블을 디스크로 스왑

아무리 축소해도 메모리에 상주시키기에 너무 커진다면 어떻게 해야 할까? 페이지 테이블을 디스크에 저장하기도 한다. 스왑은 다음 단원에서 알아보자.