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

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

  1. 본질: FCFS (First-Come, First-Served) 스케줄링은 준비 큐 (Ready Queue)에 가장 먼저 도착한 프로세스에게 우선적으로 CPU를 할당하고, 자발적으로 종료하거나 I/O를 요청할 때까지 절대로 뺏지 않는 단순 무식한 비선점형 (Non-preemptive) 알고리즘이다.
  2. 가치: 코딩이 극도로 쉽고(FIFO 큐 하나로 구현 완료), 문맥 교환 (Context Switch) 오버헤드가 최소화되어 과거 배치 처리(Batch) 시스템에서 처리량을 올리는 데 기여했다.
  3. 융합: 그러나 무거운 프로세스 하나가 CPU를 장악하면 뒤에 도착한 가벼운 프로세스들이 끝없이 묶여버리는 치명적인 **호위 효과 (Convoy Effect)**를 유발하므로, 현대 시분할 (Time-sharing) 범용 운영체제의 메인 스케줄러로는 철저히 도태되었다.

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

  • 개념: "선착순"이라는 일상생활의 가장 보편적인 규칙을 컴퓨터 스케줄링에 그대로 가져온 방식이다. 도착한 시간(Arrival Time)이 빠른 순서대로 프로세스 제어 블록(PCB)을 큐의 뒤에 붙이고, CPU가 비면 큐의 맨 앞에서 하나씩 꺼내어 실행시킨다.
  • 필요성: 컴퓨터의 자원(메모리, 속도)이 극도로 제한적이었던 초기 시절, 스케줄링 알고리즘 자체가 복잡하면 운영체제가 너무 많은 자원을 갉아먹게 된다. 따라서 운영체제 내부 로직을 최소화하면서도, "가장 먼저 부탁한 사람부터 처리해 준다"는 절대적인 공정성(Fairness)을 확보하기 위해 고안되었다.
  • 💡 비유: 마트의 **'1줄 서기 일반 계산대'**와 같다. 카트에 물건을 100개 담은 사람이든 껌 1개 담은 사람이든 상관없이, 오직 줄을 선 순서대로만 계산원(CPU)을 독점하여 끝날 때까지 비켜주지 않는다.
  • 등장 배경: 과거 천공 카드를 집어넣던 일괄 처리 (Batch) 시스템 시절에는 어차피 하루 뒤에나 결과를 볼 수 있었기 때문에 빠른 응답이 중요하지 않았다. 그냥 순서대로 차곡차곡 에러 없이 돌려주기만 하면 되었기에 큐(Queue) 구조 하나만으로 완벽히 작동하는 FCFS가 스케줄러의 조상님으로 군림했다.
  [FCFS 알고리즘의 동작 기본 원리도]

                  (Ready Queue - 선입선출 구조)
  새로운 프로세스  ▶  [ P4 ] [ P3 ] [ P2 ] [ P1 ]  ▶  [ CPU (실행) ]
   (도착 시 큐의                                      (끝날 때까지 절대 방해받지 않음)
    맨 뒤에 줄 섬)                                       │
                                                       ▼
                                                 (실행 완료 후 빠짐)

[다이어그램 해설] FCFS는 자료구조상 완벽한 FIFO (First-In, First-Out) 큐를 사용한다. 스케줄러가 어떤 놈이 우선순위가 높은지, 작업 시간이 짧은지 계산할 필요가 1도 없다. CPU가 비면 그저 큐 맨 앞의 Head 노드를 떼서 CPU에 밀어 넣으면 임무가 끝난다. 이 압도적인 '단순성'이 유일무이한 장점이다.

  • 📢 섹션 요약 비유: 맛집에 먼저 온 사람이 먼저 밥을 먹고 나가는, 가장 인간적이고 도덕적(?)인 선착순 규칙입니다. 늦게 왔다고 뒷사람을 먼저 들여보내는 새치기는 절대 허용하지 않습니다.

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

대기 시간 (Waiting Time) 계산의 비효율성 극명화

FCFS의 진정한 공포는 프로세스들의 "도착 순서"라는 우연성에 의해 시스템 성능(평균 대기 시간)이 극단적으로 널뛰기한다는 점이다. 이를 간트 차트(Gantt Chart)로 시뮬레이션해 보면 명확하다.

