다단계 큐 스케줄링 (Multilevel Queue Scheduling)

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

본질: 다단계 큐 스케줄링 (Multilevel Queue Scheduling)은 Ready 큐 하나에 모든 프로세스를 섞어놓지 않고, 프로세스의 성격(System, Interactive, Batch 등)에 따라 물리적으로 여러 개의 독립된 큐(Queue)로 분리하여 층층이 관리하는 아키텍처다.

가치: 각 큐마다 자신의 성격에 가장 잘 맞는 고유의 스케줄링 알고리즘(예: 상위는 라운드 로빈, 하위는 FCFS)을 독립적으로 적용할 수 있어 시스템의 목적에 부합하는 정밀한 자원 분배가 가능하다.

융합: 하지만 한 번 큐에 배정된 프로세스는 다른 큐로 절대 이동할 수 없는 경직성(Rigidity) 때문에 하위 큐의 기아 상태(Starvation)를 피할 수 없었으며, 이를 해결하기 위해 프로세스의 층간 이동을 허용하는 **다단계 피드백 큐 (MLFQ)**로 진화하는 징검다리가 되었다.

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

개념: 준비 완료(Ready) 상태의 프로세스들을 하나의 긴 줄로 세우는 대신, 중요도나 성격에 따라 1등석 큐, 비즈니스석 큐, 이코노미석 큐처럼 여러 개의 별도 큐를 물리적으로 생성하고 프로세스를 영구적으로 분류하는 스케줄링 기법이다.
필요성: 백그라운드에서 하루 종일 돌아가는 데이터 백업 프로그램(Batch)과 사용자가 지금 당장 키보드를 치고 있는 워드 프로세서(Interactive)를 같은 줄에 세우고 동일한 잣대(예: RR 10ms)로 평가하는 것은 어불성설이다. 성격이 전혀 다른 워크로드들은 줄을 아예 따로 세우고 다르게 취급(규칙 분리)해야 시스템 효율이 극대화된다.
💡 비유: 고속도로 톨게이트에서 모든 차를 한 줄로 세우지 않고, **'하이패스 전용 차로', '현금 전용 차로', '화물차 전용 차로'**를 아예 분리해서 요금소 직원의 일처리 방식을 달리하는 것과 같다.
등장 배경: 메모리 용량이 커지면서 한 컴퓨터 내에 (1) 시스템 데몬, (2) 사용자의 대화형 터미널, (3) 긴 일괄 처리 작업이 동시에 상주하게 되었다. 이들을 단일 큐로 통제하기엔 단일 스케줄러 알고리즘(RR이든 FCFS든)의 한계가 명확했기에 분할 통치(Divide and Conquer)의 철학이 도입되었다.

  [다단계 큐 스케줄링의 분할 통치 아키텍처]

  (최우선순위)
   [ 큐 0: 시스템 프로세스 (System) ] ────────▶ [ 라운드 로빈 (RR) 5ms ]
             ↓ (비어있어야만 아래로 기회 넘어감)
   [ 큐 1: 대화형 프로세스 (Interactive) ] ───▶ [ 라운드 로빈 (RR) 20ms ]
             ↓ (비어있어야만 아래로 기회 넘어감)
   [ 큐 2: 편집/컴파일 프로세스 ] ────────────▶ [ 라운드 로빈 (RR) 50ms ]
             ↓ 
   [ 큐 3: 일괄 처리 프로세스 (Batch) ] ──────▶ [ FCFS (선착순) ]
  (최하우선순위)                             
             
  >> 프로세스는 생성될 때 자신의 신분에 맞는 큐에 딱 꽂히고 평생 그곳을 벗어나지 못한다.

[다이어그램 해설] 이 아키텍처의 혁신성은 '알고리즘의 다원화'에 있다. 대화형 큐는 잦은 마우스 클릭에 즉각 반응해야 하므로 타임 퀀텀이 아주 짧은 RR을 쓴다. 반면 백그라운드에서 조용히 도는 Batch 큐는 문맥 교환을 줄여 처리량을 높여야 하므로 FCFS를 쓴다. 단일 큐 시절의 골칫거리였던 "RR을 쓸까, FCFS를 쓸까?"라는 고민을 "둘 다 쓴다!"로 파훼한 설계다.

📢 섹션 요약 비유: 놀이공원에서 "연간 회원권 전용 줄(빠른 RR)", "일반 티켓 줄(느린 RR)", "단체 관람객 줄(FCFS)"을 철저히 분리하고, 각 줄마다 배정하는 직원의 수를 다르게 하여 고객의 목적에 맞는 서비스를 제공하는 맞춤형 줄서기 시스템입니다.

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

