💿

11 : Multi-Level Page Table

course

last review

2023/04/14

mastery

rookie

progress

not started

date

4 more properties

Previous chapter

10 : Translation-Lookaside Buffer

Main QUEST : HOW TO MAKE PAGE TABLE SMALL

More Big Page

HYBRID : Paging & Segment

Multi-Level Page Table

Examples

Inverted Page Table

페이징의 또다른 문제를 해결하기 위해 이곳에 왔다!

페이징은 훌륭한 기법이지만, 페이지 테이블의 크면 메모리 공간 또한 많이 차지하게 된다.

Main QUEST : HOW TO MAKE PAGE TABLE SMALL

선형 배열 페이지 테이블은 크기가 크며 메모리를 과도하게 차지한다. 페이지 테이블의 크기를 줄이는 방법은?

More Big Page

가장 간단한 방법은 페이지의 크기를 늘리는 방법이 될 것이다.

•

페이지당 크기가 4KB, 페이지 테이블의 각 항목이 4바이트인 32비트 주소공간.

◦

페이지 넘버가 232212=220\cfrac{2^{32}}{2^{12}}=2^{20}212232​=220개가 되며, PFN이 2202^{20}220이고, 각 항목이 4바이트이면, 페이지 테이블의 총 용량은 4MB가 된다.

PFN의 비트가 20자리인데, 이를 18로 줄여보자. 페이지 넘버는 4배 줄고, 오프셋(페이지의 최대한도)은 4배 늘게 된다. 총 페이지 용량도 1MB로 줄어는다.

페이지 크기의 증가는 부작용을 수반한다.

바로 페이지 내부의 낭비공간이 늘어나게 된다는 문제인데, 이를 내부 단편화(internal fragmentation)이라고 한다.

응용 프로그램이 여러 페이지를 할당 받았지만 할당받은 페이지의 일부분만 사용해, 결국 메모리가 금방 고갈되게 된다.

HYBRID : Paging & Segment

페이징과 세그멘테이션을 결합하여 테이블 크기를 줄일 수도 있다!

기존의 선형 페이징 방식은 필요한 정보가 적을 경우, 메모리 낭비가 심한 단점이 있다.

valid bit의 무수한 0을 보라. 저만큼 메모리가 낭비된다.

프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 세그먼트별로 페이지 테이블을 두면 어떨까? 좋은 아이디어 같다.

이 방법에서는 세그멘테이션에서 했던 것 처럼 베이스, 바운드 레지스터를 사용한다.

그러나 각각의 세그먼트에 대한 시작 주소가 아닌, 세그먼트의 페이지 테이블의 시작 주소를 가진다.

32비트 가상주소는는 이제 VPN, 오프셋 그리고 새로 들어온 세그먼트로 구성된다.

소속 세그먼트를 나타내기 위해 상위 2비트를 사용하겠다. 01 = 코드, 10 = 힙, 11 = 스택

또한 하드웨어에 세 개의 베이스, 바운드 레지스터 쌍이 있다고 가정하자.

실행중인 프로세스에서 각 베이스 레지스터는 각 세그먼트 페이지의 시작 주소를 가진다.

TLB의 미스가 일어나면 하드웨어는 세그먼트 넘버를 사용하여 어떤 베이스와 바운드를 쓸 지 결정한다.

그 레지스터에 들어있는 물리 주소를 VPN과 다음과 같은 형식으로 조작해 PTE의 주소를 얻는다.

SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (virtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN*sizeof(PTE))
C
복사

하이브리드 기법의 핵심은 세그먼트마다 바운드 레지스터가 따로 존재한다는 것이다.

각 바운드 레지스터의 값은 최대 세그먼트의 유효페이지 수를 나타낸다.

하이브리드 기법 역시 문제가 있는데,

여전히 세그멘테이션을 사용한다.

빈공간이 많은 힙의 경우 여전히 페이지 테이블의 낭비를 면치 못한다.

하이브리드 기법은 외부 단편화를 유발한다.

페이지 테이블의 크기에 제한이 없으며, 다양한 크기를 갖기 때문이다.

이런 문제로 인해 세그멘테이션을 사용하지 않고 페이지 테이블 크기를 줄이는 게 더 좋은 방향이라고 판단된다.

Multi-Level Page Table

멀티레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다.

이는 매우 효율적이며 많은 현대 시스템에서 사용되고 있다.

멀티 레벨 페이지 테입르의 개념은 간단하다.

