SCAN 스케줄링 (엘리베이터 알고리즘)

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

본질: SCAN 스케줄링은 하드디스크 바늘(Head)이 엘리베이터처럼 한쪽 방향으로 끝까지 쭉 밀고 가면서 가는 길에 있는 모든 요청을 싹쓸이한 뒤, 디스크 끝에 도달하면 방향을 틀어 반대쪽 끝까지 싹쓸이하는 가장 본능적이고 상식적인 디스크 큐잉 알고리즘이다.

가치: 가까운 놈만 쫓다 바늘이 한곳에 갇혀버리는 SSTF(최단 거리 우선)의 치명적인 '기아 현상(Starvation)'을 원천 봉쇄하면서도, 바늘이 널뛰는 FCFS(순차 처리)의 비효율성을 박살 내어 공평성(Fairness)과 처리량(Throughput)의 황금 비율을 달성했다.

융합(한계): 하지만 엘리베이터가 양 끝을 찍고 돌아올 때, 방금 막 지나친 가운데 구역의 데이터들이 다음 차례가 올 때까지 너무 오래 기다려야 하는 불균형(Variance)이 존재하여, 훗날 C-SCAN(단방향 스위핑)이나 LOOK(끝까지 안 가고 꺾기) 같은 현대적 변종 아키텍처로 진화하는 튼튼한 뼈대 역할을 했다.

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

개념: 디스크 헤드는 0번 트랙(가장자리)부터 199번 트랙(중심) 사이를 오간다. SCAN은 바늘이 움직이는 방향(Direction)에 절대적인 락(Lock)을 건다. 바늘이 0번에서 199번을 향해(안쪽으로) 움직이기 시작했다면, 중간에 큐(Queue)에 나보다 뒤에 있는(바깥쪽) 아무리 가까운 요청이 들어와도 절대 방향을 꺾지 않는다. 199번 끝을 찍은 뒤에야 "하행선입니다~" 하고 방향을 꺾어 바깥쪽으로 내려오면서 요청을 줍는다.
필요성: 이전 세대의 에이스였던 SSTF(가장 가까운 곳 먼저)는 미친 효율을 자랑했지만, 특정 구역에 요청이 몰리면 반대쪽 구역의 요청이 평생 처리되지 못하는 '기아 현상(Starvation)'을 낳았다. OS의 존재 이유는 효율보다 '신뢰성'이다. 1주일째 응답 없는 앱이 있는 서버는 아무도 쓰지 않는다. "모든 요청이 언젠가는 무조건 처리된다는 보장(공평성)을 주면서도, 바늘이 낭비 없이 움직이게 할 방법이 없을까?"라는 딜레마 속에서, 인류가 매일 타는 '엘리베이터의 움직임'을 컴퓨터에 그대로 복사해 넣은 천재적인 휴리스틱이 탄생했다.
💡 비유: SCAN은 1층부터 10층까지 운행하는 백화점 엘리베이터와 같다. 엘리베이터(디스크 헤드)가 5층에서 10층(상행)으로 올라가고 있다. 이때 4층(가장 가까운 곳)에서 승객이 버튼을 누른다(I/O 요청). 멍청한 SSTF 엘리베이터는 "어? 4층이 제일 가깝네!" 하고 올라가다 말고 갑자기 4층으로 내려가는 미친 짓을 한다. 정상적인 SCAN 엘리베이터는 4층 버튼을 무시하고, 일단 10층 꼭대기까지 묵묵히 올라가서 사람들을 다 내려준 뒤에, 방향을 꺾어 하행선이 되어 4층 승객을 태운다. 승객 입장에서는 조금 기다리더라도 '엘리베이터가 언젠간 무조건 내 층에 온다'는 믿음을 가질 수 있다.
등장 배경 및 알고리즘의 진화:
1. FCFS의 무지성: 순서만 지키려다 기계 모터가 타버림.
2. SSTF의 탐욕: 효율만 따지다 구석진 곳의 앱이 굶어 죽음(Starvation).
3. SCAN의 중용: "방향성"이라는 제약 조건을 하나 강제함으로써, 동선 낭비도 막고 굶어 죽는 앱도 없애는 완벽한 타협점을 찾아냄.