가정: 프로세스 P1(24ms), P2(3ms), P3(3ms)가 0ms 시점에 (P1, P2, P3) 순으로 미세하게 큐에 도착했다고 가정.

  ┌───────────────────────────────────────────────────────────────────────┐
  │     [시나리오 1] 무거운 놈(P1)이 1등으로 도착했을 때 최악의 궤적      │
  ├───────────────────────────────────────────────────────────────────────┤
  │                                                                       │
  │  0        (P1 실행)            24   (P2)  27  (P3)  30 ms             │
  │  │██████████████████████████████│████│████│                           │
  │                                                                       │
  │  - P1 대기시간: 0 ms                                                  │
  │  - P2 대기시간: 24 ms (억울하게 앞사람 끝날 때까지 갇힘)              │
  │  - P3 대기시간: 27 ms (더 억울함)                                     │
  │                                                                       │
  │  ▶ 평균 대기 시간 = (0 + 24 + 27) / 3 = 17.0 ms                       │
  └───────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] P1이라는 덩치 큰 트럭이 1차선 도로(단일 CPU)를 가로막고 24ms 동안 천천히 굴러가니, 뒤에서 금방 지나갈 수 있는 오토바이들(P2, P3)이 옴짝달싹 못 하고 24ms 넘게 브레이크를 밟고 서 있어야 한다. 3ms짜리 작업을 위해 27ms를 대기한다는 것은 응답성 관점에서 시스템 붕괴를 의미한다.

  ┌──────────────────────────────────────────────────────────────────────┐
  │     [시나리오 2] 가벼운 놈(P2, P3)이 우연히 1등으로 도착했을 때      │
  ├──────────────────────────────────────────────────────────────────────┤
  │                                                                      │
  │  0 (P2) 3 (P3) 6            (P1 실행)                 30 ms          │
  │  │████│████│██████████████████████████████████████│                  │
  │                                                                      │
  │  - P2 대기시간: 0 ms                                                 │
  │  - P3 대기시간: 3 ms                                                 │
  │  - P1 대기시간: 6 ms (P1 입장에선 티도 안 나는 미미한 대기)          │
  │                                                                      │
  │  ▶ 평균 대기 시간 = (0 + 3 + 6) / 3 = 3.0 ms                         │
  └──────────────────────────────────────────────────────────────────────┘

결론적으로 프로세스 도착 순서가 (P2, P3, P1)로 찰나의 우연으로 바뀌었을 뿐인데, **평균 대기 시간이 17ms에서 3ms로 거의 6배 가까이 폭락(개선)**했다. 스케줄링 성능이 '운(Luck)'에 의존한다는 것은 범용 OS 설계에 있어서 최악의 결함이다.

  • 📢 섹션 요약 비유: 마트 계산대에서 껌 하나 산 뒷사람 10명이, 카트 3개 분량의 장을 본 첫 번째 아줌마가 계산을 마칠 때까지 원망스럽게 쳐다만 보고 있는 피 말리는 지연 구조를 만들어냅니다.

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

호위 효과 (Convoy Effect) 집중 분석

FCFS의 가장 대표적인 부작용을 일컬어 **호위 효과 (Convoy Effect)**라고 부른다. 이는 CPU 바운드 프로세스(무거운 연산)와 I/O 바운드 프로세스(가벼운 입출력 대기)가 섞여 있을 때 최악의 형태로 폭발한다.

  1. CPU 바운드 프로세스가 CPU를 잡고 길게 연산한다. (비선점이므로 누구도 터치 못함)
  2. 그 사이, 디스패치나 I/O를 마친 가벼운 I/O 바운드 프로세스들이 우르르 몰려와 Ready 큐 뒤에 줄을 선다.
  3. 디스크/네트워크(I/O 장치)는 처리할 일이 없어서 멈춰서 놀게 된다. (장치 유휴 상태 파생)
  4. 마침내 CPU 바운드 프로세스가 CPU를 놓고 I/O를 하러 가면, 큐에 있던 I/O 바운드 프로세스들이 찰나의 시간만 CPU를 쓰고 다시 전부 I/O 큐로 우르르 넘어가 버린다.
  5. 이번엔 역으로 CPU가 할 일이 없어서 놀게 된다.
  [호위 효과로 인한 자원 병렬성 파괴 현상]
  
  [CPU]  : [██ 무거운 놈 ██][ 가벼운 놈들 타다닥 ](  쉬는 중  )
  [I/O]  : (   쉬는 중   )                      [██ 다같이 몰려서 I/O 병목 ██]
  
  >> 결과: CPU와 I/O 장치가 엇박자로 쉴드 치며 돌아가므로 시스템 효율(이용률)이 바닥을 친다.

