[OS] Paging and Page Tables

Paging

• process의 virtual address space를 일정 크기 page로 쪼갠다. 그리고 physical memory를 page와 같은 크기로 즉, frame으로 쪼갠다. 각각의 page를 physical frame으로 mapping한다.
  
• internal fragmentation이 발생할 수 있다. frame size가 클수록 발생할 가능성이 크다.

Page Tables

• 자신의 virtual address space가 physical memory로 page table을 통해 mapping 되어 있다.
• process들은 자신의 고유한 page table이 있다. Page-table base register(PTBR)난 page table의 base address를 가리킨다. thread들은 address space를 공유하므로 page table을 공유한다.
• page table은 page table entry(PTE)로 구성되어 있고 각각의 PTE는 해당하는 entry가 커버하는 virtual address나 physical memory의 상태를 기록하는 형태로 구성되어 있다.
• Managed by OS, accessed by MMU
• VPN(Virtual Page Number), PPN(Physical Page Number)=PFN(Physical Frame Number)
  
  • Address Translation
    

PTE

Page Table Structure

1. Linear Page Table
   

2. Hierarchical Page Tables

   • forward-mapped page table : 전체 page table을 작은 page 크기로 쪼갠 다음 그 중에서 자신이 사용하고 있는 부분만 mapping하여 사용하고 그렇지 않은 부분은 비워둔다.
   • 1개의 VPN을 translate하기 위해 각 level 당 1번의 memory access가 필요하다.
   • page table을 조각조각 쪼갠다음 각각에 대해서 사용하고 있는 부분을 summary한 부분을 page table에 놓고 안 쓰는 부분은 page table에 넣지 않는다.
     
   • Example
     
   • 장점 : no external fragmentation
   • 단점 :

3. Hashed Page Table

   • VPN을 hash function로 돌린 후 PFN으로 바꾼다.
     

4. Inverted Page Tables

   • PFN에서 어떤 process의 VPN으로 mapping 되는지 역방향으로 하는 방식

Translation Look-aside Buffer(TLB)

• Hardware로 구현되어 있어 address translation을 가속시킨다. 최근에 찾았던 거 적어놓는다. MMU에 구현되어 있다.
• TLB entries : <page #, frame #>
  
• VA to PA 할 때 TLB에서 먼저 찾아보고 없으면 page table 전체 다 찾아본다.
• Context switch를 통해 process가 바뀌면 TLB는 flushed되어야 한다. 그렇지 않으면 잘못된 mapping이 있을 것이다.
• TLB에 address-space identifiers(ASIDs)를 붙여서 context switch할 때 TLB를 flush하지 않아도 되는 경우가 있다.