Motivation
example 1)
Address space = 32-bit
page size = 4KB
page table entry = 4B
이때, page table의 크기는?
구하는 방법
page table 크기 = page의 갯수 * page table entry의 크기page 갯수 = 전체 공간 / page size
= 2^32 / 2^12
= 2^20
2 ^ 20 * 2^2(4B) = 2^22
4MB!!
문제 : page table의 크기가 너무 크다
프로세스별로 page table 하나씩 있어야 하는데, 얘네가 메모리 공간 다 잡아먹게 생겼어
세부 문제 1 : page 갯수가 너무 많다
세부 문제 해결 1: page의 갯수를 줄여보자
page table 크기 = page의 갯수 * page table entry의 크기에서
page table entry의 크기는 고정이니까,
page의 갯수를 줄여보자!
how?
page 하나당 크기를 늘리기!
4KB->16KB로
page 크기가 커질 때의 문제 : Internal Fragmentation(내부 단편화)
1KB가 필요해서 할당했는데, 기존에는 3KB만 낭비되었다면 사이즈 키우니 15KB가 낭비
세부 문제 2 : 불필요한 page가 page table을 차지하고 있다
Heap과 Stack 사이공간 생각해보자.
사실 비어있는 공간이 대부분임에도 불구하고, Virtual Address에서는 다 page가 존재해야 해서 page table을 잡아먹고 있다.
해결 1. Hybrid Approach(Segment + Paging)
각 segment별로 page table을 가지자!
segment마다 base, bound를 가진다
Seg비트로 어떤 base에 접근할지(page table) 결정
VPN * page entry 크기로 접근
단점
- 문제 2(불필요한 page table 차지)를 해결하지 못함.
- external fragmentation 발생할 수 있음
-> 대부분 page 단위로 관리되지만 page table은 임의의 크기를 가짐 -> free space 찾아주기 어려움
해결 2. Multi-level page tables
- linear table -> tree-like table로
- page table을 page단위로 또 쪼갠다! -> 그리고 그걸 관리하는 page directory만들기
- 만약 그 page table의 page가 전부 invalid -> 그 page 할당 안함
비교
Linear page table
page가 4개인 것을 확인할 수 있음
Multi-level Page Table
PFN202, PFN204는 모두 invalid하니까 아예 allocate도 안한 것을 확인할 수 있음
page 3개
안쓰는 page가 많을수록 효율적일 것임
장점
- 공간 확실히 절약
단점
- Access Time 증가(pagedir -> page dir -> ... -> page table -> page)
- Complexity
example 1
1. page table entry 수 구하기(사실 VPN이랑 같음)
= address space 크기 / page당 크기
= 2^14/2^6 = 2^8(256)개
page table size
= 4 * 2^8
= 2^10 1KB
page table을 page로 다시 쪼개면
page table size / page size
2^10 / 2^6
= 2^4 16개
PDE(Page Directory Entry)가 16개가 됨
-> 상위 4개 bit을 Page Directory Index bit로 사용
-> 1개 page table = 16개 page로 쪼갤 수 있다!
-> VPN에서 4bit 분리
page table entry는 4B니까
1개 page당 page table entry는
64 / 4 -> 16개 들어간다.
-> page table index
Q. Page directory index 추출이 먼저인가, 아니면 page table index 추출이 먼저인가?
example 2
1. page table entry 수 구하기
2^30/2^9 = 2^21개
2. page table size 구하기
2^21 * 4 = 2^23 8MB
3. page당 page table entry 갯수 구하기
2^9 / 2^2 = 2^7개
4. page table에 page 몇개 들어가는지 구하기
2^23 / 2^9 = 2^14개
-> 상위 14bit PDI
2^14개 -> 너무 많아... -> 또 쪼개자!
Inverted Page Table
t
