[운영체제] Virtual Memory (2) - Page Replacement Algorithm

페이지 교체 알고리즘에는 여러 가지가 존재합니다. 이 중에 어떤 알고리즘을 사용하느냐에 따라 실행시간에 큰 영향을 미칠 수 있으니 최대한 좋은 알고리즘을 선택하는 것이 중요합니다.

 

1. FIFO (First in, First out)

가장 간단한 페이지 교체 알고리즘은 FIFO입니다. 말 그대로 메모리에 올라온 지가 가장 오래된 페이지를 내쫓는 알고리즘이죠. 페이지가 올라온 시간을 페이지마다 기록해도 되고, 페이지들이 올라온 순서대로 큐를 만들어서 관리해도 됩니다. 구현도 쉽고, 이해도 쉽지만, 자주 사용하는 페이지들이 올라온 지 오래되었다는 이유만으로 디스크로 돌아간 뒤 금방 다시 올라와야 하는 상황을 생각해보면 확실히 최적화된 모습의 알고리즘은 아닐 것입니다.

 

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

FIFO의 단점을 고려해서 설걔된 최적 페이지 교체 방법은 바로 앞으로 가장 오랜 시간 동안 사용되지 않을 페이지를 찾아 교체하는 방법입니다. 가장 최적의 알고리즘이긴 하지만 미래에 대한 정보를 구하기가 어렵기 때문에 구현은 어렵습니다.

 

3. LRU(Least-Recently-Used) 

최적의 알고리즘은 구현이 불가능하기 때문에, 조금 시각을 바꾸어 가장 오랜 기간 동안 사용이 되지 않은 페이지를 교체하는 방법이 있습니다. 각 페이지마다 마지막 사용 시간을 저장해 두고, 이 정보를 바탕으로 가장 오랫동안 사용되지 않은 페이지가 선택됩니다. 이러한 LRU는 좋은 알고리즘으로 평가받고 있으며, LRU를 구현할 때는 Counter 또는 Stack 중 하나의 도움을 필요로 합니다.

 

첫 번째로 Counter를 이용한 방법은 CPU 내에 clock을 추가하여 구현합니다. 페이지를 참조할 때 마다 페이지의 사용 시간이라는 필드에 이 시간 값을 복사해주는 것입니다. 교체 시에는 당연히 시간 값이 가장 작은 페이지가 선택됩니다. 

 

두 번째로 Stack을 이용한 방법은 그냥 사용되는 페이지들을 스택에 집어넣는 것입니다. 그리고 한번 사용이 되면 원래 있던 스택에서 꺼내어 다시 가장 위에 넣어줍니다. 즉 최근에 사용된 페이지들이 항상 스택의 위 쪽에 분포하고 있을 것입니다. 스택의 가장 아래쪽의 페이지가 교체될 때 선택되며, 중간의 값을 빼내어야 하는 일이 생기기 때문에 보통 Doubly Linked List로 스택을 구현합니다.

 

4. LRU Approximation Algorithm

LRU를 위한 Counter나 Stack의 지원이 어려운 경우가 있을 수 있습니다. 이럴 때는, 페이지 테이블에 참조 비트(Reference Bit)를 사용하여 LRU 근사 페이지 교체를 수행할 수 있습니다. 참조 비트는 페이지가 참조 되면 값을 1로 바꾸어 저장하는 비트입니다. 물론 처음에는 모두 0으로 시작합니다. 이를 통해 어떤 페이지가 먼저 사용되었는지는 알기 어렵지만, 어떤 페이지가 사용되지 않았는지는 판별할 수 있습니다.

 

LRU Appoximation Algorithm은 이 참조 비트를 이용하여 여러 형태로 구현될 수 있습니다.

 

1. Additional-Reference Bits Algorithm(부가적 참조 비트 알고리즘)

페이지 별로 8 비트의 참조비트를 사용하여 누가 먼저 사용되었는지를 판별할 수 있습니다. 일정한 시간 간격마다, 이 비트들은 우측으로의 shift 연산을 수행하게 됩니다. 즉 00100000이라는 참조 비트가 있었다면, 미리 정해진 일정한 시간 후에는 00010000으로 변하게 됩니다. 그리고 해당 시간 동안에 참조가 한 번이라도 발생하면 가장 왼쪽의 비트를 1로 바꾸어 줍니다. 

 

처음에는 00000000일 것이고 그러다가 참조가 되면 10000000이 되겠죠? 그러다가 시간이 흘러 두번의 Shift가 발생하는 동안 참조가 없으면 00100000이 될 것이고, 다시 참조가 일어나면 10100000으로 변할 것입니다. 이렇게 하면 수가 가장 클수록 최근에 많이 참조된 페이지로 판단이 가능할 것입니다.

 

2. Second-Chance Algorithm (2차 기회 알고리즘)

이 알고리즘은 기본적으로 FIFO 방식에 기초를 둡니다. 하지만 페이지가 선택될 때 마다 참조 비트를 확인하여 참조 비트가 0이면 바로 페이지를 교체하고, 1이면 한 번 더 기회를 주고 다음 페이지를 선택하는 알고리즘입니다. 이렇게 한 번 기회를 받게 되면 참조 비트는 다시 0으로 되돌아갑니다. 

 

이 알고리즘을 구현하기 위해 원형 큐를 많이 사용합니다. 어떤 포인터를 통해 희생될 페이지를 가리키고 해당 페이지가 참조 비트가 0이면 바로 선택되고 0이 아니라면 해당 비트를 0으로 바꾼 뒤, 0인 페이지를 찾을 때 까지 차례로 순환하게 됩니다.

 

3. Enhanced Second-Chance Algorithm

위에서의 2차 기회 알고리즘을 변경 비트까지 이용해서 구현을 하면 더 개선된 형태의 알고리즘을 만들 수 있습니다. 최대한 참조도 되지 않고 변경도 되지 않은 페이지를 먼저 찾아서 선택시켜 주는 것입니다. 여기서는 각각의 페이지를 다음의 4개의 등급으로 분류할 수 있고, 가장 낮은 등급의 페이지부터 선택을 해주면 됩니다.

 

1. (0, 0): 최근에 사용되지도 변경되지도 않은 페이지 - 교체하기 가장 적합한 페이지

2. (0, 1): 최근에 사용은 되지 않았지만 변경은 된 경우 - 교체를 위해 디스크에 접근을 해야함

3. (1, 0): 최근에 사용은 되었지만 변경은 되지 않은 경우 - 이 페이지는 다시 사용될 확률이 높음

4. (1, 1): 최근에 사용되었고 변경도 된 경우 - 최대한 선택을 미뤄야 함

 

 

 

 

여기까지 페이지 교체를 위해 이용되는 가장 유명한 알고리즘들을 살펴보았습니다. 다음 글에서는 운영체제의 마지막 장으로 파일 시스템에 대해서 공부해보도록 하겠습니다. 읽어주셔서 감사합니다.