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
- FIFOSimple: single pointer sufficesBelady'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 AlgorithmLRU clock(Secondd chance) - clock bitclock 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


1. windows NTdemand 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
2. solaris 2
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ff66a2160-4cbc-4f7c-95f5-593519e3a76b%2FUntitled.png?table=block&id=21bfeffc-ef6d-43a1-b507-7f31bce81cbd&cache=v2)