Page Replacement

Belady's Proof (Oracle solution: ideal): Evicting the page that will not be used for the longest period of time minimizes the number of page faults

Counting Algorithms

LFU(Least frequently used) but do not reflect time variable *recent used victim

MFU(Most Frequently Used) consider recent used

Timing algorithms

FIFO Simple: single pointer suffices Belady's Anomaly: more frame do not improve fifo algorithm performance

LRU (Least recently used) by counters or stack

but lru is complicate

LRU Approximation (real use)

Sampled LRU (hardware support) reference bit - can be cleared when full

Second-Chance Algorithm LRU clock(Secondd chance) - clock bit clock hand - PTE reference - often use modified bit(dirty bit) either

Evaluate algorithm usually by running it on a particular string of memory references (reference string) and computing the number of page faults on that string

Evict picked victim page

Page fault service time – Service the page-fault interrupt + Read in the page + Restart the process

Allocation of Frames

each process need minimum number of pages - Must provide enough frames to hold all the different pages that any single instruction can reference

local replacement - can not steal other process's frame - Fixed(Equal) allocation - each algorithm to process

global replacement - can steal other process's frame - Priority allocation

Proportional allocation : related to process size set frame number Priority allocation : set process priority

Page replacement Examples

windows NT demand paging with clustering(gist) process has working-set min, working-set maximum and if exceed then automatic working-set trimming process perform to restore free memory

solaris 2