Page Replacement in Operating System

When Replacement Algorithms

• If new page is brought in, need to chose a page to evict.
• Don't want to evict heavily used pages
• If page has been written to, need to copy it to disk
• Otherwise, a good copy is on the disk => can write over it

Similar problem in other parts of computer science

• One or more cache (32 or 64 memory Blocks) of recently used memory blocks
• Web server: keeps heavily used web pages in the memory; when cache is full; evicts a page
• Which page to evict?

               - The probability of evicted page to be referenced in near future should be minimum.

• Page replacement form same process or some other  process?

→ Optimal page replacement algorithm
→ Not recently used page replacement
→ First-in, first-out page replacement
→ Second chance page replacement
→ Clock page replacement
→ Least recently used page replacement
→ Working set page replacement
→ WS-Clock page replacement

Optimal Page Replacement :-

• Pick the one which will not used before the longest time (8 million vs 6 million instructions ?)
• Not possible unless know when pages will be referenced (run program on simulator, valid for one program and same data?)
• Used as ideal reference algorithm, but unrealizable!

Not recently used (NRU)

• Use R and M status bits must be updated on every memory reference.
• To be implemented in hardware
• If not in h/w simulate in OS with page fault?
• OS Periodically clear R bit to distinguish between page in use or not in use.

            - Class 0: not referenced, not modified
            - Class 1: not referenced, modified
            - Class 2: referenced, not modified
            - Class 3: referenced, modified

• Pick lowest numbered non empty class page to evict

First In First Out (FIFO)

• OS maintains a list of all the pages in the memory.
• Keep list ordered by time (latest to arrive at the end of the list)
• On page fault, evict the oldest, i.e. head of the line
• Easy to implement
• Oldest might be most heavily used! No knowledge of use is included in FIFO

Second Chance Algorithm :-

• Pages sorted in FIFO order by arrival time.
• Examine R bit of oldest page. If zero, evict. If one, put page at end of list and R is set to zero, update load time.
• If change value of R bit frequently, might still evict a heavily used page.

The Clock Page Replacement Algorithm

Clock

• Doesn't use age as a reason to evict page
• Faster-doesn't manipulate a list
• Doesn't distinguish between how long pages have not been referenced.

Least Recently Used (LRU)

• Page that have been used recently again. Converse is also true
• Page Fault; remove the page unused for longest time.Strategy called LRU.
• First Implementation; Maintain a linked list, whenever a page is referenced remove the page and insert it at the front, LRU page will be at the rear.
• Problem; very expensive to implement in h/w as well as in s/w.
• Could associate counters with each page and examine them but this is expensive.