/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Page replacement (basic concept and replacement algorithms)
Page replacement
While a user process is executing, a page fault occurs. The hardware traps to the
operating system, which checks its internal tables to see that this page is a genuine one
rather than an illegal memory access. The operating system determines where the desired
page is residing on the disk, but then finds that there are no free frames on the free frame
list: All memory is in use.
The operating system has several options at his point. It could terminate the user
process. However, demand paging is the operating system’s attempt to improve the
computer system’s utilization and throughput. Users’ should not be aware that their
processes are running on a paged system – paging should be logically transparent to the
user. So this option is not the best choice. The operating system could swap out a process,
but that would reduce the level of multiprogramming. So we explore page replacement.
This means that if no free frame is available on a page fault, we replace a page in
memory to load the desired page. The page-fault service routine is modified to include
page replacement. We can free a frame by writing its contents to swap space, and
changing the page table to indicate that the page is no longer in memory. The modified
page fault service routine is:
- Find the location of the desired page on the disk
- Find a free frame
- If there is a free frame use it.
- If there is no free frame, use a page replacement algorithm to select a victim frame.
- Read the desired page into the newly freed frame; change the page and frame tables.
- Restart the user process.
The following diagram shows theses steps pictorially.
We can reduce overhead by using a modify bit (or dirty bit). Each page or frame may have a modify bit associated with it in hardware. The modify bit is set by the hardware whenever any word or byte in the page is written into, indicating that the page has been modified. When we select a page for replacement we examine it’s modify bit. If the bit is set, we know that the page has been modified since it was read in from the disk. In this case we must write that page to the disk. If the modify bit is not set however, the page has not been modified since it was read into memory, and hence we can avoid writing that page to disk. In the following figure we show two processes with four pages each, main memory having eight frames, with two used for resident part of operating system (leaving six frames for user processes). Both processes have three of their pages in memory and therefore there is no free frame. When the upper process (user 1) tries to access its fourth page (page number 3), a page fault is caused and page replacement is needed.
Page Replacement Algorithms
In general we want a page replacement algorithm with the lowest page-fault rate. We
evaluate an algorithm by running it on a particular string of memory references (reference
string) and computing the number of page faults on that string.
To determine the number of page faults for a particular reference string and page
replacement algorithm, we also need to know the number of page frames available.
Obviously as the number of frames available increases, the number of page faults
decreases.
Expected relationship between number of free frames allocated to a process and the number of page faults caused by it
FIFO Page Replacement
The simplest page-replacement algorithm is a FIFO algorithm. A FIFO replacement
algorithm associates with each page the time when that page was brought into memory.
When a page must be replaced, the oldest page is chosen. Notice that it is not strictly
necessary to record the time when a page is brought in. We can create a FIFO queue to
hold all pages in memory. We replace the page at the head of the queue. When a page is
brought into memory we insert t at the tail of the queue.
Consider the following example, in which the number of frames allocated is 4, and
the reference string is 1, 2, 3, 4, 5, 1, 6, 7, 8, 7, 8, 9, 5, 4, 5, 4, 4. The number of page
faults caused by the process is nine, as shown below.
The problem with this algorithm is that it suffers from Belady’s anomaly: For some page replacement algorithms the page fault rate may increase as the number of allocated frames increases, whereas we would expect that giving more memory to a process would improve its performance.
Optimal Algorithm
An optimal page-replacement algorithm has the lowest page fault rate of all algorithms, and will never suffer from the Belay’s algorithm. This algorithm is simply to replace the page that will not be used for the longest period of time. Use of this algorithm guarantees the lowest possible page-fault rate for a fixed number of frames. In case of the following example (which uses the same replacement string as the example for the FIFO algorithm), the number of page faults caused by the process is seven.
Unfortunately this algorithm is difficult to implement because it requires future knowledge of the reference string. As a result this algorithm is used mainly for comparison.
LRU Page Replacement
If we use the recent past as an approximation of the near future, then we will replace the page that has not been used for the longest period of time. This approach is the least recently used algorithms. The following example illustrates the working of LRU algorithm.
Here is another example, which uses the same reference string as used in the examples for the FIFO and optimal replacement algorithms. The number of page faults in this case is nine.
An LRU page replacement may require substantial hardware assistance. The problem is to determine an order for the frames defined by the time of last use. Two implementations are feasible:
Counter-based Implementation of LRU
In the simplest case we associate with each page table entry a time-of-use field and add to the CPU a logical clock or counter. The clock is incremented for every memory reference. Whenever a reference to a page is made, the contents of the clock register are copied to the time-of-use field in the page entry for that page. In that way we always have the time of the last reference to each page. We replace the page that has the smallest time value. This scheme requires a search of the page table to find the LRU page and a write to memory for each memory access. The times must also be maintained when page tables are changed. Overflow of the clock must be considered.
Stack-based Implementation of LRU
Another approach to implementing the LRU algorithm is to keep a stack of page numbers. Whenever a page is referenced, it is removed from the stack and put on top. In this way, the top of the stack is always the most recently used page and the bottom is the LRU page. Because entities must be removed from the middle of the stack, it is best implementing by a doubly linked list with a head and tail pointer. Removing a page and putting it on the top of the stack then requires changing six pointers at worst. Each update is a little more expensive, but there is no search for a replacement the tail pointer points to the bottom of the stack which is the LRU page. The following diagram shows the working of stack-based implementation of the LRU algorithm.
Stack based implementation of the LRU page replacement algorithm
Google +