CPU Scheduling Algorithms

1. Overview

CPU 스케줄링 알고리즘(CPU Scheduling Algorithms)은 한정된 CPU Core를 두고 여러 프로세스가 실행 순서를 기다릴 때, 어떤 프로세스에 CPU 시간을 배분하고 언제 선점(Preempt)할지 결정하는 커널의 정책 체계입니다.

학습자는 먼저 도착한 작업을 순서대로 처리하는 FCFS(First-Come, First-Served)부터, 타임 슬라이스 단위로 실행권을 나누는 **선점형(Preemptive) 라운드 로빈(Round Robin)**을 이해합니다. 이어 실시간 OS(RTOS)의 우선순위 기반 스케줄링(Priority)과 현대 리눅스(Linux)의 **CFS(Completely Fair Scheduler)**가 레드-블랙 트리(Red-Black Tree)와 vruntime으로 레이턴시(Latency)와 처리량(Throughput)을 조율하는 방식을 살핍니다.

2. Scope & Boundaries

In-Scope

• 비선점형 스케줄링 (Non-Preemptive): FCFS(FIFO), SJF(Shortest Job First), 자발적 양보(Yield).
• 선점형 스케줄링 (Preemptive): 라운드 로빈(Round Robin, Time Quantum), SRTF(Shortest Remaining Time First).
• 우선순위 역학 (Priority & Queues): 다단계 큐(Multilevel Queue), 다단계 피드백 큐(MLFQ, Multilevel Feedback Queue), 기아 현상(Starvation)과 에이징(Aging).
• 현대 커널 스케줄러 (Modern Schedulers): Linux CFS(Completely Fair Scheduler), 가상 런타임(vruntime), O(1) 스케줄러, 실시간 스케줄링(SCHED_FIFO, SCHED_RR).

Out-of-Scope

• 분산 클러스터 워크로드 스케줄링: 쿠버네티스(Kubernetes) 팟(Pod)을 어느 노드에 띄울 것인지(Kube-Scheduler) $\rightarrow$ 04-03-03. Microservices & Orchestration 영역.
• GPU 텐서 코어 스케줄링: CUDA 블록 워프(Warp) 스케줄러 레벨의 하드웨어 스레딩 $\rightarrow$ 02-04-02. GPU Architecture 영역.

Boundaries

• CPU Sched vs. Disk Sched: CPU 스케줄러는 짧은 시간 단위로 어떤 실행 흐름에 CPU를 줄지 다루고, 디스크 스케줄러(Elevator/C-SCAN)는 디스크 헤드 이동과 탐색 시간(Seek Time)을 줄이는 순서를 다룹니다.

3. Counterexample

• SJF의 이상향과 기아 현상(Starvation) (The Short Job Trap): 작업 시간이 짧은 순서로 먼저 처리하면 평균 대기시간은 줄어듭니다. 하지만 짧은 작업이 계속 들어오면 처음 도착한 긴 작업은 CPU를 계속 할당받지 못하고 Ready Queue에 머무를 수 있습니다. 효율만 최적화하면 공정성이 무너지는 대표적인 사례입니다.
• 거대 퀀텀(Quantum)과 버벅이는 마우스 (Round Robin Latency Crash): 문맥 교환(Context Switch) 비용을 줄이려고 라운드 로빈의 타임 슬라이스(Time Quantum)를 1초처럼 크게 잡으면 처리량은 좋아질 수 있습니다. 대신 사용자가 클릭한 뒤 여러 백그라운드 프로세스의 실행을 기다려야 하므로 화면 반응이 늦어집니다. 반응형 데스크톱(Interactive OS)은 보통 10ms~100ms 수준의 짧은 퀀텀으로 체감 지연을 줄입니다.

4. Prerequisites

• 프로세스 상태 머신 (Basic): Ready Queue와 Blocked Queue의 차이를 알아야 스케줄러가 어떤 프로세스를 고르는지 이해할 수 있습니다. (03-02-01 Process Lifecycle)
• 컨텍스트 스위치 오버헤드 (Basic): Preemption은 공짜가 아닙니다. 레지스터와 실행 문맥을 저장하고 복원하는 비용이 함께 발생합니다. (03-02-01 Context Switch)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 실행권 회수와 시간 배분, 선점형과 비선점형 (Preemptive vs Non-Preemptive)

