Page replacement

Type the string of pages a process asks for, choose how many frames it has and the algorithm, and watch how the operating system decides who to evict: the frame trace fills in reference by reference, with every page fault, every hit and the reason behind every victim. Faults, the fault rate and the comparison of FIFO, LRU and optimal are worked out for you. It runs in your browser, on your phone too.

How to use it

  1. Type the string in refs.txt: pages 0 to 9 separated by spaces or commas (up to 30). Start with the gcc one, the same as in the theory article.
  2. Choose FIFO, LRU or Optimal and the number of frames (1 to 7). The terminal command changes with your choice.
  3. Press Step to move from reference to reference, or Run to watch it all. At each step you see what is in memory, the queue, the last use or the next use of each page, depending on the algorithm, and why the victim goes.
  4. Below are the results and the comparison: the three algorithms with the same string and a chart with the faults from 1 to 7 frames. Belady loads the anomaly string and Share copies a link with your string.

How to read the trace

Each column is one reference in the string (at the top, the instant t and the requested page) and each row is a frame. In coral, the page that has just come in because of a page fault; in green, the requested page that was already there (a hit). The fault row marks the faulting columns with an F and the out row shows the victim. It is the same table you are asked for in the exam.

The maths: fault rate = faults ÷ references and hit rate = hits ÷ references. Compulsory faults are the first time each page is requested: no algorithm can avoid them, so anything above that is the algorithm’s fault.

The rules it follows

  • Frames fill from top to bottom and the new page takes its victim’s frame.
  • FIFO evicts the page that came in first; LRU, the one unused the longest (a hit refreshes its last use).
  • The optimal algorithm evicts the page that will be requested again the latest. If several never come back, the first one in frame order goes, as in the theory article.
  • Frame numbers (5, 9, 2…) are the ones from the theory article: which ones they are does not matter, only how many.

Which algorithm wins

With the gcc string and 3 frames you get 11 faults with FIFO (a 73.3 % fault rate), 9 with LRU (60 %) and 7 with the optimal algorithm (46.7 %); 6 of them are compulsory. The optimal algorithm is impossible in a real operating system because it needs to know the future, but it is the yardstick: LRU gets fairly close by looking only at the past. And FIFO has a catch: with the string 3, 1, 4, 2, 3, 1, 5, 3, 1, 4, 2, 5 it gives 9 faults with 3 frames and 10 with 4. That is Belady’s anomaly: more frames, more faults. Press Belady and look at the chart.