페이징 : 더 작은 테이블
우리는 이전 포스트에서 페이징의 속도를 개선하기 위해서 TLB를 알아보았습니다.
하지만, 페이징의 두 번째 문제점은 페이지 테이블의 크기입니다.
선형 페이지 테이블을 예로 들어보면, 페이지 크기가 4KB이고 페이지 테이블의 각 항목은 4byte인 32bit 주소 공간을 가정해보겠습니다.
주소 공간에는 대략 백만개의 가상 페이지가 존재할 것이며, 여기에 페이지 테이블 항목의 크기를 곱하면 페이지 테이블의 크기가 됩니다. ( 4byte * 100만개 ⇒ 4MB )
즉, 하나의 프로세스를 위해서는 4MB의 페이지 테이블이 필요하게 됩니다.
만약 100개의 프로세스가 실행중이라면, 400MB의 메모리가 필요하게 됩니다.
이것을 해결하기위한 방법을 찾아보겠습니다.
간단한 해법 : 더 큰 페이지
페이지 테이블의 크기를 간단하게 줄일 수 있는 방법이 한 가지 있습니다.
페이지의 크기를 증가시키는 것입니다.
32bit 주소 공간에서, 16KB 페이지를 가정하겠습니다.
이제는 18bit의 VPN을 가지게 되고, 14bit의 offset이 필요하게 됩니다.
각 PTE의 크기가 모두 동일하다면, 페이지 테이블에는 2^18개의 항목이 존재하게 되며 페이지 테이블의 총 크기는 1MB가 됩니다.
즉, 기존 페이지 테이블에 비해 크기가 1/4로 감소하게 되었습니다.
하지만, 이 방법은 내부 단편화라는 큰 문제를 야기하게 됩니다.
페이지가 커짐에 따라 내부에 낭비되는 공간이 많아지게 되어, 응용프로그램이 여러 페이지를 할당받아도 할당 페이지의 일부분만 사용하기 때문에 메모리가 금방 고갈되는 현상이 발생합니다.
하이브리드 접근 방법 : 페이징과 세그먼트
이번 방법은 페이징과 세그멘테이션을 결합하여 페이지 테이블의 크기를 줄이는 아이디어입니다.
1KB의 크기의 페이지를 갖는 16KB의 주소 공간을 보겠습니다.
이 예제에서 한 개의 코드 페이지(VPN 0)가 PFN 10에, 그리고 한 개의 힙 페이지(VPN 4)가 PFN 23에 매핑되어 있습니다.
가상 주소 공간의 끝 부분에 두 개의 스택 페이지(VPN 14, 15)가 PFN 28, 4에 매핑 되어 있습니다.
그림에서 보는 것처럼 페이지 테이블이 대부분 비어있고 엄청나게 낭비되고 있습니다.
이것을 해결하기위해, 프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신 논리 세그멘트마다 따로 페이지 테이블을 두는 생각을 해보겠습니다.
세그멘테이션에서는 세그멘트의 물리 주소 시작 위치를 나타내는 base 레지스터, 크기를 나타내는 bound 또는 limit 레지스터가 존재합니다.
이번 시도에서는 base 레지스터가 세그멘트 시작 주소를 가리키지 않고, 세그멘트의 페이지 테이블의 시작 주소를 가지게 될 것입니다.
bound 레지스터는 페이지 테이블의 끝을 나타내기 위해 사용될 것 입니다.
이를 명확하게 보기위해 예시를 하나 보겠습니다.
4KB 페이지를 갖는 32bit 가상 주소 공간이 4개의 세그멘트로 나뉘어있다고 가정하겠습니다.
이 예제에서는 세 개의 세그멘트만 사용하겠습니다. ( 코드 01 , 힙 10, 스택 11 )
하드웨어는 세 개의 base/bound 레지스터 쌍이 존재하며, 실행 중인 프로세스에서 각 세그멘트의 base 레지스터는 각 세그멘트 페이지 테이블의 시작 물리주소를 가지게 됩니다.
이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 가지며, Context Switch 발생 시 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 값으로 변경됩니다.
TLB 미스가 발생하면, 세그멘트 비트(SN)을 사용하여, base와 bound 쌍을 결정하고 VPN과 PTE의 주소를 구합니다.
이전에 살펴보았던 선형 페이지 테이블의 동작구조와 유사하지만, 세 개 중의 하나의 base 레지스터를 사용하게 된다는 것이 다르고, bound 레지스터가 존재한다는 점이 다릅니다.
각 bound 레지스터는 세그멘트의 최대 유효 페이지의 개수를 나타냅니다.
예를들어, 첫 세 개의 페이지들을 코드 세그멘트로 사용 중이라면, 코드 세그멘트 페이지 테이블은 세 개의 항목만 할당 받을 것이고 bound 레지스터는 3이 될 것 입니다.
만약 bound 레지스터의 범위를 넘는 접근이 발생하면 예외가 발생되고 해당 프로세스슨는 종료될 것입니다.
하지만, 이 방법 역시 문제가 있습니다.
여전히 세그멘테이션을 사용하기 때문에 외부 단편화가 발생하고, 여유 공관 관리 방법도 어려워지게 됩니다.
멀티 레벨 페이지 테이블
멀티 레벨 페이지 테이블은 선형 페이지 테이블을 트리 구조로 표현합니다.
선형 페이지 테이블 ( 왼쪽 ) 과 멀티 레벨 페이지 테이블 ( 오른쪽 ) 의 가장 큰 차이점은, 멀티 레벨 페이지 테이블은 페이지 테이블의 페이지가 할당되지 않은 항목만 존재한다면 해당 페이지를 할당하지 않습니다.
페이지 디렉토리(page directory)라는 자료구조를 사용하여 각 페이지의 할당 여부와 위치를 파악합니다.
페이지 디렉토리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정부를 가지고 있습니다.
위 그림에서 선형 페이지 테이블은 중앙부에 해당하는 공간은 사용하지않지만 할당되어있고, 멀티 레벨 페이지 테이블은 할당되어 있지 않다는 것을 알 수 있습니다. 즉, 메모리를 절약할 수 있게 되었습니다.
위의 예에서 페이지 디렉터리는 페이지 디렉터리 항목(Page Directory Entries)로 이루어져있습니다.
각 항목(PDE)는 PTE와 유사한 구성을 가지고 있습니다.
유효 비트, PFN을 갖고 있습니다.
하지만, PTE의 유효비트와 PDE의 유효비트는 조금 다릅니다.
PDE가 유효하다는 것은, 그 항목이 가리키고 있는 페이지들 중 최소한 하나가 유효하다는 것을 의미합니다.
즉, PDE가 valid라면 페이지내의 최소한 하나의 PTE가 유효하다는 것을 의미합니다.
PDE가 유효하지 않다는 것은, 실제 페이지가 할당되어 있지 않다는 것을 의미합니다.
멀티 레벨 페이지 테이블은 몇가지 장점이 있습니다.
- 실제 사용중인 페이지 테이블만 메모리를 할당하기 때문에 메모리를 절약할 수 있습니다.
- 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 유용해집니다.
하지만 유의할 사항도 존재하게 됩니다.
- 다단계 접근이 발생하기 때문에 TLB 미스 시, 두 번의 메모리 접근이 발생하게 됩니다. ( 페이지 디렉토리 → PTE )
- 복잡도입니다. 단순한 선형 페이지 테이블의 경우보다 당연히 복잡해집니다.
멀티 레벨 페이징 예제
예제를 하나 보겠습니다.
64byte 페이지를 갖는 16KB 크기의 주소 공간을 생각하겠습니다.
16KB = 2^14 이므로, 주소 공간은 14bit로 나타내게 되며 page는 64byte이기 때문에 VPN은 8bit, offset은 6bit가 됩니다.
만약 선형 페이지 테이블을 사용하게 된다면 2^8 = 256개의 엔트리를 필요로하게 됩니다.
위 예제에서 가상 주소 공간 0과 1은 코드, 4와 5는 힙, 254, 255는 스택으로 사용하고있습니다.
나머지는 사용되지 않고 있습니다.
이를 2단계 페이지 테이블로 구성해보겠습니다.
선형 페이지 테이블을 페이지 단위로 분할을 해야합니다.
PTE의 크기는 4byte로 가정한다하면, 페이지의 크기가 64byte이기 때문에 페이지 테이블의 크기는 1KB가 됩니다.
그 후 페이지 테이블을 페이지의 크기로 분할을 하면 16개의 페이지로 나눌 수 있게 됩니다.
이제 여기서 page directory를 나누어야합니다.
VPN을 이용하여 page directory를 만들 것입니다.
현재 예제에서는 16개로 분할할 수 있기 때문에 4개의 bit가 필요하게 됩니다.
나머지 4개의 bit는 해당 page directory의 어떤 page entry에 접근하는지를 나타내게 될 것입니다.
따라서 아래와 같은 구조가 될 것입니다.
이 구조가 실제로 어떻게 사용되는지 보겠습니다.
Page Directory의 각 요소에는 page table들의 첫 항목이 존재합니다.
각각의 page table에는 16개의 PTE가 존재합니다.
그리고 현재 저희가 보는 예제에서는 VPN 0, 1, 4, 5, 254, 255에 유효한 page들이 존재했었습니다.
지금 보는 페이지 테이블을 살펴보면, page directory 하나와 두 개의 page table만 유지하면 모든 주소 변환이 가능하다는 것을 알 수 있습니다.
획기적으로 공간이 줄어들게 된 것이죠.
이제 주소 변환을 해보겠습니다.
예를 들어, 가상 주소 100을 변환해보겠습니다.
100을 2진수 14비트로 나타내면, 0000 0001 100100 이 되고 Page directory의 0번째 것의 1번째 Page table이 PFN이 된다는 것을 알 수 있습니다.
따라서 PFN은 23이 되고, offset인 100100 은 그대로 사용하게 되면
10111100100 ⇒ 1508이 됩니다.
2단계 이상 사용하기
현재는 2단계로만 사용했지만, 실제로는 그 보다 더 많은 단계를 나누어서 사용합니다.
간단한 예제를 통해 그 이유를 알아보겠습니다.
만약 512byte 페이지와 30bit 가상 주소 공간이 있으면 21bit의 페이지 번호와 9bit의 offset을 갖게 됩니다.
위와 같은 구조를 갖게 되는데, 페이지 테이블의 모든 entry를 나타내기 위해서는 page table index로 7개의 page table index가 필요하게 됩니다.
남은 14개가 page directory index가 될 것이고, page directory가 위와 같이 커진다면 page의 크기는 512이고 pte는 128인데 이를 초과하게 될 수 있습니다.
이를 해결하기 위해, 페이지 디렉터리 자체를 멀티 페이지들로 나누어서 트리의 단계를 늘리는 방법을 사용하여 해결합니다.
변환 과정 : TLB를 기억하자
멀티 레벨 페이지 테이블을 사용하더라도 TLB를 사용할 수 있습니다.
TLB 히트시 참조없이 물리 주소를 구성할 수 있고, TLB 미스시 2단계 페이지 테이블의 추가 메모리 접근이 있다는 것을 기억해야합니다.
역 페이지 테이블
획기적인 공간 절약 방법으로는 역 페이지 테이블 ( Inverted Page Table ) 이라는 방식도 존재합니다.
이 방법에서는 여러 개의 페이지 테이블 대신 시스템에 단 하나의 페이지 테이블만 둡니다.
페이지 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환하고, 역 페이지 테이블의 각 항목은 해당 물리 페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 갖고 있습니다.
페이지 테이블을 디스크로 스와핑하기
이제까지는 페이지 테이블이 커널 소유의 메모리 영역에 있다고 가정했습니다.
이제는 그 가정을 제거하고 페이지 테이블이 너무 커질 경우, 디스크로 스왑하는 방법을 다음에 알아보겠습니다.
요약
이번 포스트에서는 페이지 테이블이 실제로 어떻게 구성되는지를 알아보았습니다.
단순한 선형 배열을 사용하는 구조뿐아니라, 복잡한 자료 구조의 형태도 살펴보았습니다.
공간을 많이 소모하면, TLB 미스의 처리속도가 빨라지고, 공간을 작게 소모하면 상황은 반대가 되는 모순적인 선택 사항도 존재한다는 것을 알아보았습니다.
이를 통해 주어진 제약 조건들을 적절히 고려하여 자료구조를 결정해야한다는 것을 깨닫기도 하였습니다.
다음번에는 페이지 테이블을 디스크로 어떻게 스와핑하는지에 대해 알아보겠습니다.
