[OS] Paging기법의 Page Table의 크기 줄이기 - OS 공부 14

안녕하세요 Pingu입니다.

 

지난 글에서는 메모리를 고정 크기로 할당하여 사용하는 paging기법을 사용할 때 발생하는 문제점 중 paging 방법이 주소 변환을 위해 메모리에 접근하기 때문에 속도가 느린 점을 보완하기 위한 방법인 Translate Lookaside Buffer(TLB)에 대해 알아봤었습니다. 하지만 paging에는 속도가 느린 점 외에도 page table을 위한 메모리 공간을 많이 차지하는 것도 문제였었죠! 그래서 이번 글에서는 page table에 사용되는 메모리 공간을 줄이는 방법에 대해 알아보려고 합니다. 제가 공부할 때 참고하고 있는 OSTEP책에서는 Chapter 20 - Advanced Page Table 부분입니다!

Paging: Smaller Tables

Page table의 크기를 줄이기 전에 page table이 얼마나 되길래 줄여야하는지 부터 알아보겠습니다. 우선 지금 알고 있는 기본적인 page table인 linear page table(선형 페이지 테이블) 일 때 메모리를 얼마나 차지하는지 보겠습니다. 여기서 linear page table이란 page table을 모든 page entry에 대하여 유지하는 것을 말합니다. 즉 100개의 page entry가 있다면 page table의 개수도 100개가 되는 것이죠.

 

우선 page의 크기는 4KB(2^12바이트)이며 page table 크기는 4 바이트인 32 비트 주소공간이 있다고 가정하겠습니다. 32비트 주소 공간이므로 가상공간의 총크기는 2^32 = 4GB이며 page의 크기가 4KB라고 했으므로 하나의 프로세스에는 총 2^20개의 page table이 필요합니다. Page table 하나의 크기가 4바이트라고 했으니 4 * 2^20 = 2^22 = 4MB입니다. 즉 하나의 프로세스를 위해서는 4MB 크기의 page table이 필요한 것이죠. 그럼 만약 이러한 상황에서 100개의 프로세스가 동시에 실행 중이라면 어떻게 될까요? 총 400MB의 메모리를 그저 page table을 위해서 할당해야 합니다. 어떤가요? 상당히 큰 값이지 않나요? 이번 글에서는 page table의 크기를 줄여 메모리를 절약하는 방법에 대해 알아보려고 합니다.

Simple Soultion: Bigger Pages

그럼 아주 간단한 접근으로 page의 크기를 늘려서 page table의 개수를 줄일 수 있습니다. Page 크기를 늘리면 page entry 개수가 줄어들 것이며 결국 page table의 크기도 줄어들게 되는 것이죠. 간단하게 아까 예의 상황(32비트의 가상공간, page table 크기는 4바이트)에서 page의 크기가 4MB라고 해보겠습니다. 이렇게 되면 10개의 VPN 비트와 22개의 offset 비트를 가지게 됩니다. 따라서 저희의 목적인 page table의 크기도 2^10 * 4바이트 = 4KB가 되는 것이죠. 하나의 프로세스당 4KB라면 아까보다 정말 엄청나게 메모리를 절약할 수 있습니다.

 

하지만 이 방법은 page table에 의한 메모리 낭비는 줄일 수 있지만 page 자체가 너무 커서 발생하는 internal fragmentation(내부 단편화)가 발생할 수 있습니다. 따라서 실제로는 4KB, 8KB정도의 page 크기를 갖도록 사용한다고 합니다.

Hybrid Approach: Paging and Segments

예전 글에서 알아본 segmentation 기법을 기억하시나요? 지금 알아보고 있는 page와는 다르게 메모리를 가변으로 할당해주는 방법이었습니다. 현재 해결하려는 문제인 page table의 크기를 줄이는 방법 중에 segmentation 방법을 함께 사용해보면 어떨까요? 실제로 이러한 방법을 Jack Dennis라는 사람이 시도했다고 합니다. 어떤 방식으로 적용할 수 있는지 예를 보며 살펴보겠습니다.