• Why to Learn: 무한 while(1) 루프처럼 CPU를 오래 점유하는 작업을 커널이 적절히 끊어내야 전체 시스템이 멈추지 않습니다. Timer Interrupt와 Preemption은 그 기본 장치입니다.
• What to Learn:
  • Concepts: 비선점형(Non-Preemptive, 프로세스가 스스로 양보할 때까지 실행권 유지), 선점형(Preemptive, 타이머 인터럽트로 실행권 회수).
  • Skills: FCFS(First-Come First-Served), 라운드 로빈(Round Robin), 타임 슬라이스(Time Slice / Quantum) 결정.
  • Tools: CPU 타이머 하드웨어 틱(Tick).
  • Trade-offs: 타임 슬라이스를 1ms처럼 짧게 잡으면 반응성은 좋아지지만, 그만큼 문맥 교환(Context Switch)이 자주 일어나 처리량(Throughput)이 떨어질 수 있습니다.
• How to Learn:
  • 1단계: 비선점형: 프로세스가 Yield를 호출할 때까지 OS가 실행권을 회수하지 않는 상황을 살펴봅니다. 이 구조에서는 한 프로세스가 무한 루프에 빠지면 전체 반응성이 무너질 수 있습니다.
  • 2단계: 선점형 (라운드 로빈): 커널이 하드웨어 타이머로 10ms마다 Interrupt를 발생시키고, Ready Queue의 다음 프로세스에 CPU 시간을 넘기는 과정을 따라갑니다.
• Implement: 파이썬 가상 CPU_Tick() 루프를 작성합니다. 3개의 태스크 객체(T1(100ms), T2(50ms), T3(200ms))를 Ready Queue에 넣고, 타임 슬라이스 Quantum=20ms 단위로 컨텍스트 스위치 로그를 출력하는 라운드 로빈 시뮬레이터를 만듭니다.

Recommended

Core Topic 02: 동적 우선순위와 다단계 피드백 큐 (MLFQ)

• Why to Learn: CPU Bound 작업과 I/O Bound 작업을 같은 방식으로 다루면 interactive workload의 반응성이 떨어질 수 있습니다. MLFQ는 작업 특성에 따라 우선순위를 동적으로 조정하는 대표적인 방법입니다.
• What to Learn:
  • Concepts: 다단계 피드백 큐(Multilevel Feedback Queue, MLFQ), 우선순위 역전(Priority Inversion), 기아 현상(Starvation), 에이징(Aging).
  • Skills: CPU-Bound vs I/O-Bound 프로세스 판별 기법, 타임 슬라이스 강등 정책.
  • Tools: 리눅스 nice, renice 우선순위 조정 명령어.
  • Trade-offs: MLFQ는 사용자 입력처럼 짧고 자주 깨어나는 작업의 반응성을 높입니다. 대신 각 프로세스가 CPU를 얼마나 사용했는지 추적하고 큐를 승격·강등해야 하므로 스케줄러 자체의 관리 비용이 늘어납니다.
• How to Learn:
  • 1단계: 새 프로세스를 가장 높은 우선순위 큐에 넣습니다. 주어진 짧은 타임 슬라이스를 모두 CPU 연산에 쓰면 CPU Bound 작업으로 보고 더 긴 타임 슬라이스를 가진 낮은 큐로 내립니다.
  • 2단계: 낮은 큐에 오래 머문 프로세스가 계속 밀리지 않도록, 일정 시간(예: 1초)이 지나면 모든 프로세스를 높은 우선순위 큐로 되돌리는 Aging/Reset 정책을 적용합니다.
• Implement: 3개의 우선순위 리스트(Q0, Q1, Q2)로 MLFQ 스케줄러를 만듭니다. 태스크가 타임 슬라이스(10, 20, 40)를 모두 쓰면 하위 큐로 강등(append())하고, time_counter가 1000에 도달하면 Q1, Q2의 모든 요소를 Q0로 올리는 콘솔 시뮬레이션을 작성합니다.

Practical

Core Topic 03: 공정성을 계산하는 리눅스 CFS (Completely Fair Scheduler)

• Why to Learn: Linux CFS는 고정 타임 슬라이스보다 vruntime을 기준으로 CPU 사용량의 공정성을 계산합니다. 이 구조를 이해하면 현대 Linux가 interactive workload와 batch workload를 어떻게 조율하는지 볼 수 있습니다.
• What to Learn:
  • Concepts: CFS(Completely Fair Scheduler), 가상 런타임(vruntime), 레드-블랙 트리(Red-Black Tree, $O(\log N)$).
  • Skills: 우선순위(Nice value)에 따른 시간 팽창(Weight) 계산, $O(\log N)$ 삽입/추출 최적화.
  • Tools: 리눅스 커널 소스 kernel/sched/fair.c.
  • Trade-offs: O(1) 큐 배열 방식은 선택 비용이 상수 시간에 가깝지만 큐 관리가 복잡합니다. CFS는 최소 vruntime을 가진 노드를 레드-블랙 트리에서 고르므로 구조는 일관적이지만, 삽입과 탐색에 $O(\log N)$ 비용이 듭니다.
