Paging

Linear Tables

• 대부분의 시스템은 프로세스당 하나의 Page Table을 갖는다.
  • 4KB 크기의 Page, 32비트 주소 공간 (= 4GB Virtual Memory Size), 4바이트 Page Table Entry는 다음과 같다.

Page Table Size = ($\frac{2^{32}}{2^{12}}$ * 4Byte = 4MB) * ( # of Processes)

• $\frac{2^{32}}{2^{12}}$ = Page 수, n
  ⠀⠀
• 4 Byte = Page Table Entry Size

Larger Page, Smaller Table

• Linear Table을 사용하면 Page Table 크기가 커져 메모리 소비가 많아진다.
  → Page Size 증가, Page 개수 감소
  • 16KB 크기의 Page, 32비트 주소 공간 (= 4GB Virtual Memory Size), 4바이트 Page Table Entry는 다음과 같다.

Page Table Size = ($\frac{2^{32}}{2^{14}}$ * 4Byte = 1MB) * ( # of Processes)

• $\frac{2^{32}}{2^{14}}$ = Page 수, n
  ⠀⠀
• 4 Byte = Page Table Entry Size
  ⠀⠀
• Page Table 크기는 감소하지만 Internal Fragmentation 발생
  • Page 활용도 저하
  • Page 크기 증가는 Page 수 감소를 의미 → 메모리가 빠르게 소모됨

Problem

• 대부분의 Page Table의 Entry는 Invalid 상태로 공간을 차지한다.

Hybrid Approach: Paging and Segments

• Hybrid Approach: Paging과 Segmentation 모두를 최대한 활용하는 방법
• Page Table의 메모리 오버헤드를 줄이기 위해 사용
  • Base Register가 Segment 자체를 가리키는 것이 아니라 해당 Segment Page Table의 Physical Address를 유지하기 위해 사용한다.
  • Bound Register는 Page Table의 끝을 나타내는 데 사용된다.
    → Segment의 최대 Valid Page 수

Example

• 각각의 Process는 세 개(Code, Stack, Heap)의 Page Table이 연결되어 있다.
  • Process가 실행 중일 때, Segment들의 Base Register는 해당 Segment의 Linear Page Table의 Physical Address가 포함된다.

Problem

• Hybrid Approach 역시 문제가 동반된다.
  • 크기는 크지만 Heap이 자주 사용되지 않는 경우, 많은 Page Table 낭비 발생
  • External Fragmentation 발생

Multi-Level Page Tables

• Linear Page Table을 트리 형태로 만든다.
  • Page Table을 Page 크기 단위로 자른다.
  • Page Table Entry의 전체 Page가 Invalid인 경우 해당 Page를 할당하지 않는다.
  • Page Table의 Page가 유효한지 추적하려면 Page Directory라는 새로운 구조를 사용한다.

• PTBR : Page Table Base Register
• PFN : Page Frame Number

Page Directory Entry

• Page Directory는 Page Table의 한 Page당 하나의 Entry를 포함한다.
  • 여러 Page Directory Entries(PDE)로 구성된다.
• PDE는 Valid Bit과 Page Frame Number(PFN)을 갖는다.
  • Invalid: Page Table의 모든 Page가 Invalid이다.
  • Valid: PDE가 가리키는 해당 Page의 PTE가 최소 하나 이상 Valid이다.

A Detailed Multi-Level Example

• Address Space : 16KB → 2$^1$$^4$Byte
• Number of Pages : 2$^8$Byte → 16KB (Address Space) ÷ 64Byte (Page Size)
• Virtual Address : 14bit → Address Space의 크기가 2$^1$$^4$Byte
• Offset : 6bit → Page 내의 메모리 주소 수 (=Page Size) = 2$^6$Byte
• VPN : 8bit → (14 - 6)bit
  ⠀⠀
• Page Directory는 Page Table의 Page당 하나의 Entry를 필요로 한다.
  → 총 16개의 Entry

• Logical Address는 다음 두 가지로 나눌 수 있다.
  • Page Number : 20bit → 2$^2$$^0$ (2$^3$$^2$B ÷ 4KB) Pages
  • Page Offset : 12bit → 4KB Page Size
    ⠀⠀
• Page Number는 다음 두 가지로 나눌 수 있다.
  • Page Directory Index : 2$^2$$^0$ x 2$^2$ ÷ 2$^1$$^2$ = 10 bit
  • Page Table Index : 2$^1$$^2$ ÷ 2$^2$ = 10bit
    ⠀⠀
    

→ 필요할 때 할당하는 시스템

Advantage & Disadvantage

Advantage

• 사용 중인 주소 공간의 양에 비례하여 Page Table 공간만 할당한다.
• OS는 Page Table을 할당하거나 늘려야 할 때 다음 여유 Page를 확보할 수 있다.

Disadvantage

• TLB Miss 시 Page Table에서 올바른 주소 변환 정보를 얻으려면 메모리에서 두 번의 Load가 필요합니다.
  “Time-Space Trade-Off”
  • 더 작은 Page Table 크기
  • TLB Miss → 메모리에서 2개 Load → Page Directory용 1개, PTE 자체용 1개
    ⠀⠀
• Complexity 증가

Level of Indirection

• 다중 레벨 구조는 Page Directory를 사용하여 간접 레벨을 조정할 수 있다.
  • 간접적으로 위치한 Page Table은 물리적 메모리에서 원하는 곳 어디든 Page를 지정할 수 있다.

More than Two Level

• 어떤 경우에는 더 깊은 트리도 가능하다.

32bit가 아니라 30 bit인 이유 → 나머지 두 비트는 Segmentation Bit

• Page Index: 2$^2$$^1$
• Page Table Index: 2$^9$ ÷ 4(Entry Size) = 2$^7$ → 7
• Page Directory Index: 2$^2$$^1$ ÷ 2$^7$ = 2$^1$$^4$ → 14
  ⠀⠀
• Page Table Index = Offset Size ÷ Page Table Entry Size
• Page Directory Index = Page Index ÷ Page Table Index

Page Directory

• 만약 해당 Page Directory가 2$^1$$^4$개의 Entry를 갖는다면, 그것은 한 Page가 아닌 128개의 페이지에 걸쳐있을 것이다.
• 이 문제를 해결하기 위해 Page Directory를 여러 개로 분할하여 트리의 추가 레벨을 구축한다.

• 개별 Page Directory가 Entry Size를 제외한 Page Size가 되게끔 나눈다.
  → 2$^9$$^-$$^2$ → 2$^7$ → Directory당 7 bit

• 모든 Page Directory의 크기는 Entry Size를 제외한 Page Size와 같거나 작아야 한다.
  • 나누어 떨어지지 않는 경우는 마지막 Page Directory를 나머지 크기가 되게 한다.