20. Paging: Smaller Tables

 

Paging : Linear Tables

• 지금까지 배운 page table은 linear한 하나의 table임 
• 만약 PTE의 개수가 늘어나면, page table의 size도 점점 커지게 됨
• => 너무 큰 page table size는 memory 공간 낭비 문제가 있다.

 

Paging : Smaller Tables

• page table 의 size 자체는 큰데, 그 큰 page table을 전부 사용하지 않는 경우도 있음
• 다 사용하지 않는데 physical에 전부 mapping 하는 것 역시 낭비
• => internal fragmentation

 

=> 그래서 사용하지 않는 부분은 할당하지 않기로 함

 

 

 

 

Multi-level Page Tables

• linear 한 page table을 tree처럼 생각하는 방식

• page table을 page size units으로 chop up (split)
• 그렇게 나뉘어진 부분들을 page of page table 라고 부름
• 각 page of page table에서 한 entry 라도 mapping이 되어 있으면 physical에 mapping
• page of page table이 mapping 됐는지 여부를 판단할 new structure == page directory
• physical mem에 아무곳에나 mapping 가능하고, mapping 한 후 page directory의 valid bit을 1로 설정 

=> page directory까지 포함해서 총 3개의 page를 physical mem에 할당

=> linear한 page table이 4개의 page를 할당하는 것에 비해 절약이 됨 

=> && linear 하면 physical mem에 연속적으로 할당 되어 있어야함 (이건 아무데나 할당 ㄱㄴ)

 

 

 

Multi-level Page Tables : Page directory

• 아무튼 이렇게 한다
• page directory entry (PDE)
• PDE에 마찬가지로 PFN 존재 

 

 

Multi-level Page Tables : Adv & Disadv

• Advantage
• 사용하는 address space 양에 비례해서 page table 공간을 할당 받을 수 있음
• physical mem에 어느 위치에 할당하든 상관 x

• multi-level => space는 적게 써도 time이 늘어남 
• => page directory도 memory에 있어서 변환시간 늘어남
• complexity => page directory와 table을 각각 관리해야 돼서 복잡해짐.

 

 

Multi-level Page Table : Level of indirection

• 정보를 pointer 처럼 사용하는 것을 indirection 이라고 부름
• page directory에서 pfn을 보고 page of page table의 physical mem 위치를 추적할 수 있다는 뜻

 

 

A Detailed Multi-Level Example

 

• PDE invalid => raise an exception (the access is invalid)

 

 

More than Two level

• chop up 하기 전 entry 개수랑 chop up 후 entry 개수랑 헷갈리지 말자

• 애초에 chop up 하면서 entry 개수 줄여서 multi level로 만드는게 목적임

 

 

Multi-level Page Table Control Flow

• linear 였을 때랑 크게 다를 점 x 
• Page directory에서 한번 더 검사 
• PDE 가 valid 하지 않으면 할당 x
• PDE가 valid 할 때, 그 PDE 속 PTE가  valid 한 지 이중으로 검사