Problem
Page table은 크기가 너무 커서 많은 메모리가 필요하다.
예를 들어 address space가 32-bit이고 page 크기가 4KB(), PTE entry 크기는 4-byte라고 가정해보자. 이 경우 page table 크기는 4MB이다.
게다가 page table은 per-process data structure라서 더 많은 메모리를 차지한다.
Simple Solution: Bigger Pages
Page table 크기를 줄이기 위한 간단한 방법 중 하나는 더 큰 page를 사용하는 것이다.
이번엔 32-bit address space에 page 크기가 16KB라고 가정하자.(VPN: 18, offset: 14)
PTE 크기는 똑같이 4KB라고 하면, 개의 entry가 있으므로 page table 크기는 1MB이다.
하지만 bigger page는 internal fragmentation가 심각해서 잘 쓰이지 않는다.
Hybrid Approach: Paging and Segments
다음은 page table의 memory overhead를 줄이기 위해 paging과 segmentation을 적절히 섞어 사용하는 hybrid 방식이다.
위 그림처럼 16KB address space와 1KB 크기의 page를 가정해보자.
page 대부분이 invalid entries여서 메모리 낭비가 심하다. 그래서 process의 address space가 하나의 page table을 갖게 하는 게 아니라, hybrid에서는 Address space의 Code, Heap, Stack 세 logical segment들이 각각 page table을 갖도록 했다.
그러면 base register가 해당 segment의 page table의 physical address를 가리킨다. bounds register는 page table의 끝을 가리키고, segment의 valid page 최대 개수를 가지고 있다. 32-bit virtual address space와 4KB pages, 그리고 address space를 4개의 segment로 나누었다고 가정해보자.
위 그림처럼 상위 2비트로 segment를 구분할 수 있다. (00:unused, 01:code, 10:heap, 11:stack)
그럼 base bounds register 쌍은 Code, Stack, Heap Segment 세 군데에 존재한다고 가정할 수 있다.
TLB miss가 발생하면 H/W는 어떤 base bounds register를 사용할지 결정하기 위해 SN(segment bits)을 사용한다.
(TLB hit의 경우 TLB에서 valid, protection bit 확인 후 PA로 바로 접근 가능하고, TLB hit인데 invalid이면 주소를 다시 구해야 한다. : exception 발생)
H/W는 아래 코드처럼 SN과 VPN을 이용해 PTE의 주소를 구한다.(SN으로 segment 결정 → base register로 physical address를 구함 → VPN을 이용해 PTE 주소 구함)
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))
// 이후 TLB를 사용하는 경우와 사용하지 않는 경우로 나뉨hybrid는 segment마다 bounds register를 가지고 있다는 점에서 기존과 다르다.
- Problems
1. 크고 듬성듬성(Sparsely-used)하게 사용하면 page table 낭비가 심하다.
2. hybrid는 external fragmentation을 유발한다. page-sized units으로 메모리를 관리하므로 page table 크기가 가변적이고, 따라서 free space를 찾기가 어렵다.
그래서 page table을 작게 구현하려 한다.
Multi-level Page Tables
Multi-Level Page Table은 segmentation을 사용하지 않고, linear page table을 tree처럼 구현하는 접근 방식이다.
먼저 page table을 page 크기로 나눈다.
Page table이 valid 한 지 아닌지는 PD(Page Directory)라는 새로운 구조체를 이용해 판단한다.
Page directory는 page table의 page가 어디에 있는지, 또는 page table 전체가 invalid 인지 알려준다.
그림의 오른쪽은 PD에서 두 개가 mark 되어있고, memory에 두 페이지만 할당된 Multi-Level Page Table이다.
Liner 한 왼쪽과 달리 Multi-level에서는 안 쓰는 부분은 free 하고, PD를 이용해 할당된 페이지만 보여준다.
PDE(Page Directory Entry)는 page table의 첫 번째 page를 가리킨다.
PDE는 valid bit와 PFN(page of page table의 PFN)을 가지고 있다.
PDE의 valid는 page table의 page가 valid 하다는 것을 의미한다. 즉, PDE가 가리키는 page table에 valid page가 적어도 하나 이상 존재한다는 것이다.
- Pros
1. Address space에서 사용할 page table만 할당하므로, 더 compact하며 sparse address space를 효율적으로 관리할 수 있다.
2. page table이 더 필요하면 next free page를 사용할 수 있므로 메모리 관리에 용이하다.
linear PT와 달리 PD를 이용해 level of indirection을 추가했다.
- Cons
1. 기존에는 TLB miss가 발생하면 한번 memory access를 하면 되었지만, multi-level의 경우 두 번(Page directory + PTE) 접근해야 하는 time-space trade off가 있다.
2. Complexity: page-table lookup이 복잡해진다.
- A Detailed Multi-Level Example
16KB의 address space, 64-byte의 page, 14-bit virtual address space(VPN 8 + offset 6)인 공간을 가정해보자.
위 그림처럼 linear page table이라면 개의 entry가 있을 것이다.
이걸 two-level page table로 쪼개기 위해 먼저 각 PTE가 4 bytes라고 가정하자.
그럼 page table은 1KB(4 bytes PTE * 256개)가 될 것이고, page가 64 bytes였으니 page table은 16개의 page를 가질 수 있다.(16개 * 64-byte page = 1KB)
그러면 각 page는 16개의 PTE를 포함한다. (PTE: 4 bytes, page: 64 bytes)
page directory entry마다 하나의 page of page table을 가리켜야 하므로, 16개의 PDE가 필요하다.
그래서 위 그림처럼 VPN의 상위 4비트를 PDI(Page directory Index)로 사용한다.
그러면 다음과 같은 방법으로 PDE address를 구할 수 있다.
PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))PTI(Page Table Index)는 Page table에서 인덱싱을 위해 쓰인다.
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))이번엔 아래 그림을 예로 살펴보자.
Page Directory에 100번과 101번 Page Table만 valid하다고 표시되어 있고, 가운데와 오른쪽에 두 Page table과 PTE들이 나타나 있다.
16개의 PT가 필요한 linear page table과 달리 PT 3개 크기만 필요하다.(PD 1개 + PT 2개)
VPN 254 (11 1111 1000 0000)의 Address Translation을 해보자.
PDI인 최상위 4비트(1111)는 15이므로 PD의 15번째 PDE인 101번 PT를 가리킨다.
PTI인 다음 4비트(1110)은 14이므로 101번 PT의 14번째 PTE를 가리키고, PFN 55가 해당한다.
따라서 Physical Address는 PFN 뒤에 나머지 offset(00 000)을 이어 붙인 값이 된다.
- More Than Two Levels
지금까지 Two level의 Multi-level Page Table을 살펴보았는데, 필요하다면 더 깊은 tree로 구현할 수 있다.
30-bit의 virtual address space, page 크기는 512 bytes라고 가정하자.
그럼 위 그림과 같이 21-bit의 VPN과 9-bit의 offset으로 나눌 수 있다.
VPN의 최상위 14비트인 PDI를 PDI 0와 PDI 1 둘로 나누면 PD를 한 번 더 나눌 수 있다.
- The Translation Process: Remember the TLB
위의 내용에 TLB까지 적용한 경우 control flow는 다음과 같다.
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit
if (CanAccess(TlbEntry.ProtectBits) == True)
Offset = VirtualAddress & OFFSET_MASK
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
Register = AccessMemory(PhysAddr)
else
RaiseException(PROTECTION_FAULT)
else // TLB miss
// first, get page directory entry
PDIndex = (VPN & PD_MASK) >> PD_SHIFT
PDEAddr = PDBR + (PDIndex * sizeof(PDE))
PDE = AccessMemory(PDEAddr)
if (PDE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else
// PDE is valid: now fetch PTE from page table
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()가장 먼저 TLB를 탐색하고, TLB hit인 경우 Page table에 접근하지 않고, Physical address에 직접 접근할 수 있다.
TLB miss인 경우 VPN의 상위 비트인 PDI를 이용해 PDE가 valid한지 판단한다. 만약 PDE가 invalid하면 segmentation fault exception을 발생시킨다.
이후 PDE가 valid하면 VPN의 PTI를 이용해 해당 PDE가 가리키는 PT의 PTE에 접근한다. 이때 PTE가 invalid하면 segmentation fault exception을 발생시킨다.
PTE의 valid bit 다음엔 protection bit를 확인한다. rwx 권한이 없으면 protection falut exception을 일으킨다.
PTE에 성공적으로 접근해 physical address를 구할 수 있게 되면, TLB에 정보를 추가하고 같은 instruction 다시 실행해 TLB hit을 유도한다.
Inverted Page Tables
Physical page에 하나의 page를 할당하는 게 virtual page를 이용해 주소를 찾는 것보다 빠를 수도 있어서 Inverted Page Tables라는 개념이 등장했다.
hash table을 이용해 PFN을 참조하는 VPN을 역으로 찾는다는 개념이다.
Uploaded by Notion2Tistory v1.1.0