Advanced Page Tables

박정빈·2024년 4월 6일

목록 보기

15/25

앞의 포스팅에서 Paging에 대해 알아보았다. 페이징은 페이지 테이블이 너무 크고 메모리를 너무 많이 사용한다는 문제가 있었다. 이 문제를 해결하기 위한 방법들을 알아보자

더 큰 페이지

페이지 테이블이 큰이유는 페이지가 많아서 그렇다. 페이지가 커져서 페이지 수가 적어지면 페이지 테이블을 줄일 수 있을까?

더 큰 페이지를 사용함으로써 페이지 테이블의 크기를 줄일 수 있다.
16KB 페이지를 가지는 32비트 주소 공간을 생각해보자. 18비트 VPN과 14비트 offset을 가질 것이다. PTE의 크기가 같다고 가정하면, 페이지 테이블에는 $2^{18}$ 개의 항목이 있고 페이지 테이블 크기는 1MB이다. 페이지 크기가 4배로 증가한만큼 페이지 테이블의 크기가 4배로 준다.
하지만 이 방법을 사용하면 큰 페이지를 할당하기에 페이지 안에서 낭비가 발생하는 내부단편화라는 문제가 발생한다.
(할당 해줬는데 안써..)

하이브리드 방법

페이지 테이블이 너무 크니까 페이지 테이블을 세그멘테이션 해보자
그렇게 하면 Paging 과 Segmentation 의 장점만 가져올 수 있을까?

1KB 페이지를 가진 16KB 주소공간을 생각해보자
A 16KB Address Space With 1KB Pages
그리고 그 주소공간을 위한 페이지 테이블은 다음과 같다.
A Page Table For 16KB Address Space
페이지 테이블 대부분은 사용되지 않고 낭비되고 있다. 이런 낭비를 막기 위해서 새로운 아이디어가 필요하다.

프로세스의 전체 주소공간에 대한 페이지 테이블 대신, 논리적 세그먼트마다 페이지 테이블을 갖는 것이 어떨까? 이 예에서는 주소공간에서 코드,힙,스택에 각각 페이지 테이블이 있을 수 있다.
Segmentation에서 각 세그먼트의 물리적 메모리 위치를 알려주는 base 레지스터와 bound레지스터가 있었다. 그리고 우리의 하이브리드 적인 아이디어에도 MMU에 그런 구조체가 있다. 여기서 base 레지스터는 세그먼트의 페이지 테이블의 물리적 주소를 저장한다. bound 레지스터는 페이지 테이블의 끝을 나타낸다.

4KB 페이지를 사용하는 32비트 주소공간이 있고, 4개의 세그먼트로 분할되어있다고 가정해보자, 주소가 어느 세그먼트를 가르키는지 상위 두비트로 표현한다. 00은 사용되지 않는 세그먼트, 01은 코드, 10은 힙, 11은 스택을 나타낸다.

하드웨어에 코드,힙,스택에 대한 base/bound 레지스터가 있다. 각 base 레지스터는 해당 세그먼트의 물리적 주소가 있다. 즉, 각 프로세스는 3개의 페이지 테이블을 갖는다는 것이다. context switching 에서 이런 레지스터를 변경하여 새로 실행중인 프로세스의 페이지 테이블 위치를 반영해야한다.

TLB miss 가 발생했을때, 하드웨어는 세그먼트 비트(SN)로 사용할 base/bound 쌍을 결정한다. 그 후 하드웨어는 물리적 주소로 PTE주소를 형성한다.

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

각 bound 레지스터는 세그먼트 내의 최대 유효 페이지 값을 표시한다. 예를들어 코드 세그먼트가 0,1,2 페이지를 사용할 때, 코드 세그먼트의 페이지 테이블에는 세 항목만 할당되고 bound 레지스터는 3으로 설정되어, 그 이상의 메모리 접근은 예외를 발생시킨다.

