FCFS (First-Come, First-Served) 스케줄링

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

본질: FCFS(First-Come, First-Served) 디스크 스케줄링은 수십 개의 디스크 I/O 요청이 큐에 쌓였을 때, 데이터의 물리적 위치(트랙 번호)는 깡그리 무시하고 오직 큐에 '먼저 도착한 순서(시간)'대로만 디스크 바늘(Head)을 움직여 처리하는 가장 원시적인 큐잉 알고리즘이다.

가치: 구현이 큐(Queue) 하나면 끝날 정도로 극도로 단순하며, 어떤 요청이든 먼저 오기만 하면 무조건 언젠가는 처리된다는 절대적인 '공평성(Fairness)'과 기아 현상(Starvation) 면제라는 훈장을 가진다.

융합(한계): 하지만 기계식 하드디스크(HDD) 환경에서 1번, 999번, 2번 등 랜덤한 주소 요청이 들어올 경우, 바늘이 디스크의 양 끝을 미친 듯이 횡단하는 끔찍한 탐색 시간(Seek Penalty) 폭발을 유발하므로, 엘리베이터 알고리즘(SCAN)이 등장하기 전까지의 반면교사로만 남았다.

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

개념: 우리말로는 '선입선처리' 방식이다. CPU가 "블록 98, 183, 37, 122 번지 읽어와!"라고 시간 순서대로 툭툭 던지면, 디스크 스케줄러는 이걸 1도 건드리지 않고(재정렬 없음) 그냥 98번 갔다가, 183번 갔다가, 다시 37번으로 빽(Back)하는 식으로 멍청하고 우직하게 바늘을 돌린다.
필요성: 초기 운영체제를 만들던 시절, 컴퓨터 과학자들에게는 "복잡한 연산을 하느라 CPU를 갉아먹으면 안 된다"는 강박이 있었다. 들어온 I/O 요청들의 거리를 계산하고 오름차순으로 정렬(Sorting)하는 짓 자체가 1960년대 똥컴 CPU에게는 엄청난 오버헤드였다. "그냥 은행 창구처럼 제일 먼저 줄 선 놈부터 빨리빨리 쳐내자. 그게 윤리적으로도 공평하고 프로그래밍 짜기도 제일 쉽잖아?"라는 극강의 단순성과 평등주의가 이 알고리즘을 최초의 스탠다드로 만들었다.
💡 비유: FCFS는 식당의 무조건 순서대로 배달하는 초보 배달원과 같다. 배달 콜이 [강남(1시) -> 노원(1시 5분) -> 서초(1시 10분)] 순서로 들어왔다. 강남과 서초는 바로 옆 동네지만, 바보 같은 초보 배달원(FCFS)은 무조건 콜 들어온 순서를 지키기 위해 강남에 배달하고, 1시간 걸려 노원구까지 갔다가, 다시 1시간을 되돌아와 서초구로 배달을 간다. 길바닥에 뿌리는 오토바이 기름값(Seek Time)이 배달비보다 더 나온다. 하지만 손님들 입장에선 "내가 1시 5분에 시켰으니 1시 10분에 시킨 서초구 놈보다 무조건 밥을 먼저 받는다"는 완벽한 공평함(Fairness)을 보장받는다.
등장 배경 및 공평성의 함정:
1. 단순한 큐(Queue)의 시대: 들어온 순서대로 빼내는 FIFO 큐 자료구조 하나면 모든 OS가 다 만들어졌다.
2. 랜덤 액세스(Random I/O)의 재앙: 데이터베이스나 다중 프로세스가 뜨면서, 디스크 요청 주소가 1, 999, 2 로 극단적으로 널뛰기 시작함.
3. 효율성의 붕괴: 공평하긴 한데, 바늘이 널뛰기하느라 디스크 전체가 스래싱 급 렉에 빠져 서버가 뻗는 사태가 속출하며 퇴출 위기를 맞음.

