[Chapter 9. 가상 메모리] 페이지 대치 알고리즘 (최적 대치, FIFO, LRU)

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

페이지 대치(교체) 알고리즘

---

가상 메모리 기법에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재된다.

 

따라서 페이지 부재(page fault)가 발생하면 해당 페이지를 메모리로 읽어 들여야 하는데,

물리 메모리에 여유가 없어 자유 프레임이 존재하지 않을 때는 희생될 페이지를 찾아 교체를 해야 한다.

 

이때 어떤 페이지를 교체할 것인지를 찾기 위해서 페이지 대치 알고리즘을 가동하게 되며,

일반적으로 페이지 부재율(page-fault rate)이 가장 낮은 것을 선정한다.

 

 

페이지 대치 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 부재 발생 횟수를 계산하여 평가한다.

이때 그 메모리 참조 나열(= 페이지를 참조하는 페이지 번호의 순서)을 참조 열(reference string)이라고 부른다.

 

 

 

* 페이지 대치 성능의 한계 영역

상한선 : 최적 대치 알고리즘 - Belady, B0 알고리즘

하한선 : 최악 대치 알고리즘 - 랜덤 알고리즘

 

최적 대치 알고리즘 - Belady(밸러디), B0 알고리즘

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

 

페이지 부재율이 가장 낮기에 이론적으로는 최적이지만,

참조 열을 미리 알아야지만 가능한 Lookahead 알고리즘이기 때문에 구현은 불가능하다.

 

이는 페이지 대치 알고리즘의 상한선이 된다.

 

 

(예시 1) - 프레임 3개 사용

참조 열에서 * 표시는 페이지 부재를 의미한다.

 

첫 번째 페이지 대치가 필요해진 상황에서 참조 열을 봤을 때

3번 페이지가 현재 적재된 페이지들 중 가장 오랜 후에 참조할 페이지이기 때문에 교체될 페이지로 선택된 것을 볼 수 있다.

 

페이지 부재 : 7회

 

 

(예시 2) - 프레임 4개 사용

페이지 부재 : 6회

 

최악 대치 알고리즘 - 랜덤 알고리즘

현재 메모리에 있는 페이지 중에서 랜덤 하게 하나를 선택하여 대치하는 방법이다.

이는 페이지 대치 알고리즘의 하한선이 된다.

 

 

 

* 페이지 대치 알고리즘의 성능

 

 

 

FIFO 페이지 교체

FIFO : First-In First-Out

 

메모리에 올라온 지 가장 오래된 페이지를 선택하여 대치하는 알고리즘이다.

기준 : 페이지가 메모리로 들어온 시간

 

페이지가 올라온 시간을 페이지마다 기록하거나,

FIFO 큐(queue)를 만들어 큐의 머리 부분 페이지를 교체하고 새로 올라오는 페이지는 큐의 끝에 삽입한다.

 

 

이 알고리즘은 성능이 항상 좋지는 않다.

교체된 페이지가 초기화된 뒤 계속해서 자주 사용되는 변수를 포함하고 있을 수도 있기 때문이다.

 

또한 Belady's Anomaly(벨러디 변이, 벨러디의 모순) 현상이 발생한다.

이는 프로세스에게 할당되는 프레임의 수가 증가함에도 오히려 페이지 부재율이 증가하는 현상을 말한다.

 

페이지 부재 그래프

 

보통 프로세스에게 더 많은 프레임을 할당하면 페이지 부재율은 떨어질 것이라고 예상하지만,

FIFO 페이지 교체 알고리즘을 적용했을 때에는 반대로 증가할 수도 있다.

 

아래의 예시를 보자.

 

 

(예시 1) - 프레임 3개 사용

참조 열은 수행의 결과로 주어진 것이다.

 

첫 번째 페이지 대치가 필요한 부분을 보면 큐의 머리 부분에 있던 1번 페이지가 선택되어 큐에서 쫓겨나게 되고,

새로 들어온 4번 페이지가 큐의 꼬리 부분에 삽입된 것을 볼 수 있다.

 

페이지 부재 : 9회

 

 

(예시 2) - 프레임 4개 사용

 

페이지 부재 : 10회

 

 

프레임 3개를 사용했을 때보다 4개를 사용했을 때 페이지 부재 횟수가 더 높은 것을 확인할 수 있다.

 

 

LRU 페이지 교체

LRU : Least Recently Used

 

가장 오랜 기간 동안 사용되지 않은 페이지를 선택하여 대치하는 알고리즘이다.

기준 : 페이지가 마지막으로 사용된 시간

 

Belady's Anomaly 현상이 발생하지 않는다.

이러한 알고리즘들은 스택 알고리즘(stack algorithm)이라고 부른다.

 

 

 

* B0 알고리즘과 LRU 알고리즘의 대칭성에 따른 성능의 유사성

 

최적 대치 알고리즘(B0 알고리즘)에서는 미래를 보아 가장 오랫동안 사용되지 않을 페이지를 찾아서 대치하는 방법이었다.

 

LRU 알고리즘은 미래 대신 과거 시간에 적용한 최적 대치 정책으로 생각할 수 있다.

가장 오랜 기간 사용되지 않을! 페이지 대신, 가장 오랜 기간 사용되지 않은! 페이지를 대치하는 것이다.

 

참조 열 w가 있다고 할 때 (w = r1, r2, r3, ... , rt-1, rt, rt+1, ...)

B0 알고리즘은 rt를 기준으로 오른쪽으로 가장 멀리 있는 페이지를 선택하여 대치,

LRU 알고리즘은 rt를 기준으로 왼쪽으로 가장 멀리 있는 페이지를 선택하여 대치하는 것으로 볼 수 있다.

 

(두 알고리즘끼리 대칭성이 보임)

 

 

LRU 알고리즘은 가까운 미래의 근삿값으로 '가장 최근의 과거'를 사용하는 것인데,

참조의 지역성(Locality of Reference)이라는 성질에 근거하여

가장 오랫동안 사용하지 않은 페이지는 앞으로도 상당한 기간 동안 사용되지 않을 것이라고도 가정할 수 있다.

 

 

실제로도 임의의 참조 열 S, 참조열 S의 역순 Sr가 있다고 했을 때

최적 대치 알고리즘을 이 둘에 적용했을 경우 둘에 대한 페이지 부재율이 같다.

LRU 알고리즘을 적용했을 때에도 S에 대한 페이지 부재율과 Sr에 대한 페이지 부재율이 같다.

 

이는 LRU 알고리즘은 최적 대치 알고리즘에 근접하고 있다는 것이다.

 

 

 

* 시간 정보 관리

 

LRU 알고리즘은 페이지가 '참조된 시간'에 대한 정보를 이용하기 때문에

프레임들을 최근 사용된 시간 순서로 파악할 수 있어야 한다.

 

이를 위해서는 하드웨어의 지원이 필요하며, 해결 방안으로는 2가지가 존재한다.

 

 

1. 계수기(counters) 또는 클럭(clock)의 시간 값을 사용

페이지 테이블에 각 페이지 항목마다 사용 시간 필드(타임 필드)를 두고,

페이지 참조가 일어날 때마다 시스템의 클럭 레지스터 값을 복사하여 해당 필드에 기록한다.

 

페이지 대치가 필요할 때 페이지 테이블의 타임 필드를 탐색하여 시간 값이 가장 작은 페이지를 교체하면 된다.

 

하지만 매 메모리를 참조할 때마다 타임 필드를 갱신하기 위해 메모리 쓰기 작업을 필요로 하며,

페이지 테이블이 CPU 스케줄링 등에 의해 변경될 때마다 시간 값을 관리해야 하고, 시간 값의 overflow도 고려해야 한다.

 

 

2. 스택(stack) 사용

페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택의 top에 놓이게 된다.

 

이렇게 하면 스택의 top에는 항상 가장 최근에 사용된 페이지의 번호,

스택의 bottom에는 가장 오랫동안 이용되지 않은 페이지의 번호가 저장되어 있다.

 

희생할 페이지가 항상 스택의 bottom에 위치하도록 하는 것으로, 페이지 대치가 필요할 경우 페이지를 탐색할 필요는 없어진다.

 

메모리 참조가 일어날 때마다 스택을 업데이트하는 데에 드는 시간이 많이 들어 오버헤드가 크다.

 

 

 

아래는 스택을 사용하여 LRU 알고리즘을 적용한 예시이다.

그림 상에서 스택의 top과 bottom 위치를 유의해서 보도록 하자.

 

 

(예시 1) - 프레임 3개 사용

 

페이지 부재 : 10회

 

 

(예시 2) - 프레임 4개 사용

 

페이지 부재 : 8회