[운영체제] 페이지 교체 (Page replacement)

위 그림은 메모리 초과 할당(over-allocating memory) 상황을 나타내고 있다.  프로세스가 실행되는 동안 페이지 폴트가 발생한다. 운영체제는 필요로 하는 페이지가 보조저장장치에 저장된 위치를 알아내지만 valid한 프레임이 없음을 발견한다(모든 메모리 사용중). 이 상황에서 대부분의 운영체제는 스와핑과 페이지 교체를 함께 사용한다.

 

Basic Page Replacement

Demanding Paging은 요구되는 페이지만 backing store에서 가져온다. 하지만 프로그램들을 계속 실행함에 따라 요구 페이지가 계속 늘어나고, 언젠가는 메모리가 가득 차게 될 수 있다(memory full). 여기서 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out), 새로운 페이지를 메모리에 올려야한다(page-in).이를 페이지 교체라고 한다. 여기서 backing store로 page-out이 된 페이지를 victim page라고 한다. 페이지 교체 과정을 정리해 보자면 다음과 같다

1️⃣ 보조저장장치에서 필요한 페이지의 위치를 알아낸다.
2️⃣ 빈 페이지 프레임을 찾는다.
   a. 비어 있는 프레임이 있다면 그것을 사용한다.
   b. 비어 있는 프레임이 없다면 victim프레임을 선정하기 위하여 페이지 교체 알고리즘을 사용한다.
   c. (필요한 경우)victim 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.
3️⃣ 원하는 페이지를 새로 비운 프레임에 올린다. 그에 따라 페이지, 프레임 테이블을 수정한다.
4️⃣ 페이지 폴트가 발생한 지점에서부터 프로세스를 이어나간다.

빈 프레임이 없는 경우에는 프레임을 backing store에 보낼 때(page-out), 새로운 페이지를 메모리에 올릴 때(page-in) 총 두 번 디스크에 접근한다. 만약 CPU에 의해 수정(modify)되지 않았더라면 프레임을 page-out하지 않아도 되어 페이지 폴트 처리 시간(page fault service time)을 줄일 수 있어 유효 접근 시간을 줄일 수 있다.

이러한 오버헤드를 감소시키기 위해 modify bit(=dirty bit)을 사용한다. 페이지 테이블에 modify bit을 추가하여 해당 페이지가 수정되었는지를 표시한다. 페이지가 변경되지 않았으면 I/O시간을 반으로 줄일 수 있으므로 페이지 폴트 시간을 많이 줄일 수 있다. 이를 활용하여 victim page 설정시 modify bit을 참고한다.

victim page를 설정하는 방법에는 여러가지 알고리즘이 있다. 이들 중 가장 대표적인 FIFO, OPT, LRU에 대해 알아보자

페이지 교체 알고리즘을 살펴보기 전에 Page reference string이라는 용어를 알아야 한다.

CPU 주소 = {100, 101, 102, 432, 612, 103, 104, 611, 612}
Page 번호 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
Page reference string = {1, 4, 6, 1, 6}

연속된 페이지는 생략하고 하나의 페이지 번호만나타낸 것이다. 연속된 페이지를 참조할 때 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문에 이와 같이 나타낼 수 있다.

 

FIFO 페이지 교체

FIFO(first-in first-out)은 가장 간단한 페이지 교체 알고리즘이다. 페이지를 교체해야 할 때, 메모리에 올라온지 가장 오래된 페이지를 page-out 시킨다.

 

Balady의 모순

FIFO알고리즘은 이해하기도 쉽고 프로그램하기도 쉽지만 성능이 항상 좋지는 않다. 다음 예시를 생각해보자.

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

각 프레임의 개수에 따른 페이지 폴트 횟수를 구해보면 다음과 같다.

프레임이 4개일 때, 프레임이 3개인 경우보다 더 많은 프레임을 보유하고 있음에도 불구하고, 더 많은 페이지 결함이 발생하였다.

프레임 수가 증가하면(=메모리 용량이 증가하면) page fault 수가 줄어드는 것이라고 기대하지만, 특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생한다. 이러한 현상을 Belady의 모순이라 한다.

 

최적 페이지 교체 (Optimal Page Replacement)

OPT(Optimal Page Replacement) 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 Victim으로 선택한다.

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다. 이후 2번 페이지에서 페이지 결함이 발생하면, 현재 프레임이 할당된 7, 0, 1번 페이지 중 가장 오랫동안 사용되지 않을 예정인 페이지를 Victim으로 선택한다. 그림에서는 0번 페이지는 5번째, 1번 페이지는 14번째, 7번 페이지는 18번째에 다시 참조될 것이므로, 가장 늦게 참조될 7번 페이지가 Victim으로 선택된다.

하지만 이 알고리즘의 실제 구현은 현실적으로 어렵다. 프로세스가 앞으로 어떻게 메모리를 참조할 것인지를 미리 알고 있어야 하기 때문이다. 

 

LRU 페이지 교체

LRU 페이지 교체 기법은 최적의 해는 아니더라도 근사의 해를 구하여 페이지를 교체하는 방법이다. LRU는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 희생양 페이지를 선택한다.

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다. 이후 2번 페이지에서 페이지 결함이 발생하면, 프레임이 할당된 페이지들 중 가장 오랫동안 사용되지 않은 페이지를 선택한다. 이 경우에는 7번 페이지가 해당한다. 다음 0번 페이지에 대한 참조에서는 페이지 결함이 발생하지 않는다.

그 다음 3번 페이지에 대한 참조에서 페이지 결함이 발생한다. 이 때, 프레임이 할당된 2, 0, 1번들에 대해 가장 오랫동안 사용되지 않은 페이지를 선택한다. 이 경우엔 1번 페이지가 해당한다. 1번 페이지는 참조 문자열의 3번째, 2번 페이지는 4번째, 0번 페이지는 5번째에 사용되었기 때문에 1번 페이지를 선택한다.

LRU 페이지 교체 기법은 좋은 자주 사용되고 좋은 성능을 낸다. 프레임들을 최근 사용한 순서로 파악할 수 있어야 하기 때문에 LRU 페이지 알고리즘은 하드웨어의 지원이 필요하다. counter를 사용하여 페이지마다 가장 마지막으로 사용된 시간을 기록하거나, 페이지를 stack형식으로 저장하여 이를 구현할 수 있다.