페이지 교체 알고리즘

메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 재배치 정책에 대해서 알아보자.

1. 페이지 교체 알고리즘 개요

프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재(page fault)가 발생한다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데, 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑영역으로 보내야 한다. 페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지(victim page)로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상한다.

1.1 페이지 교체 알고리즘의 종류

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다.
	FIFO	처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다.
이론적 알고리즘	최적	미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.
최적 근접 알고리즘	LRU	시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다.
	LFU	사용 빈도가 적은 페이지를 스왑 영역으로 보낸다.
	NUR	최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다.
	FIFO 변형	FIFO 알고리즘을 번형하여 성능을 높인다.

위 테이블은 페이지 교체 알고리즘의 종류와 특징을 정리한 것이다. 무작위 교체 알고리즘은 무작위로 대상 페이지(victim page)를 선정하며, FIFO 페이지 교체 알고리즘은처음 메모리에 올라온 페이지를 대상 페이지(victim page)로 선정한다. 최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 살펴보고 대상 페이지(victim page)를 선정하므로 성능이 가장 좋지만 사실상 구현이 불가능하다. LRU, LFU, NUR 페이지 교체 알고리즘은 최적 페이지 교체 알고리즘에 근접하는 성능을 보이는 알고리즘으로 세 알고리즘을 합쳐서 최적 근접 알고리즘이라고 한다. 최적 근접 알고리즘 중에는 FIFO 알고리즘을 변형한 2차 기회 페이지 알고리즘(second chance algorithm)과 시계 알고리즘도 있다.

1.2 페이지 교체 알고리즘의 성능 평가 기준

어떤 알고리즘이 다른 알고리즘보다 더 좋은 성능을 가지는 데에는 다양한 비교 방법이 있다. 여기서는 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수, 페이지 성공 횟수를 기준으로 비교해보자. 페이지 교체 알고리즘은 성능뿐 아니라, 유지 비용도 고려해야 한다. 아무리 뛰어난 알고리즘이라도 계산이 많이 필요하거나 메모리를 많이 차지한다면 좋은 알고리즘이 아니다.

앞으로 소개할 모든 페이지 교체 알고리즘은 다음과 같은 메모리 접근 순서를 사용하고, 물리 메모리는 3개의 프레임을 가졌다고 가정한다. 그림에서 상단의 숫자는 메모리의 접근 순서를 나타내며 페이지 번호 대신 알파벳을 사용한다.

이제 페이지 교체 알고리즘을 순서대로 살펴보자.

2. 무작위 페이지 교체 알고리즘(random page replacement algorithm)

무작위 페이지 교체 알고리즘(random page replacement algorithm)은 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방식이다. 스왑 영역으로 쫒아낼 대상 페이지(victim page)를 특별한 로직 없이 무작위로 선정한다. 대부분 프로세스의 메모리 접근 패턴을 보면 메모리의 인접한 영역에 저장되는 지역성을 가지는데, 무작위 알고리즘은 이러한 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 한다. 따라서 알고리즘의 성능이 좋지 않아 거의 사용되지 않는다.

3. FIFO 페이지 교체 알고리즘(First In First Out page replacement algorithm)

선입선출 페이지 교체알고리즘인 FIFO 페이지 교체 알고리즘(First In First Out page replacement algorithm)은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지(victim page)로 선정하여 스왑 영역으로 쫒아낸다.

위 그림은 FIFO 페이지 교체 알고리즘 동작을 나타낸 것으로, 페이지 부재(page fault)가 일어난 경우(원하는 페이지가 메모리에 없는 경우)는 실패로, 그렇지 않은 경우(원하는 페이지가 메모리에 있는 경우)는 성공이라고 표시했다.

FIFO 페이지 교체 알고리즘은 큐로 구현한다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입된다. 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들은 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어온다.

