Paging: Smaller Tables

yalpalyappap·2021년 1월 19일

운영체제

목록 보기

12/20

page table의 두번째 문제점인 너무 커서 메모리를 많이 잡아먹는다는 문제점을 살펴보자.

이러한 array-based page table(linear page table)의 문제를 해결하기위한 page table을 더 작게 만들 수 있는 방법은 무엇이며, 더 작아졌을 때 발생하는 비효율은 무엇일까...?

Simple Solution: Bigger Pages

page table의 크기를 줄이기 위한 간단한 방법은 page 자체의 크기를 늘리는 것이다.

32bit address space에 16KB의 page를 갖는다고 하면, 18bit의 VPN, 14bit의 offset을 갖는다. 각각의 PTE가 4byte라고 할 때 이번에는 $2^{18}$ 개의 entry를 갖고, 따라서 page table당 1MB 정도의 크기를 갖는다. page의 크기가 4KB인 경우엔 page table이 4MB였고 이와 비교하면 4배가 줄어든 것이다.
하지만 이 방법의 문제점은 각각의 page 내부에 낭비가 존재하는 internal fragmentation이 발생한다는 점이다. 그래서 대부분의 시스템이 4KB의 page table을 사용하는 이유이다.

Hybrid Approach: Paging and Segment

page table의 메모리 overhead를 줄이기 위해서 segmentation과 paging을 결합하려는 시도가 생겨났다.
크기 자체가 16KB인 address space와 1KB의 page가 있다고 가정하자.(address space의 크기가 16KB, bit로 표현하지 않았음)page는 위와같이 mappping되어있다. 그에 따른 page table은 위와같다.
page table에서 볼 수 있듯이 대부분의 page는 valid bit가 0이고, 사용되지 않고있다.
만약 더 큰 크기의 32bit address space에서는 무려 백만개의 page table이 존재하므로 사용되지 않는 page는 더 많을 것이다.

따라서 어떤 하나의 프로세스에서 전체 page table을 갖는 것이 아니라 sement를 갖는 것이 hybrid approach이다.
예를들어 code, heap, stack의 3가지 segment를 갖고있다고 생각해보자. segmentation에서 우리는 segment가 물리적 메모리의 어디에 위치해 있는지를 나타내는 base register와 segment의 크기를 나타내는 bound register를 갖고있다.
하지만 hybrid approach에서는 base register는 sement를 가리키는 것이 아닌, segment에 있는 page table의 물리적 메모리 주소를 가리킨다. 그리고 bound register는 page table의 끝을 가리키는데 사용된다.
어떤 segment가 어떤 주소를 나타내는지 결정하기 위해 상위 2개비트를 활용할 것이다. 01은 code, 10은 heap, 11은 stack 영역이다.
각각의 code, stack, heap영역에 base and bound register가 있다. 프로세스가 동작하면 각각의 segment는 page table의 물리적 주소를 갖고있다. 따라서 3개의 page가 존재한다. 따라서 page table register를 활용하지 않고 base and bound register를 활용한다는 것을 제외하면 나머지 동작방식은 모두 동일하다.
예를들어 code영역에(0, 1, 2) 3개의 page가 존재하므로 code page table에는 3개의 entry가 존재하는 것이다. 그래서 bound register는 3으로 설정되고 이 bound를 넘는 access는 exception을 일으키고 프로세스를 종료시킨다.

stack, heap segment에서 할당되지 않은 page들은 page table에 없기 때문에 linear page table보다 hybrid approach를 활용함으로서 메모리를 많이 절약할 수 있다.

하지만 이 방법도 문제점은 있다.

flexible하지 않다는 문제점이 있는 segmentation을 활용해야한다는 점이다.
예를들어 사용될것에 대비하여 heap영역이 공간을 차지하고 있을 때 여전히 page table에서 낭비가 발생한다.
external fragmentation을 발생시킬 수도 있다. page의 크키가 다양해질 수 있기 때문에 메모리에서 free space를 찾는것이 매우 어려워질 수 있다.

Multi-level Page Table

segmentation에 의존하지 않고 같은 문제를 해결하는 또 다른 방법이 있다.
어떻게하면 메모리에 invalid한 page table을 저장하지 않고 해결할 수 있을까?

Multi-level page table이라는 방법을 활용한다.
tree구조를 가지며 대부분의 modern system이 이 방법을 활용한다.

page table을 page-sized unit으로 나눈다. 그 후 전체 page table entry의 page가 invalid하다면 page table에 page를 하나도 할당하지 않는다.
따라서 page table에서 page가 valid한지 여부를 알기위해서 page directory를 활용한다.
page directory는 page table에서 page가 어디에있는지를 알려주거나 또는 page table에 있는 모든 page들이 invalid한지도 알려준다.왼쪽에는 중간부분에 invalid한 영역이 있는 linear page table이 있다. linear page table에서는 invalid한 page에도 할당이 이루어져야한다.
반면에 오른쪽 Mulit-level page table에서는 page directory가 201, 204page만 valid함을 체크하고 있으므로 두 page에만 메모리 할당이 이루어진다.
그리고 page directory에서 사용되는 valid bit는 page table에서 해당 page가 valid함을 나타낸다는 것을 알아야한다.

multi-level page table의 장점은 아래와 같다.

사용하는 page에 대해서만 할당이 이루어진다는 점에서 메모리 효율적이다.
신중하게 셜계된 경우, page table과 page가 꼭 들어맞아서 메모리 관리가 효율적이다.
연속적인 메모리에 존재해야하는 linear page table과 달리 multi-level page table은 물리적 메모리의 어느위치에 있건 간에 page directory를 활용하여 찾아갈 수 있으므로 level of indirection을 추가할 수 있다.

하지만 단점도 존재한다.
linear page tabled은 transition information을 얻기위해 한번의 메모리 로드가 필요한 반면에, multi-level page table은 page directory에서 1번, page directory에서 page를 찾은 다음에 해당 page table entry로 1번, 따라서 총 2번의 메모리 로드가 필요하다.

그리고 성능향상을 위해 linear page table보다는 좀 더 복잡한 구조를 갖는다.

Detailed Multi-level table example

16kb 크기의 address space가 있고, 64byte의 page가 있다. 즉 14bit의 virtual address space에 8bit VPN, 6bit offset이다.linear page table은 위와같고 총 256개가 있다, 해당 page table을 2-level page table로 만들기 위해서 page sized unit으로 나눌 것이다.
하나의 page table entry는 4byte로 가정하면 총 page table의 크기는 1kb(256 * 4)이다. 그리고 page를 64byte라고 가정하였으므로 page table안에는 16개의 64byte page가 존재한다. 그리고 각각의 page는 16개의 page table entry를 갖고있다. 즉 page table안에 있는 256개의 PTE 중 16개를 합쳐서 1개의 64byte page를 구성한다.