클럭 알고리즘 (Clock Algorithm / NUR)

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

1. 본질: 클럭 알고리즘 (또는 NUR: Not Used Recently)은 가장 완벽한 페이지 교체 알고리즘인 LRU(최근 최소 사용)가 가진 $O(N)$의 거대한 연결 리스트 탐색 및 갱신 오버헤드를 회피하기 위해, 하드웨어의 참조 비트(Reference Bit)와 원형 큐(Circular Queue)를 결합하여 만든 LRU의 가벼운 근사치(Approximation) 모델이다.
2. 가치: 포인터를 조작하는 비싼 소프트웨어 연산 없이 시곗바늘(포인터)을 빙빙 돌리며 비트만 확인(0인지 1인지)하면 되므로, 운영체제 커널이 감당할 수 있는 $O(1)$ 수준의 극강의 탐색 속도를 제공하면서도 LRU와 거의 동일한 캐시 적중률(Hit Rate)을 달성한다.
3. 융합: 이 기법은 단지 참조 여부만 따지는 것을 넘어, "이 페이지가 수정(Dirty)되었는가?"를 알려주는 **수정 비트(Modify Bit)**와 융합되어, "가급적 디스크 쓰기(Swap-out) 비용이 안 드는 깨끗한(Clean) 페이지부터 먼저 버린다"는 2단계 클럭 알고리즘으로 진화하며 현대 Linux 및 Windows의 절대 표준으로 자리 잡았다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

• 개념: 메모리에 있는 페이지 프레임들을 시계테엽처럼 둥글게 원형 큐(Circular Queue) 형태로 연결해 두고, 스케줄러(시곗바늘)가 시계 방향으로 돌면서 각 페이지에 붙어 있는 '참조 비트(Reference Bit)'를 검사하여 0인 녀석을 가차 없이 내쫓는 페이지 교체 알고리즘이다. (그래서 Second-Chance 알고리즘이라고도 불린다).
• 필요성: 순수 LRU는 완벽했지만 무거웠다. 메모리를 읽을 때마다(초당 10억 번) 리스트의 노드를 맨 앞으로 옮기는 짓은 CPU를 마비시킨다. OS 설계자들은 "가장 오래전에 쓴 놈을 정확히 1등으로 찾아낼 필요는 없다. 그냥 '최근에 안 쓴 놈들 무리' 중에서 아무나 대충 빨리 찾아내서 버려도 성능엔 별 차이가 없다"는 타협점(Heuristic)을 찾아냈다.
• 💡 비유: 주차장에서 가장 오래 주차된 차를 찾기 위해 **'모든 차의 입차 시간을 엑셀로 정확히 정렬(순수 LRU)'**하는 게 아니라, 주차 요원이 주차장을 빙빙 돌면서 **'차 앞유리에 먼지가 쌓인(최근에 안 탄) 차를 발견하면 대충 견인(클럭 알고리즘)'**해 버리는 융통성 있는 방식과 같다.
• 등장 배경: FIFO의 멍청함(Belady의 모순)과 LRU의 무거움 사이에서 고통받던 운영체제 학계에, 하드웨어 MMU 칩셋이 "메모리를 읽을 때마다 1비트짜리 스위치(Reference Bit)를 자동으로 켜주겠다"고 지원 사격을 하면서 소프트웨어와 하드웨어가 완벽히 융합된 이 알고리즘이 탄생했다.

  [클럭 알고리즘의 동작 시각화: 시곗바늘(Hand)의 순회]

       [ Frame 0 ] (Ref=1) ◀─ (시곗바늘 시작 위치)
     ╱                     ╲
 [ Frame 3 ] (Ref=1)     [ Frame 1 ] (Ref=0)
     ╲                     ╱
       [ Frame 2 ] (Ref=1)
       
  [ 페이지 교체가 필요할 때 시곗바늘의 동작 ]
  1. 바늘이 Frame 0을 봄. Ref가 1이네? "최근에 썼군, 0으로 깎고 한 번 봐줄게(Second Chance)!" 바늘 이동.
  2. 바늘이 Frame 1을 봄. Ref가 0이네? "내가 한 바퀴 돌고 왔는데 아직도 0이야? 넌 쫓겨난다!" 💥
  3. Frame 1의 페이지를 디스크로 내쫓고 새 페이지를 적재함.
  4. 바늘은 Frame 2를 가리키며 다음 희생양을 찾을 준비를 마침.