위 그림의 메모리 접근 순서 4번을 보면 가장 오래된 페이지 A가 스왑 영역으로 가고, 페이지 B와 C가 위쪽으로 이동하며 새로운 페이지 D가 아래쪽의 남은 공간에 들어온다. 5번의 경우는 메모리에 있던 페이지 B를 요청했으므로 성공이다. 교체되어 새로 들어오는 페이지는 회색으로, 성공한 페이지는 초록색으로 구분하여 나타냈다. 이 그림에서는 총 열 번의 페이지 요구에 대해 세 번만 성공했다. 즉 페이지 부재(page fault)가 7번 발생했다.

페이지 교체 알고리즘에서는 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮기는 것이 중요하다. FIFO 페이지 교체 알고리즘은 큐로 쉽게 구현할 수 있지만 먼저 들어온 페이지를 항상 스왑 영역으로 옮긴다. 시간의 지역성을 고려하면 가장 오래된 페이지를 대상 페이지로 선정하는 것이 맞다. 그러나 메모리에 올라온 지 오래되었더라도 자주 사용되는 페이지가 있는데, FIFO 페이지 교체 알고리즘에서는 메모리에 올라온 시간만 고려하기 때문에 자주 사용되는 페이지가 스왑 영역으로 옮겨지기도 한다. 위 그림의 메모리 접근 순서 5~7번을 보면 5번에서 사용되었던, 페이지 B가 6번에서 스왑 영역으로 옮겨졌다가 7번에서 다시 메모리로 올라온다.

메모리에 먼저 올라왔어도 자수 사용되는 페이지가 있기도 하고, 나중에 올라왔어도 한 번만 사용되는 페이지가 있기도 하다. FIFO 페이지 교체 알고리즘은 무조건 오래된 페이지를 대상 페이지(victim page)로 선정하기 때문에 성능이 떨어지는데 이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘(second chance replacement algorithm)이다.

2차 기회 페이지 교체 알고리즘은 맨 뒤에 알아보도록 하자.

4. 최적 페이지 교체 알고리즘(Optimal page replacement algorithm)

최적 페이지 교체 알고리즘(Optimal page replacement algorithm)은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다. 즉, 프레임에 있는 페이지가 가장 나중에 불리는 것을 대상 페이지로 선정하는 것이다.

위 그림은 최적 페이지 교체 알고리즘의 동작 과정을 보여준다. 메모리 접근 순서 4번을 주의 깊게 살펴보자. FIFO 페이지 교체 알고리즘에서는 페이지 A가 스왑 영역으로 쫒겨나고, 페이지 D가 들어왔었다. 그러나 최적 페이지 교체 알고리즘에서는 앞으로 사용할 페이지에 A, B, C가 있는지 살펴본다. 그 결과 페이지 A는 6번에서, 페이지 B는 5번에서, 페이지 C는 9번에서 사용되므로 가장 늦게 사용되는 페이지 C를 스왑 영역으로 보낸다.

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋다. 하지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다. 최적 페이지 교체 알고리즘에 근접하는 방법을 연구한 결과 최근 최소 사용 알고리즘인 LRU(Least Recently Used)와 최소 빈도 사용 알고리즘인 LFU(Least Frequently Used), 최근 미사용 알고리즘인 NUR(Not Used Recently) 등이 개발되었다. 이러한 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optimal approximation algorithm)이라고 부른다.

위 그림은 대표적인 최적 근접 알고리즘인 LRU 페이지 교체 알고리즘, LFU 페이지 교체 알고리즘의 차이를 보여준다.

1. LRU 페이지 교체 알고리즘: 페이지에 접근한 시간을 기준으로 대상 페이지를 선정한다. 현재 시간이 11시이고, 페이지 A, B, C에 마지막으로 접근한 시간이 각각 1시 40분, 8시 50분, 9시 30분이라면 현재와의 시간 차가 가장 큰 1시 40분에 접근한 페이지 A가 스왑 영역으로 옮겨진다.