┌────────────────────────────────────────────────────────────────────┐
│        FCFS 디스크 스케줄링의 끔찍한 동선(바늘 이동) 시각화        │
├────────────────────────────────────────────────────────────────────┤
│                                                                    │
│ [ 큐에 쌓인 요청 순서 (트랙 번호) ]:  98, 183, 37, 122, 14, 124    │
│ [ 디스크 바늘(Head)의 현재 위치 ]: 53번 트랙                       │
│                                                                    │
│ ▶ 바늘의 실제 이동 경로 (들어온 순서 그대로 직진!)                 │
│                                                                    │
│   14   37     53     98    122 124        183                      │
│   │    │      [시작]  │      │  │          │                       │
│   │    │       └──────▶①    │  │          │                        │
│   │    │              └─────────────────▶②                         │
│   │    │◀───────────────────────────────────┘                      │
│   │    ③───────────────────▶④  │                                   │
│   │◀─────────────────────────┘  │                                  │
│   ⑤──────────────────────────────▶⑥                                │
│                                                                    │
│ 💥 총 헤드 이동 거리 연산:                                         │
│ |53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-124|     │
│ = 45 + 85 + 146 + 85 + 108 + 110 = 💥 총 579 트랙 이동!            │
└────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 지그재그(Z-zag) 궤적을 보라. 183번에서 37번으로 디스크 끝과 끝을 풀스윙으로 되돌아오는 저 146트랙 이동 구간은, 디스크 쇳덩어리가 비명을 지르며 10밀리초 이상의 지옥 같은 Seek 딜레이를 뿜어내는 마의 구간이다. 바늘을 한쪽으로 쓱 밀면서(14->37->98->122->124->183) 훑었으면 200 이동 거리로 끝날 일을, 순서를 지키겠다는 아집 하나 때문에 **3배가 넘는 600 가까운 동선 낭비(Overhead)**를 저지르고 말았다. 기계 공학적 관점에선 최악의 테러다.

📢 섹션 요약 비유: 엘리베이터에 탔는데 버튼 눌린 순서대로만 움직입니다. 1층에서 탄 사람이 10층을 누르고, 나중에 탄 사람이 2층을 누르면 엘리베이터가 10층까지 쭉 올라갔다가 다시 2층으로 곤두박질치는 기괴한 놀이기구가 됩니다. 엘리베이터 모터(모터 수명)가 일주일 만에 타서 고장 나 버릴 겁니다.

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

절대 기아 현상 방지 (No Starvation)

FCFS가 성능 쓰레기 취급을 받으면서도 가장 강력하게 뽐내는 유일한 무기는 **'예측 가능성(Determinism)'**과 **'기아 현상(Starvation) 제로'**다.

뒤에 나올 성능 좋은 엘리베이터(SCAN)나 최단 거리(SSTF) 알고리즘들은 "가까운 놈 먼저, 가는 길에 있는 놈 먼저" 처리한다.
만약 내 데이터가 디스크 999번 구석탱이에 있는데, 10번 구역에서만 I/O 요청이 1만 번 쏟아지면 스케줄러가 효율 챙기겠다고 10번 구역만 빙글빙글 돈다. 내 999번 요청은 10분이 지나도 평생 처리되지 못하고 굶어 죽는다(Starvation).
FCFS의 절대적 정의: FCFS는 그딴 거 없다. 네가 999번 구석에 있든 말든, 네가 먼저 큐(Queue)에 들어왔다면 10번 구역 놈들 다 무시하고 하늘이 두 쪽 나도 네 것부터 먼저 꺼내준다. 모든 I/O 요청의 대기 시간이 공평하게 수렴한다.

하드웨어 디스크 컨트롤러와의 괴리

현대 컴퓨터에서 FCFS를 소프트웨어(OS) 단에 박아버리면 치명적인 버그가 하나 더 터진다.

