[OS/운영체제] 페이지 교체 (Page Replacement) - (2)

FIFO (First-In, First-Out) Page Replacement

FIFO는 가장 단순한 페이지 교체 알고리즘으로, 메모리에 옮겨진 메모리들 중 가장 오래된 페이지를 Victim으로 선택한다. 각 페이지가 메모리로 옮겨진 시간을 직접 기록하는 것이 아니라, FIFO 큐(Queue)를 생성해 메모리의 모든 페이지를 담아 놓는다.

FIFO Page Replacement Algorithm

 

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다.

다음으로 2번 페이지의 요청에서 페이지 결함이 발생하고, FIFO 알고리즘에서는 가장 먼저 프레임을 할당받았던 7번 페이지를 Victim으로 선택해, 7번 페이지를 디스크에 기록하고 원래 7번이 할당받은 프레임을 2번 페이지에 새로 할당한다.

 

Belady's Anomaly

다음과 같은 참조 문자열에 대해 FIFO 페이지 교체 알고리즘을 적용해보자.

다음 표는 프레임의 수에 따라 발생하는 페이지 결함의 수를 나타낸 그래프이다.

프레임 수에 따른 페이지 결함 발생 횟수

프레임이 4개일 때, 프레임이 3개인 경우보다 더 많은 프레임을 보유하고 있음에도 불구하고, 더 많은 페이지 결함이 발생하였다. 일반적으로 더 많은 프레임을 보유하면 그만큼 더 성능이 향상될 것으로 기대하지만, 일부 페이지 교체 알고리즘에서는 그 반대의 결과가 나오기도 한다. 이를 Belady's Anomaly라 한다.

 

OPT (Optimal) Page Replacement

Belady's Anomaly가 발견된 후, 결과적으로 모든 알고리즘 중 가장 적은 페이지 결함을 나타내고 Belady's Anomaly가 발생하지 않는 최적의 페이지 교체 알고리즘이 연구되었다. 

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

Optimal Page Replacement Algorithm

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다.

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

프로세스 스케줄링의 SJF 알고리즘과 마찬가지로, Optimal 페이지 교체 알고리즘은 참조 문자열의 미래 내용을 알고 있어야 한다는 전제가 필요해 구현하기가 어렵다는 단점이 있다.

 

LRU (Least Recently Used) Page Replacement

Optimal 페이지 교체 알고리즘은 실현 불가능하지만, 이와 유사한 알고리즘은 가능하다. FIFO 알고리즘과 OPT 알고리즘의 가장 큰 차이는 FIFO 알고리즘은 페이지가 메모리에 옮겨지는 시간을 사용하고, OPT는 페이지가 실제로 사용된 시간을 사용한다는 것이다.

만약 우리가 과거 참조 내용을 통해 근미래의 참조를 추정할 수 있다면 가장 오랜 기간동안 사용되지 않은 페이지를 교체할 수 있을 것이다. 이러한 접근이 LRU 페이지 교체 알고리즘이다.

LRU 알고리즘은 각 페이지가 마지막으로 사용된 시간을 사용한다. 페이지 교체가 필요할 때, 지금까지 가장 오랜 기간동안 사용하지 않은 페이지를 Victim으로 선택한다. 

LRU Page Replacement Algorithm

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다.

이후 2번 페이지에서 페이지 결함이 발생하면, 프레임이 할당된 페이지들 중 가장 오랫동안 사용되지 않은 페이지를 선택한다. 이 경우에는 7번 페이지가 해당한다.

다음 0번 페이지에 대한 참조에서는 페이지 결함이 발생하지 않는다.

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

LRU 알고리즘은 페이지 교체 알고리즘 중 자주 사용되고, 좋은 성능을 낸다. 문제는 LRU 알고리즘에서 마지막으로 사용된 시간을 어떻게 결정하느냐인데, 이 부분에서 하드웨어적 지원이 필요할 수도 있다. 

 

Counter를 사용한 구현

페이지 테이블 항목에 가장 마지막으로 사용된 시간을 기록하는 것이다. (CPU의 clock이나 counter를 사용) 이 방법에서는 항상 페이지가 마지막으로 참조된 시간을 유지해야 한다. (변경이 발생했을 때 기록) 또한 clock의 오버플로우도 고려되어야 한다.

 

Stack을 사용한 구현

페이지 번호들을 stack구조로 저장하여 구현하는 방법이다. 페이지가 참조되면, 스택에서 해당 페이지 번호를 삭제하고 다시 push한다. (그 페이지 번호는 스택의 top에 존재하게 된다)

스택을 사용한 방법

이 방법을 사용하면 항상 가장 최근에 참조된 페이지는 stack의 top에 있고, 가장 오랫동안 참조되지 않은 페이지는 stack의 bottom에 존재하게 된다.

 

LRU-Approximation Page Replacement

