티스토리 뷰
Multi-Level Page Table의 필요성
Page Table은 각 프로세스마다 가지고 있으며 Memory내에 OS가 관리할 수 있는 영역에 저장이 된다.
따라서 Paging에서 고려해야 되는 것은 Page Table의 크기를 줄이는 것일 것이다.
예) PTE(Page Table Entry)의 크기가 4B로 가정할 때 32bit address space
Page는 4KB의 크기를 가지므로 entry는 약 $$2^{22}$$ 개의 entry가 필요하고, Page Table의 크기가 4MB가 된다.
각 프로세스마다 4MB 크기의 Page Table을 Memory에 저장한다는 것은 적절하지 않아 보인다.
(물론 swap공간의 얘기도 있지만, 여기서는 넘어가자.)
Page Table의 크기를 줄이는 방법은 여러가지가 있는데 직관적인 방법은 $$^{1)}$$Page크기를 늘리면 된다.
당연히 Page 크기가 커지면 entry개수가 줄어들어서 전체 Page Table의 크기가 줄게된다.
하지만 이 방식은 각 Page마다 internal fragmentation을 증가시켜 결국 메모리 낭비가 초래된다.
또 다른 방법은 $$^{2)}$$segmentation을 하는 것이다.
Code, Stack, Heap segment에 대해 Page Table을 각각 두어서 메모리를 절약하자는 것이다.
($$1\over4$$에 해당하는 부분이 절약되게 된다.)
이렇게 되면 우선 각 segment를 위한 base, bound register가 필요하게 된다.
따라서 총 6개의 base, bound register가 존재하여 각 segment의 page table 정보를 갖게 된다.
그리고 이 register값들은 Context-switch 시에 PCB에 저장되어야 할 것이다.
하지만 이 방식 역시 분명 단점이 존재한다.
- Page table waste (Heap Space의 경우 sparse하게 메모리가 잡혀있는 경우가 생긴다)
- External fragmentation (Page Table의 크기가 다양하므로)
Page Table의 크기를 줄이는 방법
1. Page 크기의 확장
- 전체 entry수가 줄면서 Page Table 크기가 감소
- internal fragmentation
2. Segmentation (Hybrid Approach)
- Code, Stack, Heap을 위한 Page Table을 따로 분리 (Heap과 Stack사이 공간을 위한 Page Table이 필요없다)
- Page Table waste (sparsely-used heap space)
- External fragmentation (variable size of Page Table)
3. Multi-Level Page Table
4. Inverted Page Table
Multi-Level Page Table
Multi-Level Page Table의 핵심은 Page Table을 위한 Page Table을 만드는 것이다.
프로세스마다 Page Table은 Memory에 저장이 되는데, 이를 Page 단위로 나누어서 생각해 보자는 것이다.
즉 선형구조가 아닌 Tree구조로 Page Table을 만든다.
Linear Page Table은 4MB내의 invalid한 entry도 모두 memory를 잡고 있어서 메모리 낭비가 크다는 문제가 있었다.
하지만 Page Table을 Page 단위로 나누어서 이를 위한 또다른 Page Table(이를 Page directory라고 한다)를 생성한다면
적어도 모두 invalid한 entry를 담은 Page 는 memory에 할당하지 않을 수도 있다.
우선 2-level Page Table의 예를 살펴보자.
위 그림에서 PDBR은 Page Directory Base Register로 물리 메모리 공간에 저장되어 있는 Page Directory의 Base 주소를 가진다.
페이지 테이블을 페이지 크기의 단위로 나누고, 해당 페이지 테이블의 페이지가 invalid하다면 메모리에 할당하지 않는다.
Multi-Level Table의 장점
1. Invalid한 페이지를 할당하지 않으므로 메모리를 절약할 수 있다.
2. 작은 단위(Page 크기, 4KB)로 Page Table을 분할함으로써 메모리 관리가 용이하다.
(Page Table 할당을 위한 공간을 찾기가 편하다.)
Multi-Level Table의 단점
1. Time-Space trade-offs
- TLB Miss가 났을 경우 두번의 Memory접근이 필요하다.
- TLB Miss가 나면 우선 $$^{1)}$$Page Directory의 접근을 해야하고,
$$^{2)}$$Page Directory에서 얻어온 Page Table Entry 정보로 접근을 또 해야한다.
2. Complexity
- Page Table의 검색이 더 복잡해 진다.
개념 이해를 위해 예제를 하나 살펴보자.
예) 2-Level Page Table
1. 가정
- 16KB 크기의 Address space
- 64B 크기의 Page
2. 16KB 크기의 Address Space는 14 bit로 표현된다.
Linear Page Table을 생각해 볼 때 그 크기는 entry수 = $$2^{14} \over 2^6$$ = $$2^8$$ 이므로 $$2^{10}$$B = $$1$$KB가 된다.
이를 Page단위로 또 분할하므로 PDE의 수는 $$2^4 = 16$$개가 된다.
따라서 아래와 같이 표현된다.
3. 이제 다음과 같은 2-level Page Table이 주어졌다고 하자.
그리고 0x3F80에 대한 주소 변환을 해보자.
0x3F80은 이진수 11 1111 1000 0000 이다.
우선 Page Directory Index = 1111$$_{(2)}$$ = 15 이므로 PFN 101을 나타냄을 알 수 있다.
Page Directory의 15번째 entry의 valid bit = 1이므로 유효함을 알 수 있다.
그 다음 Page Table Index = 1110$$_{(2)}$$ = 14 이므로 PFN 55이고 valid = 1임을 알 수 있다.
따라서 Offset인 00 0000과 PFN 55의 이진표현인 00 1101 11을 합쳐서
Physical Address 00 1101 1100 0000 = 0x0DC0을 얻는다.
요약하자면, 단순히 Page크기를 늘리는 것은 internal fragmentation이 발생하고, segmentation을 이용한 hybrid 방식에서는 메모리 낭비와 external fragmentation이 나타났다. 이러한 방식의 단점을 보완하고자 나온것이 Multi-level Page Table이다. Multi-level Page Table은 기존 Page Table의 크기를 줄이고, 관리하는데 용이한 Page table이다. 핵심은 기존의 Linear Page Table을 Page단위로 잘라서 Page Directory로 관리하자는 것이며, 이를 통해 invalid Page를 할당하지 않게 된다. 하지만 space-time trade-offs가 발생하고 좀더 Page Table search에 복잡성을 갖는다는 단점을 지니고 있다.
Reference
1. Operating Systems : Three Easy Pieces(OSTEP)