2. LFU 페이지 교체 알고리즘: 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정한다. 페이지 A, B, C가 메모리에 올라온 후 각각 104번, 8번, 430번 사용되었다면 8번 사용한 페이지 B를 스왑 영역으로 옮긴다.

최적 페이지 교체 알고리즘은 미래의 데이터를 참고로 하기 때문에 구현이 불가능한 반면에, 최적 근접 알고리즘은 과거의 데이터로부터 미래를 예측하기 때문에 최적 페이지 교체 알고리즘과 유사한 성능을 보인다.

5. LRU 페이지 교체 알고리즘(Least Recently Used page replacement algorithm)

LRU 페이지 교체 알고리즘(Least Recently Used page replacement algorithm)은 '최근 최소 사용 페이지 교체 알고리즘'이라고도 한다. 직역하면 말이 어려운데, 간단히 말해 '메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다'이다. 즉 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지(victim page)로 선정한다는 것이다. LRU 페이지 교체 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있다. 각 구현 방법의 차이는 다음과 같다.

5.1 페이지 접근 시간에 기반한 구현

LRU 페이지 교체 알고리즘의 가장 간단한 형태는 페이지에 접근한 시간을 기록하여 구현하는 것이다.

위 그림은 LRU 페이지 교체 알고리즘의 동작을 보여준다. FIFO 페이지 교체 알고리즘이 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체한다면, LRU 페이지 교체 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체한다. 즉 페이지에 읽기, 쓰기 ,실행과 같은 연산이 이루어진 시간을 기준으로 하는 것이다. 즉, FIFO 페이지 교체 알고리즘은 메모리에 올라온 시간이 가장 오래된 페이지를 대상 페이지로 선택하고, LRU패이지 교체 알고리즘은 메모리에 올라온 페이지 중 가장 오래전에 사용된(읽기, 쓰기, 실행 등) 페이지를 대상 페이지로 삼는 것이다.

위 그림에서는 편의상 맨 위의 숫자를 초 단위로 가정하고, 이 페이지가 메모리에 올라오거나 사용될 때마다 그 시간(초)을 괄호안에 표시했다. 가령 3초에 페이지 C가 메모리에 올라왔으므로 C 괄호의 숫자는 3이다. 5초에는 페이지 B에 접근했으므로 B 괄호의 숫자는 2가 5로 변경된다. 또한, 8초에도 페이지 A에 접근했으므로 A의 괄호는 6에서 8로 변경된다.

LRU 페이지 교체 알고리즘에서는 숫자가 가장 작은 페이지, 즉 사용된 지 가장 오래된 페이지를 대상 페이지로 선정한다. 가령 6초의 경우, 페이지 A를 올리기 위해 가장 오랫동안 접근하지 않았던 페이지 C를 스왑 영역으로 옮긴다. 9초의 경우도 가장 오랫동안 접근하지 않았던 페이지 D를 스왑 영역으로 옮기곡 그 자리에 페이지 C를 올린다.

같은 메모리 접근 패턴에 대해 FIFO 페이지 교체 알고리즘의 페이지 성공 횟수는 3이고, LRU 페이지 교체 알고리즘의 페이지 성공 횟수는 4이다. 주의할 점은 메모리 접근 패턴을 변경하면 LRU 페이지 교체 알고리즘의 성능이 FIFO 페이지 교체 알고리즘만큼 느려지기도 하고 최적 페이지 교체 알고리즘만큼 좋아지기도 한다는 사실이다. 일반적으로 LRU 페이지 교체 알고리즘의 선능은 FIFO 페이지 교체 알고리즘보다 우수하고 최적 페이지 교체 알고리즘보다는 조금 떨어진 것으로 알려져 있다.

5.2 카운터에 기반한 구현

LRU 페이지 교체 알고리즘은 페이지 접근 시간을 기록하여 구현할 수도 있지만 카운터를 사용하여 구현할 수도 있다. 가령, 위 그림에서 시간을 표시한 괄호 숫자를 카운터 숫자로 생각하면 된다.