이처럼 하나의 굼뜬 프로세스가 좁은 길을 가로막음으로써, 전체 부대(I/O 바운드 프로세스들)가 그 느린 속도에 맞춰 줄줄이 느릿느릿 따라가야 하는 현상이 마치 느린 트럭을 호위하며 기어가는 행렬과 같다고 하여 붙여진 이름이다.

다른 비선점 알고리즘과의 1:1 비교

비교FCFS (선착순)SJF (가장 짧은 작업 우선)
판단 기준누가 먼저 도착했는가?누가 가장 빨리 끝나는가?
장점절대적인 기회 균등 (기아 상태 방지)평균 대기시간 극단적 최소화 (최적)
단점호위 효과 발생 (평균 대기시간 폭망 가능성)긴 작업은 영원히 실행 못 함 (기아 발생), 런타임 예측 불가
  • 📢 섹션 요약 비유: FCFS는 "먼저 온 사람이 먼저 탄다"는 정의로움이 있지만, 에버랜드 롤러코스터 앞에서 앞사람이 친구 100명 자리를 미리 맡아뒀다고 하루 종일 그 팀만 태우는 것과 같은 부조리를 야기합니다.

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

실무 시나리오

  1. 하둡(Hadoop) / 맵리듀스(MapReduce) 기본 잡 스케줄러: FCFS는 시분할 OS에서는 멸종했지만, 거대한 빅데이터 처리 시스템의 초기 기본 큐로 쓰였다. 어차피 응답 시간이 중요하지 않은 며칠짜리 로그 분석 배치(Batch) 작업들을 유저가 던진 순서대로(FIFO) 클러스터 자원에 할당하여 순차적으로 돌릴 때는 복잡한 스케줄링 로직이 필요 없는 FCFS가 가장 안정적이고 구현하기 좋았다.
  2. 이벤트 드리븐(Event-Driven) 서버 큐 (Node.js/Redis): 커널의 CPU 스케줄러가 아닌 애플리케이션 레벨의 큐 메커니즘에서는 여전히 FCFS(FIFO 큐)가 지배적이다. Redis 서버에 들어오는 수만 개의 명령어(SET, GET) 처리나 Node.js의 이벤트 루프에 쌓인 콜백 함수들은 선착순(도착 시간 순)으로 큐에 쌓이고 앞단부터 순차적으로 처리된다. 이 큐가 막히는 현상이 바로 애플리케이션 레벨의 호위 효과(Event Loop Block)다.
  ┌───────────────────────────────────────────────────────────────┐
  │     실무에서 FIFO(FCFS) 패턴 도입 여부 의사결정 트리          │
  ├───────────────────────────────────────────────────────────────┤
  │                                                               │
  │   구현하려는 시스템에서 '처리 시간의 편차'가 큰가?            │
  │                │                                              │
  │                ▼                                              │
  │     [모든 작업이 1ms 이하로 비슷하게 매우 짧다]               │
  │       ├─▶ 예: Redis 명령어 커맨드, 게임 패킷 처리             │
  │       └─▶ 판단: FCFS(단순 FIFO 큐) 도입이 가장 완벽.          │
  │                 (호위 효과가 발생할 건덕지가 없음)            │
  │                                                               │
  │     [어떤 건 1ms, 어떤 건 1시간으로 크기가 들쭉날쭉하다]      │
  │       ├─▶ 예: OS 프로세스, 복잡한 API 웹 서버, DB 쿼리        │
  │       └─▶ 판단: FCFS 절대 금지! 라운드 로빈이나 선점형 필수.  │
  │                 (호위 효과로 인해 서버가 즉시 마비됨)         │
  └───────────────────────────────────────────────────────────────┘

