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

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

1. 본질: 다단계 큐 스케줄링 (Multilevel Queue Scheduling)은 준비 큐 (Ready Queue)를 하나로 두지 않고, 시스템·대화형·배치 작업처럼 성격이 다른 프로세스를 서로 다른 큐로 고정 분류해 관리하는 기법이다.
2. 가치: 큐마다 다른 스케줄링 정책을 적용할 수 있어, 응답성이 중요한 작업과 처리량이 중요한 작업을 같은 규칙으로 억지로 다루지 않아도 된다.
3. 판단 포인트: 분류가 고정되어 있어 유연성은 낮고, 상위 큐가 과도하게 바쁘면 하위 큐가 기아 상태 (Starvation)에 빠질 수 있으므로 MLFQ (Multilevel Feedback Queue)와의 경계를 분명히 이해해야 한다.

Ⅰ. 개요 및 필요성

다단계 큐 스케줄링은 프로세스의 종류별로 줄을 따로 세우는 스케줄링 방식이다. 하나의 Ready Queue 안에 시스템 데몬, 사용자 인터랙티브 작업, 백그라운드 배치 작업을 모두 넣고 동일한 정책으로 처리하면, 어느 한쪽의 요구를 만족시키는 순간 다른 한쪽이 손해를 본다. 짧은 응답 시간이 중요한 작업과 긴 처리 시간이 중요한 작업은 요구 조건이 다르기 때문이다.

이 방식이 필요한 이유는 CPU (Central Processing Unit) 스케줄링의 목표가 하나가 아니기 때문이다. 대화형 작업은 응답 시간 (Response Time) 이 중요하고, 배치 작업은 처리량 (Throughput) 과 문맥 교환 비용 절감이 중요하다. 시스템 프로세스는 어떤 경우에는 지연 허용 폭이 더 작을 수도 있다. 하나의 규칙으로 모두를 만족시키기 어렵기 때문에, 먼저 성격별로 분리한 뒤 각 큐마다 최적의 정책을 적용하는 발상이 나왔다.

즉 다단계 큐는 "누가 먼저 실행될까?"를 넘어서, "애초에 누구와 누구를 같은 줄에 세워야 하는가?" 에 답하는 기법이다. 공정성만이 아니라 서비스 계층화(service differentiation)를 위한 스케줄링 구조라고 볼 수 있다.

┌───────────────────────────────────────────────────────────────────┐
│ 단일 Ready Queue의 한계                                           │
├───────────────────────────────────────────────────────────────────┤
│ [System Daemon] [Terminal] [Compiler Job] [Backup Task] [Editor] │
│                 모두 같은 큐에 섞이면                              │
│          한 정책으로는 응답성·처리량을 동시에 만족시키기 어렵다    │
└───────────────────────────────────────────────────────────────────┘

• 📢 섹션 요약 비유: 다단계 큐 스케줄링은 응급실, 일반 외래, 건강검진 접수 창구를 하나로 합치지 않고 따로 두는 병원 운영 방식과 같다. 환자 성격이 다른데 줄까지 같으면 전체가 비효율적이 된다.

Ⅱ. 아키텍처 및 핵심 원리

다단계 큐 스케줄링의 핵심은 분류(classification), 큐 간 선택, 큐 내부 선택의 3단계다. 먼저 프로세스를 성격에 따라 특정 큐에 배정하고, 그다음 어느 큐에 CPU를 줄지 정한 뒤, 마지막으로 선택된 큐 안에서 실제 프로세스를 뽑는다. 중요한 점은 전통적인 다단계 큐에서는 한 번 배정된 프로세스가 다른 큐로 이동하지 않는 경우가 많다는 것이다.

아래 그림은 다단계 큐의 전형적인 동작 흐름을 보여 준다.

┌───────────────────────────────────────────────────────────────────┐
│ Multilevel Queue Scheduling Flow                                 │
├───────────────────────────────────────────────────────────────────┤
│ New Process                                                       │
│     │                                                             │
│     ▼                                                             │
│ Classifier                                                        │
│     ├─▶ Q0 : System        ─▶ RR 5 ms                             │
│     ├─▶ Q1 : Interactive   ─▶ RR 20 ms                            │
│     └─▶ Q2 : Batch         ─▶ FCFS                                │
│                ▲                                                  │
│                │                                                  │
│      Queue Scheduler chooses one queue                            │
│      (fixed priority or queue time slice)                         │
└───────────────────────────────────────────────────────────────────┘

