LOOK 및 C-LOOK (디스크 스케줄링 최적화)

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

본질: LOOK과 C-LOOK은 멍청한 기계식 SCAN(엘리베이터) 알고리즘이 아무 요청도 없는 디스크 양 끝 벽(0번, 199번)까지 무식하게 쿵쿵 찍고 오던 헛수고를 박살 내기 위해, 진행 방향 앞쪽에 더 이상 처리할 요청이 없는지 미리 내다보고(LOOK) 바로 방향을 꺾어버리는 지능형 최적화 알고리즘이다.

가치: 불필요한 허공 헛스윙 이동 거리(Seek Time)를 완벽하게 도려내어 디스크의 기계적 마모를 줄이고, 가까운 곳에 몰려 있는 요청들을 칠 때 기존 SCAN 방식보다 반응 속도(Response Time)를 비약적으로 단축시킨다.

융합: '가장 멀리 있는 요청'을 탐색하는 소프트웨어적 큐(Queue) 검사 연산(CPU 오버헤드)이 미세하게 추가되지만, 그로 인해 얻는 디스크 탐색 시간(ms) 이득이 만 배 이상 크기 때문에 현대 하드디스크(HDD) 환경의 실질적인 디폴트 엘리베이터 로직으로 융합 정착했다.

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

개념:
- LOOK: SCAN(엘리베이터)처럼 양방향으로 움직이되, 디스크 바늘이 가는 길 앞에 더 이상 요청(데이터)이 없으면 벽(0이나 199) 끝까지 가지 않고 그 자리에서 즉시 Turn(반대 방향 턴)을 해버린다.
- C-LOOK (Circular LOOK): C-SCAN처럼 한 방향으로만 훑고 돌아오되, 마지막 요청만 처리하면 벽을 안 찍고 즉시 첫 번째 요청이 있는 곳으로 Rollback(점프 복귀) 해버린다.
필요성: 디스크 트랙이 0부터 199번까지 있다. 현재 바늘은 50번이고 상행 중이다. 제일 멀리 들어온 요청이 120번이다. 멍청한 SCAN 알고리즘은 120번 데이터를 줍고 나서도, 121번부터 199번까지 아무 데이터가 없는데 허공을 가르며 기계 모터를 징징 돌려 199번 벽을 쾅 찍고 나서야 하행선으로 방향을 돌렸다. 이 '아무 의미 없는 허공 스윙 거리(79 트랙 이동)' 동안 CPU와 프로세스들은 넋을 잃고 렉이 걸린다. "아니, 가는 길에 짐이 없으면 눈(LOOK)으로 좀 쓱 보고 걍 쿨하게 바로 턴(Turn)하면 안 돼? 왜 융통성 없이 끝을 찍냐고!"라는 엔지니어들의 딥빡침이 이 스마트한 알고리즘을 탄생시켰다.
💡 비유: SCAN은 융통성 0점의 마을버스고, LOOK은 센스 만점의 셔틀버스다. 마을버스(SCAN)는 종점(199번 트랙)에 내릴 손님이 한 명도 없고 정류장에 탈 사람도 없어도, 무조건 노선표대로 텅 빈 산꼭대기 종점까지 올라가서 도장을 찍고 내려와야 한다(기름값/시간 낭비). 반면 셔틀버스(LOOK) 기사님은 출발 전 명부를 쓱 보고(Look), "오늘 제일 멀리 가는 손님이 5정거장 앞이네? 그럼 5정거장에 손님 내려주고 종점 안 가고 바로 차 돌려서(Turn) 내려올게요!"라고 해버린다. 승객(CPU) 입장에선 차가 빨리빨리 돌아오니 배차 간격(응답 속도)이 미친 듯이 짧아져 환호하게 된다.
등장 배경 및 휴리스틱(Heuristic)의 한계 돌파:
1. SCAN의 맹목적 벽 찍기: 양 끝단에 데이터가 없어도 무조건 0과 MAX를 왕복하며 I/O 레이턴시 낭비 폭발.
2. 큐(Queue) 훔쳐보기 기술 도입: 스케줄러가 바늘을 움직이기 직전, 큐에 남아있는 최대/최솟값을 $O(1)$로 뽑아내어 바늘의 '논리적 끝점'을 재정의함.
3. 현업 스탠다드 등극: C-SCAN의 완벽한 공평성에 LOOK의 동선 다이어트가 결합된 C-LOOK이 기계식 하드의 궁극적 최종 진화형으로 교과서를 덮음.