OS가 열심히 "10 -> 900 -> 20" 순서로 정직하게 I/O 명령을 하드디스크로 쐈다 치자.
그런데 최신 하드디스크 내부의 펌웨어(NCQ, Native Command Queuing 지원 칩셋)는 바보가 아니다.
칩셋 왈: "OS 이 멍청한 놈이 바늘 다 망가지게 순서를 이상하게 줬네? 내가 내 맘대로 순서 다시 정렬해서 10 -> 20 -> 900으로 긁을게!"
하드웨어가 스스로 맘대로 순서를 뒤집어버리면, OS는 자기가 1등으로 보낸 900번이 가장 늦게 응답 오는 꼴을 보며 OS 스케줄링의 통제력을 완전히 상실하게 된다.
📢 섹션 요약 비유: 구청장(OS)이 민원 처리 순서를 "접수된 순서대로 1번 김씨, 2번 박씨" 정해서 서류를 줬더니, 현장 공무원(디스크 컨트롤러)이 "아니 김씨 집 너무 멀어. 가까운 박씨 집부터 갔다 올래" 하고 멋대로 순서를 바꿔서(NCQ) 구청장의 공평한 지시(FCFS)를 휴지 조각으로 만들어버리는 꼴입니다.

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

비교 1: I/O 워크로드에 따른 FCFS의 체감 성능

무조건 나쁜 건 아니다. 데이터가 어떻게 들어오냐에 따라 FCFS도 빛을 발한다.

워크로드 패턴	동작 양상	FCFS의 성능
랜덤 I/O 집중 (DB 서버)	10번, 1만 번, 500번 마구잡이로 들어옴	☠️ 최악. 바늘 널뛰기로 서버 폭파
순차 I/O 집중 (영화 복사)	10번, 11번, 12번, 13번... 일렬로 들어옴	🚀 최상. 어차피 순서가 동선이라 렉 0초
I/O 부하가 거의 없을 때	1초에 1개씩 어쩌다 들어옴	🟢 정렬(Sorting) 오버헤드 없어서 제일 빠름

소프트웨어 오버헤드의 극한적 다이어트

스케줄링 알고리즘이 큐를 재정렬(Sorting)하려면 CPU 사이클이 소모된다. 큐에 1만 개의 요청이 쌓였을 때, 거리순으로 정렬(SSTF)하려면 $O(N^2)$ 이나 $O(N \log N)$의 수학 연산이 들어간다. 하지만 FCFS는 그냥 큐에 집어넣고(Push), 앞에서부터 빼면(Pop) 끝이다. 시간 복잡도 **$O(1)$**이다. 운영체제의 가장 큰 미덕 중 하나인 "CPU를 디스크 관리에 낭비하지 않는다"는 원칙 하나만큼은 우주에서 가장 완벽하게 지켜낸 알고리즘이다.

┌──────────┬────────────┬────────────┬─────────────────────────────┐
│ 평가 지표  │ 디스크 바늘 동선│ CPU 연산 낭비  │ 특정 앱 굶어 죽음│
├──────────┼────────────┼────────────┼─────────────────────────────┤
│ FCFS     │ ☠️ 최악 널뛰기 │ 🚀 0% (완벽) │ 🟢 절대 없음          │
│ 최적화 로직│ 🟢 가장 짧음  │ 🔴 정렬 렉 심함 │ ☠️ 구석 앱 굶음   │
└──────────┴────────────┴────────────┴─────────────────────────────┘

[매트릭스 해설] FCFS는 철저하게 기계(HDD)를 굴려서 CPU(소프트웨어)를 쉬게 하는 사상이다. 하지만 모터 달린 기계가 움직이는 8ms의 물리적 시간은 CPU가 연산하는 나노초 스피드를 도저히 이길 수 없었다. 결국 컴퓨터 공학은 "CPU가 조금 힘들게 수학(정렬)을 풀더라도, 기계식 바늘의 움직임(Seek Time)을 단 1mm라도 깎아내는 것"이 시스템 전체로 보면 1,000배 이득이라는 쓰라린 교훈을 얻고 FCFS를 버렸다.

