Part 2 of 7 · 2 min read
Page replacement
Think of it this way. A desk holds three books. A fourth book is needed, so one of the three goes back to the shelf. The choice matters: if the book put away is needed again in a minute, the trip to the shelf is wasted. The analogy stops in one place: a person can guess from the work in hand, while the kernel can only look at the past.
In plain words: In a computer, step 3 of the fault steps on page 7 ("find a free frame") has a hard case: no frame is free. The kernel then picks a victim, a page in memory that will be removed. It writes the victim out if it has been changed (section 5), marks its page table entry as absent, and reuses the frame for the page that faulted.
The tests of an algorithm use a reference string, a list of the page numbers that a program touches, in order. The goal is the fewest faults over the string. The string used on this page is called S, and the made-up values are chosen to show the differences:
S = 5 2 4 5 6 4 6 5 3 6 4 6 1 1 2 3 6 2 (18 references, 6 different pages)
A fault happens when the page asked for is not in a frame. With 3 frames, the first three different pages fault on any rule, because the frames start empty. These are sometimes called cold faults.
Page replacement
Page replacement is the choice, made when the kernel needs a frame and every frame is in use, of a victim page to remove from memory so that its frame can hold the page that has just been asked for.
Example: with three full frames holding pages 5, 2 and 4, a fault on page 6 forces the kernel to remove one of the three.
Check yourself: 1. What is a victim? 2. How many faults does any rule cause on the first three different pages with 3 frames? 3. What is the aim of a replacement rule?