그런데 접근 시간을 기록하든 카운트를 기록하든 두 방법은 모두 추가적인 메모리 공간을 필요로 하는 것이 단점이다. 가령, 0~1024초를 표시하려면 10bit가 필요하고 더 큰 숫자를 표시하려면 더 많은 비트를 사용해야한다는 것이다. 이러한 추가 공간으로 인해 사용자가 사용할 수 있는 공간이 낭비된다.

5.3 참조 비트 쉬프트 방식(reference bit shift)

LRU 페이지 교체 알고리즘을 실제로 구현하는 데 참조 비트 쉬프트(reference bit shift)방식을 사용할 수도 있다. 참조 비트 쉬프트 방식은 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다. 또한 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다.(shift)

위 그림은 참조 비트 쉬프트 방식을 보여준다. 위 그림의 첫번째는 페이지 B에 접근하면 페이지 B의 참조 비트 맨 앞(왼쪽)이 1이 된다. 다음으로 페이지 A에 접근하면 모든 참조 비트가 오른쪽으로 한 칸 이동(shift)되고, 페이지 A의 맨 앞 참조 비트가 1이 된다. 그리고 페이지 B에 다시 접근하면 모든 참조 비트가 오른쪽으로 한 칸 이동하고, 페이지 B의 맨 앞 참조 비트가 1이 된다. 이와 같은 방식으로 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다. 따라서, 페이지 C가 대상 페이지로 선정된다.

참조 비트 쉬프트 방식은 LFU 페이지 교체 알고리즘과 혼동되기도 한다. LFU 페이지 교체 알고리즘은 페이지의 접근 횟수를 측정하여 대상 페이지를 선정한다.

위 그림을 보면 참조 비트 쉬프트 방식이 LRU 페이지 교체 알고리즘이라는 것을 이해할 수 있다.

페이지 A에 네 번, 페이지 B에 한 번, 페이지 C에 다섯 번 접근했다. 그러나 참조 비트 중 가장 큰 값은 가장 최근에 접근한 페이지 B이고, 가장 작은 값은 가장 오랫동안 접근하지 않은 페이지 C이다. 따라서 페이지 C가 대상 페이지로 선정된다. 그림에서 보듯이 참조 비트 쉬프트 방식은 참조한 횟수가 아니라, 참조한 시간을 기준으로 대상 페이지를 선정하므로 LRU 페이지 교체 알고리즘의 한 방식으로 분류된다.

비록 1B이기는 하지만 참조 비트 쉬프트 방식도 작지 않은 공간을 사용하므로 공간을 낭비하는 것이 단점이다. LRU 페이지 교체 알고리즘의 단점은 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다는 것이다.

6. LFU 페이지 교체 알고리즘(Least Frequently Used page replacement algorithm)

최적 근접 알고리즘 중 LFU 페이지 교체 알고리즘(Least Frequently Used page replacement algorithm)은 '최소 빈도 사용 알고리즘' 이라고도 한다. LFU 페이지 교체 알고리즘은 페이지가 몇 번 사용 되었는 지를 기준으로 대상 페이지(victim page)를 선정한다. 다시 말해 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.

위 그림은 LFU 페이지 교체 알고리즘의 동작을 보여준다. 괄호의 숫자는 사용 빈도를 나타낸다. 가령 5번째의 B(2)는 페이지 B가 메모리에 올라온 후 지금까지 두 번 사용되었다는 의미이다. 이 사용 빈도에 따라 대상 페이지를 결정하는데, 만약 사용 빈도가 동일하다면 맨 위의 페이지를 선택하도록 가정하고 시나리오를 작성했다.

LFU 페이지 교체 알고리즘에서는 처음 메모리에 올라온 페이지의 사용 빈도가 1이고, 페이지가 사용될 때마다 하나씩 증가한다. 위 그림의 접근 순서 5번을 보면 페이지 B의 사용 빈도가 1에서 2로 증가했다. 이어서 메모리 접근 순서 6번에서 페이지 부재(page fault)가 발생하는데, 페이지 B는 대상 페이지(victim page)에서 제외되고, 사용 빈도가 같은 페이지 C와 D 중 맨 처음에 있는 페이지 D가 스왑 영역으로 쫒겨난다.