📢 섹션 요약 비유: 택배 동선(스케줄) 짜는 데 머리를 1시간(CPU 연산) 쓰느니, 뇌를 비우고 순서대로 액셀을 밟는 게(FCFS) 빠를 거라고 생각했습니다. 막상 해보니 길에서 10시간(디스크 렉)을 버렸습니다. 차라리 책상에 앉아 1시간 빡세게 머리 굴려서 동선을 짠 뒤(SSTF/SCAN), 3시간 만에 배달을 다 끝내는 게 진짜 현명한 노동이라는 걸 깨달은 역사입니다.

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

실무 시나리오: NVMe SSD 환경에서의 'Noop(None)' 스케줄러 부활

놀랍게도, 버려졌던 낡은 FCFS 알고리즘이 2020년대 최신 100만 IOPS 급 NVMe SSD 서버 환경에서 Noop 또는 None 이라는 이름표를 달고 화려하게 황제로 부활했다.

문제 상황: SSD는 바늘(Head)도 없고 원판도 없다. 10번지를 찌르든 10만 번지를 찌르든 전기가 꽂히는 속도는 0.001ms로 100% 똑같다. (탐색 시간 Seek Time 자체가 물리적으로 0이다).
최적화 로직의 트롤링:
- 멍청한 리눅스 커널이 옛날 버릇 못 버리고, 들어온 I/O 요청을 바늘 동선 아껴준답시고 열심히 O(N log N)으로 정렬(Sorting)을 하고 자빠졌다.
- SSD는 이미 데이터 처리할 준비가 다 됐는데, OS 커널이 정렬하느라 0.1초 동안 요청을 안 주고 쥐고 있어서 서버 전체 I/O 대역폭이 반토막이 났다.
Noop (FCFS) 의 재평가:
- 실무진은 빡쳐서 I/O 스케줄러 설정을 **echo none > /sys/block/nvme0n1/queue/scheduler**로 강제로 바꿔버렸다.
- 이 옵션은 OS의 모든 정렬과 묶기 꼼수를 다 꺼버리고, "들어온 순서대로 0.1초의 망설임도 없이 그냥 무식하게 SSD로 쳐박아라!(FCFS)"라는 극단적 원시 상태로 되돌리는 튜닝이다.
- 결과: CPU 오버헤드가 0이 되고, SSD의 내부 6만 개 하드웨어 큐가 100% 폭발적으로 가동되며 IOPS 벤치마크가 신기록을 경신했다. 가장 멍청한 알고리즘(FCFS)이, 가장 똑똑한 하드웨어(SSD)와 만났을 때 우주 최강의 스피드를 내는 역설적 융합이 완성된 것이다.

📢 섹션 요약 비유: 낡은 자전거(HDD)로 심부름 갈 땐 동선을 치밀하게 안 짜면 다리에 알이 배겨(스래싱) 죽습니다. 하지만 순간이동 포탈(SSD)을 얻은 지금, 동선을 짠답시고 책상에서 10분 동안 고민(정렬 렉)하는 건 바보 짓입니다. 포탈 시대엔 생각할 시간에 일단 순서대로(FCFS) 닥치는 대로 포탈에 쑤셔 넣는 뇌 빼기 전술이 우주에서 제일 빠릅니다.

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

정량/정성 기대효과

구분	내용
기아 현상(Starvation) 절대 방어	디스크 구석에 있는 데이터라도, 요청된 순서를 절대적으로 지켜주어 무한 대기 버그로 앱이 터지는 현상을 0%로 소거
CPU 코어 연산량 0에 수렴	큐에 삽입/삭제만 하는 단순 링크드 리스트 조작으로, OS 커널의 I/O 블록 레이어 오버헤드를 이론적 최소치로 다이어트
차세대 반도체 스토리지와의 찰떡궁합	기계적 렉(Seek)이 소멸된 NVMe SSD 환경에서, 복잡한 스케줄링 낭비를 벗어던진 순수 I/O 파이프라인(none)으로 부활하여 100만 IOPS 달성

결론 및 미래 전망

