Homework 5

Assigned: Mar. 3
Due: Mar. 24 [sic].

Problem 1

Consider a toy paging system. There are four frames and seven pages. In the sequence of events listed below, "Read I" means that an address in page I must be read; "Write I" means that an address in page I must be written to; "TICK" is a clock tick. (Keep in mind that the arguments to Read and Write are pages, not frames.) List the page faults that occur, and the frames chosen for the new pages, if the OS uses (A) the Not Recently Used (NRU) PRA; (B) the Second Chance PRA; (C) the aging PRA; (D) Belady's (optimal) algorithm. If the algorithm gives a tie between pages to replace, choose the one with the lower frame. Assume that memory is initially empty.

NRU

Time: Events:           Page->Frame   
   1  Write 1         Fault  1 -> 1  
   2  Read 2          Fault  2 -> 2       
   3  Write 3         Fault  3 -> 3
   4  Read 4          Fault  4 -> 4
   5  Write 5         Fault  5 -> 2
   6  TICK
   7  Read 1          
   8  Write 3         
   9  Read 6          Fault  6 -> 4
  10  Read 2          Fault  2 -> 2
  11  Read 4          Fault  4 -> 2
  12  TICK
  13  Read 1          
  14  Write 4         
  15  Read 6          
  16  Write 6
  17  Read 4          
  18  TICK
  19  Read 5          Fault  5 -> 1
  20  Write 2         Fault  2 -> 2

Second Chance

Time: Events:           Page->Frame   
   1  Write 1         Fault  1 -> 1  
   2  Read 2          Fault  2 -> 2       
   3  Write 3         Fault  3 -> 3
   4  Read 4          Fault  4 -> 4
   5  Write 5         Fault  5 -> 1
   6  TICK
   7  Read 1          Fault  1 -> 2
   8  Write 3         
   9  Read 6          Fault  6 -> 4
  10  Read  2         Fault  2 -> 1
  11  Read 4          Fault  4 -> 3
  12  TICK
  13  Read 1          
  14  Write 4         
  15  Read 6          
  16  Write 6
  17  Read 4          
  18  TICK
  19  Read 5          Fault  5 -> 4
  20  Write 2         

Aging

(Assuming that the counter is reset to 0 when the page is paged out.)
Time: Events:           Page->Frame   
   1  Write 1         Fault  1 -> 1  
   2  Read 2          Fault  2 -> 2       
   3  Write 3         Fault  3 -> 3
   4  Read 4          Fault  4 -> 4
   5  Write 5         Fault  5 -> 1
   6  TICK
   7  Read 1          Fault  1 -> 1
   8  Write 3         
   9  Read 6          Fault  6 -> 2
  10  Read 2          Fault  2 -> 4
  11  Read 4          Fault  4 -> 1
  12  TICK
  13  Read 1          Fault  1 -> 1
  14  Write 4         Fault  4 -> 2
  15  Read 6          Fault  6 -> 4
  16  Write 6
  17  Read 4          
  18  TICK
  19  Read 5          Fault  5 -> 3
  20  Write 2         Fault  2 -> 1

Belady's (Optimal) Algorithm

Time: Events:           Page->Frame   
   1  Write 1         Fault  1 -> 1  
   2  Read 2          Fault  2 -> 2       
   3  Write 3         Fault  3 -> 3
   4  Read 4          Fault  4 -> 4
   5  Write 5         Fault  5 -> 4
   6  TICK
   7  Read 1          
   8  Write 3         
   9  Read 6          Fault  6 -> 3
  10  Read  2         
  11  Read 4          Fault  4 -> 2
  12  TICK
  13  Read 1          
  14  Write 4         
  15  Read 6          
  16  Write 6
  17  Read 4          
  18  TICK
  19  Read 5          
  20  Write 2         Fault  2 -> 2