37_가상 메모리 페이지 교체(Page Replacement) - LRU 근사 페이지 교체, 계수 기반 페이지 교체 , 페이지 버퍼링 알고리즘

37_가상 메모리 페이지 교체(Page Replacement)

• LRU 근사 페이지 교체, 계수 기반 페이지 교체 , 페이지 버퍼링 알고리즘

 

[LRU 근사 페이지 교체 (LRU Approximation Page Replacement)]

LRU 페이지 교체 지원을 충분히 할 수 있는 하드웨어는 거의 없다. 그러나 많은 시스템은 참조 비트(reference bit)의 형태로 어느 정도 지원하고 있다. 페이지 참조가 있을 때마다(페이지 내의 어떤 바이트라도 읽거나 쓸 때) 하드웨어가 그 페이지에 대한 참조 비트를 설정 한다.

참조 비트는 페이지 테이블에 있는 각 항목과 대응 된다. 얼마가 지나면 페이지 사용의 순서는 모르겠지만 어떤 페이지가 그 동안 사용되었고 어떤 페이지가 한번도 사용되지 않았는지를 알 수 있다. 이러한 부분적인 정보가 많은 LRU 근사 알고리즘의 기본이 된다.

 

• 부가적 참조 비트 알고리즘(Additional Reference Bit Algorithm)이라 하며 일정한 간격마다 참조 비트들을 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다. 각 페이지에 대해 8비트의 참조 비트를 할당 한다. 예를 들어 8 번의 구간 동안 페이지 사용내역을 기록하며 이 8비트 값을 정수로 생각하면 가장 작은 획수를 갖는 페이지가 LRU 페이지가 되고 이를 교체 할 수 있다. 가장 작은 값을 갖는 페이지 모두를 교체할 수도 있고 그들 사이에서 FIFO 방식으로 하나를 선택할 수도 있다.

 

• 이차 기회 알고리즘(Second Chance Algorithm)의 기본(클록 알고리즘이라고도 함)은 FIFO 교체 알고리즘 이다. 이는 페이지가 선택 될 때 마다 참조 비트를 확인 한다. 참조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 FIFO 페이지로 넘어간다. 한 번의 기회를 받게 되면 참조 비트는 해제되고 도착 시간이 현재 시간으로 재설정 된다. 이에 따라 그 페이지는 다른 모든 페이지들이 교체될 때까지 (또는 기회를 받을 때 까지) 교체되지 않는다. 따라서 참조 비트가 계속 설정되어 있을 정도로 자주 사용되는 페이지는 전혀 교체되지 않을 것이다. 이차 기회 알고리즘은 순환큐를 이용하거나 FIFO를 이용한다.

 

 

• 개선된 이차 알고리즘(Enhanced Second Chance Algorithm)은 두 개의 비트를 조합하여 사용하며 가장 낮은 등급을 가지면서 처음 만난 페이지를 교체한다. 이 알고리즘과 단순 클록 알고리즘의 가장 큰 차이는 입/출력 회수를 줄이기 위해 변경된 페이지에 대해 우선순위를 준다는 것이다. 주의점은 교체될 페이지를 찾기까지 여러 번 순환큐를 검사할 수도 있다는 것이다.

(0, 0)	최근에 사용되지도 변경되지도 않은 경우	교체하기 가장 좋은 페이지
(0, 1)	최근에 사용되지는 않았지만 변경된 경우	디스크에 저장해야 하기 때문에 교체에 적당하지 않음
(1, 0)	최근에 사용은 되었으나 변경 되지 않은 경우	곧 다시 사용될 가능성 높음
(1, 1)	최근에 사용되었고 변경도 된 경우	다시 사용될 가능성이 높으며 교체하려면 디스크에 기록이 필요함

 

 

 

[계수 기반 페이지 교체 (Counting Based Page Replacement)]

• LFU(Least frequently used) 알고리즘 : 참조 횟수가 가장 작은 페이지를 교체하는 방법. 활발하게 사용되는 페이지는 큰 참조 값을 갖게 되므로 교체될 가능성이 적다고 판단. 그러나 초기에는 많이 사용되다 그 이후로 다시 페이지를 사용하지 않는 경우 판단이 빗나갈 수 있다. 집중적으로 사용됨으로 인해 사용하지 않더라도 메모리에 머물 가능성이 있다. 해결책으로 참조 횟수를 일정한 시간마다 하나씩 오른쪽으로 이동해서 지수적으로 그 영향력을 감소시키는 방법이 있다.

 

• MFU(most frequently used) 알고리즘 : 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거

 

MFU나 LFU는 일반적으로 잘 쓰이지는 않는다. 이 알고리즘을 구현 하는데는 많은 비용이 들고 최적 페이지 교체 정책을 제대로 근사하지 못하기 때문이다.

 

 

[페이지 버퍼링 알고리즘 (Page Buffering Algorithm)]

페이지 교체 알고리즘과 병행하여 여러 가지 버퍼링 기법이 사용될 수 있다. 시스템들은 자유 프레임 여러 개를 풀(pool)로 가지고 있다가 페이지 부재가 발생하면 예전과 마찬가지로 교체될 페이지를 찾지만 교체도리 페이지의 내용을 디스크에 기록하기 전에 자유 프레임에 새로운 페이지를 먼저 읽어 들이는 방법이다.

 

교체되는 페이지가 쓰여지기를 기다리지 않고 프로세스가 가능한 빨리 시작할 수 있도록 해준다. 이후에 교체될 페이지가 다 쓰여지고 나면 그 프레임은 다시 자유 프레임 풀에 추가 된다.

 

 

또 다른 방법은 자유 프레임 풀은 유지 하지만 그 풀 속 각 프레임의 원리 임자 페이지가 누구였었는지를 기억해 놓는 것이다. 풀 속의 프레임 내용은 그것을 디스크 장치에 썼다고 하더라도 수정되지 않았을 확률이 있으므로 거기에 저장되어 있던 페이지는 프레임이 사용되기 전까지는 다시 사용될 수 있기 때문이다. 이 경우 입/출력은 전혀 필요하지 않으며 페이지 부재가 일어날 때 찾는 페이지가 아직도 풀에 훼손되지 않은 채로 남아 있는지 검사한 후 만약 없으면 그 때 디스크에서 페이지를 읽어 들인다.

 

[참고자료]

Operating System Concepts / 홍릉과학출판사