Operating systems

Page fault

Prashanth L.A.

2023-09-25

Lecture 23 (contd)

So far

Paging

 

What happens if pages, or even the page tables don’t fit in memory?

Require an additional level in the memory hierarchy

The crux

How can the OS make use of a larger, slower device to transparently provide the illusion of a large virtual address space?

Swap Space

Page table entry

What If Memory Is Full ?

New Control Flow

Try to fetch instruction@VA

  1. extract VPN
  2. Check TLB for VPN
    1. TLB hit
      • get PFN+offset \(\Rightarrow\) Fetch PA
    2. TLB miss: calculate PTE address \(PA_{PTE}\)
      • Fetch \(PA_{PTE}\)
        1. if present and accessible, get PFN, insert in TLB and retry
        2. else raise PAGE FAULT exception

New Control Flow (again)

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

TLB hit

(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)
  if (CanAccess(TlbEntry.ProtectBits) == True)
    Offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
    Register = AccessMemory(PhysAddr)
else
    RaiseException(PROTECTION_FAULT)

TLB miss

else
  PTEAddr = PTBR + (VPN * sizeof(PTE))
  PTE = AccessMemory(PTEAddr)
  if (PTE.Valid == False)
      RaiseException(SEGMENTATION_FAULT)
  else
    if (CanAccess(PTE.ProtectBits) == False)
      RaiseException(PROTECTION_FAULT)
    else if (PTE.Present == True)
      // assuming hardware-managed TLB
      TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) RetryInstruction()
    else if (PTE.Present == False)
      RaiseException(PAGE_FAULT)

Page Fault Control Flow – Software

PFN = FindFreePhysicalPage() // no free page found
if (PFN == -1) // run replacement algorithm
  PFN = EvictPage()
DiskRead(PTE.DiskAddr, pfn) // sleep (waiting for I/O)
PTE.present = True // update page table with present
PTE.PFN = PFN // bit and translation (PFN)
RetryInstruction()

When to replace

Option 1: Wait until memory is entirely full

Option 2: Let Daemons free things up

Lecture 24

Replacement policy

Example

0x000, 0x100, 0x200, 0x300, 0x400, 0x500, 0x600, 0x700, 0x800, 0x900

Optimal Replacement Policy

Example with cache size 3

Access stream: \(0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1\)

Access Hit/Miss? Evict Resulting Cache State
0 Miss 0
1 Miss 0,1
2 Miss 0,1,2
0 Hit 0,1,2
1 Hit 0,1,2
3 Miss 2 0,1,3
0 Hit 0,1,3
3 Hit 0,1,3
1 Hit 0,1,3
2 Miss 3 0,1,2
1 Hit 0,1,2

Hit rate\(=\frac{6}{6+5}=0.545\)

Policy 1: FIFO

Example

Access Hit/Miss? Evict Resulting Cache State
0 Miss 0
1 Miss 0,1
2 Miss 0,1,2
0 Hit 0,1,2
1 Hit 0,1,2
3 Miss 0 1,2,3
0 Miss 1 2,3,0
3 Hit 2,3,0
1 Miss 3,0,1
2 Miss 3 0,1,2
1 Hit 0,1,2

Hit rate\(=\frac{4}{4+7}=0.364\)

Belady’s anomaly

How does the cache hit rate change when moving from a cache size of 3 to 4 pages?

With FIFO, it may increase

Try the memory stream: \(1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5\)

Policy 2: Random

Sample run

Access Hit/Miss? Evict Resulting Cache State
0 Miss 0
1 Miss 0,1
2 Miss 0,1,2
0 Hit 0,1,2
1 Hit 0,1,2
3 Miss 0 1,2,3
0 Miss 1 2,3,0
3 Hit 2,3,0
1 Miss 3 2,0,1
2 Hit 2,0,1
1 Hit 2,0,1

Hit rate\(=\frac{5}{5+6}=0.454\)

Using History

Historical Information Meaning Algorithms
recency If a page has been accessed recently, it should not be replaced LRU
frequency If a page has been accessed many times, it should not be replaced LFU

LRU example

Access Hit/Miss? Evict Resulting Cache State
0 Miss 0
1 Miss 0,1
2 Miss 0,1,2
0 Hit 1,2,0
1 Hit 2,0,1
3 Miss 2 0,1,3
0 Hit 1,3,0
3 Hit 1,0,3
1 Hit 0,3,1
2 Miss 0 3,1,2
1 Hit 3,2,1

Hit rate\(=\frac{6}{6+5}=0.545\)

Other algos

Lecture 25

Workload 1: No-Locality

No-locality workload Remarks