페이지 테이블을 페이지 크기의 단위로 나눈다.

페이지 테이블의 페이지가 유효하지 않는 항목만 있다면, 해당 페이지를 날려버린다.

페이지 디렉터리(page directory)라는 자료구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다.

페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재여부와 위치를 가진다.

위 예제를 해체해보자.

좌측 그림은 전형적인 선형 페이지 테이블로, 가운데 주소공간은 사용되지 않고 있지만 페이지 테이블에 할당되어있다.

우측은 멀티레벨 페이지 테이블로, 두개의 유효한 페이지가 있다. 유효페이지 두개는 메모리에 존재한다.

멀티레벨 페이지 테이블은 몇가지 장점이 있다.

멀티 레벨 테이블은 사용된 주소공간의 크기에 비례해 페이지 테이블 공간이 할당된다.

보다 작은 크기의 페이지 테이블로 주소공간을 표현할 수 있다.

페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 용이하다.

페이지 테이블을 할당, 확장할때 OS는 free 페이지 풀에 있는 빈 페이지를 가져다 쓰면 끝이다!

생각해보자. 선형 페이지 테이블은 연속된 물리 메모리 공간을 차지한다. 보통 선형 페이지 테이블의 경우 메모리의 크기가 큰 경우가 많은데, 크기가 크고 연속된 물리 공간을 찾는 건 쉬운일이 아니다.

반대로 멀티레벨 페이지는 페이지 디렉터리를 사용해 각 페이지 테이블의 위치를 파악할 수 있다. 각 페이지가 중구난방이더라도 페이지 디렉터리를 통해 위치추적이 가능하다!

그러나 장점만 있는 것은 아니다.(늘 그렇듯이) 다음과 같은 단점을 가진다.

멀티 레벨 테이블은 추가 비용이 발생한다.

주소변환을 위해 두번 이상의 메모리 로드가 발생한다.(한번은 페이지 디렉터리, 한번은 PTE)

선형 페이지 테이블에 비해서 시간 효율을 일정 버린 셈이다.

페이지 테이블의 검색이 선형 테이블보다 복잡해진다.

Examples

페이지당 64바이트를 갖는 16KB의 크기의 작은 주소공간을 생각해보자.

16KB =

2^{14}

이므로, 주소공간의 비트길이는 14비트다.

페이지당 64바이트이므로, 오프셋은 6, VPN은 8비트로 구성되어, 256개의 선형 페이지 테이블이 1차적으로 가정될 수 있다.

각 페이지 테이블 당 4바이트라고 가정할 경우, 페이지 테이블의 크기는 256 ^ 4 = 1024바이트 = 1KB이다.

페이지가 64바이트였으므로, 1KB를 64바이트로 쪼개자. 총 16개의 페이지로 분할 될 것이며, 각 페이지에는 16개의 PTE가 있을 것이다.

이제 VPN으로부터 페이지 디렉터리 인덱스를 추출하고, 페이지 테이블의 각 페이지 위치를 파악하는 법을 살펴보자. 페이지 디렉터리, 페이지 테이블의 페이지 모두 항목의 배열임을 잊지 말자.

먼저 페이지 디렉터리의 인덱스를 구성한다. 작은 페이지 테이블은 256개의 항목으로 각 16개의 페이지로 나뉘어 있으며, 각 페이지당 16개의 PTE가 있다.

결과적으로 16개의 페이지를 인덱싱하려면, 4bit를 사용하여 디렉터리를 구성한다. VPN의 상위 4비트를 다음과 같이 사용한다.

VPN에서 페이지-디렉토리 인덱스(page-directory index : PDIndex)를 추출하면 다음과 같은 식이 나올 것이다.

PDEAddr = PageDirBaseReg + (PDIndex * sizeof(PDE))
C
복사

PD의 해당 항목이 무효 처리되어있으면, 이 접근은 유효하지 않다.

반대로 PDE가 유효하다면 추가 작업을 해야한다.

페이지 테이블의 페이지에서 원하는 페이지 테이블 엔드리를 읽어들기는 것이 목표다. 나머지 비트를 사용하자.

페이지 테이블 엔트리의 주소는 다음과 같이 계산한다.

PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
C
복사

PTE의 주소를 생성하려면, 페이지 디렉터리 항목에서 얻은 페이지-프레임 넘버를 먼저 좌측 쉬프트 연산한 후, 페이지 테이블 인덱스에 합산한다.

Inverted Page Table

나중에…

Next chapter