페이징 알고리즘에서의 LRU와 클럭 알고리즘에 대한 고찰

LRU 알고리즘은 메모리 내에 있는 각 페이지마다 카운터(counter)를 설치하여 최근에 가장 적게 사용된 페이지가 제거하도록 한다.

FIFO에 비해 구성이 어렵다는 단점도 있다. 원리를 보면 페이지가 참조될 경우 페이지의 카운터는 0으로 설정된다.

그리고, 일정한 시간 간격 후에는 페이지의 카운터를 1씩 증가하여 가장 최근에 가장 적게 사용된 페이지는 가장 높은 갖게 되어 이를 제거하면 된다.

이때 사용된 카운터를 수명 레지스터(life register)라 한다. 메인 메모리는 프로세스를 자유 큐(Free queue) 에 캐시를 보충하기 위해

LRU 알고리즘은 페이지 데몬에 의하여 사용된다. 페이지 데몬은 메모리의 페이지들을 모두 받아들이고, 페이지들을 소유하지만

사용하지는 않는다. 페이지 데몬이 LRU 절차에 의해 자유화 시킬 페이지를 검색하는 것을 “스캐닝(scanning)”이라 한다.

많은 페이지들을 필요로 하면, 페이지 데몬의 스캔은 빨라진다. “스캔 비율(scan rate)”는 얼마나 많은 페이지들을 매초마다 확인하고,

메모리가 얼마나 부족한지를 가리킨다. 클럭(clock) 알고리즘은 시스템에 있는 모든 메모리를 연결하여 마치 하나의 원을 만들고

시계의 시,분 바늘처럼 2개의 바늘의 준다. 이때 두 바늘의 차이를 handspreadpages라하며, 하나의 바늘은 맨 처음(front hand)을 가리키며,

다른 하나는 마지막(rear hand)를 가리킨다. 만약, 메모리가 부적하면 페이지 데몬은 두 바늘을 동시에 움직이면서, 맨 처음(front hand)는

해당 페이지의 접근 비트를 정리 (clear)하고, 마지막(rear hand)는 해당 페이지에 접근 비트가 설정되어 있는지 조사를 한다. 접근 비트가 설정 되어

있지 않을 경우 해당 페이지를 자유화 시킨다, 그리고, 해당 페이지는 접근이 이루어 진다면 H/W적인 MMU에 의하여 접근 비트가 자동으로 설정된다.