Virtual Memory Page Replacement Example
Dynamically as they run, processes in the computer issue access
requests for certain virtual memory pages in a certain sequence. Imagine a
system with 7 virtual pages and only 3 page frames in physical memory to house
them. Imagine that the page-access request sequence happens to be for the
following virtual pages in the following order: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2.
|
Virtual
Page #
|
Logical
Address space
|
Page
Frame #
|
|
1
|
4-8 k
|
|
|
2
|
8-12 k
|
|
|
3
|
12-16 k
|
|
|
4
|
16-20 k
|
|
|
5
|
20-24k
|
|
|
|
Page
Frame #
|
Physical
Memory Address
|
|
1
|
4-8 k
|
|
2
|
8-12 k
|
|
3
|
12-16 k
|
|
Below, we load the specified virtual pages into the 3 page frames as they are
requested, in their request sequence. Whenever loading the requested page
requires displacing an already-loaded one, we consider it a "Fault"
and mark it as such below. In that event, we must select a to-be-displaced
"victim" from among the already-loaded 3 virtual pages. There are
different methods for doing that. Once we select the victim, we would write a
copy of it to the swap space or virtual memory file on disk (for retrieval when
again next requested) before overwriting the victim's page frame with the
content of the new virtual page, thus giving the frame to that page for a while.
One method of "victim selection" is the least-recently-used
algorithm. There, we examine the sequence of recent requests (along the top of
the diagrams below) because it represents usage occurrences. In it we look for
the page numbers of the 3 virtual pages currently in memory. So we select the
particular page which appears earliest in the sequence. Another method is
first-in-first-out. There, we examine the sequence of recent page-frame
occupancy patterns (the sets of triple-boxes). Of the 3 currently loaded virtual
pages we look for the one whose continuous "tenancy" stretches back
the farthest.
Below, the outcomes for each method are shown. Further below, the process is
repeated as it would unfold if the number of page frames were 4 instead of 3. In
both cases, the fact that fewer faults arise when using LRU than when using FIFO
suggests that LRU is a more efficient algorithm.
THREE Page Frames
Least-recently-used (LRU) method:
First-in-First-out (FIFO) method:
FOUR Page Frames
Least-recently-used (LRU) method:
First-in-First-out (FIFO) method: