[CS] 페이지 교체 알고리즘

페이지 교체 알고리즘

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용하는데, 이를 가상메모리 기법이라 합니다.

페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시 Page Fault가 발생합니다. 이때, 어떤 프레임에 있는 페이지를 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 합니다.

 

 

1. FIFO(First in First out) 알고리즘

• FIFO 알고리즘은 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘입니다.
• 구현이 간단하지만 성능은 좋지 않은 편입니다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있습니다.
• Belady`s Anomaly 현상이 발생할 수 있습니다.
• 이는 프레임의 개수가 많아져도 Page Fault가 줄어들지 않고 늘어나는 현상을 말합니다.

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

 

2. OPT(Optimal) 알고리즘

• OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘입니다.
• 모든 페이지 교체 알고리즘 중 Page Fault 발생이 가장 적습니다.
• Belady`s Anomaly 현상이 발생하지 않습니다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야 하기 때문에 실제로 구현하기 거의 불가능합니다.
• 실제로 사용하기 보다는 연구 목적을 위해 사용됩니다.

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

 

3. LRU(Least Recently Used) 알고리즘

• LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘입니다.
• OPT 알고리즘과 비슷한 효과를 낼 수 있습니다.
• 성능이 좋은 편입니다.
• 많은 운영체제가 채택하는 알고리즘입니다.

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

 

4. LFU(Least Frequently Used) 알고리즘

• LFU 알고리즘은 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체합니다.

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

 

5. MFU(Most Frequently Used) 알고리즘

• MFU 알고리즘은 LFU 알고리즘과 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.

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