11-12-2012, 02:08 PM
Paging Algorithms and Implementation Issues
Paging Algorithms.pdf (Size: 617.55 KB / Downloads: 110)
Page replacement algorithms
Page fault forces a choice
No room for new page (steady state)
Which page must be removed to make room for an
incoming page?
How is a page removed from physical memory?
If the page is unmodified, simply overwrite it: a copy
already exists on disk
If the page has been modified, it must be written back to
disk: prefer unmodified pages?
Better not to choose an often used page
It’ll probably need to be brought back in soon
Optimal page replacement algorithm
What’s the best we can possibly do?
Assume perfect knowledge of the future
Not realizable in practice (usually)
Useful for comparison: if another algorithm is within 5%
of optimal, not much more can be done…
Algorithm: replace the page that will be used furthest
in the future
Only works if we know the whole sequence!
Can be approximated by running the program twice
Once to generate the reference trace
Once (or more) to apply the optimal algorithm
Nice, but not achievable in real systems!
Not-recently-used (NRU) algorithm
Each page has reference bit and dirty bit
Bits are set when page is referenced and/or modified
Pages are classified into four classes
0: not referenced, not dirty
1: not referenced, dirty
2: referenced, not dirty
3: referenced, dirty
Clear reference bit for all pages periodically
Can’t clear dirty bit: needed to indicate which pages need to be flushed to disk
Class 1 contains dirty pages where reference bit has been cleared
Algorithm: remove a page from the lowest non-empty class
Select a page at random from that class
Easy to understand and implement
Performance adequate (though not optimal
Clock algorithm
Same functionality as
second chance
Simpler implementation
“Clock” hand points to next
page to replace
If R=0, replace page
If R=1, set R=0 and advance
the clock hand
Continue until page with
R=0 is found
This may involve going all
the way around the clock…