Page Replacement

Page Replacement

• When a page fault occurs, page replacement algorithms are used for loading the page in memory and no free page frame exist in memory.

• Page fault occurs if a running process references a nonresident page.

• The goal of a replacement strategy is to minimize the fault rate. To evaluate a replacement algorithm, following parameters are used:

1. The size of a page 2. A set of reference strings 3. The number of page frames. 

• Given these inputs, we can determine the number of page faults and hence the page-fault rate. A reference string is a list of pages in order of their reference by the processor.

• When we find that a page frame reference is in main memory then we have a page hit and when page fault occurs we say it is page miss. A poor choice of page replacement algorithm may result in lot of page misses.

• Page replacement algorithm deals with how the kernel decides which page reclaim. Operating systems selects the local or global page replacement policy. Local replacement policy allocates a certain number of pages to each process. If a process needs new page, it must replace one of its own pages. If the OS uses a global policy, it can take a page from any process, using global selection criteria. UNIX OS uses global page replacement policy.

First-In-First-Out

• FIFO page replacement algorithm removes the pages that have been in memory the longest. Here system keeps track of the order in which pages enter primary memory.

• When page must be replaced, the oldest page is selected. System maintain a FIFO queue of pages. Pages are inserted at the tail of the queue.

• FIFO algorithms interfere with the locality of the process.

• Consider the reference string: 1, 2, 3, 4, 2, 5, 3, 4, 2, 6, 7, 8, 7, 9, 7, 8, 2, 5, 4, 9 Page frame size = 3

Total number of page fault = 14

Page frame size = 4

Total number of page fault = 12

Belady's Anomaly

• Using FIFO algorithm for some reference strings actually generate more page faults when more page frames are allotted. This truly unexpected result was first demonstrated by Belady in 1970 and is known as Belady's anomaly.

• FIFO does not satisfy the inclusion property and is not a stack algorithm.

• A page replacement algorithm that satisfies the inclusion property is free from Belady anomaly.

• Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Page frame size = 3

Total number of page fault = 9

Page frame size = 4

Total number of page fault = 10

• Paging algorithm has worse performance when the amount of primary memory allocated to the process is increased. The problem creates because the set of pages loaded with a memory allocation of 3 is not same as the with a memory allocation of 4.

• There are a set of demand paging algorithms whereby the set of pages loaded with an allocation of m frames is always a subset of the set of pages loaded with an allocation of m + 1 frame. This property is called the inclusion property.

• FIFO does not satisfy the inclusion property and is not a stack algorithm. LRU can be a stack algorithm.

• FIFO algorithm uses only the modified and status bits when swapping is used. 

Advantage of FIFO :

1. FIFO is very simple and easy to implement.

Disadvantages of FIFO :

1. It suffers from Belady's anomaly.

2. It is not very effective.

3. System needs to keep track of each frame.

LRU Page Replacement Algorithm

• LRU stands for least recently used. This replacement policy chooses to replace the page which has not been referenced for the longest time. This policy assumes the recent past will approximate the immediate future. The operating system keeps track of when each page was referenced by recording the time of reference or by maintaining a stack of references.

• System must maintain a time stamp for every page that indicates the time of the last access. When deciding which page to remove, the operating system must scan all the pages of memory for finding the oldest time stamp. Instead of keeping an extra time stamp bits, LRU is implement by maintaining pages in an ordered list.

• System can manage LRU with a list called the LRU stack or the paging stack. In the LRU stack, the first entry describes the page referenced least recently, the last entry describes to the last page referenced. If a page is referenced, move it to the end of the list.

• LRU algorithm does not interfere with the locality of the process.

• Consider the reference string: 1, 2, 3, 4, 2, 5, 3, 4, 2, 6, 7, 8, 7, 9, 7, 8, 2, 5, 4, 9

Page frame size = 3

Total number of page fault = 16

Page frame size = 4

Total number of page fault = 13

• LRU is a stack algorithm. Increase in memory size will never cause an increase in the number of page interrupts.

Advantages:

1. It is quite good algorithm.

2. It is amenable to full statistical analysis.

3. Never suffers from Belady's anomaly.

Disadvantages:

1. Problem is how to implement.

2. It requires hardware assistance.

LRU Approximation Algorithms

• LRU is a desirable algorithm to use, but it is expensive to implement directly. It is often approximated. By using one reference bit, user can do a second-chance or clock replacement algorithm.

• Page frames are arranged in circular list. Initially each reference bit is set to 0. It is set to 1 any time the page is referenced, Algorithm uses pointer to points to the next candidate for a page replacement.

• When a page replacement is needed, the frame pointed to is considered as a candidate. If its reference bit is 0, it is selected. If its bit is 1, the bit is set to 0, and the pointer is incremented to examine the next frame. This continues until a frame is found with a reference bit of 0. This may require that all frames be examined; bringing us around to the one we started with.

Second chance replacement

• In some books, the second chance replacement policy is called the clock replacement policy. In the second chance page replacement policy, the candidate pages for removal are consider in a round robin matter and a page that has been accessed between consecutive considerations will not be replaced.

• The page replaced is the one that, considered in a round robin matter. It has not been accessed since its last consideration.

• Working:

1. Add a "second chance" bit to each memory frame.

2. Each time a memory frame is referenced, set the "second chance" bit to ONE (1) - this will give the frame a second chance.

3. A new page read into a memory frame has the second chance bit set to ZERO (0)