[다이어그램 해설] FCFS 아키텍처를 쓰기 위한 절대 전제 조건은 **"대기 큐에 들어오는 모든 태스크들의 크기(Size)가 일률적으로 작아야 한다"**는 점이다. Redis는 인메모리 단일 스레드 기반이므로 모든 연산이 마이크로초 단위로 끝난다. 그래서 큐에 선착순(FCFS)으로 쌓아놓아도 막힘 없이 물 흐르듯 처리된다. 만약 Redis에 KEYS * 같은 전체 스캔(무거운 작업)을 던지면 여지없이 FCFS의 호위 효과가 터지며 서버가 멈춘다.

  • 📢 섹션 요약 비유: 우편물 분류 공장에서 모든 봉투의 크기가 똑같다면 선착순으로 기계에 밀어 넣는 게 최고지만, 갑자기 냉장고만 한 소포가 섞여 들어오면 컨베이어 벨트(FCFS 큐) 전체가 멈춰서 파탄이 납니다.

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

기대효과

스케줄러의 연산 오버헤드나 자료구조(Tree, Heap) 조작 비용을 제로에 가깝게 만들고, 모든 프로세스가 "언젠가는 반드시 내 차례가 온다"는 절대적인 기아 상태 (Starvation) 회피를 보장받는다.

결론 및 미래 전망

운영체제 메인 스케줄러로서의 FCFS는 박물관에 갔지만, 분산 메시지 큐 (Kafka, RabbitMQ 등) 아키텍처의 근간으로서 데이터의 **순서 보장(Ordering)**이 필수적인 스트리밍 처리 분야에서는 여전히 1순위 철학으로 군림하고 있다. 시분할 시스템에서는 도태되었으나, 클라우드 네이티브의 이벤트 소싱 (Event Sourcing) 환경에서 데이터의 선후 관계를 훼손하지 않기 위해 현대적으로 재해석되어 널리 사용되고 있다.

  • 📢 섹션 요약 비유: 선착순이라는 규칙은 복잡한 인간관계(범용 OS)를 조율하기엔 너무 단순하고 답답해서 버려졌지만, 공장의 정밀 컨베이어 벨트(메시지 큐 순서 보장)를 설계할 때는 절대 어겨서는 안 될 제1법칙으로 부활했습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭관계 및 시너지 설명
호위 효과 (Convoy Effect)긴 처리 시간을 가진 프로세스 하나 때문에 FCFS 스케줄링 큐 전체의 평균 대기시간이 나락으로 떨어지는 구조적 병목 현상이다.
비선점형 스케줄링 (Non-preemptive)앞선 프로세스가 스스로 양보할 때까지 타이머 인터럽트로 강제 제압할 수 없다는 FCFS의 근본적인 토대다.
FIFO 큐 (First-In, First-Out)가장 먼저 들어온 데이터가 가장 먼저 나간다는 FCFS를 물리적(자료구조적)으로 구현한 가장 원초적이고 단순한 리스트다.
응답 시간 (Response Time)FCFS에서 가장 방어하기 힘든 취약 지표로, 도착 순서라는 우연에 의해 치명적으로 흔들리며 대화형 시스템 도입을 불가능하게 했다.
라운드 로빈 (Round Robin)FCFS의 억울한 호위 효과를 해결하기 위해, 도착 순서는 유지하되 '타임 퀀텀'을 주어 강제로 뒤로 돌려보내는 방식으로 진화한 선점형 선착순이다.

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

  1. 학교 화장실에서 먼저 줄 선 친구가 화장실에 들어가면, 그 친구가 볼일을 다 보고 나올 때까지 밖에서 무조건 기다려야 하는 선착순 규칙이 FCFS예요.
  2. 늦게 온 친구가 아무리 화장실이 급해도(우선순위가 높아도), 규칙 때문에 절대 먼저 들어갈 수 없고 발을 동동 구르며 기다려야 해요.
  3. 만약 먼저 들어간 친구가 배탈이 나서 30분 동안 안 나온다면(호위 효과), 뒤에 1분이면 끝날 친구들 10명이 화장실 앞에서 오줌을 싸게 되는 무서운 사태가 벌어집니다!