목차
Multi-level Page Table
paging 방식을 이용하면 장점도 있지만, 프로세스 크기가 커지면 페이지 테이블도 같이 크기가 커진다는 단점이 있다.
위 문제의 해결책을 살펴보자.
paging 방식은 page table이라는 별도의 자료구조를 반드시 필요로하므로 메모리 자원을 소비한다.
프로세스의 크기가 작으면 프로세스 내 페이지 수가 적을 것이고, page table의 entry는 page개수와 같으므로 page table의 크기도 작을 것이다.
하지만 만약에 매우 큰 프로세스가 있다면, page table 칸 수도 커지는 문제가 발생한다.
그러면 페이지 테이블이 차지하는 메모리 공간이 매우 커질것이다.
위 그림에서 가장 아래 그림이 프로세스의 virtual address space를 나타낸 것이다.
32bit 컴퓨터의 경우 virtual address space의 크기는 최대 4GB이고, 3~4GB는 커널, 0~3GB는 프로그램 코드, 데이터, 스택의 영역인데, 이곳이 꽉 차서 이론적으로 최대 크기의 프로세스가 있다고 가정하면, 위 그림의 가장 아래 그림처럼 0번지부터 4GB-1번지까지 꽉 차서 모두 4KB 크기의 페이지들로 나누어질 것이다.
그러면 페이지 개수는 4GB / 4KB이므로 약 100만개이다.
두번째 그림은 해당 프로세스의 page table이다. page table의 entry 개수도 약 100만개가 된다.
그런데 page table도 결국 커널이 만들어서 메인메모리에 집어넣는 것이므로, 몇개의 page 공간이 필요하다.
페이지 하나는 4096byte인데, 여기에 4byte크기인 엔트리를 넣으면 최대 1024개 담을 수 있다. 100만개를 담으려면 페이지 하나 안에 페이지 테이블을 만들기가 역부족인 것이다.
각 페이지 안에 1024개 엔트리가 들어간다고 하면, 1MB개를 담기 위해서는 페이지가 약 1KB개 필요하다.
다시말해 페이지 테이블 자체가 페이지 1024개로 구성된다는 것이다. 메모리를 굉장히 많이 차지한다는 문제가 있다.
또 아래와 같은 문제점이 존재한다.
예를 들어 두번째 그림을 보면, 가장 왼쪽의 entry는 프로세스의 0번 페이지를 나타내는 0번 entry이고, 하나의 page 크기 안에 들어가는 entry 개수는 1024개이므로 두번째 빨간 박스 안에서 처음 시작하는 entry는 1024번 entry이다.
그런데 그림처럼 논리적으로 보면 entry가 순서에 맞게 연이어져있는것처럼 보이지만, 실제로 메인 메모리에 들어가게 되면 paging 방식이 사용되어 각 빨간 박스인 page들이 여러군데 흩어져 저장될것이다.
즉 1023번 entry를 읽은 다음 순차적으로 1024번 entry를 읽어야하는데, 실제로는 다른 내용이 들어있는 프레임일수 있다.
이러한 문제점을 해결하기 위해 page table의 page들을 논리적으로 연속되게 만드는 방법으로 대표적인 두가지 Multi-level page table, inverted page table가 있다.
성능 문제때문에 요즘 대부분 운영체제는 multi-level page table을 사용한다.
multi-level page table 방법은 위 그림처럼 페이지 테이블을 구성하는 페이지들을 저장하는 테이블을 윗 계층에 하나 더 만드는 방법이다.
이 페이지 테이블을 outer page table이라고 한다.
32bit 컴퓨터에서는 이와 같이 page table이 두 계층이면 된다. 이런 경우 주소가 어떤식으로 구성되는지 살펴보자.
4KB page를 사용하면 offset은 12bit가 되고, 나머지 20bit는 모두 page number이다.
이때 page table이 두 계층이면, 페이지 번호를 나타내는 숫자가 두 개 필요하다.
그래서 20bit를 10bit, 10bit로 나눠서 outer page table, 기본 page table의 인덱스번호를 차례대로 저장한다.
이때 outer page table에는 기본 page table의 모든 page들이 저장되어있기 때문에 entry 개수가 기본 page table의 page 개수와 같다.
위에서 계산한대로 기본 page table의 page 개수는 1024개였으므로, outer page table의 entry 개수도 1024개이다.
또한 꽉 찬 virtual address space도 4KB page로 나누면 총 1024개의 page로 구성된다.
이 1024는 2의 10제곱이므로, 해당 entry index를 나타내기 위해서 10bit가 필요하기 때문에 20bit가 10bit 10bit로 나뉘는 것이다.