스케줄링의 2계층 구조 (Two-level Scheduling)

다단계 큐는 내부적으로 두 번의 스케줄링 결정을 내린다. 이것이 아키텍처의 핵심이다.

큐 간 스케줄링 (Scheduling between Queues)
- 어떤 큐에게 CPU를 줄 것인가를 결정한다.
- 고정 우선순위 선점 방식 (Fixed-priority Preemptive): 가장 보편적이다. 상위 큐(Q0)에 단 하나라도 프로세스가 있으면 무조건 Q0부터 실행한다. 하위 큐(Q3)가 실행 중인데 상위 큐에 하나가 도착하면 즉시 모가지를 치고(선점) 상위 큐로 CPU가 넘어간다.
- 타임 슬라이스 방식 (Time-slice): 상위 큐가 CPU를 영원히 독점하는 걸 막기 위해, 전체 CPU 시간의 80%는 Q0과 Q1에 주고, 20%는 하위 Q2, Q3에 강제로 배분하는 식의 시분할을 큐 단위로 적용하기도 한다.
큐 내부 스케줄링 (Scheduling within Queue)
- 선택된 큐 안에서 어떤 프로세스에게 CPU를 줄 것인가 결정한다.
- 각 큐는 앞서 언급한 대로 자신만의 독자적인 스케줄링 알고리즘(RR, FCFS, SJF 등)을 독립적으로 가동한다.

다단계 큐의 경직성 (신분제의 고착)

이 모델의 가장 큰 특징이자 치명적 한계는 "이동 불가 (No Migration)" 원칙이다.

  ┌──────────────────────────────────────────────────────────────────────┐
  │         다단계 큐에서의 '이동 불가' 원칙에 따른 비극 시뮬레이션      │
  ├──────────────────────────────────────────────────────────────────────┤
  │                                                                      │
  │  1. [워드 프로세서 실행]                                             │
  │     성격: 대화형 프로세스 ─▶ 큐 1 (Interactive Queue) 배정           │
  │     특징: 마우스 칠 때만 CPU 잠깐 쓰고 I/O 대기를 반복. 쾌적함!      │
  │                                                                      │
  │  2. [사용자가 워드에서 1,000페이지 PDF 저장 버튼 클릭!]              │
  │     성격 돌변: I/O 대기 없이 CPU만 100% 혹사하는 괴물로 변신!        │
  │                                                                      │
  │  🚨 시스템의 비극 (Rigidity)                                         │
  │  - 얘는 이제 사실상 일괄 처리(Batch) 성격으로 바뀌었다.              │
  │  - 하지만 '이동 불가' 원칙 때문에 여전히 큐 1의 높은 권력을 누린다.  │
  │  - 결과: 이 PDF 렌더링이 끝날 때까지 같은 큐 1에 있는 다른 진짜      │
  │          대화형 프로세스(웹브라우저 등)들이 렉에 걸려 뻗어버린다.    │
  │  - 큐 간의 철저한 격리가 무용지물이 되는 순간이다.                   │
  └──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 프로세스는 살아 움직이며 성격(Phase)이 바뀐다. 처음에 "대화형" 딱지를 달고 1등석에 탑승한 프로세스가 갑자기 짐을 100개씩 풀어놓으며 무거운 연산을 시작해도, 승무원(스케줄러)은 얘를 이코노미석(Batch 큐)으로 쫓아낼 법적 근거가 없다. 이 경직성이 다단계 큐 스케줄링이 현대 OS에서 단독으로 쓰이지 못하는 가장 큰 물리적 벽이다.

📢 섹션 요약 비유: 인도의 철저한 카스트 제도와 같습니다. 왕족(시스템 큐)으로 태어나면 무조건 호의호식하고, 천민(배치 큐)으로 태어나면 평생 무거운 짐(FCFS)만 져야 합니다. 천민이 아무리 똑똑해져도 왕족 큐로 절대 넘어갈 수 없는 꽉 막힌 사회입니다.

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

우선순위 스케줄링 (Priority) 과의 비교 차이

두 모델 모두 "높은 순위 먼저"라는 뼈대는 같지만 물리적 구현체가 다르다.