하이브리드 접근방식은 상당한 메모리 절약을 한다. 힙과 스택사이의 할당되지 않은 페이지는 페이지 테이블에 공간을 차지하지 않는다. 하지만 세그멘테이션을 사용하기에 유연함이 떨어지며, 외부 단편화가 생길 수 있다.

Multi-level Page Tables

Multi-level Page Tables는 선형 페이지 테이블을 트리 구조로 변환한다. 이 방법은 효과적이어서 많은 현대 시스템에서 사용한다.

기본 아이디어는 다음과 같다. 페이지 테이블을 페이지 크기 단위로 나눈다. 그 다음, PTE의 전체 페이지가 무효한경우, 해당 페이지 테이블의 페이지를 할당하지 않는다. 페이지 테이블의 페이지가 유효한지를 추적하기위해 페이지 디렉토리(page directory)를 사용한다. 페이지 디렉토리는 페이지 테이블의 페이지 위치와 페이지 테이블의 유효 페이지 존재 여부를 알려준다.

아래 사진을 보면, 왼쪽에는 기존의 선형 페이지 테이블이 있다. 여기서는 사용하지 않는 공간도 할당되어 있는 것을 볼 수 있다.
반면, 오른쪽의 Multi-level Page Table은 사용하는 페이지만 할당하며, 페이지 디렉토리로 이를 추적하는 모습을 볼 수 있다.
Linear (Left) And Multi-Level (Right) Page Tables
이 예시의 경우는 페이지 디렉토리와 페이지 테이블 두 단계로 나뉘므로 two level page table이라고 할 수 있다. 페이지 디렉토리 항목은 PDE(page directory entries)라고 한다.

이 방법은 주소 공간의 사용량에 비례하여 페이지 테이블 공간을 할당하기에 메모리를 아낄 수 있다. 또, 페이지 테이블이 페이지와 딱 맞기에 메모리 관리가 용이하다. 페이지 테이블을 할당하거나 할당할 때, 페이지 디렉토리를 통한 간접 참조로 페이지 테이블을 물리적 메모리의 원하는 위치에 배치할 수 있다.

하지만 이 방법은 비용이 발생한다. TLB miss가 발생한다면, 페이지 디렉토리와 페이지 테이블,메모리에 두 번의 로드가 필요하다. 그리고 선형 구조에서 트리 구조로 바뀐 만큼 $logn$ 의 검색 시간이 든다. 공간을 아낀 만큼 시간을 쓰는 것이다. 또, 페이지 테이블을 위한 디렉토리가 존재한 만큼 더 복잡해졌다.

Multi-level Page Table의 예시

64바이트 페이지와 4바이트 PTE를 갖는 16KB크기의 주소공간을 생각해보자
16KB= $2^{14}$ 이므로 주소공간을 14비트로 나타내고, 64Byte= $2^6$ 이므로 VPN은 6비트, offset은 8비트로 나타낸다. 그리고 선형 페이지 테이블을 사용한다면, 페이지 테이블당 256개의 PTE가 존재한다.
A 16KB Address Space With 64-byte Pages
위의 주소공간에서 가상 페이지 0,1번은 코드에 4,5번은 힙에 254,255번은 스택에 할당되고 나머지는 사용하지 않는다. 우리는 이 선형 페이지 테이블을 two level 페이지 테이블로 만들것이다. 이를 위해 선형 페이지 테이블을 페이지 크기의 단위로 나누어야한다. 테이블은 4바이트의 PTE 256개로 구성되므로, 페이지 테이블은 1KB이다. 그리고 64 바이트 페이지를 사용하기에 16개의 64바이트 페이지로 나눌 수 있다. 각 페이지에는 16개의 PTE를 저장할 수 있다. (PDE 하나당 16개의 PTE를 표현하므로 총 PDE 16개 X PTE 16개 = 256개)

이제 VPN으로 페이지 디렉토리에 인덱싱한다음 페이지 테이블의 페이지로 인덱싱해야한다.
먼저 페이지 디렉토리에 인덱싱 해보자 이것은 16개의 페이지에 퍼져있는 256개의 PTE가 있다. 페이지 디렉토리는 각 페이지를 가리키므로 16개의 PDE가 있다. 그리고 VPN의 상위 네 비트로 PDE를 구별한다.