LRU 알고리즘을 구현하기 위해선 적절한 하드웨어의 지원이 필요하다. 하지만 하드웨어의 지원을 받을 수 없다면 다른 페이지 교체 알고리즘을 사용해야 할 것이다.

많은 시스템들은 이러한 상황에서 참조 비트(Referenct bit)를 지원한다. 참조 비트는 페이지 테이블 항목에 존재하며, 페이지가 참조될 때 하드웨어에 의해 설정된다. 

참조 비트는 최초 0으로 초기화되어 있으며, 사용자 프로세스가 실행되면 각 참조되는 페이지들에 대한 참조 비트는 1로 설정된다. 이 참조 비트를 통해 어떤 페이지가 프레임에 할당된 후 사용되지 않았는지 알 수 있지만, 페이지가 사용된 순서는 알 수 없다. 이 정보가 많은 LRU-Approximation 페이지 교체 알고리즘의 기반이 된다.

 

Additional Reference Bits Algorithm

우리는 참조 비트를 일정 시간 간격으로 기록함으로써 페이지 참조 순서에 대한 추가적인 정보를 얻을 수 있다.

참조 비트의 순서를 나타내는 8비트(1바이트)를 각 페이지마다 따로 저장하고, 일정 시간 간격으로 참조 비트를 기록하는 것이다. 예를 들어 총 8번의 시간 간격 동안 참조 비트를 기록했을 때, 기록된 비트가 00110001이라면 처음과 5, 6번째의 시간 간격 중에 참조가 발생했다는 의미이다.

8번 이후의 시간 간격 동안 기록되는 참조 비트는 기존의 8비트 수를 right shift하여 기록한다. 00110001에서 다음 시간 간격에 페이지가 참조되었다면, 다음 비트는 10011000이 된다. 따라서 8비트의 참조 비트 기록을 정수로 변환하였을 때, 가장 오랫동안 참조되지 않은 페이지는 가장 낮은 정수값을 갖게 된다.

동일한 정수값을 가지는 페이지가 여러 개 존재한다면, FIFO 알고리즘 등으로 하나의 페이지를 Victim으로 선택한다.

 

Second-Chance Algorithm

Second-Chance 알고리즘은 기본적으로 FIFO 알고리즘에 기반을 둔다. 대신 페이지가 선택되었을 때 그 페이지를 교체하지 않고, 그 페이지의 참조 비트를 본다.

Second-Chance Algorithm

만약 참조 비트가 0이라면, 그 페이지를 교체한다. 하지만 참조 비트가 1이라면, 그 페이지는 교체되지 않고 한 번의 기회를 더 얻게 된다. 이 때 해당 페이지의 참조 비트는 0으로 초기화된다. 페이지 선택은 다음 FIFO 페이지로 넘어간다.

만약 FIFO 알고리즘을 통해 그 페이지를 다시 선택했을 때, 그 페이지의 참조 비트가 또 1이라면 그 페이지는 교체되지 않는다. 즉, FIFO 알고리즘을 통해 페이지가 선택되었을 때, 그 페이지의 참조 비트가 1인 한 그 페이지는 교체되지 않는다.

참조 비트가 0인 페이지를 찾을 때까지 페이지를 계속 순환하여 탐색하야 하므로, Second-Chance 알고리즘은 환형 큐(Circular Queue)를 통해 구현된다. 

 

Enhances Second-Chance Algorithm

Second-Chance 알고리즘을 참조 비트 및 수정 비트(Modify bit)를 한 쌍으로 사용하여 향상시킬 수 있다.

(참조 비트, 수정 비트) 쌍의 값에 따른 의미는 다음과 같다.

 - (0, 0) : 최근에 사용되지도 않았고, 수정되지도 않은 페이지다. 이는 교체하기 가장 적합한 페이지다.

 - (0, 1) : 최근에 사용되진 않았지만 수정된 페이지다. 이 페이지를 교체하려면 페이지를 디스크에 써야 하기 때문에, 교체하기에 그렇게 좋은 페이지는 아니다.

 - (1, 0) : 최근에 사용되었지만 수정되진 않은 페이지다. 다음 순환에서 교체될 가능성이 높다.

 - (1, 1) : 최근에 사용되었으며 또한 수정된 페이지다. 다음 순환에서 교체될 수는 있지만, 교체되기 위해서는 페이지를 디스크에 써야 한다.

 

Counting-Based Page Replacement

LFU (Least Frequently Used)

LRU는 순환 큐에서 해당 페이지를 보는 순간 참조 비트 값에 따라 페이지를 교체한다. 따라서 실제로는 매우 자주 사용되는 페이지이지만 순환 큐에서 우연히 참조 비트가 0을 갖게 되어 교체될 수도 있다.

따라서 페이지가 사용된 횟수를 기록해 그 횟수가 가장 낮은 페이지를 교체하는 방법이다.

 

MFU (Most Frequently Used)

count가 가장 작은 페이지가 방금 들어왔을 것이고, 아직 사용되지 않았다는 판단에 기반을 둔다.

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.