하드디스크는 용량이 굉장히 크기 때문에, 디스크에 큰 가상주소공간을 형성한다면 메모리의 계층 구조 상 메인메모리가 상대적으로 캐시 역할을 하게 된다고 볼 수 있다.

디맨드 페이징을 구현하기 위해서 스와핑이 일어나는데, 캐시가 모자랄 때(메인메모리가 모자랄 때) 디스크로부터 페이지를 읽어와서 바꿔주는 것이다.

그렇기 때문에 처음에 프로세스의 모든 페이지를 메모리에 준비하는게 아니라, cpu가 필요로 할 때 메모리에 올라와있지 않은 페이지에 대해서 페이지 폴트를 발생시킴으로써 디스크로부터 읽어오며, 이를 디맨드 페이징이라고 한다.

그러나 디스크에 액세스하는 속도는 기본적으로 메모리보다 훨씬 느리다.

그래서 접근하려는 페이지가 메모리에 올라와있음으로써 페이지 폴트가 자주 나지 않게, 캐시 힛이 자주 발생하도록 하게 만드는 것이 중요한데, 이런 캐시 힛 비율에 영향을 많이 주는 것이 페이지 교체 정책들이다.

즉, 메모리에서 어떤 페이지를 내보내고 새로운 페이지로 교체해야 잘 교체했다고 소문날까에 대한 고민이다.

Optimal

먼저, 미래를 예측해서 가장 이상적인 방식으로 페이지를 교체해주는 정책이다.

어떤 순서로 페이지에 액세스할 것인지를 다 알고 있기 때문에, 앞으로 가장 오랫동안 접근되지 않을 페이지를 빼버리는 것이다.

가장 최적의 액세스 타임을 보여주지만, 스케줄링에서의 SJF 처럼 현실적으로 구현할 수 없는 정책이다.

모든 미래를 알아야 한다는 굉장히 비현실적인 조건이 필요하기 때문이다.

그래서 이를 최대한 근사시키면서 현실적으로 구현 가능한 알고리즘이 제시되었는데, 이것이 LRU 이다.

Least Recently Used

LRU는, 최근에 액세스되었던 페이지들을 기억함으로써, 그들 중 가장 오랫동안 사용되지 않았던 페이지를 교체 대상으로 정한다.

즉, 미래가 아닌 과거의 정보들을 토대로 하는 점에서 OPT보다 훨씬 현실적인 알고리즘이라고 볼 수 있다.

이렇게 실제로 구현 가능한 정책들 중에서(FIFO, 랜덤 등등)는 일반적으로는 가장 성능이 좋은 편이다(꼭 그렇지만은 않음).

일반적으로 LRU는 연결 리스트 형식으로 구현하여, 시간이 지날수록 접근된지 오래된 노드(페이지)들은 뒤로 밀리고, 최근 사용된 노드들은 앞쪽으로 갱신된다.

또한, 도중에 연결 리스트의 중간에 있는 노드가 액세스되는 경우에는, 해당 노드가 리스트에서 빠져 다시 앞쪽으로 연결되는 방식이다.

이런 방식으로 연결 리스트를 유지할 수 있다면, 페이지를 빼낼 때 단순히 가장 뒤에 있는 노드(가장 오랫동안 접근되지 않은 노드)를 빼면 된다.

애플리케이션 레벨에서 이걸 구현하는 것은 어렵지 않지만, 운영체제가 페이지를 교체할 때 가져다 쓰기에는 그 오버헤드가 심각한 편이다.

애초에 매초 수백만개의 명령어를 처리하는데, 이 때 연결리스트를 매번 업데이트할 경우 그냥 엄청나게 느려지게 될 것이다.

그래서 소프트웨어적으로 구현하지 않고 하드웨어의 지원을 받아, 메모리에 액세스할때마다 하드웨어가 프레임 별로 접근된 타임스탬프를 찍어놓고, 교체가 필요할 시에는 운영체제가 한번 쭉 스캔하여 타임스탬프가 가장 빠른(가장 오래된) 것을 찾아내는 것이다.

