클럭 알고리즘

클럭 알고리즘(Clock algorithm)은 페이지 교체 알고리즘 중 하나로, LRU(Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다.

1 개념

클럭 알고리즘은 각 페이지마다 1비트의 참조 비트(reference bit)를 유지한다. 이 비트는 페이지가 참조될 때마다 1로 설정되며, 페이지 교체가 필요할 때 이를 기준으로 교체 대상을 판단한다.

2 동작 방식

1. 각 페이지 프레임은 원형 큐로 연결되고, 참조 비트와 함께 관리됨

2. 페이지 폴트가 발생하면, "초침"이 가리키는 페이지부터 확인

3. 참조 비트가 0이면 → 해당 페이지를 교체

4. 참조 비트가 1이면 → 0으로 초기화하고 다음 페이지로 이동

5. 교체 대상이 결정될 때까지 반복

3 예시

페이지 프레임 수: 4 프레임 상태: [A¹, B¹, C⁰, D¹] → C의 참조 비트가 0이므로 C가 교체 대상이 됨

4 개선형: Second-Chance 알고리즘

• FIFO 기반 교체 대상에서 참조 비트가 1이면 제거하지 않고 기회를 한 번 더 줌
• 클럭 알고리즘은 Second-Chance를 순환 큐로 구현한 형태

5 장점

• LRU와 유사한 효과를 하드웨어 없이 구현 가능
• 간단한 구조, 낮은 오버헤드
• 실제 시스템에서 많이 사용됨 (예: Linux)

6 단점

• 정확한 LRU가 아니므로 참조 순서를 완전히 반영하지는 못함
• 페이지 수가 많을 경우, 교체 대상 탐색에 시간이 걸릴 수 있음

7 실제 활용

• UNIX 계열 운영체제의 페이지 교체 구현
• Linux의 기본 페이지 교체 알고리즘 중 하나
• 일부 시스템은 클럭 + Aging 알고리즘 혼합 사용

8 같이 보기

• 페이지 교체 알고리즘
• LRU (페이지 교체 알고리즘)
• NUR (페이지 교체 알고리즘)
• 2차 기회 알고리즘
• 참조 비트
• 가상 메모리

9 참고 문헌

• 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