운영체제 - 페이지 교체 알고리즘

페이지 교체 알고리즘

---

이전 포스팅에서 요구 페이징에 대해서 알아보았다. 요구 페이징에서 Backing Store에 있는 페이지를 물리 메모리로 불러오는 작업을 진행하게 되는데 여기서 물리 메모리에 빈 공간이 없을 경우 페이지 교체 알고리즘을 통해서 기존의 페이지를 바꿔주는 작업이 필요하게 된다.

운영체제 - 요구 페이징

 

페이지 교체 알고리즘은 빈 공간이 없는 물리 메모리 공간에서 희생당할 프레임(Victim Frame)을 골라 교체하는 알고리즘을 의미한다.

 

페이지 교체 알고리즘을 사용하는 목적은 요구 페이징에서 발생하는 페이지 부재 즉, Page Fault가 발생하는 것을 줄이는 것이 목표이다.

 

페이지 교체 알고리즘은 종류가 여러가지 있는데 하나씩 살펴보면서 어떤 특징을 가지는지 살펴보자.

 

• FIFO(First In First Out) 알고리즘

FIFO 알고리즘은 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.

 

큐 자료구조를 이용하여 구현하게 되는데 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.

 

다른 페이지 교체 알고리즘에 비해서 구현이 간단하지만 자주 사용하는 페이지여도 교체되기 때문에 성능은 좋지 않은 편이다.

 

FIFO 알고리즘을 사용하면 Belady's Anomaly 현상이 발생할 수 있기 때문에 성능에 영향을 줄 수 있다.

 

• Belady's Anomaly

Belady's Anomaly란 프레임의 개수가 많아져도 page fault가 줄어들지 않고 늘어나는 현상을 말한다.

 

FIFO 알고리즘

간단한 예시로 그림을 그려보았다. 여기서 초록색 네모 박스는 페이지를 찾았을 경우를 표시했다.

 

예시를 보면 페이지를 찾은 횟수는 총 3회로 나머지 7번에 대해서는 page fault가 발생한 것을 알 수 있다.

 

큐를 이용해서 FIFO 알고리즘을 구현하게 되는데 먼저 들어온 페이지가 자주 참조하는 것이라도 FIFO의 특성으로 인해 스왑 영역으로 옮겨지는 상황이 발생하게 된다.

 

• LRU(Least Recently Used) 알고리즘

LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지는 앞으로도 사용할 확률이 적다고 판단하여 해당 페이지를 교체하는 알고리즘이다.

 

LRU 알고리즘은 최근에 사용한 페이지는 앞으로 다시 사용될 가능성이 높다는 시간 지역성 성질을 고려한다.

 

LRU 알고리즘은 페이지에 접근한 시간, 카운터, 참조 비트 등을 기준으로 대상 페이지를 선정한다.

 

성능이 대체로 좋은 편이지만 추가적으로 최근에 사용했다는 값을 저장해야 되기 때문에 메모리 공간을 낭비할 수 있다.

 

아래의 그림을 통해서 LRU 알고리즘의 동작 방식을 알아보자.

LRU 알고리즘

FIFO도 시간 값을 통해서 페이지를 교체한다는 점에서 LRU와 비슷해 보이지만 약간의 차이가 있는데 FIFO 알고리즘은 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체한다면, LRU 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체하는 것이다.

 

즉, 메모리에 올라온 페이지 중에서 가장 오랫동안 사용하지 않은 페이지를 대상으로 하여 바꾸는 것이다.

 

괄호 안에 있는 숫자는 페이지에 접근한 숫자를 뜻하며 중간 중간에 빨간색 글씨로 바뀐 것은 페이지에 접근하여 사용했다는 것으로 1을 더해줘서 값을 바꿔주었다.

 

위에서 살펴본 FIFO 알고리즘과 비교해보면 page fault 횟수가 하나 줄어든 것을 알 수 있다.

 

LRU 알고리즘의 단점으로는 참고해야 되는 값이 추가로 필요하기 때문에 추가적인 메모리 공간이 필요하게 된다.

 

• LFU(Least Frequently Used) 알고리즘

LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다. 즉, 그동안 해당 페이지를 몇 번 사용했는지를 체크하여 가장 적은 페이지를 스왑 하는 알고리즘이다.

 

페이지가 사용된 횟수를 기준으로 대상 페이지를 선정하게 되는데 앞서 살펴본 LRU와 마찬가지로 참조된 횟수를 저장할 추가적인 메모리가 필요하게 되고 이로 인한 메모리 낭비가 발생할 수 있다는 단점을 가지고 있다.

 

대체로 LRU 알고리즘와 비슷한 성능을 보여주게 된다.

 

그림을 보면 각 페이지마다 그동안 몇 번 참조했는지를 표시하고 특정 페이지를 사용하게 되면 참조 횟수를 1 더해준다.

 

그다음 메모리에 없는 페이지가 들어오면 가장 참조 횟수가 적은 페이지와 교체되는데 만약 참조 횟수가 동일하다면 큐 자료구조의 특성으로 인해 보다 앞에 위치한 메모리와 교체되게 된다.

 

• OPT(Optimal) 알고리즘

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

 

모든 페이지 교체 알고리즘 중에서 page fault 발생이 가장 적다. 하지만 프로세스가 앞으로 사용할 페이지를 미리 알아야 하기 때문에 실제로 구현하는 것은 거의 불가능한 알고리즘이다.

 

앞서 FIFO에서 발생하는 Belady's Anomaly 현상이 발생하지 않는다.

OPT 알고리즘

그림을 예시로 보면 순서 4번에서 페이지가 1, 2, 4로 구성되는데 기존의 3번 페이지는 가장 마지막인 10번째 순서에서 다시 사용되기 때문에 가장 늦게 사용되는 페이지이므로 스왑 영역으로 보내게 된다.

 

따라서 나머지 접근 순서인 5번부터 9번까지는 page fault 없이 원하는 페이지에 접근이 가능하다.

 

• MFU(Most Frequently User) 알고리즘

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

 

 

• NUR(Not Used Recently) 알고리즘

NUR 알고리즘은 최근에 사용하지 않은 페이지를 교체하는 알고리즘으로 LRU와 비슷한 알고리즘이다.

 

앞서 살펴봤던 LRU, LFU 알고리즘과 성능이 비슷하지만 해당 알고리즘이 가지고 있던 단점인 메모리 공간 낭비 문제를 해결할 수 있는 것이 NUR 알고리즘의 장점이다.

 

각 페이지마다 두 개의 비트를 사용하는데 PTE(Page Table Entry)의 참조 비트와 변형 비트를 이용해서 교체할 대상 페이지를 선정하게 된다.

 

만약 같은 비트의 페이지가 여러 개라면 무작위 또는 FIFO 알고리즘을 사용하여 대상 페이지를 선정하게 된다.

 

추가적인 메모리 공간이 필요하지 않기 때문에 적은 오버헤드로 적절한 성능을 보여주지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 못한다.

 

참고 자료

---

OS는 할껀데 핵심만 합니다. 17편 페이지 교체 알고리즘(FIFO, LRU, LFU , NUR, 2차 기회 알고리즘, 시계

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

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