┌───────────────────────────────────────────────────────────────────────────┐
│        멍청한 C-SCAN vs 똑똑한 C-LOOK의 허공 스윙(헛발질) 절약 시각화     │
├───────────────────────────────────────────────────────────────────────────┤
│                                                                           │
│ [ 큐 요청 순서 ]:  98, 183, 37, 122, 14, 124                              │
│ [ 헤드 위치 ]: 53번 트랙 / [ 199번을 향해 상행 중! ]                      │
│                                                                           │
│ ▶ 1. 멍청한 C-SCAN (무조건 199번 벽 끝까지 가서 점프)                     │
│   14   37     53     98    122 124        183      199                    │
│   │    │      [시작] ──▶     │  │          │        │                     │
│   │    │                    └─────────▶ │        │                        │
│   │    │                                  └───────▶ ││ (허공 낭비)
│ 0 │    │ ◀─ (199 찍자마자 0번 끝으로 미친 듯이 뒤로 날아감)  ───┘         │
│ └─▶│    │                                                                 │
│                                                                           │
│ ▶ 2. 센스 만점 C-LOOK (가장 먼 183번까지만 가고 바로 점프!)               │
│   14   37     53     98    122 124        183      199                    │
│   │    │      [시작] ──▶     │  │          │                              │
│   │    │                    └─────────▶ │                                 │
│   │    │                                  └───────▶                       │
│   │ ◀─ (183번 줍자마자, "뒤에 없지?" 확인 후 14번으로 직통 점프!)         │
│   └─▶│                                                                    │
│                                                                           │
│ ✅ 결과: 183~199번 허공(16트랙) 이동 + 14~0번 허공(14트랙) 이동           │
│         총 30트랙(왕복 60트랙)의 무의미한 쇳덩어리 헛수고를 완벽히 도려냄!│
└───────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 그림에서 보듯 C-LOOK은 '쓸데없는 짓'을 안 한다. 바늘이 183번을 줍는 찰나에 스케줄러가 큐를 확인(Look)한다. "더 이상 큰 번호 없지? 오케이 그럼 벽(199) 안 찍는다. 제일 작은 요청 번호가 뭐야? 14번이네. 그럼 0번 벽까지 가지도 말고 바로 14번으로 점프 뛴다!" 기계 모터의 동선(Seek Distance)을 뼈까지 발라먹는 소프트웨어의 지독한 마이크로 튜닝이다.

📢 섹션 요약 비유: 엘리베이터(SCAN)를 탔는데 나 혼자 8층을 눌렀습니다. 이 바보 엘리베이터는 8층에 나를 내려주고 굳이 아무도 없는 꼭대기 15층까지 윙~ 하고 올라갔다 내려옵니다(C-SCAN). C-LOOK 엘리베이터는 내가 8층에 내리는 순간 큐(버튼)를 싹 보고 "아 윗층 누른 사람 없네?" 하고 그 즉시 8층에서 1층으로 바로 꺾어 내려가 1층 대기 손님을 빛의 속도로 태우는 알파고급 융통성입니다.

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

Look-ahead (미리 내다보기)를 위한 큐(Queue) 구조의 변화

바늘이 멈추지 않고 방향을 꺾으려면, 소프트웨어(OS)가 하드웨어보다 먼저 "앞에 짐이 있는지"를 초고속으로 계산해 내야 한다.

FCFS 시절의 큐는 그냥 들어온 순서대로 박히는 단순 리스트(List)였다. 이 구조에선 183번 뒤에 190번이 숨어있는지 찾으려면 리스트를 다 까봐야(O(N)) 해서 CPU가 느려진다.
LOOK 스케줄러의 무기: OS는 I/O 큐를 **레드-블랙 트리(Red-Black Tree)**나 최소/최대 힙(Heap) 같은 고도화된 이진 탐색 트리 구조로 바꾼다.
바늘이 183번에 도착했을 때, 트리에서 $O(1)$ 속도로 Max Value를 찔러보고 "최댓값이 183이네. 내가 지금 먹은 게 끝이군!" 하고 0.0001ms 만에 판단을 끝내버리고 바늘 모터를 반대로 확 꺾어버린다(Turn).

C-LOOK의 점프(Rollback) 메커니즘

C-SCAN과 C-LOOK은 한쪽 방향으로만 데이터를 긁고 반대쪽으로 올 때는 **'읽지 않고 빈 차로 돌아온다(Return Sweep)'**는 공통점이 있다.

