Page Replacement Algorithms

I.S.L SARWANI,

Asst prof, IT,

ANITS

Basic Page Replacement

• 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) free frame. Update the page and frame tables.
• Restart the process

Page Replacement

Page Replacement Algorithms

• Want lowest page-fault rate
• Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
• In all our examples, the reference string is

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO Page Replacement Algorithm

• Maintain a linked list of all pages
• in order they came into memory
• ​
• Page at beginning of list replaced

​

• Disadvantage
• page in memory the longest may be often used

FIFO Page Replacement

First-In-First-Out (FIFO) Algorithm

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 3 frames (3 pages can be in memory at a time per process)

​

​

​

​

​

​

• 4 frames����

��FIFO Replacement – Belady’s Anomaly

• more frames  more page faults

1

2

3

1

2

3

4

1

2

5

3

4

9 page faults

1

2

3

1

2

3

5

1

2

4

5

10 page faults

4

4

3

Belady’s algorithm

• Belady's anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.
• FIFO page replacement algorithm produced near twice more page faults in a larger memory than in a smaller one.

Optimal Page Replacement Algorithm

• Replace page needed at the farthest point in future
• Optimal but unrealizable
• ​
• Estimate by …
• logging page use on previous runs of process
• although this is impractical

Optimal Page Replacement

How do you know this?

Used for measuring how well your algorithm performs

​

LRU Page Replacement

Least Recently Used (LRU)

• Assume pages used recently will used again soon
• throw out page that has been unused for longest time
• ​
• Must keep a linked list of pages
• most recently used at front, least at rear
• update this list every memory reference !!
• ​
• Alternatively keep counter in each page table entry
• choose page with lowest value counter
• periodically zero the counter
• ​

LRU Algorithm (Cont.)

• Counter implementation
• Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter
• When a page needs to be changed, look at the counters to determine which are to change

​

• Stack implementation – keep a stack of page numbers in a double link form:
• Page referenced:
• move it to the top
• requires 6 pointers to be changed
• No search for replacement

Contd..

• Stack algorithm: The set of pages in memory for n frames is always a subset of pages in memory with n+1 frames.
• These algorithms never exhibit Belady’s anomaly.
• Updating must be done for every memory reference.

​

Second Chance Page Replacement Algorithm

• Operation of a second chance
• pages sorted in FIFO order
• Page list if fault occurs at time 20, A has R bit set�(numbers above pages are loading times)

The Clock Page Replacement Algorithm

Global vs. Local Allocation

• Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another
• Local replacement – each process selects from only its own set of allocated frames

Thrashing

• If a process does not have “enough” pages, the page-fault rate is very high. This leads to:
• low CPU utilization
• operating system thinks that it needs to increase the degree of multiprogramming
• another process added to the system
• Thrashing  a process is busy swapping pages in and out