Advanced Page Table

기존 Page Table의 문제점

32bit 주소체계 / Page 크기 : 16KB 라 가정하자.

이 때 Offset은 페이지 크기인 16*2^10=2^14bit가 필요하다.

따라서 32-14=18bit가 VPN으로 사용 가능하므로 총 2^18개의 VPN을 표현할 수 있다.

 

Page Table은 VPN 수로 크기가 정해지므로, 하나의 Entry가 4byte라면 4*2^18=2^20byte=1MB 크기가 될 것이다.

Page Table은 프로세스 하나당 한개씩 생성되므로 프로세스가 100개라면 무려 100MB의 메모리를 차지하게 된다.

따라서 Page Table의 크기를 더 줄여야 할 필요가 있다.

Page Table에는 위와 같이 할당받았지만 사용하지 않는 Page들에 대한 Entry들도 모두 저장되어있다.

이렇게 무의미한 Entry들을 줄임으로서 Page Table의 크기를 절약할 수 있다.

 

 

1. Hybrid Approach: Paging and Segments

첫번째 방법은 Segment별로 각각의 Page Table을 만드는 것이다.

이렇게 하면 사용하지 않는 부분에 대한 Entry를 만들지 않아 메모리를 절약할 수 있지만

Heap이 넓고 고르게 사용된다면 External Fragmentation이 다시 발생할 것이다.

 

 

2. Multi-level Page Table

이 방식은 그동안의 선형적인 Page Table이 아니라 level을 나눔으로써 불필요한 메모리 사용을 줄이는 방식이다.

이 방식에서는 Page Table을 저장할 Page Directory라는 새로운 구조를 만들어서 사용한다.

Page Directory는 Page Directory Entry(PDE)들로 구성되어 있는데 각각의 PDE에는 Page Table의 위치가 저장된다.

Translation이 발생하면 Page Directory로 가서 해당하는 Page Table로 찾아가 PFN을 얻어오게 된다.

이 때 주소값 또한 어떤 Page Directory Index(PDI)에 저장되어 있는지를 기록해야 하므로 위와 같이 바뀌게 된다.

VPN의 앞부분에 PDI를 기록할 bit를 추가하면 된다.

 

※ 단순히 2개의 level이 아니라 Multi-level로도 구성할 수 있는데 level이 많아질수록 메모리 공간을 절약할 수는 있지만 그만큼 접근 단계가 늘어나므로 Translation 시간은 늘어나게 된다. (Time-Space tradeoff)

 

 

3. Hashed Page Table

그렇다면 접근도 상수 시간안에 가능하고 공간도 많이 차지하지 않는 Hashing을 이용할 수 있다는 생각도 할 수 있다.

하지만 Hashing은 평균적인 접근 시간은 빠르지만 최악의 경우 오랜 시간이 걸릴 수 있기 때문에 안정적이고 빠른 Translation을 위해서는 Hashing을 사용하는 것이 적절하지 않다.