• How to Learn:
  • 1단계: 고정 타임 슬라이스 대신 각 프로세스의 CPU 사용량을 vruntime으로 누적합니다. 스케줄러는 레드-블랙 트리에서 vruntime이 가장 작은 프로세스를 다음 실행 대상으로 고릅니다.
  • 2단계: 우선순위가 높은 프로세스(nice 값이 낮은 프로세스)는 실제 CPU를 같은 시간만큼 써도 vruntime 증가량이 더 작게 계산됩니다. 이 가중치 덕분에 높은 우선순위 작업이 더 자주 선택됩니다.
• Implement: 최소 힙(Min Heap, RB트리 모사) 자료구조에 프로세스 3개(우선순위 가중치 W = 1, 2, 4)를 push합니다. 루프마다 루트 노드([vruntime, name])를 pop하여 10ms씩 실행하고, vruntime += 10 * (1 / W) 공식으로 가중치가 높은 프로세스의 vruntime이 천천히 증가하도록 만든 뒤 다시 push합니다.

Advanced

Core Topic 04: 멀티코어 환경의 캐시 지역성과 NUMA, 코어 친화도 (Multicore & Affinity)

• Why to Learn: 많은 코어를 가진 서버에서는 스레드를 아무 코어에나 옮기면 L1/L2 cache locality가 깨지고 메모리 접근 비용이 커질 수 있습니다. Affinity와 NUMA 정책은 이런 비용을 줄이기 위한 공간 배치 전략입니다.
• What to Learn:
  • Concepts: 코어 친화도(CPU Affinity / Pinning), NUMA(Non-Uniform Memory Access) 아키텍처, 로드 밸런싱(Load Balancing), 캐시 워밍(Cache Warming).
  • Skills: 스레드를 특정 코어에 바인딩(Pinning), 로컬 메모리 우선 접근(Local Node Memory).
  • Tools: 리눅스 taskset, numactl.
  • Trade-offs: 특정 스레드를 0번 코어에 고정(Pinning)하면 cache locality는 좋아질 수 있습니다. 하지만 0번 코어에 부하가 몰렸을 때 다른 코어로 일을 옮기기 어려워 전체 load balancing 효율이 떨어질 수 있습니다.
• How to Learn:
  • 1단계: 프로세스가 0번 코어에서 돌다가 1번 코어로 이동(Migration)하면, 1번 코어의 L1 캐시에 필요한 데이터가 없어 메인 메모리(RAM)에서 다시 가져와야 할 수 있습니다. 이 Cold Cache Miss 비용을 관찰합니다.
  • 2단계: NUMA 구조에서는 CPU마다 가까운 메모리 영역이 다릅니다. Remote Access가 늘어나면 지연이 커지므로, 스케줄러가 로컬 CPU와 로컬 메모리를 함께 고려하는 이유를 확인합니다.
• Implement: 리눅스 터미널에서 taskset 명령어 시나리오를 작성합니다. taskset -c 0,1 ./my_heavy_server로 스레드가 0번, 1번 코어에서만 실행되도록 제한하고, htop과 perf 지표로 core utilization과 cache hit 변화를 관찰합니다.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Operating Systems (Scheduling) — Performance context.
• [P1] CS2023 - OS/Operating System Principles (Scheduling) — Core requirements.

Secondary

• [Operating Systems: Three Easy Pieces] Remzi — The policy/mechanism separation.
• [Algorithms for Operating Systems] — Mathematical analysis of scheduling.

Industry

• [Kernel.org: CFS Scheduler Design] — The most important real-world scheduler doc.
• [Microsoft: Windows Thread Scheduling] — Multi-level feedback queue in practice.

9. Final Checklist

Primary

• '선점형' 스케줄링이 인터랙티브 시스템(사용자 대응)에서 왜 '비선점형'보다 좋은 반응성을 제공하는지 설명 가능한가? (P1)
• '반환 시간(Turnaround)'과 '대기 시간(Waiting)'의 정의를 구분하고 시스템 효율 평가지표로 활용할 수 있는가? (P1)

Secondary

• '라운드 로빈' 설계 시, 타임 퀀텀이 문맥 교환 오버헤드의 10배 이상이어야 하는 이유를 효율성 관점에서 설명할 수 있는가?
• 프로세스의 I/O Burst와 CPU Burst 특성이 스케줄러의 우선순위 결정에 어떤 단서를 주는지 도출할 수 있는가?

Industry

• 게임 서버 커널 튜닝 시, nice 값을 통한 우선순위 상향이 네트워크 패킷 처리 지연(Jitter)을 어떻게 완화하는지 제안할 수 있는가? (SFIA)
• 멀티코어 환경에서 '코어 피닝(Core Pinning)'을 하지 않았을 때, 작업이 코어 사이를 떠돌며(Thrashing) 발생하는 캐시 손실 비용을 기술할 수 있는가?