클럭 알고리즘 편집하기

클럭 알고리즘(Clock algorithm)은 [[페이지 교체 알고리즘]] 중 하나로, [[LRU]](Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다.
==개념==
클럭 알고리즘은 각 페이지마다 1비트의 '''참조 비트(reference bit)'''를 유지한다. 이 비트는 페이지가 참조될 때마다 1로 설정되며, 페이지 교체가 필요할 때 이를 기준으로 교체 대상을 판단한다.
==동작 방식==
1. 각 페이지 프레임은 원형 큐로 연결되고, 참조 비트와 함께 관리됨 2. 페이지 폴트가 발생하면, "초침"이 가리키는 페이지부터 확인 3. 참조 비트가 0이면 → 해당 페이지를 교체 4. 참조 비트가 1이면 → 0으로 초기화하고 다음 페이지로 이동 5. 교체 대상이 결정될 때까지 반복
==예시==
페이지 프레임 수: 4  프레임 상태: [A<sup>1</sup>, B<sup>1</sup>, C<sup>0</sup>, D<sup>1</sup>]  → C의 참조 비트가 0이므로 C가 교체 대상이 됨
==개선형: Second-Chance 알고리즘==
*FIFO 기반 교체 대상에서 참조 비트가 1이면 제거하지 않고 기회를 한 번 더 줌
*클럭 알고리즘은 Second-Chance를 순환 큐로 구현한 형태
==장점==
*[[LRU]]와 유사한 효과를 하드웨어 없이 구현 가능
*간단한 구조, 낮은 오버헤드
*실제 시스템에서 많이 사용됨 (예: Linux)
==단점==
*정확한 LRU가 아니므로 참조 순서를 완전히 반영하지는 못함
*페이지 수가 많을 경우, 교체 대상 탐색에 시간이 걸릴 수 있음
==실제 활용==
*UNIX 계열 운영체제의 페이지 교체 구현
*Linux의 기본 페이지 교체 알고리즘 중 하나
*일부 시스템은 클럭 + Aging 알고리즘 혼합 사용
==같이 보기==
*[[페이지 교체 알고리즘]]
*[[LRU (페이지 교체 알고리즘)]]
*[[NUR (페이지 교체 알고리즘)]]
*[[2차 기회 알고리즘]]
*[[참조 비트]]
*[[가상 메모리]]
==참고 문헌==
*Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
*Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson
*Linux Kernel Documentation - Page Replacement Algorithms
[[분류:운영체제]]
[[분류:가상 메모리]]