비교 항목	우선순위 스케줄링 (단일 큐)	다단계 큐 스케줄링 (Multi-Queue)
자료 구조	1개의 큐 안에 번호 딱지만 다르게 붙어있음	번호(성격)별로 물리적인 큐가 N개 따로 존재
탐색 오버헤드	누가 제일 높은지 1개 큐를 뒤져야 함 (O(N) 또는 O(log N))	그냥 0번 큐부터 쑥 보고 있으면 꺼냄 (극강의 O(1))
알고리즘 유연성	큐가 하나라 무조건 선착순 or 특정 규칙 하나만 가능	큐마다 RR, FCFS 등 서로 다른 알고리즘 떡칠 가능
기아 상태 방어	에이징(Aging) 변수 조작으로 쉽게 회피 가능	큐 간 이동이 안 되므로 하위 큐 기아 방어 매우 어려움

오버헤드 면에서는 다단계 큐가 압도적으로 빠르다. 커널은 0번 큐 헤드, 1번 큐 헤드 포인터만 순서대로 쳐다보면 되기 때문에 디스패치 지연이 극한으로 줄어든다. 하지만 그놈의 "이동 불가" 규정이 하위 큐의 기아 상태(Starvation)를 확정적으로 만들어버린다.

📢 섹션 요약 비유: 우선순위 제도가 "한 교실(단일 큐) 안에서 1등부터 줄 세우기"라면, 다단계 큐는 아예 건물을 쪼개서 "우등생 반 건물, 열등생 반 건물(물리적 분리)"을 만들고 선생님(알고리즘)도 완전히 다르게 배정하는 대규모 학원 시스템입니다.

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

실무 시나리오

리눅스 RTOS 및 커널 스레드 분리 아키텍처: 완전한 다단계 큐(이동 불가) 철학은 현대 범용 OS 유저 공간에서는 버려졌지만, 커널 공간과 실시간(Real-time) 태스크를 분리할 때는 아직도 절대적인 원칙으로 쓰인다. 리눅스에서 일반 사용자의 워크로드는 스케줄링 클래스가 SCHED_NORMAL (CFS 알고리즘)에 배정되지만, 하드웨어 인터럽트 처리나 실시간 데몬은 SCHED_FIFO나 SCHED_RR 같은 최상위 독립 큐에 고정 배정된다. 이 두 세계의 프로세스들은 큐 사이를 횡단하지 않으며, 실시간 큐가 비어있을 때만 비로소 유저 큐(CFS)로 CPU가 내려온다. 철저한 다단계 큐의 실무 응용이다.
쿠버네티스 (K8s) QoS 클래스의 우선순위 관리: 쿠버네티스의 파드(Pod) 퇴거(Eviction) 및 자원 배분 정책은 완벽히 다단계 큐 철학을 차용한다. 자원이 부족할 때 K8s는 파드를 세 가지 절대 계급으로 나눈다.
- Guaranteed (최상위: Limit=Request)
- Burstable (중간: Limit > Request)
- BestEffort (최하위: Limit 설정 안 함) 자원 경합이 터지면 K8s OOM Killer는 묻지도 따지지도 않고 BestEffort 계급부터 학살한다. 이 계급은 런타임에 절대 이동(Migration)하지 않는 철저한 다단계 아키텍처다.

  ┌─────────────────────────────────────────────────────────────────┐
  │     클라우드 인프라의 트래픽 라우팅 다단계 큐 (QoS) 분배 전략   │
  ├─────────────────────────────────────────────────────────────────┤
  │                                                                 │
  │   [API Gateway (Kong, AWS API GW)]                              │
  │   수만 건의 트래픽 유입 ─── (분류기 Classifier) ──┐             │
  │                                            │                    │
  │   [티어 1: 유료 프리미엄 회원 API 요청] ◀─────────┤             │
  │      └─▶ 전용 고성능 큐 / 쓰레드 풀 100개 할당        │         │
  │                                            │                    │
  │   [티어 2: 일반 로그인/결제 요청] ◀──────────────┤              │
  │      └─▶ 범용 큐 / 쓰레드 풀 50개 할당               │          │
  │                                            │                    │
  │   [티어 3: 무료 사용자 단순 검색 (Best Effort)] ◀──┘            │
  │      └─▶ 잉여 큐 / 쓰레드 풀 10개 (남는 자원만)                 │
  │                                                                 │
  │   🚨 서버 폭주 시: 티어 3 큐의 연결부터 가차 없이 끊어(Drop)    │
  │                 티어 1과 2의 CPU(응답성)를 절대 방어한다.       │
  └─────────────────────────────────────────────────────────────────┘

