Recent Post

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

  • 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.

No comments