[다이어그램 해설] 클럭 알고리즘의 마법은 "한 번 봐준다(Second Chance)"는 데 있다. 시곗바늘이 지나갈 때 1을 0으로 깎아둔다. 만약 프로그램이 이 페이지를 자주 쓴다면, 시곗바늘이 다시 한 바퀴를 돌아서 오기 전에 CPU가 이 페이지를 참조하여 하드웨어가 다시 1로 복구시켜 놓을 것이다. 한 바퀴를 돌았는데 여전히 0이라는 것은 "최소 1 주기 동안 한 번도 안 쓰였다(Not Used Recently)"는 명백한 증거가 된다.

• 📢 섹션 요약 비유: 순찰을 도는 경비원입니다. 자고 있는 병사(Ref=0)를 발견하면 깨워서 경고(Ref=0 유지)를 줍니다. 다음 바퀴에 또 와봤는데 또 자고 있으면 가차 없이 영창(디스크)에 보냅니다. 하지만 그사이에 병사가 깨서 일을 하고 있으면(Ref=1), "열심히 하네" 하고 그냥 넘어가는(0으로 깎음) 합리적이고 빠른 순찰 방식입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

하드웨어의 지원: 두 개의 마법 비트 (R & M)

클럭 알고리즘이 진짜 실무(NUR: Not Used Recently)로 작동하려면 페이지 테이블에 존재하는 두 개의 하드웨어 비트를 조합해야 한다.

1. R 비트 (Reference Bit): 참조 비트. 읽거나(Read) 쓰면(Write) 하드웨어가 무조건 1로 세팅한다.
2. M 비트 (Modify Bit / Dirty Bit): 수정 비트. 데이터에 쓰기(Write) 연산을 했을 때만 1로 세팅된다.

이 두 비트를 조합하면 총 4개의 클래스(계급)가 나온다. 스케줄러는 바늘을 돌릴 때 무조건 가장 낮은 계급(클래스 0)부터 1순위로 찾아내어 쫓아낸다.

2단계 클럭 (Two-Handed Clock) 알고리즘

현대 BSD 유닉스나 리눅스는 1개의 바늘이 아니라 2개의 바늘을 돌린다.

• 선행 바늘 (Front Hand): 앞서가면서 R 비트를 0으로 깎아 내리는(에이징) 역할만 한다.

• 후행 바늘 (Back Hand): 선행 바늘과 일정한 각도(시간차)를 두고 뒤따라가며, "아까 쟤가 0으로 깎았는데 아직도 0이야?"를 확인하고 진짜로 페이지를 쫓아내는 살수(Killer) 역할을 한다. 이 두 바늘 사이의 거리(각도)가 곧 페이지가 살아남을 수 있는 "유예 기간(Grace Period)"을 결정하는 핵심 튜닝 파라미터가 된다.

• 📢 섹션 요약 비유: 청소부가 두 명 있습니다. 앞사람(선행 바늘)은 안 쓰는 물건에 노란 딱지를 붙이고 갑니다. 1주일 뒤 뒷사람(후행 바늘)이 와서, 노란 딱지가 여전히 붙어있고 주인이 떼지 않았다면 그 물건을 쓰레기차에 실어 버립니다. 완벽한 숙성(Aging)과 판별의 분업입니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

클럭 알고리즘 vs 순수 LRU vs FIFO 의 실전 포지셔닝

Dirty Bit (M)가 가져온 디스크 I/O 최적화의 혁명

클럭 알고리즘이 진정으로 위대한 이유는 LRU를 베껴서가 아니다. 바로 Modify Bit (Dirty Bit)를 융합하여 교체 비용 자체를 박살 냈기 때문이다.

• 램이 꽉 차서 페이지를 내쫓아야 한다.

• 순수 LRU는 멍청하게 "가장 오래된 놈"인 A를 내쫓는다. 그런데 A는 수정(Dirty)된 페이지라 디스크에 10ms 동안 쓰는(Swap-out) 작업이 필요하다.

