Virtual Memory : Page Replacement Algorithm

Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages. There are many different page-replacement algorithms.

A page replacement algorithm looks at the limited information about accessing the pages provided by hardware, and tries to select which pages should be replaced to minimize the total number of page misses, while balancing it with the costs of primary storage and processor time of the algorithm itself. There are many different page-replacement algorithms. Probably every operating system has its own unique replacement scheme. But in general an algorithm with lowest page-fault rate is desired. To evaluate an algorithm we run it on a particular string of memory references and compute the number of page faults. The sequence of memory references is called a Reference String. To generate reference strings artificially we can use either a random-number generator or we can manually trace a given system and recording the address of each memory reference. The later choice produces a large number of data ( on the order of 1 million addresses per second ). to reduce the number of data, we do two things.
  • First, for a given page size (which is fixed by the Hardware or system ), we need to consider only the page number, not the entire address.
  • Second, if we have a reference to a page p, then any immediately following references to page p will never cause a page fault.
  • For example, consider the following sequence of addresses − 0100, 0215, 0600, 1234, 0076, 0096, 0408, 0300, 0730, 0800, 0911, 0123, 
  • If the page size is 100 byte, this sequence is reduced to the following reference string :

        1, 2, 6, 12, 0, 0, 4, 3, 7, 8, 9, 1

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 should decrease.

1. FIFO Algorithm : It is the simplest algorithm and easy to implement. The main idea is the page brought in first is replaced first. For maintaining the order of occurrence two methods are used :

a. Associate with each page the time when that page was brought into memory.
b. Create a FIFO queue to hold all pages in memory.

We replace the oldest page or the page at the head of the queue. The new page is brought into memory as a newest page or as a new tail of the queue. For example, consider the reference string as :

1, 2, 6, 5, 0, 0, 4, 3, 1, 0, 2

With the above reference string, the below figure shows how this algorithm works :


A page is replaced if the incoming page is not in the queue. In the above figure we can see which pages are in the frames, when a a fault occurs. There are 9 faults all together.

        Fault Rate = 9/11 = 0.88


2. Optimal Algorithm : An optimal page-replacement algorithm has the lowest page-fault rate. This algorithm says that select a page for replacement for which time for the next reference is greatest. That means it will not be required for the longest period of time. For example, consider the situation with 3 frames and following reference string :

        1, 2, 6, 5, 0, 0, 4, 3, 1, 0, 2

The below figure shows how this algorithm works :


Using optimal page-replacement algorithm on the example reference sting results in 8 page faults.

        Fault Rate = 8/11 = 0.72

The advantage of the optimal page replacement algorithm is that it never suffers from Belady's anomaly. And it guarantee the lowest possible page fault rate for a fixed number of frame.

Belady's Anomaly : According to Belady, for some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases.

The disadvantage of this algorithm is that it is difficult to implement, because it requires future knowledge of the reference string. As a result, this algorithm is used mainly for comparative studies. 

3. LRU Algorithm : The main idea of LRU or Least Recently Used algorithm is to replace the page that has not been used for the longest period of time. In other words, select that page for replacement whose time since last reference is greatest. The selected page would then have the oldest time stamp. but the overhead in maintaining such a value is large enough and thus, LRU strategy is not often implemented in current system. We can implement the LRU algorithm by using a list structure that contains one entry for each occupied page frame. Whenever a page frame is referenced, the entry for that page is placed at the head of list. Older entries moved towards the tail of the list. For exmple, consider the given reference list :

        1, 2, 6, 5, 0, 0, 4, 3, 1, 0, 2


Using LRU algorithm on the example reference sting results in 8 page faults. 

        Fault Rate = 8/11 = 0.72

LRU is similar to the optimal page-replacement algorithm that is looking backword in time, rather than forward. To keep track the time of the last use for frames, Hardware assistance is required. LRU replacement algorithm also does not suffer from Belady's anomaly.

4. Counting Algorithms : In this algorithm we keep a counter of the number of references that have been made to each page. then we use one of the following two schemes :

LFU Algorithm : The Least frequently used page replacement algorithm requires that the page with the smallest count be replaced. The reason for this selection is that an actively used page should have a large reference count. 

MFU Algorithm : The most frequently used page-replacement algorithm is based on the argument that the page with the smallest count was probably just brought in and has yet to be used.




Next Topic :

No comments:

Post a Comment