Paging
- PA를 고정된 크기 Block인 page flames로 나눈다.
- LA또한 고정된 크기 Block인 page로 나눈다.
Page Table
- 각 프로세스는 각자 page table이 존재한다.
- Page table base register가 VPN을 PFN으로 변환한다.
- MMU와 OS에 의해 관리된다.
Page Table Entry(PTE)
- V: valid bit: PA에 적재되어있는지 알려주는 bit
R: Reference bit: PTE가 접근된적이 있는지 알려주는 bit
M: modified bit: 페이지의 내용이 변경되었는지 알려주는 bit
prot: protection bit: 페이지의 접근권한 Read-write-execute
PFN: page frame number: PA를 알려줌
Protection
Context switch될 때, Page Table Base Register(PTBR)가 process에 맞게 설정된다.
하지만 process는 자신의 페이지 테이블을 통해서만 메모리에 접근하기 때문에 프로세스가 다른 프로세스의 페이지 테이블을 가리킬 방법이 없다.
그래서 Valid bit, prot을 적절히 설정해 준다.
paging structure
-
32-bit크기의 CPU와 4KB의 크기의 Page가 있다고 가정해보자
Page의 총 수는 2^32/2^12 = 2^20 = 1M 이다.
Page table entry크기가 4Byte이므로 한 프로세스의 page table의 크기는 4MB 이다. -
100개의 프로세스를 실행시킨다면 400MB의 페이지 테이블이 필요하기 때문에 페이지 테이블이 너무 커진다. 그래서 효율적으로 page table을 관리할 방법이 필요하다.
-
해결방법으로 Hierarchical page table, Hash Page table, Inversion page table을 사용한다.
Hierarchical page table
- page table을 나누어 Outer page table을 만듬
- 하지만 level이 커질 수록 메모리를 자주 참조해야하는 단점이 있다.
TLB
- page table은 길기 때문에 TLB를 이용해서 빠르게 PA로 변환해준다.
- Context Switch가 일어날 때 TLB는 Flush된다.
MMU는 TLB를 확인
TLB hit: TLB에 Page Table이있으면 PA변환
TLB miss: Page table을 통해 PA변환
Hash Page table
- page number에 해시함수를 적용한 값을 바탕으로 hash table의 entry를 참조한다.
- 만약 hash값이 동일하면 collision이 발생하게 된다.
이를 해결하기 위해 linked list 자료구조를 사용한다.
Inversion Page table
- PFN을 통해 VPN과 PID를 찾는다.
- O(N)의 시간복잡도로 최악의경우 탐색에 많은 시간이 소요된다.
[참고] Operating Systems Three Easy Pieces/Remzi H.Arpaci-Dusseau/ CreateSpace Publishing
