# Page Replacement Algorithms

## Basic Page Replacement Algorithms

### Optimal Algorithm

• Select that page for replacement which is going to be replaced the last i.e the page whose time to replacement is the longest.
• This approach results in fewest page faults.
• However, this approach is not feasible, as we can never really know which page has the longest time to replacement.
• This algorithm is just theory, it is not implementable.

### Least Recently Used (LRU)

• Select that page for replacement which has not been used for the longest time.
• The approach relies on an assumption that the page which has not been used for the longest time is the least likely page to be used in future.
• It has reasonably good performance in terms of limiting swapping.
• Calculating page which has been used least recently used creates an overhead.

### First In First Out (FIFO)

• Implement a queue and replace pages accordingly.
• Page which comes in first is the first one to be replaced.
• I.e replace the page which has been in main memory the longest.
• The algorithm is easy to implement.
• But it may swap out pages that are used a lot!

### Clock Policy Algorithm

• This Algorithm behaves similar to LRU. Associate 'Use Bit' with each frame. When frame first loaded in main memory, use bit for that frame set to 1.
• When page is subsequently referenced, use bit set to 1. Set of pages that are candidates for page replacement form a circular buffer with pointer.
• Pointer movies along circle when a page is needed for replacement. While moving, any page with use bit 1 , its use bit is set to 0. The first page with use bit 0 is picked for replacement.
• Its behaviour is similar to FIFO apart from the fact that it skips pages whose use bit is set to 1.

## Advanced Page Replacement Algorithms

### Working Set Strategy

• W(T,D) = Set of Pages that have been referenced in the last D virtual time units.
Virtual Time Units is generally number of instructions.
• Working Set is non decreasing function of Window Size(D). i.e W(T,D+1) contains W(T,D)
• Working Set of each process is monitored.The pages of the process which are no longer in the working set are periodically removed from the resident set.
• Process can be executed only if its working set is in main memory

• Size and membership of working set change over time.
• Need to timestamp every page reference and keep a time ordered queue.
• Optimal value of D is unknown and would vary.

### Page Fault Frequency

• Algorithm uses use bit. Use bit is set to 1 when page is accessed.
• Set a threshold time 'F' for measuring page fault rate. When page fault occurs, OS notes virtual time units since last page fault.
• If time < F, ad page to resident set of process.
If >=F , discard all pages with use bit 0 and shorten size of resident set.
• Time between page faults is 1/(page fault rate)
• No page drops out of resident set before F virtual time units.
• Does not perform well during locality shifts.

### Variable-Interval Sampled Working Set (VSWS)

• Evaluates working set of a process at sampling instances based on elapsed virtual time.
• Use bits of all resident pages are reset at the beginning of a sampling interval. At the end of the interval, only the pages referenced during the interval will have their use bit set to 1.
• The pages with use bit set to 1 are retained at the end of the interval while other pages are discarded. That means, at the end of the interval, resident set can only decrease.
• However, faulted pages are added to the resident set during the interval.

Quiz
1. Theoretically the best page replacement algorithm is
1. Optimal algorithm
2. Least Recently Used(LRU)
3. First In First Out(FIFO)
4. Clock Policy Algorithm
2. Clock Algorithm outperforms FIFO algorithm in cases where
1. All pages are equally likely to be referenced
2. Certain pages are referenced more often than the others
3. Some pages are never referenced
4. None of the above
3. We can find the page having the longest time to replace by using
1. Optimal Algorithm
2. Working Set Strategy Algorithm
3. It is not possible to find the time to replacement for a page
4. None of the above