Page replacement algorithms
1
OS 2009-10
When a page fault occurs
2
OS has to choose a page to evict from memory
If the page has been modified, the OS has to schedule
a disk write of the page
Th page j t read overwrites a page i memory (
The
just
d
it
in
(e.g.
4Kbytes)
Clearly it’s better not to pick a page at random
Clearly, it s
Same problem applies to memory caches
OS 2009-10
Benchmarking
3
Tests are done by generating p g references (
yg
g page
(either
from real code or random)
Sequences of page numbers (no real address, no
offset)
Example:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
OS 2009-10
Optimal page replacement
4
At the moment of page fault:
Label each page in memory is labeled with the number of
instructions that will be executed before that page is first
referenced
Replace the page with the highest number: i.e. postpone as
much as possible the next page fault
Nice optimal, but unrealizable
Nice, optimal
The OS can’t look into the future to know how long it’ll take to
reference every page again
OS 2009-10
Example: optimal
5
Sequence
PF
6 page faults
OS 2009-10
Belady’s anomaly
6
Try this sequence
With 3 page frames
With 4 page frames
With FIFO, with the optimal algorithm, (later) with the LRU
OS 2009-10
“Not recently used” algorithm
7
Use Referenced and Modified bits
R&M are in hardware, potentially changed at each
reference to memory
R&M are zero when process is started
On clock interrupt the R bit is cleared
On page fault, to decide which page to evict:
Classify:
Class 0 – R=0,M=0
Class 1 – R=0,M=1
Class 2 – R=1,M=0
Class 3 – R=1,M=1
Replace a page at random from the lowest class
OS 2009-10
FIFO replacement
8
FIFO, first in first out for pages
,
p g
Clearly not particularly optimal
It might end up removing a p g that is still
g
p
g page...