4. When you need to find a page for removal, look in a round robin manner in the memory frames :

i. If the second chance bit is ONE, reset its second chance bit (to ZERO) and continue.

ii. If the second chance bit is ZERO, replace the page in that memory frame.

Total number of page fault = 9

Optimal Page Replacement

• The data which will not be accessed permanently or for a longest time should be replaced in optimal page replacement algorithm.

• Optimal page replacement algorithm gives less page fault as compared to FIFO and LRU. This algorithm never suffer from Belady's anomaly.

• Use of this page-replacement algorithm guarantees the lowest possible page-fault rate for a fixed number of pages

• The key distinction between FIFO and optimal is that FIFO uses the time when a page was brought into memory whereas optimal uses the time when a page is to be used.

• It is difficult to implement because of future reference.

• Consider the reference string : 1, 2, 3, 4, 2, 5, 3, 4, 2, 6, 7, 8, 7, 9, 7, 8, 2, 5, 4, 9 

Page frame size = 3

Total number of page fault = 13

Page frame size = 4

Total number of page fault = 11

Advantages:

1. It has lowest page fault rate.

2. Optimal never suffer from Belady's anomaly.

3. Used for comparison studies.

Disadvantages:

1. Difficult to implement.

2. It requires future reference string.

Difference between FIFO, LRU and Optimal

Example 4.12.1 Consider the string 0, 1, 2, 3, 0, 1, 2, 3, 0,1, 2, 3, 4, 5, 6, 7. With frame size 3 and 4. Calculate page fault.

Solution: 1) FIFO

Page frame size = 3

* Page fault

This example incurs 16 page faults in FIFO algorithm,

FIFO algorithm with four page frames

Number of page fault is 8.

2) LRU

Number of page fault = 16.

Consider the same reference string with 4 page frames

Number of page fault = 8.

3) Optimal

Number of page fault = 10.

With page frame = 4 for same reference string.

Number of page fault = 8.

Example 4.12.2 Consider the following page reference string :

1, 2, 3, 2, 5, 6, 3, 4, 6, 3, 7, 3, 1, 5, 3, 6, 3, 4, 2, 4, 3, 4, 5, 5, 1.

Indicate page fault and calculate total number of page faults and successful ration for FIFO, Optimal and LRU algorithms. Assume there are four frames and initially all the frames are empty.

Solution: i) FIFO

Total number of page fault = 16

ii) Optimal

Total number of page fault = 11

iii) LRU

Total number of page fault = 11

Example 4.12.3 Consider the following page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

How many page faults would occur for the following replacement algorithms, assuming 1 and 3 free frames. Remember that all frames are initially empty so that first unique page request will all cost one fault each. LRU replacement, FIFO, Optimal replacement, LFU and MFU.    AU: May-19, Marks 10

Solution: Page frame = 1 then page fault for FIFO, LRU, Optimal, LFU and MFU is 20.

1. LRU (page frame = 3)

Number of page fault = 15

2. FIFO (page frame = 3)

Number of page fault = 15

3. Optimal (page frame = 3)

Number of page fault = 10

4. LFU (page frame = 3)

Number of page fault = 14

5. MFU (page frame = 3)

Number of page fault = 16

Second chance Algorithm

• Second chance algorithm is also called clock algorithm. It maintains reference bit per page.

• Goal: Remove a page that has not been referenced recently.

• Second chance algorithm is actually a FIFO replacement algorithm with a small modification that causes it to approximate LRU. It uses reference bit. When a page is selected according to a FIFO order, user checks its reference bit.

• It uses a circular buffer with as many slots as there are frames in memory. Each buffer slot contains a record rd {page number; reference bit), for a page currently in memory.

• If reference bit is set then page was referenced and this page is not removed otherwise page is removed. When a page is replaced, a pointer is set to point to the next frame in buffer.

• Second chance is looking for an old page that has not been referenced in the most recent clock interval. If all the pages have been referenced, second chance degenerates into pure FIFO.

• It requires hardware support for reference bit.

• A reference bit for each frame is set to 1 in following conditions:

1. Page is first time loads into the frame memory.

2. When page frame is referenced.

• When it is time to replace a page, the first frame encountered with the reference bit set to 0 is replaced. During the search for replacement, each reference bit set to 0.

Example:

Total number of page fault = 14

Example 4.12.4  Discuss situations in which the least frequently used (LFU) page replacement algorithm generates fewer page faults than the least recently used (LRU) page-replacement algorithm. Also discuss under what circumstances the opposite holds good.    AU May-16, Marks 8

Solution : Consider the following sequence of memory accesses in a system that can hold four pages in memory: 1 1 2 3 4 5 1. When page 5 is accessed, the least frequently used page-replacement algorithm would replace a page other than 1, and therefore would not incur a page fault when page 1 is accessed again. On the other hand, for the sequence "1 2 3 4 5 2," the least recently used algorithm performs better.

University Questions

1. When do page faults occur? Consider the reference string :

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6,

how many page faults and page fault rate occur for the FIFO, LRU and optimal replacement algorithms, assuming one, two, three, four page frames?   AU Dec.-17, Marks 13

2. Discuss situation under which the most frequently used page replacement algorithm generates fewer page faults than the least recently used page replaement algorithm. Also discuss under which circumstances the opposite holds.   AU May-18, Marks 13

3. Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Calculate the number of page faults could occur for optimal page replacement algorithm and LRU page replacement algorithm.    AU May-22, Marks 13