302. 클럭 알고리즘 (Clock Algorithm)

핵심 인사이트 (3줄 요약)

본질: 클럭(Clock) 알고리즘은 하드웨어 비용이 비싼 LRU(Least Recently Used)를 직접 구현하는 대신, **참조 비트(Reference Bit)**를 활용하여 최근에 쓰인 페이지는 살려주고 안 쓰인 페이지를 골라내는 LRU 근사(Approximation) 알고리즘이다.

가치: 각 페이지마다 단 1비트의 꼬리표만 있으면 되므로 구현이 극도로 단순하면서도, 실제 성능(적중률)은 완벽한 LRU와 거의 대등하여 현대 운영체제(Linux, Windows 등)의 실질적인 표준으로 자리 잡았다.

융합: '2차 기회(Second Chance)'라는 자비로운 철학을 바탕으로 원형 큐(Circular Queue) 구조를 빙글빙글 돌며 Victim을 찾으며, Dirty Bit와 결합하여 디스크 쓰기 비용까지 고려한 지능형 교체로 확장된다.

Ⅰ. 개요 및 필요성

개념: 페이지들을 원형 리스트(큐)로 연결하고, '시계 바늘'이라 불리는 포인터가 돌아가며 각 페이지의 참조 비트를 검사하는 방식이다. 참조 비트가 1이면 0으로 깎고 다음으로 넘어가며, 0인 페이지를 만날 때만 쫓아낸다.
필요성: LRU는 이론상 훌륭하지만, 페이지가 수백만 개일 때 매 클럭마다 사용 순위를 정렬(Stack 관리)하는 것은 CPU 입장에서 재앙적인 오버헤드다. 클럭 알고리즘은 **"정확히 누가 제일 안 쓰였는지 순위를 매길 필요는 없다. 그냥 한 바퀴 도는 동안 한 번도 안 쓰인 녀석만 찾아도 충분하다"**는 실용주의적 발상에서 탄생했다.
💡 비유: 교실 복도를 빙글빙글 도는 선생님(포인터)이 학생들 책상을 봅니다. 책을 펴고 공부 중인 애(R=1)는 한 번 봐주고 책만 덮어둡니다(R=0). 다음 바퀴 때도 여전히 책이 덮여 있으면(R=0), 걔는 공부 안 한 것으로 간주하고 교실 밖으로 내보내는 합리적 감시 시스템입니다.
등장 배경: 초기 가상 메모리 설계자들은 FIFO의 멍청함과 LRU의 복잡함 사이에서 괴로워했다. 1968년 코바토(Corbato)가 제안한 'Second Chance' 알고리즘은 단 1비트의 하드웨어 지원만으로 LRU를 훌륭하게 흉내 냈고, 이후 모든 상용 OS의 핵심 엔진이 되었다.

┌──────────────────────────────────────────────────────────────┐
│             클럭 알고리즘(Clock Algorithm)의 순환 탐색 메커니즘            │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  [페이지 큐]   [P0:1]  [P1:0]  [P2:1]  [P3:1]  [P4:0]        │
│                 ↑ (현재 바늘 위치)                            │
│                                                              │
│  [동작 시나리오]                                              │
│  1. P0의 참조비트가 1이네? -> 기회 한 번 더 준다!               │
│  2. [P0:1] -> [P0:0] 으로 비트 깎고 바늘은 P1으로 이동.           │
│  3. P1의 참조비트는 0이네! -> "넌 한 바퀴 동안 안 쓰였구나!"      │
│  4. P1을 즉시 퇴출(Eviction)하고 새 페이지를 이 자리에 앉힘.      │
│  5. 새 페이지의 참조비트는 다시 1로 세팅, 바늘은 P2로 이동.        │
│                                                              │
│  * 핵심 원리: "죽기 전에 한 번의 기회를 더 준다 (Second Chance)"   │
└──────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 헬스장 회원을 정리할 때, "어제 온 사람"을 찾는 게 아니라 "한 달간 한 번도 안 온 사람"을 찾는 방식입니다. 선생님이 한 바퀴 돌 때까지 출석 도장을 안 찍은 게으른 회원만 골라내는 시스템입니다.