• 클럭 알고리즘은 바늘을 돌리다가 "오래됐지만 덜 오래된 B"를 발견한다. 근데 B는 수정 안 된 Clean 페이지다. 클럭은 10ms짜리 스왑을 치느니, 조금 덜 오래된 Clean 페이지 B를 1나노초 만에 날려버리고 새 페이지를 받는다.

• 결과: 클럭은 LRU보다 캐시 히트율이 1~2% 떨어지지만, 끔찍한 디스크 쓰기(Swap-out) 오버헤드를 절반 이하로 줄여 전체 시스템 성능(Throughput)을 압도적으로 높여버린다.

• 📢 섹션 요약 비유: 순수 LRU는 고지식한 원칙주의자라서 "무조건 제일 오래된 놈부터 짐을 싸서 쫓아낸다"며 짐 싸는 데 1시간을 낭비합니다. 클럭(NUR)은 융통성 있는 매니저라, "제일 오래되진 않았지만, 짐이 아예 없어서 당장 1초 만에 쫓아낼 수 있는 놈(Clean 페이지)"을 우선적으로 쫓아내어 방을 초고속으로 비웁니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

1. 리눅스 커널의 Kswapd 데몬 (클럭 알고리즘의 실체): 실무 서버에서 top을 쳤을 때 보이는 kswapd라는 커널 데몬이 바로 이 클럭 알고리즘의 시곗바늘이다.
   • 동작: 시스템의 램 여유 공간이 high watermark 밑으로 떨어지면 잠자고 있던 kswapd가 깨어난다. 그리고 low watermark를 회복할 때까지 백그라운드에서 페이지들의 R 비트를 검사하며 바늘을 미친 듯이 돌려 Clean 페이지는 지우고, Dirty 페이지는 디스크로 몰아낸다.
   • 아키텍트 튜닝: vm.swappiness 값을 0으로 주면 이 시곗바늘이 유저 애플리케이션의 메모리를 건드리지 않게 묶어버릴 수 있다. 반대로 값이 높으면 시곗바늘이 너무 적극적으로 돌아 서버가 스래싱(Thrashing)의 늪에 빠질 수 있다.
2. 데이터베이스 버퍼 풀 (Oracle DB, InnoDB)의 튜닝: DB 엔진은 OS의 페이지 교체(클럭)를 불신한다. 자기가 직접 메모리(버퍼 풀)를 관리한다.
   • 문제: 풀 스캔 쿼리 SELECT * FROM BIG_TABLE을 때리면, 클럭 알고리즘의 바늘이 휙 돌면서 기존 단골 데이터들의 R 비트를 다 0으로 깎고, 스캔된 쓰레기 데이터로 램을 가득 채워버린다 (캐시 오염, Cache Pollution).
   • 실무 조치: 최신 DB 엔진은 단순 클럭을 넘어 Midpoint Insertion LRU 방식을 쓴다. 새로 들어온 데이터를 큐의 맨 앞(Top)이 아니라 중간(Midpoint)에 꽂는다. 그리고 1초 뒤에 "다시 한번" 조회가 일어나야만 진짜 VIP석(Top)으로 올려준다. 풀 스캔으로 한 번 스치고 지나가는 쓰레기 데이터들은 중간에 꽂혔다가 바로 꼬리로 밀려나서 버려지게 만드는 극강의 실무 튜닝이다.

  ┌───────────────────────────────────────────────────────────────────┐
  │     메모리 과부하(OOM) 방어 시 아키텍트의 교체 정책 우회 전략     │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [요구사항: 10GB 짜리 머신러닝(ML) 모델을 메모리에 상주시켜야 함]│
  │                                                                   │
  │   [ ❌ 주니어의 배포 (OS 클럭 알고리즘에 운명을 맡김) ]           │
  │     - 모델을 RAM에 로드하고 예측 API 서빙 시작.                   │
  │     - 결과: 밤사이에 다른 로그 수집 데몬이 램을 쓰면서, OS의      │
  │             시곗바늘(kswapd)이 내 ML 모델의 절반을 디스크로       │
  │             스왑-아웃 시켜버림. 아침에 첫 API 응답 10초 걸림!     │
  │                                                                   │
  │   [ ✅ 시니어 아키텍트의 배포 (mlock 시스템 콜 활용) ]            │
  │     - 코드에 `mlock(모델 주소, 10GB)` 함수를 명시적으로 호출.     │
  │     - 효과: OS 커널에게 "내 메모리엔 절대 시곗바늘(클럭) 대지 마!"│
  │             라고 철창(Pinning)을 쳐버림.                          │
  │     - 결과: 서버 램이 꽉 차면 다른 데몬이 OOM으로 죽을지언정,     │
  │             내 ML 모델은 1년 내내 램에 100% 락인(Lock-in)되어     │
  │             극강의 0.01초 API 지연 시간을 영구 방어함.            │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "OS가 알아서 최적으로 교체해 주겠지"라는 믿음은 일반 PC 사용자에게나 통하는 말이다. 1초의 지연도 허용하지 않는 백엔드 인프라에서는, 중요한 데이터(코어 캐시, ML 모델, 핫 인덱스)가 클럭 알고리즘의 희생양이 되지 않도록 **메모리 락킹(Memory Locking)**을 통해 OS의 오지랖을 물리적으로 박살 내는 것이 아키텍트의 기본 소양이다.