FCFS (First-Come, First-Served) 스케줄링은 컴퓨터 과학의 가장 원초적인 본능이자, 모든 복잡한 최적화 알고리즘들이 성능을 비교할 때 기준점(Baseline)으로 삼는 훌륭한 샌드백이다. 기계식 모터가 지배하던 하드디스크(HDD)의 어두운 암흑기에는 바늘을 널뛰게 하여 서버를 박살 내는 "가장 피해야 할 1순위 안티패턴"으로 교과서에서 조리돌림 당했다. 하지만 기술의 수레바퀴는 돌고 돌아, 기계적 탐색 시간(Seek Time)이 0으로 소멸해 버린 플래시 메모리(SSD/NVRAM) 시대가 도래하자 상황은 180도 뒤집혔다. 이제 CPU가 머리를 쥐어짜며 큐를 정렬하는 짓(SCAN/SSTF)이야말로 최악의 낭비가 되었으며, "생각하지 말고 들어오는 족족 던져라"는 이 원시적인 FCFS 철학이 noop이라는 이름으로 화려하게 부활하여 전 세계 클라우드 데이터센터의 디폴트 스토리지 엔진으로 군림하고 있다. 돌고 도는 컴퓨터 아키텍처의 아이러니를 가장 완벽하게 보여주는 드라마틱한 알고리즘이다.

📢 섹션 요약 비유: 무식하게 힘만 세고 머리를 안 쓰는 병사(FCFS)는 활과 화살(HDD) 부대에서는 과녁을 못 맞춰 쫓겨났습니다. 세월이 흘러 유도 미사일(SSD) 시대가 오자, 복잡하게 탄도를 계산하는 똑똑한 장교들(SCAN)은 미사일 쏘는 속도가 늦어 도태되었고, 생각 없이 미사일 버튼만 1초에 100번씩 미친 듯이 눌러대는 힘센 멍청이 병사(FCFS)가 최고의 전쟁 영웅으로 부활한 눈부신 역주행 스토리입니다.

📌 관련 개념 맵 (Knowledge Graph)

탐색 시간 (Seek Time) | FCFS가 디스크 바늘을 널뛰기하게 만들어서 지수함수적으로 뻥튀기시켜버리는, 기계식 HDD 최악의 페널티 타임
기아 상태 (Starvation) | 효율만 쫓는 똑똑한 알고리즘들이 종종 일으키는 '구석탱이 데이터 무한 방치' 에러. FCFS는 이 에러만큼은 100% 막아내는 절대 방패임
SSTF (Shortest Seek Time First) | FCFS의 널뛰기 동선에 빡쳐서, "현재 위치에서 가장 가까운 곳부터 가라!"고 만든 1차 진화형 엘리베이터 알고리즘
Noop 스케줄러 | 쇳덩어리가 없는 최신 SSD 환경에서, 복잡한 정렬을 다 버리고 옛날 FCFS로 회귀하여 CPU 렉을 없앤 리눅스의 마법의 세팅
I/O 멀티플렉싱 | 순서대로만 처리하는 FCFS의 답답함을 우회하여, 여러 I/O를 한 방에 묶어서 쳐내는 현대 서버의 비동기 아키텍처

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

FCFS 스케줄링이 뭔가요? 식당에서 손님이 문 열고 들어와 줄을 선 순서(1번, 2번, 3번) 그대로, 단 1초의 새치기도 용납하지 않고 정직하게 밥을 내어주는 규칙이에요.
너무 공평하고 좋은 거 아닌가요? 공평하긴 하죠. 근데 1번 손님은 짜장면, 2번은 피자, 3번은 다시 짬뽕을 시키면 주방장(디스크)이 중식 만들다 양식 만들다 다시 중식(바늘 널뛰기)을 하느라 프라이팬 태워 먹고 속도가 엄청 느려져요.
그럼 어떻게 해야 빨라져요? 똑똑한 주방장은 순서를 살짝 무시하고 짜장면이랑 짬뽕(가까운 주소)을 한 번에 싹 다 같이 볶아낸 뒤(동선 최적화), 마지막에 피자를 구워서 내보낸답니다.