이 그림에서 핵심은 큐 내부 정책과 큐 간 정책이 분리되어 있다는 점이다. 예를 들어 대화형 큐는 RR로 짧게 돌리고, 배치 큐는 FCFS로 길게 돌릴 수 있다. 하지만 상위 큐에 절대 우선권을 주면 하위 큐는 오래 기다릴 수 있다. 그래서 다단계 큐는 구조적으로 강력하지만, 동시에 경직된 신분제가 되기 쉽다.

특히 프로세스의 행동 특성이 실행 중에 바뀌는 경우 문제가 생긴다. 처음에는 인터랙티브처럼 보이던 작업이 대규모 계산으로 변해도, 큐가 고정이면 계속 높은 대우를 받을 수 있다. 반대로 처음에 배치 큐에 들어간 작업은 나중에 짧은 대화형 패턴을 보여도 쉽게 승급되지 않는다.

• 📢 섹션 요약 비유: 다단계 큐는 건물마다 다른 업무를 맡긴 회사 조직도와 같다. 고객 응대팀, 연구팀, 물류팀을 따로 두면 효율은 좋아지지만, 한 번 배치된 사람이 다른 부서 일에 맞게 옮겨 다니기 어려우면 조직이 경직된다.

Ⅲ. 비교 및 연결

다단계 큐를 제대로 이해하려면 단일 우선순위 큐와 다단계 피드백 큐 (MLFQ) 를 함께 비교해야 한다. 셋 다 우선순위를 다루지만, 분류 방식과 이동 가능성이 다르다.

단일 우선순위 스케줄링은 한 줄 안에서 순위를 매기는 방식이라 구현은 단순하지만, 서로 다른 워크로드 특성에 맞는 정책을 개별 적용하기 어렵다. 반면 다단계 큐는 큐별 정책을 다르게 둘 수 있어 서비스 차등화에는 강하다. 그러나 분류가 고정되면 실행 중 행동 변화를 반영하지 못한다. 그래서 현대 운영체제는 다단계 큐의 틀을 유지하되, MLFQ처럼 이동을 허용하거나 CFS (Completely Fair Scheduler)처럼 연속적인 공정성 모델을 채택한다.

또한 다단계 큐는 네트워크 QoS (Quality of Service), 프린터 스풀링, 실시간 작업 분리 같은 분야와도 연결된다. 즉 이 개념은 CPU 스케줄링 하나에만 갇힌 것이 아니라, 서비스 계층별 자원 분리라는 더 넓은 설계 패턴으로 확장된다.

• 📢 섹션 요약 비유: 단일 우선순위 큐가 한 운동장에서 학생을 줄 세우는 방식이라면, 다단계 큐는 아예 학년별 운동장을 따로 두는 방식이고, MLFQ는 경기력에 따라 다른 운동장으로 옮겨 다니게 하는 방식과 같다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서 다단계 큐 스케줄링은 서비스 등급이 분명하고, 작업 성격이 비교적 안정적일 때 유용하다. 예를 들어 실시간 태스크와 일반 태스크를 섞어 두면 안 되는 환경, 백그라운드 배치와 사용자 인터랙션을 분리해야 하는 환경에서는 큐를 아예 분리하는 편이 낫다. 운영체제나 런타임은 이를 통해 중요한 클래스에 더 짧은 지연과 명확한 우선권을 줄 수 있다.

실무 판단 기준

1. 작업 클래스가 오래 유지되는가? 성격이 자주 바뀌면 고정 분류는 부적합하다.
2. 최상위 큐에 절대 우선권이 필요한가? 실시간 성격이면 고정 우선순위가 필요할 수 있다.
3. 하위 큐 기아를 허용할 수 있는가? 불가능하다면 큐 간 시간 할당이나 MLFQ가 더 적합하다.
4. 큐마다 다른 정책이 실질적 이득을 주는가? 모두 같은 정책이면 굳이 여러 큐로 나눌 이유가 약하다.