┌──────────────────────────────────────────────────────────────────────────┐
│        SCAN (엘리베이터) 알고리즘의 우아한 동선 시각화                   │
├──────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│ [ 큐 요청 순서 ]:  98, 183, 37, 122, 14, 124                             │
│ [ 헤드 위치 ]: 53번 트랙 / [ 현재 방향 ]: 0번을 향해 하행 중!            │
│                                                                          │
│ ▶ SCAN 발동: "무조건 끝(0번)까지 내려가면서 다 줍고, 그다음 꺾어라!"     │
│                                                                          │
│      14   37     53     98    122 124        183                         │
│ 0    │    │      [시작]  │      │  │          │      199                 │
│ │    │    │◀──────┘      │      │  │          │                          │
│ │    │◀───┘              │      │  │          │                          │
│ │◀───┘                     │      │  │          │                        │
│ └─────────────────────────▶①    │  │          │                          │
│                                └──────▶②  │          │                   │
│                                       └──▶③          │                   │
│                                              └──────────▶④               │
│                                                                          │
│ ✅ 이동 경로: 53 -> 37 -> 14 -> 0(끝점 찍기!) -> 98 -> 122...            │
│ 🌟 특징: SSTF처럼 와이퍼가 요동치지 않고, 끝을 찍을 때까지 묵묵히 전진함.│
└──────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 알고리즘의 가장 중요한 특징은 **"0번(또는 199번)이라는 디스크의 물리적 끝점(End Point)을 무조건 찍고 돌아온다"**는 것이다. 큐에 14번까지만 요청이 들어왔음에도 불구하고, SCAN은 14번을 처리한 뒤 멈추지 않고 아무런 요청도 없는 0번 벽까지 쿵! 하고 찍은 뒤에야 방향을 틀어 올라간다. 이 융통성 없는 끝점 찍기가 훗날 LOOK 알고리즘으로 진화하게 되는 빌미가 된다.

📢 섹션 요약 비유: 청소 로봇(SCAN)이 거실을 청소할 때, 쓰레기(요청)가 있는 곳만 쫓아다니며 핑퐁 치는 게(SSTF) 아니라, 벽 끝에서 반대쪽 벽 끝까지 지그재그로 우직하게 밀고 나가며 전체를 훑습니다. 설령 벽 근처에 쓰레기가 없어도 일단 벽을 쿵 찍고 돌아섭니다. 쓰레기를 하나도 놓치지 않는 확실한 청소법입니다.

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

기아 현상 (Starvation)의 수학적 박멸

SSTF에서 구석에 있던 999번 요청이 굶어 죽었던 이유는, 바늘이 50번대에서만 계속 맴돌았기 때문이다. SCAN 알고리즘 하에서는 이 악순환이 수학적으로 불가능하다.

바늘이 50번에서 상행(오른쪽)으로 출발했다.
50번대에서 새로운 요청이 1초에 1만 개씩 쏟아져 들어온다 치자.
SCAN 스케줄러는 이 1만 개의 요청을 **"현재 진행 방향(상행)에 있는가?"**로 필터링한다.
바늘은 50 -> 51 -> 52로 계속 전진하므로, 50번 자리에 새 요청이 아무리 많이 들어와도 뒤를 돌아보지 않는다.
결국 바늘은 무조건 999번(디스크 끝)에 도달하게 되어 있으며, **디스크의 어떤 구석에 박힌 요청이라도 최대 '디스크 1왕복 시간' 안에는 무조건 처리된다는 강력한 시간 상한선(Upper Bound)**이 보장된다.

불균형의 저주 (Variance Problem)

SCAN은 공평해 보이지만 위치에 따라 대기 시간이 로또급으로 차이 나는 치명적인 구조적 결함을 안고 있다.

가운데(50번) 위치의 꿀 혜택: 바늘이 상행할 때 1번, 하행할 때 1번 지나간다. 즉, 바늘이 전체를 왕복하는 동안 중간에 있는 트랙은 아주 짧은 주기로 2번이나 바늘의 은혜를 입는다.
양 끝단(0번, 199번) 위치의 피눈물: 바늘이 199번을 찍고 0번으로 출발했다. 하필 그 직후 198번에 새로운 요청이 들어왔다. 이 불쌍한 198번 요청은 바늘이 저 멀리 0번 끝까지 갔다가 다시 199번으로 돌아올 때까지 **디스크 전체 왕복 시간의 2배(Maximum Delay)**를 꼬박 기다려야 한다.
결론: SCAN은 양 끝단 데이터에게 너무 가혹하며, 응답 시간의 편차(Variance)가 위치에 따라 심하게 요동친다.
📢 섹션 요약 비유: 강남역(가운데)에 서 있으면 서울행 버스와 부산행 버스가 수시로 지나가서 버스 타기가 엄청 쉽습니다. 하지만 버스 종점(디스크 양 끝)에 사는 사람은 버스가 한 번 떠나버리면 버스가 반대쪽 종점을 찍고 다시 돌아올 때까지 하루 종일 정류장에서 떨어야 하는 끔찍한 차별 대우를 받게 됩니다.

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

비교 1: SSTF vs SCAN

현업 스케줄러의 역사에서 가장 치열했던 성능 대결이다.

비교 척도	SSTF (Shortest Seek Time First)	SCAN (엘리베이터)
이동 철학	"무조건 내 눈앞에 가까운 놈 먼저!"	"무조건 방향 안 꺾고 일직선으로 쭉 밀기!"
기아(Starvation)	☠️ 심심하면 터짐 (치명적 약점)	🟢 절대 안 터짐 (완벽 방어)
평균 탐색 시간	수학적으로 가장 짧음 (효율 최상)	SSTF보다 살짝 길지만 훌륭함
응답 시간 분산	극단적으로 심함 (1초 ~ 영원히)	양 끝단 차별은 있지만 SSTF보단 훨씬 일정함

데드라인(Deadline) 스케줄러로의 진화

리눅스는 SCAN의 "끝단 차별 문제"를 해결하기 위해 가만히 있지 않았다. 아무리 SCAN을 돌려도, 특정 요청이 큐에 들어온 지 너무 오래되어 굶어 죽기 일보 직전이라면? 리눅스의 Deadline 스케줄러는 엘리베이터(SCAN) 큐 옆에, **시간 초시계가 달린 FIFO 큐(Read 500ms, Write 5초 제한)**를 하나 더 몰래 놔둔다. 평소엔 엘리베이터처럼 예쁘게 처리하다가, 구석탱이 요청이 데드라인(500ms)을 넘겨서 비명을 지르면, 엘리베이터 방향이고 뭐고 깡그리 무시하고 즉시 그쪽으로 바늘을 꺾어버려 응답 지연의 상한선을 철통같이 방어한다.

┌──────────┬────────────┬────────────┬─────────────────────────────────┐
│ 상황       │ SSTF의 대처  │ SCAN의 대처  │ Deadline의 대처           │
├──────────┼────────────┼────────────┼─────────────────────────────────┤
│ 구석에 요청옴│ 무시함 (효율) │ 가던 길 다 가고 감│ 가던 길 다 가고 감│
│ 1분째 굶는 중│ ☠️ 계속 무시함│ 가던 길 다 가고 감│ 🚀 즉시 꺾어서 감 │
└──────────┴────────────┴────────────┴─────────────────────────────────┘

[매트릭스 해설] 컴퓨터 시스템에서 "언젠가 처리해 줄게(SCAN)"는 완벽한 정답이 아니다. "최소 0.5초 안에는 무조건 처리해 줄게(Deadline)"라는 하드 타임 리밋(Time Limit)이 있어야만 실시간 오디오/비디오 스트리밍이 끊기지 않는 엔터프라이즈 OS로 인정받는다.

📢 섹션 요약 비유: 버스 기사(SCAN)가 정해진 노선대로만 차를 몹니다. 그런데 저기 정류장에 임산부(데드라인 임박 데이터)가 쓰러져 가고 있습니다. 규칙을 깨고 차를 돌려(SSTF 꺾기) 임산부부터 병원으로 이송하는 융통성(Deadline 스케줄러)이 있어야 진정한 명품 시스템입니다.

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

실무 시나리오: HDD 서버의 파일 시스템 조각화와 SCAN의 위력

문제 상황: 데이터베이스 백업 파일 10GB를 하드디스크에 쓰는데, 하드디스크가 오래되어 빈 공간이 1번, 50만 번, 10만 번으로 조각조각 찢어져 있다.
OS의 큐잉: 커널은 이 10GB를 4KB씩 250만 개의 I/O 요청으로 찢어서 스케줄러 큐에 던진다.
SCAN의 무쌍 (Elevator Sweep):
- 만약 FCFS였다면 바늘이 1번 갔다가 50만 번 갔다가 10만 번 가면서 헤드 모터가 타버렸을 것이다.
- 하지만 SCAN 스케줄러(CFQ의 뼈대)는 이 250만 개의 지저분한 요청을 트랙 번호순으로 싹 정렬한다.
- 그리고 디스크 0번부터 끝번까지 바늘을 부드럽게 1바이트 쓱~ 밀고 지나가며 250만 개의 흩어진 조각들을 마치 원래 하나였던 것처럼 빛의 속도로 긁어모은다.
결과: 이 엘리베이터의 스위핑(Sweeping) 효과 덕분에, 물리적으로 파편화된 디스크라도 스케줄러 큐 깊이(Queue Depth)만 깊게 세팅해 주면 순차 읽기(Sequential Read)에 버금가는 막강한 스루풋을 뽑아낼 수 있다.

SSD에서의 엘리베이터 퇴출

앞서 말했듯 SSD는 바늘이 없다. 1번을 찌르나 50만 번을 찌르나 속도가 같다. SSD 앞단에서 엘리베이터(SCAN) 알고리즘을 돌리며 번호순으로 예쁘게 줄을 세우는 짓은, 그 줄 세우는 연산(Sorting) 자체가 CPU 낭비다. 현대 리눅스는 하드웨어가 NVMe SSD임을 감지하는 순간, 이 위대했던 엘리베이터 스케줄러를 즉각 폐기하고 none/noop (아무 짓도 안 하고 들어온 대로 던지기) 스케줄러로 자동 전환해 버린다.

📢 섹션 요약 비유: 엘리베이터 스케줄러는 층계참을 오르내리는 '무거운 기계식 관성'이 있을 때만 의미가 있습니다. 내가 10층짜리 건물에서 층간 순간 이동 포탈(SSD)을 얻었는데, 굳이 "효율을 위해 1층부터 10층까지 순서대로 줍자"라며 머리를 싸매고 동선 계획을 짜는 건 그야말로 시간 낭비, 뻘짓의 극치입니다.

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

정량/정성 기대효과

구분	내용
기아(Starvation) 현상 원천 멸종	디스크 진행 방향이 끝을 찍고 무조건 돌아오므로, 어떤 악성 트래픽이 몰려도 특정 I/O가 영원히 소외되는 시스템 버그 완전 소거
디스크 기계 장치 수명 보존	바늘이 이리저리 꺾이는 급발진/급정거 빈도를 최소화하여, 데이터센터 내 수십만 대 하드디스크의 액추에이터 마모와 발열을 극적으로 낮춤
현대 I/O 스케줄러의 아키텍처 원형	이후 파생된 C-SCAN, LOOK, CFQ 등 모든 진보된 운영체제 디스크 스케줄링 기법들이 이 '단방향 싹쓸이' 철학을 복사해 감

결론 및 미래 전망

