[OS] 3. 페이지 교체 알고리즘[OPT/FIFO/LRU/LFU/NUR/SCR 등]

1. 페이지 교체 알고리즘

- 페이지 부재(Page Fault) 발생 시 가상 기억 장치에서 필요한 페이지 찾아 주기억 장치에 적재하는 것이 목적

- 주기억 장치의 모든 페이지 프레임이 사용 중일 때, 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 기법

- 종류 : OPT, FIFO, LRU, LFU, NUR, SCR 등

 

 

2. OPT(OPTimal replacement, 최적 교체)

- 벨레이디(Belady)가 제안, 앞으로 가장 오랫동안 사용하지 않을 페이지 교체 방법

- 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

 

 

3. FIFO (First In First Out) 

- 각 페이지에 주기억 장치에 적재될 때 가장 먼저 들어와서 가장 오래 있었던 페이지 교체 기법

 

 

4. LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않는 페이지 교체 기법

 

 

5. LFU(Least Frequently Used)

- 사용 빈도가 가장 적은 페이지 교체

- 활발히 사용되는 페이지는 사용 횟수가 많을 경우 교체되지 않고 사용됨

 

 

6. NUR(Not Used Recently)

- 최근에 사용하지 않는 페이지를 교체하는 기법

 

 

7. SCR (Second Chance Replacement)

- 가장 오래동안 주기억장치에 있던 페이지중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하는 기법이다.

 

 

 

페이지 교체 알고리즘의 대한 그림 설명은 아래와 같이 블로그 참조

https://doh-an.tistory.com/28

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR