Chapter#16 Paging Advanced

Chapter#16 Paging Advanced

- Hybrid Approach

- Multi-level Page Table

- Inverted Page Table

---

Hybrid Approach

굳이 안쓰이는 공간에 대해서 page table이 메모리 공간을 잡아 둘 의미가 없다

-> Segmentation과 Paging 동시 사용

- code, heap, stack별로 page table을 만들자

- base register : 각 segment에 대해 page table의 physical address를 가리킴

- bound(or limit) register : page table의 끝을 가리킴(length)

 

Design of Hybrid Approach

Virtual Address : 상위 2 bits는 segment value를 의미

00 : Unused segment

01 : Code

10 : Heap

11 : Stack

H/W(CPU) : 3개의 base/bound pairs(각각 code, heap, stack 의미)

S/W(OS) : context switch가 일어나면, base/bound pairs는 새로 running되는 프로세스의 page table값으로 변경

Hybrid Apprach의 문제점

External fragmentation 발생 : page table 공간이 연속적이어야하고 크기가 동적임

Free-space management가 어려움 : Best-fit으로 할지 Worst-fit으로 할지 결정을 해야 함

 

---

Multi-level Page Table

page table을 page sized unit으로 자름

page table entry의 전체 page가 invalid하면 하당 entry의 page는 할당하지 않음

할당 되었는지 아닌지 잘 확인하기 위해 한단계를 더 거침 = page directory

장점 : 

메모리 절약 : 안쓰는 page는 메모리 할당이 안됨

메모리 관리 효율 증가 :

- linear page table은 VPN으로 인덱싱된 PTE의 연속적인 배열이었는데, 이는 External fragment 발생

- multi-level page table은 멀티 레벨을 통해 간접적으로 접근하므로, 페이지들이 불연속적으로 배열 가능

단점 :

Time-Space trade-off : TLB miss가 일어나면 2레벨 load가 필요

Complexity : 테이블 한개짜리보다 더 많은 테이블을 관리함

 

Linear PT VA

Multi-level PT VA

linear page table의 VPN은 해당 엔트리를 바로 가리키지만

multi-level의 경우 VPN 앞쪽 bits가 PDE(Page Directory Entry)이고, 뒤쪽 bits가 PTE(Page Table Entry)이다.

- PDE로 먼저 valid인지 확인하고 PTE를 확인하여 physical memory access

 

같은 방식으로 2보다 큰 level Page Table만들 수 있음

 

e.g. 7 bit Page Directory Index 0 and 1, 7 bit Page Table Index, 9bits Offset

Virtual Address	1GB(2^30)
Page Size	512B(2^9)
VPN	21 bit
Offset	9 bit
Page Table Entry(per pate)	128(=2^7) PTEs(per page)
Page Table Size	512B
1st Page Directory Table Entry	128(=2^7) (per process)
1st Page Directory Table Size	512B
0st Page Directory Table Entry	128(=2^7) (per process)
0st Page Directory Table Size	512B

---

Inverted Page Table

많은 Page Table을 사용하는게 굳이 필요한가? - 실질적으로 사용되는 PTE는 physical memory의 page frame 수와 같다

virtual address의 VPN을 hash function을 통해 physical pages 수에 맞게 할당한다

> # of PTEs = # of physical pages

장점

메모리 효율 : 

TLB miss 지원을 위한 memory reference가 더 적음

단점

Hash Collision : worst-case access time

- collision발생 시 탐사 방법에 따라 다르지만 아무튼 access time이 증가함

- inverted page table entry 수 증가 -> 더 많은 메모리 필요

- collision발생 시 PTE위치로 PFN 알 수 없음 -> Table에 PFN 값도 추가되어야 함

Page Sharing이 어려움(가능은 함)

Swapping지원이 비효율적

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.