SCAN 스케줄링 (엘리베이터 알고리즘)은 인류가 발명한 알고리즘 중 일상생활의 직관(엘리베이터)이 컴퓨터 아키텍처에 100% 동일하게 이식되어 대성공을 거둔 가장 아름답고 고전적인 사례다. "가까운 것을 좇는 인간의 탐욕(SSTF)"이 낳은 불평등을 "한 방향으로 끝까지 간다"는 기계적인 규칙 하나로 우아하게 통제하며, 시스템 공학에서 효율성(Efficiency)과 공평성(Fairness)이라는 영원한 두 마리 토끼의 황금 타협점을 찾아냈다. 낸드 플래시(SSD)의 폭발적인 보급으로 바늘이 움직이는 탐색 시간(Seek Time) 자체가 0초가 되며 이 알고리즘의 본래 목적은 역사의 박물관으로 향하고 있다. 그러나 디스크 바늘은 사라졌을지언정, "수많은 요청을 큐에 모은 뒤 한 방향으로 정렬하여 배치(Batch) 처리한다"는 이 위대한 스위핑(Sweeping) 철학은 현대의 데이터베이스 쿼리 옵티마이저나 네트워크 패킷 라우팅 알고리즘 깊숙한 곳에 영원한 영혼으로 살아 숨 쉬고 있다.

📢 섹션 요약 비유: 엘리베이터가 "내려가는 길이니까 올라가는 버튼은 무시하고 일단 1층까지 쭉 가겠습니다"라고 하는 건, 당장 올라가고 싶은 내 입장에선 답답한 일입니다. 하지만 그렇게 룰을 지키지 않고 부르는 대로 휙휙 꺾으면 건물 전체 사람들이 영원히 엘리베이터를 못 타게 됩니다. SCAN은 개인의 답답함을 시스템 전체의 질서로 승화시킨 거대한 사회적 약속입니다.

📌 관련 개념 맵 (Knowledge Graph)

SSTF (Shortest Seek Time First) | SCAN이 짓밟고 일어선 과거의 천재. 가장 가까운 곳만 쫓다가 구석탱이 데이터를 굶겨 죽인(기아 현상) 반면교사
기아 현상 (Starvation) | 디스크 바늘이 한 동네에서만 놀아서 다른 동네 요청이 평생 처리되지 못하는, SCAN이 100% 박멸한 최악의 버그
C-SCAN (Circular SCAN) | SCAN의 양 끝단 불평등(가운데만 2번 들르는 혜택)을 빡쳐서, 한쪽으로 쭉 밀고 다시 처음으로 훅 돌아와서 1방향으로만 도는 개선판
LOOK 알고리즘 | SCAN이 바보같이 요청도 없는데 0번 끝 벽까지 쿵! 하고 찍고 오는 걸 고쳐서, "가장 마지막 요청까지만 가고 턴해!"라고 지능을 더한 실전판
Noop (None) 스케줄러 | 쇳덩어리가 없는 최신 SSD 환경에서 "엘리베이터 정렬 이딴 거 다 필요 없으니까 그냥 쑤셔 넣어!"라며 이 위대한 역사를 종식시킨 최신 옵션

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

엘리베이터(SCAN) 알고리즘이 뭔가요? 우체부 아저씨가 동네에 편지를 돌릴 때, 1번 집 갔다가 100번 집 갔다가 널뛰기하지 않고, 1번 집부터 골목 끝까지 한쪽 방향으로 쭉~ 걸어가면서 순서대로 편지를 예쁘게 꽂아주고 오는 거예요.
왜 그렇게 하나요? 가까운 집만 먼저 쫓아다니면(SSTF), 골목 끝에 사는 할머니는 평생 편지를 못 받을 수도 있거든요! 한 방향으로 쭉 가면 늦게라도 무조건 모든 사람이 편지를 받게 돼요.
불편한 점은요? 아저씨가 골목 끝에서 턴해서 막 돌아오고 있는데, 방금 지나친 바로 앞집에서 "편지 하나 더요!" 하고 부르면, 아저씨가 반대쪽 골목 끝까지 다 갔다가 다시 돌아올 때까지 엄청 오래 기다려야 한답니다.