Page Replacement: The Problem

The modify bit earns its keep

The hardware sets the modify bit, also called the dirty bit, when a page is written to. The replacement code reads it.

So an algorithm that can choose between two equally good victims should choose the clean one, and a page of read-only code is always clean, which makes program text the cheapest thing in memory to throw away: it can always be read again from the program file.

What makes one algorithm better than another

The lowest page fault rate on the same reference string with the same number of frames. Nothing else, and in particular not how clever it sounds.

A reference string is page numbers, not addresses. The offset inside the page makes no difference to whether the page is in memory, so the addresses 0, 100 and 4000 with a 4096 byte page are all page 0 and are one reference for this purpose.

And a repeat costs nothing: two references in a row to the same page can cause at most one fault, so a string 1 1 1 2 behaves exactly like 1 2. That is worth knowing in the hall, because it shortens a long string before the work starts.

More frames, fewer faults

The relationship every question assumes, computed here on the reference string this book uses throughout the next four chapters:

Faults: frames 1 to 7

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Twenty references over six distinct pages. The faults, counted by sim/pagerepl.py:

Three things to take from that table, and each is a question in itself.

One: with one frame every reference faults. Twenty references, twenty faults, because no page survives to the next reference.

Two: with six frames all three algorithms give six faults, which is the number of distinct pages. Once there are as many frames as the program has pages, the algorithm stops mattering: every page is brought in once and never thrown out. That is why a question always gives a frame count smaller than the number of distinct pages.

Three: more frames is not a guarantee. FIFO gives 15 faults at two frames and 15 again at three: the extra frame bought nothing at all on this string. Chapter eighty five shows a string where an extra frame makes FIFO worse, which is Belady's anomaly, and it is found by search rather than asserted.

The five algorithms this module needs

Every one of them is the same three steps, and only the choice of victim changes.

Distinctions that carry marks

What it does not mean

Replacement is not swapping. One page moves, not a process.

The victim need not belong to the faulting process. Whether it may belong to another one is the global against local question of Chapter ninety.

A page fault is not the algorithm's fault. The algorithm decides only which page leaves, and therefore how many faults happen later.

More frames does not always mean fewer faults. It usually does, and FIFO can break the rule.

The reference string is not the addresses. It is the page numbers, and repeats next to each other collapse.

Quick revision

• Demand paging over allocates memory on purpose; when every frame is taken and a page is

needed, something must give.

• Of the three options, terminating the process is unacceptable, swapping a whole process out is

crude, and page replacement frees one frame.

• The service routine: find the page on disk, look for a free frame, else choose a victim,

write it out if dirty, invalidate it in its page table and in the TLB, read the page in, restart the instruction.

• A dirty victim costs two transfers and a clean one costs a single read; program

text is always clean.

• An algorithm is judged by the

page fault rate on the same reference string with the same number of frames.

• A reference string is page numbers, and consecutive repeats of a page cause at most one

fault.

• On the standard string of twenty references over six pages: one frame gives 20 faults

for every algorithm; six frames give 6 for every algorithm; three frames give 15 for FIFO, 12 for LRU and 9 for optimal.

• FIFO gives 15 faults at both two and three frames, and Chapter eighty five shows it getting

worse with more frames.

Test yourself

1. How can the operating system run out of frames if it is managing memory properly? Because

demand paging lets it promise more memory than exists, which is safe while no process needs all its pages, and stops being safe when several processes need more at the same moment.

1. Why is terminating a process not an acceptable answer? Paging is meant to be invisible to

the program; a program that dies because other programs are busy is not.

1. Give the steps of servicing a fault when no frame is free. Find the page on disk; find no

free frame; choose a victim by the replacement algorithm; write the victim out if it is dirty; mark it invalid in its page table and remove it from the TLB; read the wanted page in; set the entry valid; restart the instruction.

1. Why does the modify bit matter, and by how much? A clean victim needs one transfer and a

dirty one needs two, so the bit can halve the cost of a fault; Chapter eighty two's sum put the difference at 81 against 137 times slower.

1. What is forgotten at step 6, and why is it serious? Removing the victim from the TLB. A

stale entry lets its former owner reach a frame that now belongs to somebody else.

1. On what basis is a replacement algorithm judged? The page fault rate it gives on the same

reference string with the same number of frames. 7. The addresses 0, 100 and 4000 are touched in turn, with a 4096 byte page. How long is the reference string? One reference: all three addresses are in page 0.

1. With six frames and six distinct pages, which algorithm is best? None of them: every page

is loaded once and never replaced, so all give six faults. The algorithm matters only when the frames are fewer than the pages in use.