위와 같이 16KB의 가상 주소 공간을 가지며 page 크기가 1KB인 상황을 가정해보겠습니다. Code 부분에서 1개의 page, heap 부분에서 1개의 page, stack에서 2개의 페이지를 사용하고 있네요. 그리고 각각의 page는 실제 메모리에 할당되어 있습니다. 위의 상태를 보면 현재 page table이 얼마나 비효율적 인지 알 수 있습니다. 총 16개의 page entry가 존재할 수 있지만 정작 사용하는 것은 4개인데도 불구하고 page table은 모든 공간을 유지하고 있습니다. 이 상황에서 segmentation 기법에서 사용하는 base, limit 레지스터를 활용하여 메모리 낭비를 줄여보도록 하겠습니다. 실제 segmentation에서와는 다르게 base, limit 레지스터를 각 segment의 page table에 접근할 수 있도록 사용합니다. base 레지스터는 page table을 가리키는 데 사용하고 limit 레지스터는 page table의 끝을 나타낼 수 있습니다.

 

간단하게 예를 보며 이해해보도록 하겠습니다. 우선 page의 크기가 4KB, 32bit 가상 주소공간을 갖는 시스템에서 4개의 segment로 분할된 주소 공간이 있다고 생각해보겠습니다. 여기서는 4개의 segment 중 3개만 사용한다고 가정하겠습니다. 그러면 segment를 구분하기 위해 필요한 비트수는 2개입니다. 00을 사용하지 않는 segment라고 하고 Code는 01, Heap이 10, Stack이 11이라고 가정하겠습니다.

그럼 위와 같은 주소를 갖게 됩니다. 그리고 각각의 segment에 대해 base, limit 레지스터가 존재한다고 하면, 프로세스가 실행중일 때 page table의 주소를 레지스터에 저장하게 되는 것이죠! Context switch가 발생한다면 레지스터의 값을 새로 실행할 프로세스의 정보로 바꿔주면 됩니다. 여기에 저번 글에서 배운 TLB도 적용하여 만약 TLB Miss가 발생했다고 하면 segment 비트를 사용하여 주소변환을 진행하면 됩니다.

 

이러한 하이브리드 방식의 기존 paging기법과의 큰 차이점은 segment당 limit 레지스터가 있다는 것 입니다. 따라서 limit 레지스터가 segment의 page table의 끝 값을 가지므로 사용하지 않는 page table의 공간을 유지할 필요가 없습니다. 하지만 이러한 하이브리드 방법은 segmentation의 문제인 외부 단편화 문제가 발생하게 됩니다. 또한 segmentation 방법을 사용할 때 생각해야 하는 여유 공간을 관리하는 방법도 복잡해집니다.

Multi Level Page Tables

그럼 이번에는 page table에서 사용하지 않는 공간은 메모리에서 제거하는 방법인 multi level page table을 알아보겠습니다. 실제로 많은 시스템에서 사용되는 방법이며 아주 효과적으로 작동한다고 합니다!

 

우선 multi level page table의 기본적인 아이디어는 page table을 page 단위로 자른 뒤 하나라도 유효한 entry가 없다면 해당 page table를 유지하지 않는 것입니다. 이러한 것을 처리하기 위해 multi level page table에는 page directory라는 개념을 도입합니다. Page directory는 page table의 page가 어디에 있는지, 해당 page table에 유효한 page가 있는지를 알려주는 데 사용합니다.

 

그럼 예를 보며 이해해 보겠습니다!

위의 그림을 보면 왼쪽에는 기존에 사용하던 page table이 있고 오른쪽에는 지금 알아보고 있는 multi level page table를 표현해놨습니다. 왼쪽 page table을 살펴보면 page 단위로 page table을 구분했을 때 2개의 page table은 전혀 사용하고 있지 않은 것을 볼 수 있습니다. 즉 기존의 방법을 쓰면 메모리 낭비가 발생하는 것이죠.

 

