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
Disadvantages
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)
Disadvantages
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.
