페이징의 두번째 문제점은 페이지 테이블의 크기이다.
전에 말했듯이, 선형 페이지 테이블을 예시로 들면, 32비트 운영체제의 경우 페이지 테이블 하나의 크기는 4MB 정도 되고, 프로세스가 100개라면 페이지 테이블을 위해 400MB의 메모리가 필요하다.
핵심 질문: 페이지 테이블을 어떻게 더 작게 만들까?
선형 페이지 테이블은 메모리를 과하게 차지한다. 어떻게 테이블의 크기를 줄일까? 주요 개념은 무었이고, 어떤 자료구조를 사용할까?
1. 간단한 해법: 더 큰 페이지
페이지 테이블의 크기를 줄이는 가장 간단한 방법은 페이지의 크기를 늘리는 것이다.
16KB의 페이지를 가정한다면, 18비트의 VPN과 14비트의 offset을 가질 것이다. 4KB 페이지 방식에 비해 VPN이 4배 줄었기 때문에, 테이지 테이블의 크기도 1MB로 줄어들 것이다.
그러나 페이지 크기 증가의 가장 큰 문제는 내부 단편화이다. 내부에 사용되지 않는 공간이 낭비된다. 이는 곧 메모리의 빠른 고갈로 이어진다. 그래서 대부분의 시스템음 4KB/8KB의 페이지를 사용한다.
2. 하이브리드 접근 방법: 페이징과 세그먼트
1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 들어보자. 코드 페이지(VPN 0)은 PFN 10에, 힙 페이지(VPN 4)는 PFN 23에, 두개의 스택 페이지(VPN 14, 15)는 PFN 28, 4에 매핑되어 있다. 보이는 것처럼 대부분의 페이지 테이블이 비어있다. 32비트 주소 공간 페이지에서는 더 심할 것이다.
이를 위해 코드, 힙, 스택 세그먼트에 대해 페이지 테이블을 두는 방식을 고안했다.
각 코드, 힙, 스택 세그먼트는 각각의 페이지 테이블을 가진다. 각 테이블은 베이스와 바운드 레지스터를 가져 테이블의 위치와 범위를 표시한다. 각 프로세스는 3개의 페이지 테이블을 가지게 된다.
TLB 미스가 발생하면, seg 비트를 통해 어떤 베이스-바운드 레지스터를 사용할지 결정하고, VPN과 Offset을 통해 주소 변환이 이루어진다.
하이브리드 방식에서 사용되지 않은 페이지는 테이블에서 공간을 차지하지 않아 메모리 관점에서 더 좋다. 그러나 문제 또한 존재한다.
- 여전히 세그멘테이션을 사용한다. 이는 주소 공간에 사용에 있어 특정 패턴을 가정하기 때문에 유연하지 않다.
- 외부 단편화를 유발한다. 페이지 테이블은 크기에 제한이 없기 때문에 다양한 크기를 가져, 메모리 상에서 공간 확보가 더 복잡하다.
3. 멀티 레벨 페이지 테이블
선형 페이지 테이블을 트리 구조로 표현한다. 매우 효율적이기 때문에 현대 시스템에서 많이 사용한다(x86).
멀티 레벨 페이지 테이블의 기본 개념은 간단하다. 먼저, 페이지 테이블을 페이지 크기 단위로 나눈다. 만약 페이지 테이블의 페이지가 유효하지 않은 항목만 있다면 해당 페이지는 할당하지 않는다.
헷갈리면 안되는게, 주소 공간의 페이지를 의미하는게 아니라,
페이지 테이블을 페이지의 단위로 나눈 것이다.
페이지 디렉터리(page directory)라는 자료구조를 통해 각 페이지의 할당 여부와 위치를 파악할 수 있다.
페이지 디렉토리는 페이지당 하니의 entry를 가지고 있다. 페이지 테이블의 시작 부분을 가진다. 즉 베이스 레지스터 같은 느낌이다. page directory entry가 유효한지 알려주는 valid bit와 page frame number로 구성된다.
페이지 디렉터리를 통해 실제로 사용중인 페이지 테이블에만 접근할 수 있도록 해줘 메모리 낭비를 방지할 수 있다.
멀티 레벨 페이지 테이블은 몇가지 장점이 있다.
- 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당되기 때문에, 보다 작은 크기의 페이지 테이블로 주소 공간을 표현할 수 있다.
- 페이지 테이블을 페이지 크기로 분할하기 때문에 메모리 관리에 유용하다.
- 페이지 테이블의 할당이나 확장할 때, free 페이지 풀에서 가져다 쓰면된다.
- 선형 테이블은 연속된 물리 공간을 가져야하지만, 페이지 디렉터리를 사용하면 페이지들이 물리 메모리 안에서 산재해있어도 되므로 더욱 유연하다.
그러나 TLB 미스 시, 주소 변환을 위해 두 번의 메모리 로드가 발생한다. 페이지 디렉터리 한 번, PTE 한 번.
예제
해당 방식의 주소 공간은, 페이지 디렉터리 엔트리(PDE)의 위치를 찾기 위한 page directory index와, 페이지 테이블의 페이지에서 매핑할 PFN을 찾기 위한 page table index를 가진다.
11 1111 1000 0000
다음 주소를 멀티 레벨 페이지 테이블 방식을 이용하여 변환해보자. 첫번째 4비트(1111)은 15번째 PDE를 나타낸다. PDE 15의 vaild비트가 1이기 때문에, 페이지 테이블의 페이지에 접근할 수 잇다.
이후의 4비트(1110)은 페이지 내에서 원하는 페이지 엔트리(14번째)를 찾는다. 이제 주소의 VPN 부분이 PFN으로 변환되어(111 1110 → 0011 0111) 메모리 접근을 하게될 것이다.
2단계 이상 사용하기
페이지 디렉터리가 너무 커질 수도 있다. 이런 경우, 페이지 디렉터리 자체를 멀티 페이로 나누어서 트리의 단계를 늘릴 수 있다.
4. 역 페이지 테이블
이 방법은 시스템에 단 하나의 페이지 테이블만 둔다. 페이지 테이블은 물리 페이지를 가상 주소의 페이지로 변환한다. 역 페이지 테이블의 엔트리는 물리 페이지를 사용 중인 프로세스의 번호와 해당 가상 페이지 번호를 가지게 된다.
5. 페이지 테이블을 디스크로 스와핑하기
지금까지는 페이지 테이블은 커널이 소유하고 있는 물리 메모리 영역에 있다고 가정했다. (MMU에 저장)
아무리 페이지 테이블 크기를 줄이기 위한 시도를 하고 있지만, 여전히 클수도 있다. 그래서 일부 시스템은 페이지 테이블을 커널의 가상 메모리에 위치시키고, 페이지 테이블을 디스크로 스왑시키기도 한다.
다음 단원에서 자세히 나오게 된다.