같은 메모리 접근 패턴에 대해 LRU 페이지 교체 알고리즘}의 페이지 성공 횟수는 4이고, LFU 페이지 교체 알고리즘의 페이지 성공 횟수는 5번이다. LFU 페이지 교체 알고리즘이 LRU 페이지 교체 알고리즘보다 한 번 더 성공했지만 일반적인 경우 두 알고리즘의 성능이 비슷하다고 알려져 있다. LRU, LFU 페이지 교체 알고리즘은 둘 다 FIFO 페이지 교체 알고리즘보다 성능이 우수하다.

LFU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다는 것이다. 페이지 접근 횟수(빈도)를 표시하는 데 추가 공간이 필요하므로 그만큼 메모리가 낭비된다.

7. NUR 페이지 교체 알고리즘(Not Recently page replacement algorithm)

NUR 페이지 교체 알고리즘(Not Recentlu replacement algorithm)은 LRU, LFU 페이지 교체 알고리즘 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘이다. NUR 페이지 교체 알고리즘은 '최근 미사용 페이지 교체 알고리즘'이라고도 불린다.

1,000번 접근한 페이지와 20번 접근한 페이지가 있다면 당연히 20번 접근한 페이지를 스왑 영역으로 쫒아내야 한다. 그러나 95번 접근한 페이지와 91번 접근한 페이지가 있다면 어떤 페이지를 쫒아내도 큰 상관없다. 과거로부터 미래를 추정할 때 95번 접근한 페이지와 91번 접근한 페이지는 앞으로 접근할 확률이 비슷하기 때문이다. 알고리즘에서 접근 시간이든 접근 빈도든 정확한 값을 유지하는 것은 공간만 많이 차지할 뿐 의미가 없다. NUR 페이지 교체 알고리즘은 이러한 경향을 반영한 방식으로, 추가 비트 2개만 사용하여 미래를 추정한다.

NUR 페이지 교체 알고리즘에서는 페이지마다 참조 비트와 변경 비트를 가지므로 페이지마다 추가되는 메모리 공간이 2비트뿐이다. 여기서 참조 비트는 앞서 살펴보았던 PTE 접근 비트를 가리키고, 변경 비트는 PTE의 변경 비트를 가리킨다. 참조 비트와 변경 비트는 초깃값이 0이며 다음과 같은 경우에 1이된다.

1. 참조 비트: 페이지에 접근(read/execute)하면 1이 된다.
2. 변경 비트: 페이지가 변경(write/append)되면 1이 된다.

모든 페이지의 초기 상태는 (0,0)이다. 이 상태에서 페이지에 읽기 또는 실행과 같은 '접근'이 발생하면 (1,0)으로 바뀐다. 만약 페이지에 쓰기 또는 추가 같은 '변경'이 일어나면 (0,1)이 된다. 또한 접근과 변경, 두 가지 연산이 다 발생하면 (1,1)이 된다.

NUR 페이지 교체 알고리즘에서 대상 페이지(victim page)를 선정할 때는 (0,0), (0,1), (1,0), (1,1) 중에서 하나를 고르는데, 가장 먼저 (0,0)인 페이지를 선정한다. 즉 접근한 적도 변경한 적도 없는 페이지를 스왑 영역으로 옮긴다. 만약 (0,0)인 페이지가 없다면 (0,1)인 페이지를, (0,1)인 페이지가 없다면 (1,0)인 페이지를 (1,0)인 페이지가 없다면 최종적으로 (1,1)인 페이지를 스왑 영역으로 옮긴다.

참조 비트	변경 비트
0	0
0	1
1	0
1	1