VPN 의 상위 4 비트로 구한 페이지 디렉토리 인덱스(PDIndex)로 PDE의 주소를 구할 수 있다.

PDEAddr = PageDirBase + (PDIndex* sizeof(PDE))

그리고 이 PDE를 통해 PTE를 가져와야한다. PTE를 찾기 위해 VPN의 나머지 비트를 사용한다.

이 나머지 비트를 페이지 테이블 인덱스(PTIndex)라 하면

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

를 통해 PTE주소를 구할 수 있다.

아래 사진은 페이지 디렉토리와 페이지 테이블의 예시이다.
A Page Directory, And Pieces Of Page Table
PDE는 페이지 테이블에 대한 매핑이 있다.
물리적 페이지 100에는 주소 공간의 첫 16개 VPN에 대한 항목이 있다. 예제에서는 VPN 0,1 (코드)와 4,5 (힙) 에 대한 매핑 정보가 있다.
물리적 페이지 101에는 나머지 16개 VPN에 대한 항목이 있다.
기존의 16개 페이지 테이블을 유지하는 것과 비교하면 메모리 절약을 많이 했다.

VPN 254의 0번 바이트를 참조하는 주소 0x3f80또는11 1111 1000 0000을 변환해보자
VPN의 상위 4비트는 페이지 디렉토리에서의 인덱싱이다. 1111은 마지막 항목이다. 마지막 항목이 101을 가리키므로 101의 페이지 테이블로 이동한다.
VPN의 다음 4비트는 페이지 테이블에서의 인덱싱이다. 1110은 페이지 테이블에서 14번째 항목이다. 그리고 거기에는 55가 있어서 가상 주소 공간의 페이지 254가 물리적 페이지 55에 매핑되었다는 사실을 알려준다. PFN=55이고 offset은 0번이므로 다음을 통해 주소를 계산할 수 있다.

PhysAddr = (PTE.PFN << SHIFT) + offset//= 00 1101 1100 0000 = 0x0DC0

More Than Two Levels

페이지 디렉토리와 페이지 테이블로 이루어진 two level 페이지 테이블이 아니라, 더 깊은 트리로 구성할 수 있다.
페이지 크기가 512바이트, PTE 크기가 4바이트인 30비트 가상 주소 공간을 생각해보자
21비트 VPN, 9비트 offset의 가상주소가 생긴다.

페이지 크기가 512 바이트이고 PTE크기가 4바이트이므로 한 페이지에 128(512/4)개의 PTE가 있다. 따라서 페이지 테이블 인덱싱 비트는 7비트이다.( $2^7=128$ )
7비트를 쓰고 나면 VPN에서 14비트가 남는다. 페이지 디렉토리에 이 14비트를 모두 사용한다면, $2^{14}=16384$ 의 PDE가 있는 것이고 각 PDE를 페이지 테이블로 매핑하는 목표가 실패하게된다.
이 문제를 해결하기 위해 페이지 디렉토리를 여러 페이지로 분할하고, 또 다른 디렉토리를 추가할 수 있다.

PD Index 0을 사용해서 인덱싱 후 PD Index 1을 사용해서 인덱싱하고, PDE와 PD Index를 결합하여 PTE주소를 찾을 수 있다.

The Translation Process: Remember the TLB

TLB는 여전히 사용할 수 있으며 level이 많아질수록 TLB miss 발생시 메모리 접근이 많아진다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB 히트
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else // TLB 미스
    // 먼저, 페이지 디렉터리 항목 가져오기
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if (PDE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else
        // PDE가 유효함: 이제 페이지 테이블에서 PTE 가져오기
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE = AccessMemory(PTEAddr)
        if (PTE.Valid == False)
            RaiseException(SEGMENTATION_FAULT)
        else if (CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT)
        else
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()