Ⅱ. 아키텍처 및 핵심 원리

참조 비트(Reference Bit)의 하드웨어 마법

클럭 알고리즘이 빠른 이유는 하드웨어가 일을 다 해주기 때문이다.

CPU가 어떤 페이지를 읽거나 쓸 때, MMU(하드웨어)는 조용히 해당 페이지의 Reference Bit를 1로 토글한다.
OS(소프트웨어)는 이 비트를 읽기만 하면 된다. 소프트웨어가 일일이 누가 쓰였는지 기록할 필요가 전혀 없다.

2차 기회 (Second Chance)의 자비

바늘이 가리키는 페이지가 R=1이면, 하드웨어가 찍어준 '공부 열심히 함' 인증 마크다.
OS는 이 마크를 지우고(R=0) 한 번 봐준다. 만약 이 페이지가 진짜 중요해서 금방 또 쓰인다면, 바늘이 다시 돌아오기 전에 하드웨어가 다시 R=1로 바꿔줄 것이다.
바늘이 다시 돌아왔을 때도 여전히 R=0이라면, 그 페이지는 정말로 아무도 찾지 않는 '죽은 페이지'이므로 안심하고 쫓아낼 수 있다.
📢 섹션 요약 비유: 유효 기간이 지난 쿠폰에 한 번 더 도장을 찍어주며 "다음번에 오시면 써드릴게요"라고 말하는 친절한 사장님의 마음씨와 같습니다. 그사이에 안 오면 정말로 버리는 거죠.

Ⅲ. 비교 및 연결

FIFO vs LRU vs Clock 알고리즘 비교

비교 항목	FIFO	LRU	Clock (NUR)
하드웨어 지원	없음	고가 (Stack/Counter)	저가 (1비트 참조비트)
알고리즘 복잡도	최하	최고	낮음 (포인터 순회)
적중률 (성능)	낮음	최상	상 (LRU에 근접)
벨라디의 모순	발생함	발생 안 함	발생 안 함

확장판: Enhanced Clock (개선된 클럭 알고리즘)

단순 참조 비트(R) 외에 수정 비트(M, Dirty Bit)까지 함께 고려하는 지능형 방식이다. 쫓아낼 때 **"덜 쓰였으면서도 수정 안 된 놈(M=0)"**을 1순위로 찾는다. 왜냐하면 수정된 놈을 쫓아내면 디스크에 쓰는 비용이 추가로 들기 때문이다.

(R=0, M=0): 최고 효율의 Victim. 즉시 버림.
(R=0, M=1): Victim 후보. 하지만 디스크에 써야 하므로 2순위.
(R=1, M=0): 최근 사용됨. 기회 줌.
(R=1, M=1): 최근 사용 및 수정됨. 가장 나중에 버림.

📢 섹션 요약 비유: 방 정리를 할 때 "오래 안 쓴 물건" 중에, "그냥 버려도 되는 것(Clean)"을 "먼저 씻어서 넣어야 하는 것(Dirty)"보다 먼저 버리는 아주 상식적이고 알뜰한 정리법입니다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

