Information Technology Reference
In-Depth Information
6
7
89
7
8
9 0
8
9
0
6
6
8
8
7
7
9
9
8
8
10
7
7
9
9
8
7
1
0
10
9
9
(
a
)
6
7
8
9
7
8
9
10
8
9
10
6
6
6
9
9
9
9
9
9
9
9
7
7
7
7
7
7
10
10
10
10
8
8
8
8
8
8
8
8
8
(
b
)
Figure 7.13 FIFO replacement technique. (a) FIFO replacement using two page frames
(#PFs
¼
11), (b) FIFO replacement using three page frames (#PFs
¼
5)
faults was reduced to five. Since five pages are referenced, this is the optimum con-
dition. The FIFO policy results in the best (minimum) page faults when the reference
string is in strict order of increasing page number references.
Least Recently Used (LRU) Replacement
According to this technique, page
replacement is based on the pattern of usage of a given page residing in the main
memory regardless of the time spent in the main memory. The page that has not
been referenced for the longest time while residing in the main memory is selected
for replacement. The LRU technique matches most programs' characteristics and
therefore is expected to result in the best possible performance in terms of the
main memory hit ratio. It is, however, more involved compared to other techniques.
To illustrate the use of the LRU mechanism, we offer the following example.
Example
Consider the following reference string of pages made by a processor:
4, 7, 5, 7, 6, 7, 10, 4, 8, 5, 8, 6, 8, 11, 4, 9, 5, 9, 6, 9, 12, 4, 7, 5, 7. Assume that the
number of page frames allocated in the main memory is FOUR. Compute the
number of page faults generated. The trace of the main memory contents is
shown in Figure 7.14. Number of page faults
17.
In presenting the LRU, we have a particular implementation, called stack-based
LRU. In this implementation, the most recently accessed page is now represented by
¼
Figure 7.14 LRU replacement technique
Search WWH ::
Custom Search