Paging

Description:

• Virtual/physical address space is divided into equal sized pages:
  • A page contains $N$ bytes where $N$ is a power of 2, $N=4096$(4 KB) is a typical size
  • A whole page is read or written during data transfer between RAM and disk
  • Each page in virtual memory space has a unique index called Virtual Page Number (VPN)
  • Similarly, each page in physical memory space has a unique [Physical Page Number ]
• When requested, a page is copied from secondary storage into a physical RAM location
• Each process/app theoretically have 1 page table
• The correspondence (mapping) between virtual to physical addresses is saved
  • When the same virtual address is encountered, it is translated using this saved mapping information
• Registers:
  • Page-table base register (PTBR) points to the page table
  • Page-table length register (PTLR) indicates the size of the page table

Address Translation:

• 
• Page table register: tells the OS where in the memory the table is stored
• Page Table Entry (PTEs): 1 entry of the table, has valid bit and the Physical Page Number
• When querying: the Virtual Page Number nb is used to find which entry to get the PPN from and only get it if its valid
  • then the PPN + page offset is the byte of physical address needed
• If read fail, invalid or not exist, then read the page is copied from the secondary storage to memory

Page Table requires overhead:

• ex: each process is 4gb (2^32) with page size 4kb (2^12)
• therefore
  • 32-12: nb of pages for 1 process, 2^20 entries
  • each entry store PPN for , example, 4 bytes, then page size of 1 process is 4*2^20=4mb
  • with 10 process, requires 40mb RAM for pages

Page Fault:

• Miss penalty on a page fault is significant: Up to ~100M cycles
• Low miss (page fault) rates are essential
  • Fully associative page placement (put anywhere in MM)
  • LRU replacement of a page when MM is full
• The Operating System handles page placement
• Write policy:
  • Too expensive to do true LRU (100K-1M pages); Use LRU approximation
  • Each PTE has a Reference bit (ref)
  • Reference bit is set when a page is accessed
  • OS periodically clears all Reference bits
  • OS chooses a page with a Reference bit of 0
  • Write back policy is used (instead of write through)
    • Dirty bit in PTE is set on a write to main memory
    • Page with set Dirty bit is written to disk if replaced

Effective Time Acces (ETA)

• Hit ratio 𝛂 – percentage of times that a page number is found in the TLB
  • 80% means the desired page number is found in TLB 80% of the time.
• Seeking time on TLB is 𝜖 (unit of time) and memory access speed is n (unit of time)
• Effective Access Time (EAT) = 𝛂 (n + 𝜖) + (1-𝛂)(2n + 𝜖) = 2n + 𝜖 - 𝛂n
• Examples:
  • 𝛂 = 80%, 𝜖 ~ 0 (ns), n = 10 (ns) ⇒ EAT = 12 (ns). (20% slowdown)
  • 𝛂 = 99%, 𝜖 ~ 0 (ns), n = 10 (ns) ⇒ EAT = 10.1 (ns). (1% slowdown)

Implementation of Page Table

• Issue: too many pages to search for

1. Hierarhcical PT: break up the logical address space into multiple page tables, n-level page table
   • Increased Access Time: Accessing a page may require multiple memory accesses (one for each level of the page table).
2. Hashed PT: The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location
   • Complex hashing logic and complex to handle collision
3. Inverted PT: Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages
   • This is used
   • Slower Lookup Times, unless search in parallel