리눅스 페이지 회수 데몬 (kswapd) 리눅스 커널의 메모리 관리자인 kswapd는 거대한 클럭 알고리즘의 변형이다. 리눅스는 페이지를 Active List와 Inactive List로 나누고, 바늘이 돌면서 Active에 있는 페이지를 Inactive로 내리고, Inactive에서 끝까지 살아남지 못한 놈을 스왑 영역으로 쫓아낸다. 실무 엔지니어는 vmstat의 sr(scan rate)을 보며 클럭 바늘이 얼마나 미친 듯이 돌고 있는지를 통해 메모리 압박 상태를 진단한다.
클라우드 고밀도 컨테이너 환경 하나의 물리 서버에 수백 개의 Docker 컨테이너를 올릴 때, 각 컨테이너의 페이지를 관리하는 오버헤드가 크면 시스템이 멈춘다. 클럭 알고리즘은 비트 하나로 수천만 페이지를 0.1ms 만에 훑을 수 있는 경량성 덕분에, 클라우드 인프라의 가상 메모리를 지탱하는 1등 공신이 되었다.

도입 체크리스트

OS 튜닝: 시스템의 메모리 스캔 속도가 너무 빠르다면(CPU 점유율 상승), 이는 클럭 알고리즘이 쫓아낼 놈을 못 찾아서 헛바퀴를 돌고 있다는 뜻이다. 이때는 페이지 교체 알고리즘을 탓할 게 아니라 물리 메모리를 증설해야 한다.
📢 섹션 요약 비유: 경찰이 한 명인데(OS), 범죄자(Victim)를 찾으려고 전국을 다 뒤지면 나라가 망합니다. 동네마다 CCTV(참조비트)를 달아두고 앉아서 모니터만 보고 범인을 골라내는 클럭 알고리즘의 효율성이 현대 사회를 유지하는 비결입니다.

Ⅴ. 기대효과 및 결론

정량적 기대효과

메모리 오버헤드 99% 절감: 모든 참조 시간을 기록하는 LRU 대비, 비트 하나만 쓰는 클럭 알고리즘은 메모리 관리 장부의 크기를 획기적으로 줄여준다.
예측 가능성 확보: 벨라디의 모순을 해결함으로써 하드웨어 증설이 성능 향상으로 직결되는 상업적 신뢰도를 보장한다.

결론

클럭 알고리즘은 **"완벽함보다 충분함(Good enough)"**을 택한 공학적 지혜의 결정체다. 1%의 정확도를 더 얻기 위해 시스템 리소스를 90% 낭비하는 LRU의 결벽증을 버리고, 1비트의 정보만으로 95%의 성능을 이끌어낸 이 알고리즘은 가성비를 중시하는 컴퓨터 아키텍처의 철학을 가장 잘 대변한다.

📢 섹션 요약 비유: 시계 바늘이 한 칸 움직일 때마다 컴퓨터는 조금 더 똑똑해지고, 낡은 기억은 사라집니다. 이 쉼 없는 순환이 있기에 우리의 컴퓨터는 매일 아침 새것처럼 쌩쌩하게 돌아갈 수 있습니다.

📌 관련 개념 맵

개념 명칭	관계 및 시너지 설명
2차 기회	클럭 알고리즘의 핵심 철학으로, 한 번 더 기회를 주어 지역성을 보호함.
참조 비트	하드웨어가 찍어주는 유일한 단서이자 알고리즘의 연료.
NUR (Not Used Recently)	최근에 사용되지 않은 것을 버린다는 클럭 알고리즘의 또 다른 학술적 명칭.
Active/Inactive List	현대 OS에서 클럭 알고리즘을 구현할 때 사용하는 효율적인 자료 구조.
Dirty Bit	교체 비용(디스크 쓰기)을 결정짓는 클럭 알고리즘의 보조 판단 장치.

👶 어린이를 위한 3줄 비유 설명

클럭 알고리즘은 선생님이 시계 방향으로 빙글빙글 돌면서 친구들의 책상을 검사하는 거예요.
공부하고 있는 친구는 칭찬해주고 지나가지만, 자고 있는 친구를 발견하면 그 친구를 교실 밖으로 내보내고 새 친구를 데려오죠.
정확히 누가 제일 오래 잤는지 따지지는 않지만, 엄청 빠르게 잠만보 친구들을 골라내서 교실을 항상 활기차게 만드는 방법이랍니다!