왜 안 읽고 올까? 내려올 때 읽어버리면 가운데 트랙만 2번 연속으로 읽혀서 양 끝단 데이터가 기아(Starvation) 직전까지 굶는 '대기 시간 불평등'이 터지기 때문이다.
그래서 183번(끝)을 찍고 14번(처음)으로 돌아올 때, 14번으로 내려가는 그 구간에 100번, 50번 요청이 있어도 쿨하게 씹고 지나간다. 14번 바닥을 찍고 다시 '상행선'이 될 때 비로소 그놈들을 주워 담는다.
이 **무자비한 빈 차 점프(No I/O Rollback)**가 역설적으로 디스크 전체 요청의 대기 시간(Variance)을 한 치의 오차도 없이 평등하게 만들어준다.
📢 섹션 요약 비유: 밭에 씨앗을 뿌릴 때(I/O), 밭고랑 끝까지 갔다가 뒤돌아서 내려오며 씨앗을 뿌리면(SCAN) 가운데 밭만 두 번 뿌려져 썩습니다. 농부(C-LOOK)는 한 줄을 다 뿌렸으면 밭 끝에서 헛걸음하지 않고 곧바로 다음 줄 시작점(첫 요청지)으로 전력 질주해 돌아온 뒤(빈 차 점프), 다시 앞만 보고 씨앗을 뿌립니다. 헛걸음(점프)은 힘들지만 모든 밭에 똑같은 시간에 씨앗이 뿌려지는 완벽한 농사법입니다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: 4대 엘리베이터 알고리즘 가계도 최종 정리

면접관이 찔렀을 때 0.1초 만에 튀어나와야 하는 스케줄링 패밀리의 족보다.

이름	핵심 철학 (이동 방식)	허공 삽질(끝점 찍기) 여부	응답 시간 분산(공평성)	실무 채택
SCAN	상행, 하행 양쪽으로 다 긁음	무조건 0, 199 끝점 찍음 (멍청함)	나쁨 (가운데만 꿀빰)	폐기
C-SCAN	한쪽 방향만 긁고 점프 복귀	무조건 0, 199 끝점 찍음 (멍청함)	좋음 (균등함)	폐기
LOOK	상행, 하행 양쪽으로 긁음	마지막 짐에서 턴함 (스마트함)	나쁨 (가운데만 꿀빰)	특수 목적
C-LOOK	한쪽 방향만 긁고 점프 복귀	첫 짐/마지막 짐 사이만 점프 (극강)	최고 (균등+빠름 🚀)	HDD의 최종 대세

SCAN 계열의 공통점: "새치기(Arm Stickiness) 방어"

SSTF(가장 가까운 거리 우선)의 치명적 단점은 '새치기'였다. 내가 50번 트랙인데 51번, 49번에서 계속 콜이 들어오면 바늘이 그 자리에 갇혀버린다. 하지만 LOOK이나 C-LOOK은 **"내 진행 방향(예: 상행) 뒤쪽에서 아무리 가까운 요청이 들어와도 절대 뒤돌아보지 않는다"**는 강철 같은 룰을 지킨다.

바늘이 50 -> 60 으로 상행 중이다.
갑자기 방금 쓱 지나온 59번 트랙에서 I/O 요청이 터졌다! 고작 1칸 차이다.
SSTF였다면 침을 흘리며 뒤돌아 59번을 먹었겠지만, LOOK은 가차 없이 무시하고 61번을 향해 전진한다. 이 59번 놈은 바늘이 끝까지 1바퀴를 뺑 돌고 다시 상행선으로 올라올 때까지 혹독하게 굶어야 한다.
이 철통같은 "진행 방향 락(Lock)" 덕분에 어떤 구석에 있는 데이터라도 1바퀴 안에는 무조건 구제받는 기아 상태(Starvation) 박멸이 성립된다.

┌──────────┬────────────┬────────────┬────────────────────────────────┐
│ 스케줄러   │ 동선 낭비 (Seek)│ 공평성 (Variance)│ 기아 (Starvation) │
├──────────┼────────────┼────────────┼────────────────────────────────┤
│ FCFS     │ ☠️ 최악 널뛰기 │ 🟢 제일 공평함 │ 절대 안 터짐           │
│ SSTF     │ 🚀 우주 최강   │ ☠️ 랜덤 로또 수준 │ ☠️ 구석탱이 아사    │
│ C-LOOK   │ 🟢 아주 훌륭함 │ 🟢 매우 일정함 │ 절대 안 터짐           │
└──────────┴────────────┴────────────┴────────────────────────────────┘