그러나 또 문제가 발생하는데, 오늘날의 메모리 용량을 봤을 때 4KB의 페이지가 수백만개 생길텐데, 또 매번 하드웨어적으로 이러한 수많은 프레임을 다 스캔할 수도 없다.

그래서 나온 것이 아래의 Clock 알고리즘이다.

Clock algorithm

이 알고리즘은, 꼭 “가장” 오래된 페이지를 교체해야한다는 생각에서 벗어나서, 적당히 오래된 페이지를 교체해보자는 방식으로 LRU를 근사하는 알고리즘이다.

Clock Algorithm에서 필요한 정보는, 해당 PTE의 use bit이다.

이 플래그는 지금까지 해당 페이지가 사용(액세스, 참조)된 적 있는지 없는지에 대한 값이 되는데, 클럭 알고리즘은 사용된 적 있는 페이지는 교체 대상으로 삼지 않는다.

즉, 메모리의 프레임들을 순환 방식으로 훑어나가며, use bit가 0인 페이지를 찾으면 교체해버리고, 또 폴트가 발생하면 또 다음 페이지를 찾아 교체하는 방식이다.

그렇다면 use bit가 언제 0이 되고 언제 1이 되는지가 중요해지는데, 0인 페이지를 찾을때까지 도중에 만난 1인 페이지들을 0으로 바꿔버린다.

이번에는 사용된 적 있다고 하니까 봐주지만, 만약 내가 메모리를 싹 돌고 다시 방문했는데 아직도 0 상태에 놓여있으면 그때는 교체하겠다는 뜻이다.

물론 그 사이에 해당 페이지에 접근이 일어난다면, use bit가 다시 1로 세팅되기 때문에 다음 검사에서도 교체되지 않고 또 넘어가게 된다.

이렇게 프레임들을 순환하며 탐색하기 때문에, 이를 원형 큐 형태(시계)로 보고, 분침이 마구 돌아가며 프레임을 검사하는 것과 유사하다고 해서 Clock 이라는 이름이 붙었다.

이 때 추가적으로 고려하는 dirty bit에 대한 정보가 있다.

dirty bit는, 해당 페이지에 뭔가 쓰여진(수정된) 적이 있다는 뜻에서 modified bit라고도 불린다.

이 비트가 1이라는 것은, 스왑 공간에 있는 내용을 메모리로 가져온 뒤 해당 내용이 변경되었다는 뜻이기 때문에, 만약 이 페이지를 다시 디스크로 보낼 경우에는 페이지를 디스크에 다시 써줘야된다는 뜻이다.

결국 dirty bit가 1인 페이지를 교체 대상으로 삼아버리면 디스크 IO가 발생하기 때문에 교체가 곧바로 일어나지 않는다.

그래서 use bit가 0이면서 동시에 dirty bit도 0인 페이지를 최우선적으로 빼는 것이 좋다.

N’th Chance

N’th Chance는, 클럭 알고리즘에서 use bit 가 0 이면 바로 교체해버리는게 아니라, 해당 페이지에게 N번까지 기회를 주는 정책이다.

시곗바늘이 프레임들을 지나가다가 사용되지 않은 페이지를 만나면 해당 페이지의 카운터를 1씩 올리다가, 결국 카운터가 N이 될때까지 사용되지 않으면 교체되는 것이다.

즉 N이 1이면 클럭 알고리즘과 동일하기 때문에, N값이 작을수록 클럭에 더 근접하게 되어 효율적이지며, N이 커질수록 LRU에 더 근접하다고 볼 수 있다.

N’th Chance 방식에서는 dirty한 페이지에 대한 고려를 더 섬세하게 할 수 있다.

Dirty한 페이지에는 N값을 크게 설정해서 기회를 더 줌으로써, 디스크 IO를 덜 발생시키도록 유도하는 것이다.

마찬가지로 Clean 페이지에는 N을 작게 설정하여 기회를 덜 줘서, 더티한 페이지보다 상대적으로 빨리빨리 교체될 수 있도록 한다.