• 📢 섹션 요약 비유: 백화점 청소부(클럭 알고리즘)는 폐점 후 오랫동안 안 만진 물건(R=0)은 다 버립니다. 중요한 프로젝트 서류를 책상 위에 올려두면 다음 날 청소부가 쓰레기인 줄 알고 버립니다(스왑 아웃). 절대 버려지면 안 되는 서류는 청소부가 못 건드리게 유리관(mlock)을 씌워두어야 안전합니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

클럭(NUR) 알고리즘을 통해 운영체제는 링크드 리스트 조작이라는 무거운 소프트웨어 오버헤드 없이 하드웨어 비트 하나만으로 LRU에 필적하는 99%의 캐시 히트율을 달성하며, Dirty Bit 최적화를 통해 끔찍한 디스크 스왑(Swap-out) I/O 비용을 절반 이하로 줄이는 메모리 관리의 극한 가성비를 얻어냈다.

결론 및 미래 전망

클럭 알고리즘(Clock, Second-Chance, NUR)은 이론(LRU)과 현실(오버헤드) 사이에서 인류가 찾아낸 가장 완벽한 타협점이자, 지난 40년간 지구 상의 모든 데스크톱과 서버의 가상 메모리를 지탱해 온 숨은 영웅이다. 하지만 메모리가 테라바이트(TB) 단위로 커지면서, 아무리 O(1) 탐색이라도 시곗바늘이 수천만 개의 4KB 페이지를 빙빙 돌며 검사하는 행위 자체가 백그라운드 CPU 자원을 너무 많이 먹는 한계에 봉착했다. 이에 미래의 클라우드 시스템은 이 자잘한 페이지 교체 검사를 버리고, **컨테이너 단위의 거시적 메모리 통제(Cgroups)**나, 머신러닝 AI가 프로세스의 메모리 접근 패턴을 미리 학습하여 페이지 폴트가 터지기 전에 선제적으로 램과 디스크를 스왑해버리는 **AI 기반 예측형 메모리 관리(Predictive Memory Management)**의 시대로 진화하고 있다.

• 📢 섹션 요약 비유: 클럭 알고리즘은 40년 전 만들어진 완벽한 수동 시계입니다. 톱니바퀴가 완벽하게 맞물려 에러 없이 돌아갑니다. 하지만 짐이 산더미처럼 많아진 현대의 물류 창고(데이터센터)에서는 톱니바퀴만으론 감당이 안 되어, AI가 "어떤 물건이 내일 팔릴지" 미리 예측해서 앞쪽에 꺼내놓는 스마트 물류 창고 시스템으로 진화하고 있습니다.

📌 관련 개념 맵 (Knowledge Graph)

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

1. 냉장고가 꽉 차서 반찬 하나를 버려야 할 때, 엄마는 냉장고를 빙빙 돌며 반찬통을 확인해요.
2. 반찬통에 "어제 먹음"이라는 스티커(R 비트 1)가 붙어있으면, 엄마는 안 버리고 스티커만 딱 떼고 한 번 봐줘요(Second Chance).
3. 계속 빙빙 돌다가 스티커가 없는 반찬(R 비트 0)을 발견하면? "오랫동안 아무도 안 먹었네!" 하고 망설임 없이 쓰레기통(디스크)에 버리는 아주 빠르고 똑똑한 규칙이랍니다!