[매트릭스 해설] C-LOOK은 마법이 아니다. SSTF가 가진 '최단 거리'의 폭발적 효율을 조금 포기하고, FCFS가 가진 '공평성'을 조금 섞어서 빚어낸 황금비율의 비빔밥이다. 세상 모든 운영체제 아키텍처는 결국 극단주의(FCFS, SSTF)가 실패하고 중도주의(C-LOOK)가 승리한다는 것을 가장 잘 보여주는 산증인이다.

📢 섹션 요약 비유: 버스를 타고 가는데 바로 1정거장 전에 내릴 역을 지나쳤습니다(새치기 요청). 기사님(C-LOOK)한테 "기사님 딱 10미터만 후진해 주세요(SSTF)!"라고 빌어도 기사님은 절대 뒤로 안 갑니다. 종점 찍고 다시 돌아오는 차를 1시간 기다려서 타야 합니다. 내 입장에선 피눈물이 나지만, 뒤에 탄 수백 명의 승객들(시스템 안정성)의 스케줄을 꼬이지 않게 지켜주는 가장 위대한 버스 철칙입니다.

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

실무 시나리오: 리눅스 CFQ (Completely Fair Queuing)의 내장 심장

리눅스 블록 레이어의 지배자: 2010년대 중반까지 전 세계 리눅스 서버의 디폴트 하드디스크 스케줄러는 CFQ였다. CFQ의 소스코드를 까보면 그 심장 엔진은 바로 이 C-LOOK 기반의 스위핑(Sweeping) 로직으로 돌아간다.
CFQ의 융합 흑마술:
- C-LOOK만 쓰면 프로세스 A가 디스크 전체(0~199번)에 걸쳐 1만 개 요청을 뿌려버리면, 프로세스 B는 바늘이 한 바퀴 도는 내내 굶어야 한다.
- 그래서 CFQ는 프로세스(앱)마다 개별적으로 **Time Slice(시간 쿠폰)**를 준다.
- "앱 A야, 네 시간 쿠폰(예: 100ms) 동안만 네가 부른 블록들을 C-LOOK으로 엘리베이터 태워서 쫙 긁어줄게! 100ms 끝나면 바늘 멈추고 B 앱으로 교대해!"
결과: 기계의 동선 낭비(Seek)를 최소화하는 하드웨어 튜닝(C-LOOK)과, 어떤 프로세스도 억울하게 굶지 않게 하는 소프트웨어 튜닝(Time Slice)이 결합된 하드디스크 I/O 최적화의 알파이자 오메가가 완성되었다.

안티패턴: SSD 환경에서의 C-LOOK

앞장에서도 입이 닳도록 말했지만 또 강조한다. C-LOOK의 전제 조건은 **"디스크의 바늘(Arm)이 이동하는 물리적 시간(Seek Time)이 데이터 전송 시간보다 압도적으로 길다"**는 것이다. NVMe SSD는 바늘이 없다. 199번지 찌르고 0번지 찌르는 속도(Seek Time = 0)가, 199번 찌르고 198번 찌르는 속도랑 물리적으로 100% 똑같다. SSD 앞단에 C-LOOK 스케줄러를 걸어버리면, OS는 아무 쓸모도 없는 "누가 199번이고 누가 0번이냐"를 계산(Sorting)하고 트리를 만드느라 아까운 CPU 코어 연산력만 파먹고 0.1ms의 렉을 추가로 발생시킨다. SSD 서버에서는 묻지도 따지지도 않고 none 이나 mq-deadline으로 바꿔서 이 똑똑한 바보(C-LOOK)의 멱살을 치워버려야 IOPS가 100만 단위로 터져 나온다.

📢 섹션 요약 비유: C-LOOK은 계단을 걸어 올라가야(Seek Time) 하는 아파트 택배 배달에서, 1층부터 꼭대기까지 한 방에 동선을 짜주는 최고의 가이드입니다. 하지만 층간 순간 이동 포탈(SSD)이 뚫린 최신 아파트에서, 기사한테 "잠깐! 계단 동선 짤 때까지 기다려!"라고 막아서면 기사가 화병으로 쓰러집니다. 시대가 바뀌면 최고의 알고리즘도 최악의 쓰레기 렉 유발자로 전락합니다.

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

정량/정성 기대효과

