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

페이지 교체 알고리즘이란?

• 가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하여 사용한다.

• 하지만 필요한 페이지만 올려도 메모리는 결국 차게 되고, 올라와있던 페이지가 다 사용된 후 자리만 차지하고 있을 수도 있다.

    즉 메모리가 가득 차면 안쓰는 페이지는 out 하고, 필요한 페이지는 in 시켜야 한다.

• 이 때 효율적인 페이지 교체를 위해 고안된 방법이 바로 페이지 교체 알고리즘이다.

• 프로세스와 운영체제의 경향에 알맞은 알고리즘을 선택하여 사용하는것이 좋다.

---

FIFO (First-in First-out)

• 메모리에서 내보낼 페이지를 선택할 때, 메모리에 먼저 올라온 페이지 순서대로 내보내는 방법

• 가장 간단한 방법이며, 특히 초기화 코드에 적절한 알고리즘이다.

    ◦  초기화 코드란? : 프로세스가 처음 실행될 때 최초 초기화를 수행하는 역할의 코드

---

OPT (Optimal)

• 앞으로 가장 사용하지 않을 예정인 페이지를 가장 우선적으로 내보내는 알고리즘

• FIFO에 비해 페이지 결함의 발생 횟수를 많이 감소시킬 수 있다.

    ◦  페이지 결함 : 메모리에 페이지가 올라와 있지 않아 페이지 적재가 필요한 상황

• 미래에 어떤 페이지가 사용되는지의 여부를 예측할 수 없기 때문에(앞으로 가장 사용하지 않을 예정인 페이지가 무엇인지 알 수 없음)
    이론적으로만 가능한 알고리즘이다.

---

LRU (Least-Recently-Used)

• 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

    ◦  최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다는 논리

• OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적인 구현이 가능하다.

• OPT 보다 페이지 결함이 더 많이 발생할 수 있지만, 구현 가능한 페이지 교체 알고리즘 중에서는 가장 좋다.

---

LFU (Least-Frequently-Used)

• 페이지의 참조 횟수로 교체할 페이지를 선택하는 알고리즘

• 누적 참조 횟수가 가장 낮은 페이지를 우선적으로 내보낸다.

    ◦ 가장 적게 참조된 페이지는 앞으로도 사용되지 않을 확률이 높다는 논리

    ◦ 누적 참조 횟수가 동일한 페이지끼리는 가장 오랫동안 사용되지 않은 페이지가(LRU) 우선적으로 제거된다.

• LRU는 참조된 시점을 고려하지만, LFU는 참조 횟수를 고려하기 때문에 더 과거의 참조성향까지 고려할 수 있다.

• 단점

    ◦  가장 최근에 참조된 페이지가 교체될 수 있다. (최근에 참조된 페이지일수록 앞으로 더 많이 참조될 가능성이 있는데 말이다)

    ◦  구현이 LRU보다 더 복잡하고 오버헤드가 발생할 수 있다.

---

MFU (Most-Frequently-Used)

• 마찬가지로 페이지의 참조 횟수를 활용하는 알고리즘
• LFU와 반대로, 누적 참조 횟수가 가장 높은 페이지를 우선적으로 내보낸다.

    ◦ 가장 많이 참조된 페이지는 앞으로 사용되지 않을 확률이 높다는 논리 (충분히 쓸만큼 쓴 페이지일 것이다)

---

참고자료

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)