위에서부터 아래로 대상 프레임(victim page) 우선순위가 낮아진다. 만약 모두 (1,1)이면 초기화를 하도록 한다.

NUR 페이지 교체 알고리즘에서 우선 고려 대상은 참조 비트이다. 참조 비트가 0인 페이지를 먼저 찾고, 변경 비트가 0인 페이지를 찾는다. 만약 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다. 흔한 경우는 아니지만 모든 페이지의 비트가 (1,1)일 때는 어떤 페이지가 더 자주 사용되는 지를 알 수 없어 NUR 페이지 교체 알고리즘을 정상적으로 적용할 수 없다. 그러므로 NUR 페이지 교체 알고리즘에서 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화한다.(reset)

위 그림은 NUR 페이지 교체 알고리즘의 동작을 보여준다. 알파벳 아래의 첫 번재 숫자는 참조 비트, 두 번째 숫자는 변경 비트를 나타낸다. 읽기, 쓰기, 변경 작업인지는 정확하게 안써놨으니 모든 작업은 읽기 연산으로 가정한다. 따라서 위 그림에서 변경 비트가 1이 되는 경우는 없다. 또한 (0,0)인 페이지가 여러 개일 때는 가장 위에 있는 페이지를 대상 페이지(victim page)로 선정하였다.

위 그림에서 처음 메모리에 올라온 모든 페이지의 참조 비트와 변경 비트는 (0,0)이다. 이후 메모리 접근 순서 5번에서 페이지 B에 접근하면 페이지 B의 비트가 (1,0)으로 바뀐다. 다음으로 메모리 접근 순서 6번에서 페이지 A에 접근하면 페이지 B는 대상 페이지에서 제외되고 페이지 C와 D중 가장 위에 있는 페이지 D가 스왑 영역으로 쫒겨난다. 최종적으로 페이지 성공 횟수는 5회이다. 이는 LRU 페이지 교체 알고리즘의 페이지 성공 횟수와 같은데, 단 2bit만 추가하여 LRU 페이지 교체 알고리즘과 비슷한 성능을 보인 것이다.

최적 근접 알고리즘인 LRU, LFU, NUR 페이지 교체 알고리즘의 성능은 거의 비슷하며 FIFO 페이지 교체 알고리즘보다 우수하다. 이 중에서 NUR 페이지 교체 알고리즘은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 뿐만 아니라 쉽게 구현할 수 있다는 장점 덕분에 가장 많이 사용되고 있다.

8. FIFO 변형 알고리즘

FIFO 페이지 교체 알고리즘은 메모리에 올라온 순서만 고려하고 자주 사용하는 페이지를 고려하지 않기 때문에 성능이 좋지 않다. 이러한 단점을 개선한 알고리즘으로 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다. 이 두 알고리즘은 FIFO 페이지 교체 알고리즘의 방식을 기본으로 하되 페이지에 접근할 때마다 순서의 변화를 주어 성능을 향상한다.

8.1 2차 기회 페이지 알고리즘(second chance replacement algorithm)

2차 기회 페이지 알고리즘(second chance replacement algorithm)은 FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용하지만, 차이점은 특정 페이지에 접근하여 페이지 부재(page fault)없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지(page fault)에서 제외한다는 것이다. 즉, 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 준다는 것이다.

위 그림은 2차 기회 페이지 교체 알고리즘의 동작을 보여준다. FIFO 페이지 교체 알고리즘과 비교하여 메모리 접근 순서 5번에서 맨 앞에 있던 페이지 B는 성공한 후 큐의 맨 뒤로 옮겨진다. FIFO 페이지 교체 알고리즘에서 맨 앞에 있던 페이지 B는 성공한 후 큐의 맨 뒤로 옮겨진다. FIFO 페이지 교체 알고리즘에서는 큐의 맨 뒤로 옮겨지면 대상 페이지(victim page)로 선정될 확률이 줄어든다. 2차 기회 페이지 교체 알고리즘의 페이지 성공 횟수는 FIFO 페이지 교체 알고리즘보다 하나 더 많은 4이다.

