Hardware Reference
In-Depth Information
program gets to page 7, the main memory will be as shown in Fig. 6-6(a). An at-
tempt is eventually made to fetch an instruction from virtual page 8, which causes
a page fault. A decision has to be made about which page to evict. The LRU algo-
rithm will choose virtual page 0, because it has been used least recently. Virtual
page 0 is removed and virtual page 8 is brought in to replace it, giving the situation
in Fig. 6-6(b).
Virtual page 7
Virtual page 6
Virtual page 5
Virtual page 4
Virtual page 3
Virtual page 2
Virtual page 1
Virtual page 0
Virtual page 7
Virtual page 6
Virtual page 5
Virtual page 4
Virtual page 3
Virtual page 2
Virtual page 1
Virtual page 8
Virtual page 7
Virtual page 6
Virtual page 5
Virtual page 4
Virtual page 3
Virtual page 2
Virtual page 0
Virtual page 8
(a)
(b)
(c)
Figure 6-6.
Failure of the LRU algorithm.
After executing the instructions on virtual page 8, the program branches back
to the top of the loop, to virtual page 0. This step causes another page fault. Virtu-
al page 0, which was just thrown out, has to be brought back in. The LRU algo-
rithm chooses page 1 to be thrown out, producing the situation in Fig. 6-6(c). The
program continues on page 0 for a little while. Then it tries to fetch an instruction
from virtual page 1, causing a page fault. Page 1 has to be brought back in again
and page 2 will be thrown out.
It should be apparent by now that here the LRU algorithm is consistently mak-
ing the worst choice every time (other algorithms also fail under similar condi-
tions). If, however, the available main memory exceeds the size of the working set,
LRU tends to minimize the number of page faults.
Another page-replacement algorithm is
FIFO
(
First-In First-Out
). FIFO re-
moves the least recently loaded page, independent of when this page was last refer-
enced. Associated with each page frame is a counter. Initially, all the counters are
set to 0. After each page fault has been handled, the counter for each page pres-
ently in memory is increased by one, and the counter for the page just brought in is
set to 0. When it becomes necessary to choose a page to remove, the page whose
counter is highest is chosen. Since its counter is the highest, it has witnessed the
largest number of page faults. This means that it was loaded prior to the loading of
any of the other pages in memory and therefore (hopefully) has a large a priori
chance of no longer being needed.
If the working set is larger than the number of available page frames, no algo-
rithm that is not an oracle will give good results, and page faults will be frequent.