대표적 적용 맥락

• 실시간 클래스와 일반 클래스 분리: 실시간 태스크를 일반 태스크보다 상위 큐에 둬 지연을 제한한다.
• 포그라운드/백그라운드 분리: 사용자 입력 반응 작업과 대량 일괄 작업을 다른 큐에서 처리한다.
• 서비스 등급별 자원 배분: 중요 서비스와 저우선 서비스의 CPU 가시성을 분리한다.

안티패턴

• 인터랙티브 작업이 배치 작업으로 변해도 같은 큐에 고정해 두는 설계
• 상위 큐가 항상 바쁜데도 하위 큐 보호 정책 없이 고정 우선순위만 고집하는 구성
• 큐를 여러 개 만들어 놓고 실제로는 모든 큐에 동일 정책을 적용해 복잡도만 높이는 설계

기술사 관점에서는 "여러 큐로 나눈다"는 정의에서 멈추지 말고, 큐 간 스케줄링 방식, 이동 불가의 한계, MLFQ로의 진화까지 답해야 한다. 그래야 다단계 큐를 정적 분리 모델로 정확히 설명할 수 있다.

• 📢 섹션 요약 비유: VIP 창구를 따로 만드는 것은 효율적이지만, VIP 줄이 하루 종일 비지 않으면 일반 줄 사람이 영영 못 들어갈 수도 있다. 그래서 창구 분리에는 반드시 운영 원칙이 따라야 한다.

Ⅴ. 기대효과 및 결론

다단계 큐 스케줄링의 가장 큰 효과는 서로 다른 작업군을 하나의 평균값으로 뭉개지 않고, 클래스별로 다른 정책을 줄 수 있다는 점이다. 이를 통해 응답성, 처리량, 우선권 보장 같은 목표를 계층별로 분리해 설계할 수 있다. 즉 이 기법은 공정성 하나만 보는 방식이 아니라, 시스템이 제공해야 할 서비스 수준을 스케줄러 구조에 반영하는 방법이다.

하지만 고정 분류는 분명한 한계를 가진다. 현대 워크로드는 실행 중 특성이 바뀌고, 사용자는 상호작용성과 장기 공정성을 동시에 기대한다. 그래서 다단계 큐는 오늘날 단독 완성형이라기보다, MLFQ나 현대 공정 스케줄러를 이해하기 위한 중간 단계의 핵심 개념으로 보는 편이 정확하다.

정리하면 다단계 큐 스케줄링은 "작업 성격별로 줄을 분리해 다른 규칙을 적용하는 정적 계층화 모델" 로 기억하면 된다. 강한 서비스 차등화에는 좋지만, 적응성은 제한적이다.

• 📢 섹션 요약 비유: 다단계 큐는 학교에서 학년별 교실을 나눠 다른 시간표를 적용하는 제도와 같다. 수업 운영은 쉬워지지만, 학생의 상태가 바뀌어도 반 이동이 어렵다면 한계가 분명해진다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

단일 Ready Queue 기반 스케줄링
        │
        ▼
작업 성격 차이에 따른 정책 충돌
        │
        ▼
다단계 큐 스케줄링
        │
        ├──────────────▶ 큐 간 고정 우선순위
        ├──────────────▶ 큐별 개별 정책 적용
        ├──────────────▶ 하위 큐 기아 문제
        └──────────────▶ MLFQ · Aging · 공정 스케줄링으로 발전

이 흐름도는 다단계 큐가 단일 큐의 한계를 해결하기 위해 등장했지만, 다시 경직성과 기아 문제를 낳아 더 적응적인 스케줄러로 발전해 가는 과정을 보여 준다.

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

1. 다단계 큐 스케줄링은 친구들을 한 줄로 세우지 않고, 나이와 할 일에 따라 여러 줄로 나누는 방법이에요.
2. 그래서 급한 친구 줄은 빨리 움직이고, 오래 걸리는 친구 줄은 천천히 움직일 수 있어요.
3. 하지만 한 번 뒤쪽 줄에 서면 앞으로 옮기기 어려워서, 기다림이 너무 길어질 수 있다는 점도 함께 생각해야 해요.