일반적으로 2차 기회 페이지 교체 알고리즘의 성능은 LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고, FIFO 페이지 교체 알고리즘보다 약간 높은 것으로 알려져 있다. 그러나 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가되는 것이 단점이다.

2차 기회 페이지 교체 알고리즘은 FIFO 페이지 교체 알고리즘을 변형한 것이기 때문에 2차 기회 FIFO 페이지 교체 알고리즘(second chance FIFO page replacement algorithm)이라고도 한다.

8.2 시계 알고리즘(clock algorithm)

시계 알고리즘(clock algorithm)은 2차 기회 페이지 교체 알고리즘과 유사하여 두 알고리즘을 같은 알고리즘으로 보기도 하지만 실제 구현은 서로 다르다.

위 그림은 시계 알고리즘의 특징을 보여준다. 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용하는 것이 가장 큰 차이점이다.

시계 알고리즘에서는 스왑 영역으로 옮길 대상 페이지(victim page)를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 바닥으로 내려가면 다음에는 다시 큐의 처음을 가리키게 된다. 위 그림에서 보듯이 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부르는 것이다.

위 그림은 시계 알고리즘의 동작을 보여준다. 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가된다. 참조 비트의 초깃값은 0이며, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경된다. 시계 알고리즘의 대상 포인터는 메모리가 꽉 찰 경우 스왑 영역으로 쫒겨날 페이지를 가리킨다. 만약 가리키는 페이지가 스왑 영역으로 쫒겨나면 대상 포인터를 밑으로 이동한다. 이때 참조 비트까 1인 페이지는 건너뛰고, 메모리의 바닥에 도착하면 원형 큐처럼 다시 메모리의 상단으로 이동한다. 이렇게 참조 비트가 1인 페이지를 대상 페이지에서 제외하는 이유는 2차 기회 페이지 교체 알고리즘처럼 기회를 한 번 더 주기 위해서이다. 그러나 대상에서 제외되는 경우는 단 한 번뿐이고, 참조 비트까 1인 페이지를 건너뛸 때는 0으로 바꿔놓는다. 이는 한 바퀴를 돌아 다시 대상 포인터가 오면 제외하지 않겠다는 의미이다.

위 그림의 동작을 메모리 접근 순서별로 사펴보면 다음과 같다.
1. 1번에서 페이지 A가 메모리에 올라오면 대상 포인터는 페이지 A를 가리킨다.
2. 2,3에서 페이지 B, C가 메모리에 올라온다.
3. 4번에서 대상 포인터가 가리키는 페이지 A가 스왑 영역으로 가고 페이지 D가 메모리에 올라온다. 대상 포인터는 한 칸 아래인 페이지 B로 이동한다.
4. 5번에서 페이지 B가 페이지 참조에 성공하면 페이지 B의 참조 비트는 1이 되어 기회를 얻는다. 대상 포인터는 페이지 B의 참조 비트를 0으로 만든 후 한 칸 아래인 페이지 C로 이동한다.
5. 6번에서 대상 포인터가 가리키는 페이지 C가 스왑 영역으로 가고 페이지 A가 메모리에 올라온다. 대상 포인터는 원을 돌아 메모리의 맨 위인 페이지 D로 이동한다.
6. 7,8번에서 페이지 B,A를 성공적으로 참조하여 참조 비트를 1로 바꾼다.
7. 9번에서 대상 포인터가 가리키는 페이지 D가 스왑 영역으로 가고 페이지 B, A 둘다 참조비트가 1이므로 0으로 변경한 후 건너뛴다. 대상 포인터는 메모리를 돌아서 맨 위의 페이지 C를 가리킨다.

시계 알고리즘은 대상 포인터와 각 페이지당 참조 비트 하나만 추가하면 되기 때문에 NUR 페이지 교체 알고리즘보다 추가 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 것이 단점이다.