페이지 교체(page-replacement) 알고리즘

Published in

POCS

6 min readJul 15, 2019

요구 페이징 시스템은 프로세스가 특정 페이지를 요구할 때 해당 페이지를 물리 메모리에 로딩한다.

메모리에 필요한 페이지가 있을 때는 잘 진행되지만, 없을 경우에는 문제가 생긴다. 프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 또다시 ‘페이지를 올릴 빈 프레임이 없을 경우’ 란 문제에 직면할 수 있다.

이 때 사용하는 것이 새로 올릴 페이지와 교체할 희생 프레임을 찾는 알고리즘, 페이지 교체 알고리즘이다.

아래의 페이지 교체 알고리즘 예시들은 각 프로세스에 프레임 3개를 주고, 지역성 교체를 가정한 것이다.

FIFO(first in first out)

가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체한다. 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용할 수 있다.

FIFO 알고리즘은 이해가 쉽고, 구현이 간단하다. 다만 성능은 언제나 좋다고 장담할 수 없다. 위의 그림을 예시로 보자면

페이지 7의 경우에는 프로세스 초기에 쓰인 후 한동안 쓰이지 않기 때문에 FIFO교체 방식이 큰 문제를 일으키지 않는다.
페이지 2(9번째)의 경우, 직전 페이지 부재(page 4)로 인해 페이지 4와 페이지 2가 교체되고 난 후, 또 다시 페이지 2를 사용하기 위해 교체했던 페이지 2를 다시 불러들였다.

활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있다.

최적(Optimal) 페이지 교체

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

최적 알고리즘은 수행하기 전에 선행되어야 할 전제조건이 있다. 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것이다. 이 전제 조건이 실제 활용에서는 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘 이다.

때문에 이 알고리즘은 실제 구현 목적보다 다른 알고리즘과 비교 연구 목적을 위해 주로 사용된다.

최적 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 알고 교체하기 때문에 모든 페이지 교체 알고리즘을 통틀어 가장 페이지 교체 수가 적다.

페이지 7의 경우, 18번째에 가서나 다시 쓰일 것을 미리 알고 있기 때문에 페이지 2와 페이지 7을 교체했다.
페이지 1의 경우(page3, 6번째 참조), 현재 올라와있는 {2, 0, 1} 중 페이지 1이 14번째 참조로 가장 뒤에 쓰일 것을 알기 때문에 페이지 1과 페이지 3을 교체했다.

LRU(least-recently-used)

가장 오래 사용되지 않은 페이지를 교체하는 알고리즘이다.

최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다.

최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능하다. 예측 방법으로 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용하는 것이다.

LRU 알고리즘은 최적 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘 보다 효율적이다.

페이지 2의 경우(9번째), 직전의 페이지 부재(page 4) 에서 (페이지 2가 바로 다음에 사용될 것을 모르기 때문에) {2, 0, 3} 중 가장 오랫동안 사용되지 않았던 페이지 2를 교체한다.
페이지 0의 경우(11번째), 가장 오랫동안 사용되지 않았던 페이지 4를 페이지 0과 교체한다. 실제로 페이지 4는 이후에 해당 프로세스에서 참조되는 일이 없다.

LRU 알고리즘은 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가 받고있다.