구분	내용
기계적 오버헤드 99% 순삭	요청이 없는 허공의 빈 트랙(예: 0~14번, 183~199번 구간)을 오가는 의미 없는 모터 구동 시간을 잘라내어 디스크 수명과 전력을 방어
Response Variance(편차) 최적화	가운데 데이터든 끝단 데이터든 1회 왕복(Sweep) 턴 안에는 무조건 1번씩 균등하게 처리되어 서비스 꼬리 지연(Tail Latency) 완전 붕괴 방지
디스크 스래싱(Thrashing) 억제	한쪽 구역에 요청이 융단폭격으로 쏟아지는 디도스성 I/O가 터져도, 방향 락(Direction Lock)을 통해 절대 갇히지 않고 뚫고 나가는 강건함 제공

결론 및 미래 전망

LOOK 및 C-LOOK 알고리즘은 둔탁한 하드디스크 쇳덩어리가 뿜어내는 물리적 제약(관성과 탐색 시간)을 소프트웨어적 지능(미리 내다보기)으로 완벽하게 어르고 갠 컴퓨터 공학의 눈물겨운 걸작이다. "갈 필요 없는 길은 가지 않고, 일단 가기로 한 길은 끝까지 민다"는 이 단순명료한 철학은 기계식 하드디스크의 I/O 성능을 이론적 한계치까지 쥐어짜 내며 수십 년간 윈도우와 리눅스 서버의 심장부(디폴트 스케줄러)를 책임졌다. 비록 트랜지스터로 떡칠 된 SSD의 광속 I/O 시대가 오며 '바늘의 동선'을 짠다는 개념 자체가 역사 속으로 소멸하고 있지만, 이 C-LOOK이 남긴 "들어온 큐의 요청을 전체적으로 훑어보고(Look ahead) 불필요한 노드를 잘라내는(Pruning) 전처리 철학"은 데이터베이스 쿼리 최적화기(Optimizer)나 클라우드 패킷 라우팅 알고리즘에 영원한 영감을 주며 기술의 유전자로 살아남을 것이다.

📢 섹션 요약 비유: 맹목적으로 법전의 글자만 보고 텅 빈 낭떠러지까지 수색을 나가는 멍청한 로봇 경찰(SCAN)의 머리에, 현장 상황을 눈으로 보고 유도리 있게 수색 구역을 좁혀서 바로 복귀(Turn)하는 베테랑 형사의 직관(LOOK)을 코드로 이식해 낸, 인공지능이 없던 시절 OS가 빚어낸 가장 인간다운 최적화입니다.

📌 관련 개념 맵 (Knowledge Graph)

C-SCAN (Circular SCAN) | LOOK 알고리즘의 원조. 끝에 데이터가 없어도 무조건 벽(0이나 199)을 찍고 오는 무식함 때문에 C-LOOK에게 자리를 빼앗김
엘리베이터 알고리즘 | 한 방향으로 쭉 밀면서 태우는 SCAN 계열 알고리즘들을 통틀어 부르는 대중적인 별명
Starvation (기아 현상) | SSTF(가까운 놈 먼저)를 썼을 때 구석의 요청이 평생 버림받는 치명적 버그로, C-LOOK은 이 기아를 완벽하게 면역시킴
Red-Black Tree (레드-블랙 트리) | 스케줄러가 "내 앞길에 제일 먼 놈이 누구지?"(Look)를 O(N) 렉 없이 O(log N) 만에 초고속으로 찾게 해주는 OS 커널의 특수 자료구조
SSD (Solid State Drive) | 기계적 바늘이 없어 Seek Time이 0초라, 이 위대한 C-LOOK 동선 계산을 한낱 쓰레기 오버헤드로 만들어버린 파괴적 하드웨어

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

C-LOOK이 뭔가요? 버스 기사 아저씨(디스크 바늘)가 1번부터 100번 정류장까지 쭉 돌 때, 만약 오늘 손님이 80번 정류장까지만 있으면 굳이 빈 차로 100번 종점까지 안 가고 80번에서 바로 차를 돌려(턴) 돌아오는 센스예요!
SCAN 버스랑 뭐가 달라요? 바보 SCAN 버스는 80번에 마지막 손님이 내려도, "회사 규정이야!" 하면서 아무도 없는 텅 빈 산꼭대기 100번 종점까지 기어 올라가서 쿵! 찍고 내려오느라 기름을 다 버리거든요.
돌아올 때는 왜 손님을 안 태워요? 내려올 때 태워주면 50번 정류장 사람은 하루에 2번이나 버스를 타고, 1번 사람은 1번밖에 못 타서 차별이 생기잖아요. 무조건 빈 차로 처음으로 휙 돌아간 뒤에 출발해야 모두가 똑같이 공평하게 버스를 탈 수 있답니다.