VIRTUAL MEMORY

Background

Demand Paging

Valid-Invalid bit

Page Fault

  1. If there is ever a reference to a page, first reference will trap to OS -> page fault.
  2. OS looks at another table to decide:


  3. a) Invalid reference => abort.
    b) Just not in memory.
  4. Get empty frame.
  5. Swap page into frame.
  6. Reset tables, validation bit = 1.
  7. Restart instruction:

What happens if there is no free frame?

Performance of Demand Paging

Page Replacement

Page-Replacement Algorithms

First-In-First-Out (FIFO) Algorithm

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO Replacement - Belady's Anomaly

Optimal Algorithm

Least Recently Used (LRU) Algorithm

LRU Approximation Algorithms

Allocation of Frames

Global versus local allocation

Thrashing

Working-Set Model

How do you keep track of the working set?

Page-Fault Frequency Scheme

Other Consideration

  1. Prepaging
  2. Page size selection


  3. - fragmentation
    - table size
    - I/O overhead
    - locality
  4. Program structure


  5. - Array A[1024,1024] of integer
    - Each row is stored in one page
    - One frame -
    - Program 1
     for j := 1 to 1024 do 
        for i := 1 to 1024 do 
          A[i,j] := 0; 
      1024 * 1024 page faults
    - Program 2
     for i := 1 to 1024 do 
        for j := 1 to 1024 do 
          A[i,j] := 0; 
    1024 page faults
  6. I/O interlock and addressing

Demand Segmentation - used when insufficient hardware to implement demand paging.