이와 다르게 오른쪽 그림을 살펴보면, page directory라는 자료 구조가 있으며 이 자료구조에는 실제로 사용중인 2개의 page table만 접근할 수 있도록 하여 메모리 낭비를 방지합니다. 이렇게 주소 변환에 한 번의 단계가 추가되었기 때문에 multi level이라고 부르며 위의 예는 two level page table이라고 볼 수 있습니다. 위의 예에서 page directory는 page당 하나의 page entry만을 가지고 있습니다. 이는 해당 page table의 시작 부분 즉 base 레지스터 같은 역할을 한다고 보면 됩니다. Page directory는 page directory entry(PDE)로 구성되며 PDE는 유효한 값인지를 알려주는 valid bit 그리고 page frame number로 구성됩니다. 물론 이 구성은 최소한의 조건입니다. 하나의 page 단위에서 하나라도 사용 중이라면 valid bit에는 1을 저장합니다.

 

그럼 이러한 Multi level page table을 사용하면 어떤 장점이 있을까요? 첫 번째로 가장 중요하게 해결해야할 문제인 page table의 메모리 공간을 줄여줍니다. 실제로 사용 중인 page table에만 메모리를 할당하기 때문이죠! 두 번째 장점은 page table의 각 부분을 page 단위로 나눠서 관리하므로 잘 구현한다면 메모리 관리가 쉬워집니다. Multi level page table은 page table의 일부를 가리키는 page directory를 사용하므로 실제 메모리의 원하는 곳에 page table page를 배치할 수 있습니다.

 

하지만 언제나 그렇듯 장점만 존재하는 것은 아닙니다. TLB Miss가 발생한다면 메모리에서 PT에 접근하기 위해 이제는 Page directory에도 접근해야 합니다. 즉 2번의 메모리 접근이 발생하는 것이죠. 그리고 당연한 말이겠지만 기존의 방법보다는 복잡합니다. 

A Detailed Multi Level Example

그럼 실제 예를 보며 multi level page table이 단점에도 불구하고 사용할 가치가 있는지 살펴보겠습니다. Page의 크기가 64바이트이고 PTE의 크기가 4바이트인 16KB 주소공간을 갖는 시스템으로 예를 들어보겠습니다. 16KB = 2^14, 즉 주소 공간을 14비트로 나타내며 page 크기가 64바이트이므로 VPN으로 6비트, offset으로 8비트를 사용하겠죠? 그리고 만약 linear page table을 사용한다면 page table 하나당 256개의 PTE가 존재할 것입니다.

즉 위와 같이 page가 가상 주소 공간에 존재하게 되는 것입니다. 위의 예에서는 Code로 0, 1 page, Heap으로 4,5 page, stack으로 254, 255page를 사용하고 있습니다. 아까 PTE의 크기를 4바이트로 가정했으므로 linear page table을 사용한다면 page table 하나의 크기는 1KB입니다. Page의 크기가 64바이트이므로 page table은 16개의 page로 나눌 수 있습니다.

 

그럼 이제 이 상황에서 multi level page table을 위해 page directory를 만들어야 합니다. VPN을 가지고 와서 page directory를 생성하는 것입니다. 이 예에서는 256개의 PTE가 16 page에 나뉘어있으므로 총 16개의 directory entry를 만들면 될 것 같습니다. 즉 이를 위한 비트로는 4개의 비트가 필요하겠네요.

이렇게 14비트의 주소 공간 중 상위 4비트를 page directory index를 나타내기 위해 사용하면 됩니다. 이제는 특정 page table을 가리키게 되었으니 해당 page table의 어떤 page entry정보에 접근해야 하는지를 알아야 합니다. 1개의 page table에는 16개의 page entry가 있었으니 4개의 비트로 표현할 수 있을 것 같네요. 따라서 VPN의 나머지 4비트를 PTE정보로 사용하면 됩니다.

그럼 이제 실제로 주소를 변환해보며 이렇게 구성한 가상 주소가 어떻게 사용되는지 살펴보겠습니다.

위와 같이 page directory의 각 요소에는 page table들의 첫 항목이 존재합니다. 각각의 page table에는 16개의 entry가 존재합니다. 지금 살펴보고 있는 예에서는 VPN 0,1, 4,5, 254,255에 유효한 page들이 있었습니다. 즉 위와 같이 2개의 page table와 하나의 page directory만 유지하면 메모리 할당을 문제없이 수행할 수 있는 것입니다. 기존의 방법대로라면 16개의 page table을 유지했어야 했으니 엄청나게 메모리를 아낄 수 있겠네요!

 

