Page 교체 알고리즘

1. FIFO

- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 것.(메모리에 올라온 지 가장 오래된 페이지 교체)

- 구현이 간단하지만 성능은 좋지 않음. 

- Belady's Anomaly(page frame의 개수가 많아져도 page가 없는 page fault 발생이 오히려 늘어나는 현상) 발생 가능.

https://code-lab1.tistory.com/60

 

https://code-lab1.tistory.com/60

 

2. Optimal Page Replacement(최적 페이지 교체)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘

- 가장 page-fault 발생이 적을 알고리즘

- Belady's Anomaly 발생 X

- process가 앞으로 사용할 page를 미리 알아야 해서 실제로 구현이 거의 불가능. 

https://code-lab1.tistory.com/60

 

3. LRU(Least Recently Used) 페이지 교체

- 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘

- 최적 알고리즘과 비슷한 효과. 성능이 좋은 편이라서 많은 OS가 채택하는 알고리즘

https://code-lab1.tistory.com/60

 

4. LFU(Least Frequently Used) 페이지 교체

- 참조횟수가 가장 적은 페이지를 교체하는 알고리즘

- 교체 대상이 여러 개면 가장 오랫동안 사용하지 않은 페이지 교체

- 초기에 한 페이지를 집중해서 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있음.

앞으로 사용하지 않아도 초기에 사용된 참조 횟수가 높아 메모리에 계속 남아있기 때문. 

https://code-lab1.tistory.com/60

 

 

5. MFU(Most Frequently Used)

- 참조 횟수가 가장 많은 페이지를 교체

- 참조횟수가 적은 페이지가 비교적 최근에 사용되어서 앞으로 사용될 가능성이 높다는 판단. 

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

 

LFU와 MFU는 실제로 잘 사용되지 않음. 

구현에 상당한 비용이 들고, LRU만큼 제대로 유사하게 구현해내지 못하기 때문. 

 

 

Reference

• https://code-lab1.tistory.com/60