[다이어그램 해설] CPU 스케줄러뿐만 아니라 백엔드 아키텍처에서 서비스 수준 협약(SLA)을 지키기 위한 절대적인 방어선이 다단계 큐 패턴이다. 돈을 낸 고객(VIP)의 요청과 무료 고객의 요청을 같은 메시지 큐(단일 큐)에 넣는 것은 인프라 설계의 하수다. 아예 토픽이나 큐를 물리적으로 분리하여, VIP 큐 리스너에게 CPU 코어를 더 많이 할당하는 방식이 현대 서버 분산 처리의 핵심 철학이다.

📢 섹션 요약 비유: 넷플릭스에서 망 사용료를 낸 통신사 전용 캐시 서버(상위 큐)를 따로 구축하여 HD 화질을 보장하고, 망 사용료를 안 낸 곳은 일반 서버(하위 큐)에 던져서 느린 화질로 고정시켜 버리는 냉혹한 비즈니스 아키텍처와 같습니다.

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

기대효과

서로 다른 스케줄링 요구사항(빠른 응답 vs 높은 처리량)을 가진 이기종 프로세스들을 단일 CPU 위에서 충돌 없이 가장 완벽하게 조율할 수 있다. 큐 헤드만 탐색하면 되므로 스케줄링 연산 오버헤드가 거의 O(1)에 수렴하는 극한의 시스템 효율을 얻는다.

결론 및 미래 전망

다단계 큐 (Multilevel Queue) 스케줄링은 서로 다른 워크로드를 분리한다는 대전제를 세운 기념비적 아키텍처다. 그러나 **"신분 이동의 불가"**가 낳는 끔찍한 기아 상태(Starvation)와 시스템 유연성 부족으로 인해, 범용 운영체제의 CPU 스케줄러로서의 수명은 거기서 끝이 났다. 결국 이 아키텍처에 에이징(Aging) 철학을 주입하여, "시간이 지나면 아래 큐에서 위 큐로 올라가고, 타임 퀀텀을 다 쓰면 위 큐에서 아래 큐로 쫓겨나는" 동적 에스컬레이터 시스템, 즉 **다단계 피드백 큐 (MLFQ)**로 진화하는 위대한 거름이 되었다. 현재는 OS 커널을 넘어 K8s QoS, 네트워크 라우터 패킷 스케줄링의 근간으로 사용되고 있다.

📢 섹션 요약 비유: 이 제도는 완벽한 아파트 층수(큐 분리)를 만들어냈지만 계단과 엘리베이터(이동 수단)를 만들지 않은 미완성 도면이었습니다. 이 도면에 엘리베이터를 설치해 층간 이동을 허용한 순간(MLFQ), 인류 스케줄링 역사의 마스터피스가 완성되었습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
다단계 피드백 큐 (MLFQ)	다단계 큐의 "이동 불가"라는 치명적 결함을 뜯어고쳐 프로세스가 큐 위아래를 자유롭게 오르내릴 수 있게 한 최종 진화 형태다.
라운드 로빈 (RR)	다단계 큐의 상위 큐(Interactive)에서 대화형 프로세스들의 응답성을 보장하기 위해 주로 채택되는 부품 알고리즘이다.
기아 상태 (Starvation)	상위 큐에 프로세스가 무한정 들어오면, 아랫줄 큐(Batch)의 프로세스들이 구조적으로 영원히 CPU를 받지 못해 죽어버리는 현상이다.
O(1) 스케줄링 오버헤드	우선순위를 일일이 정렬할 필요 없이, 가장 최상단 큐의 Head만 쳐다보고 빼면 되기 때문에 획득하는 극강의 탐색 속도다.
전경/배경 (Foreground/Background)	프로세스 성격을 두 개로 나누어, 현재 화면에 뜬 창은 전경 큐(RR), 뒤에 숨은 창은 배경 큐(FCFS)로 물리적으로 나누는 초기 아이디어다.

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

급식소에서 전교생을 한 줄로 세우면 너무 복잡하니까, "선생님 줄", "1학년 줄", "6학년 줄"을 아예 따로따로 바리케이드를 쳐서 만들어 놓은 게 다단계 큐 스케줄링이에요.
선생님 줄은 무조건 제일 맛있는 반찬을 빨리 받을 수 있고, 6학년 줄은 선생님과 1학년이 다 받을 때까지 무조건 기다려야 해요.
가장 큰 문제는, 내가 한 번 6학년 줄에 섰으면 절대 1학년 줄로 새치기나 이동을 할 수 없어서 밥을 영영 못 먹을 수도 있는 슬픈 규칙(이동 불가)이라는 점이에요!