그럼 실제로 주소변환을 해보겠습니다. 지금 주소 공간을 잠깐 그려보면..

위와 같은데 그럼 한 번 가상 주소 100번을 주소 변환해보겠습니다.

그림이 이해가 되시나요.. 아무래도 Multi level page table 과정이 복잡하다 보니 좀 난잡해 보이네요 ㅠ.. 일단 설명을 하자면, 우선 가상 주소 100을 14비트로 나타내면 0000 0001 100100으로 나타납니다. 아까 알아본 대로 앞에서부터 4비트는 Page directory index(PDI), 그다음 4비트는 page table index(PTI), 그리고 나머지는 offset으로 사용하면 됩니다. PDI는 0이고 PTI는 1이니 page table을 찾아가서 PFN을 보면 23입니다. 따라서 실제 주소는 23*64 + 36이 되는 것이죠!

More Than Two Levels

지금까지 알아본 multi level page table은 사실 2 레벨밖에 없었습니다. 그런데 실제로는 이보다 더 많은 레벨로 구현한다고 합니다. 그럼 왜 더 많은 레벨을 구성해야 하는지 살펴보겠습니다. 간단하게 예를 하나 들어보면, page의 크기가 512바이트, PTE의 크기가 4바이트인 30비트 가상 주소 공간이 있다고 생각해보겠습니다. 그럼 VPN으로 21비트, offset으로 9비트를 사용하는 즉 아래와 같은 구조로 가상 주소가 구성됩니다.

Page table의 모든 entey를 나타내기 위해서 page table index로는 7비트가 필요할 것 같습니다.(512 / 4 = 128 = 2^7) 이 말은 page directory index에 남는 비트가 14개가 남게 됩니다. 위와 같이 page directory가 커지면 어떻게 될까요? 위와 같이 되면 한 page의 크기는 512이고 각각 pte는 128개인데 이를 초과하는 값이 생길 수도 있게 됩니다. 예를 들어 page directory에 220개의 항목이 있다면 하나의 page로 나타낼 수 없고 2개에 걸쳐서 표현되므로 실질적으로는 multi level page table이 사라지게 됩니다.

 

이 문제를 해결하기 위해 page directory를 몇 개의 page로 나누어 사용하게 되는데, 아래 그림과 같이 나눌 수도 있습니다.

The Translation Process: Remember the TLB

Multi level page table을 사용하더라도 TLB는 사용할 수 있습니다. TLB가 있다면 언제나 하드웨어는 주소변환을 하기 전 TLB부터 확인합니다. TLB Miss가 발생하면 multi level page table로 주소 변환을 시도할 텐데, 이때 메모리 접근이 기존 방법보다도 더 많이 발생하게 됩니다.

Inverted Page Tables

Page table 크기를 줄이는 방법에는 page table의 개념을 거꾸로 적용하는 방법입니다. 즉 프로세스마다 page table이 하나씩 존재하는 것이 아닌 모든 프로세스가 하나의 page table을 사용하는 것이죠. 이렇게 하면 page table의 메모리 사용을 줄일 수 있습니다.

Swapping the Page Table to Disk

지금까지는 page table이 실제 메모리에 존재한다고 가정했습니다. 그렇기 때문에 이번 글에서 이렇게 열심히 page table의 크기를 줄이는 방법을 알아봤었죠. 일부 시스템에서는 page table 중 일부를 DISK로 swap 하여 사용하기도 합니다. 다음 글에서 이에 대해 알아보도록 하겠습니다.

Summary

이번 글에서는 page table이 어떻게 동작하는지, 그리고 어떻게 하면 메모리 사용을 줄일 수 있는지를 알아봤습니다. 하지만 TLB의 사용 때문에 Multi level page table 같은 방법들에도 단점들이 존재했습니다. 다음 글에서는 page table을 DISK에 저장하고 swap 하여 사용하는 방법에 대해 알아보도록 하겠습니다.

 

감사합니다.