[정보처리기사] 페이지 교체 알고리즘

1. FIFO (First In First Out)

- 가장 먼저 메모리에 적재된 페이지를 먼저 교체하는 기법

- 프레임 개수를 늘리면 부재 발생이 감소해야 하나, 오히려 부재 발생이 증가하는 Belady's Anomaly 이상 현상 발생

https://www.youtube.com/watch?v=qEgXhnujBA8&pp=ygUw7KCV7LKY6riwIOyLpOq4sCAg7Y6Y7J207KeAIOq1kOyytCDslYzqs6Drpqzsppgg 

-> 먼저 사용된 페이지 프레임에 줄(취소선) 그어서 확인

 

2. LRU (Least Recently Used)

- 최근에 가장 오랫동안 사용되지 않은 페이지를 교체

https://www.youtube.com/watch?v=9CCAK-N8Nwg&pp=ygUw7KCV7LKY6riwIOyLpOq4sCAg7Y6Y7J207KeAIOq1kOyytCDslYzqs6Drpqzsppgg 

-> 참조 페이지 기준으로 그 전에 어떤 페이지가 교체되었는지 확인

 

3. LFU (Least Frequently Used)

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

https://www.youtube.com/watch?v=eyF_y15iYi4&pp=ygUw7KCV7LKY6riwIOyLpOq4sCAg7Y6Y7J207KeAIOq1kOyytCDslYzqs6Drpqzsppgg 

-> 사용된 빈도 수 계산해서 적은 페이지 교체

 

4. NUR (Not Used Recently)

- 최근의 사용여부를 확인하기 위해 각 페이지마다 두 개의 비트 사용

- 참조비트와 변형비트 이용해서 페이지 교체

-> 참조비트와 변형비트가 모두 0인 경우 가장 먼저 교체, 1인 경우 가장 나중에 교체 

 

5. OPT (Optimal replacement, 최적 교체)

- 앞으로 가장 사용되지 않을 페이지를 교체

- 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘이나, 참조 상황을 예측하기 어려움

 

6. SCR (Second Chance Replacement)

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