CPU Scheduling Algorithms

1. Overview

CPU 스케줄링 알고리즘(CPU Scheduling Algorithms, CSA)은 운영체제가 컴퓨터의 가장 핵심적인 물리 자원인 'CPU의 시간(Wall-clock Time)'을 어떻게 조각내어 프로세스들에게 공평하고 효율적으로 배분할지를 결정하는 지휘 체계입니다.

프로세스들은 저마다 요구 사항이 다릅니다. 어떤 놈은 사용자와 대화하고(Interactive), 어떤 놈은 묵묵히 계산만 합니다(Batch). 학습자는 단순히 먼저 온 놈을 먼저 처리하는 FCFS부터, 짧은 일을 먼저 끝내는 SJF, 그리고 현대 OS의 표준인 **다단계 피드백 큐(MLFQ)**의 물리적 가동 원리를 배웁니다. 특히 CPU가 주도권을 뺏어오는 **선점(Preemption)**의 물리적 비용과 시스템 처리량(Throughput), 응답 시간(Response Time) 사이의 상충 관계를 수리적으로 분석합니다. 이를 통해 '끊김 없는 사용자 경험'과 '서버의 극강 효율'을 동시에 달성하는 자원 통제 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Scheduling Principles: 공정성(Fairness), 효율성(Efficiency), 반환 시간, 대기 시간 등의 물리 지표
• Classic Algorithms: FCFS, SJF, SRTF, RR(Round Robin), Multi-level Queue 설계
• Preemption Mechanics: 타이머 인터럽트를 통한 강제 제어권 회수의 물리 시퀀스
• Priority Management: 기아 현상(Starvation) 방지를 위한 에이징(Aging) 하드웨어 로직

Out-of-Scope

• 멀티프로세서 환경에서의 부하 분산(Load Balancing) 알고리즘 (07. System Architecture 영역으로 위임)
• 디스크 I/O 스케줄링 및 네트워크 패킷 스케줄링 상세 (해당 장치 노드에서 분담)

Boundaries

• CSA vs. Real-time: 일반 CSA가 '평균적 만족도'를 높인다면, 실시간 스케줄링(02-06-XX)은 '데드라인이라는 절대적 물리 시간 준수'에 집중하여 구분합니다.

3. Counterexample

• 단순히 "순서를 정하는 공식"을 CSA라고 정의하는 것은 잘못입니다. 스케줄링 결정 시점(Scheduling Point)이 언제 발생하는지, 왜 I/O Bound 프로세스를 먼저 실행시키는 것이 CPU와 입출력 장치를 동시에 가동시키는 '물리적 가동률' 측면에서 왜 유리한지 수리적으로 입증하지 못한다면 CSA의 실전적 의미를 놓친 것입니다. 또한 **라운드 로빈(RR)**의 타임 슬라이스가 너무 작아질 때, 실제 유효 연산 시간보다 **문맥 교환(Context Switch)**이라는 물리적 낭비가 더 커지는 임계점을 산출하지 못한다면 설계 능력이 부족한 것입니다.

4. Prerequisites

• Process Lifecycle & PCB (Basic): 준비 큐(Ready Queue)와 프로세스 상태 기초가 필수입니다. (03-02-01 PLP)
• Interrupts, Exceptions, and Trap Handling (Recommended): 타이머 인터럽트 구동 원리 이해가 권장됩니다. (03-01-03 IET)

5. Learning Map

1. The Game of Time: 무한한 요구와 유한한 CPU 시간 사이의 물리적 충돌을 이해합니다.
2. Simple Order: 줄을 서는 방식(FCFS)부터 '빨리 끝날 놈 우선'(SJF)까지의 기초 물리 논리를 배웁니다.
3. Fair Slicing: 시간을 잘게 쪼개어 모두가 조금씩 전진하는 라운드 로빈(RR)의 리듬을 익힙니다.
4. Adaptive Queues: 프로세스의 평소 행실을 보고 등급을 매겨 유동적으로 관리하는 MLFQ의 지능을 완성합니다.

6. Learning Topics

Basic

Core: 스케줄링 지표와 선점의 물리 (Metrics & Preemption)

• Why to Learn: 무엇을 '성공'으로 정의하느냐에 따라 스케줄러의 물리적 거동이 완전히 달라지기 때문입니다.
• What to Learn:
  • Turnaround Time: 제출부터 완료까지의 총 물리 소요 시간
  • Waiting Time: 실행을 못 하고 준비 큐에서 썩은 물리 시간
  • Preemptive vs Non-preemptive: 실행 중인 놈을 강제로 끌어내릴 수 있느냐의 물리 권한
• How to Learn:
  • 5개의 작업 리스트를 놓고 FCFS와 RR로 실행했을 때 각 프로세스의 '대기 시간 합'을 수리적으로 계산 실습
  • 타이머 인터럽트 주기가 10ms일 때, CPU가 스케줄러 코드를 실행하기 위해 지불하는 연산 손실비 산출
• Implement: 프로세스 도착 시간과 실행 시간을 입력받아 평균 대기 시간을 출력하는 시뮬레이터

Recommended

Core: 라운드 로빈과 타임 퀀텀 (Round Robin Physics)

• Why to Learn: 현대 멀티태스킹의 가장 기본이 되는 물리적 시간 분할 기법이기 때문입니다.
• What to Learn:
  • Time Quantum ($q$): 한 번에 할당받는 물리적 시간 조각의 크기
  • Context switch trade-off: $q$가 너무 크면 FCFS가 되고, 너무 작으면 오버헤드만 남는 물리 법칙
  • Fairness: 각 프로세스가 최소 $1/n$의 CPU 시간을 보장받는 수리적 증명
• How to Learn:
  • 타임 퀀텀 값을 0.1ms에서 100ms까지 바꿔가며 시스템 전체의 'Througput(작업/초)' 변화 곡선 작성 실습
  • 유저가 마우스를 움직일 때 응답 지연이 느껴지지 않는 타임 퀀텀의 물리적 상한선 도출
• Implement: 원형 큐(Circular Queue)를 활용하여 프로세스를 순차적으로 할당하는 RR 알고리즘

Practical

Core: 다단계 피드백 큐와 행실 추론 (MLFQ Mechanics)

• Why to Learn: 과거의 행동을 보고 미래를 예측하여, 예측 불가능한 다양한 프로세스들을 가장 영리하게 관리하는 현대 OS의 심장이기 때문입니다.
• What to Learn:
  • Multi-level Priority: 단계별로 다른 타임 퀀텀을 가진 물리적 큐 배치
  • Priority Boost: 하위 큐에서 굶고 있는 놈들을 주기적으로 상위로 끌어올리는 물리 구제
  • Adaptive Feedback: CPU를 다 쓰면 우선순위를 낮추고, I/O로 반납하면 유지하는 보상 물리
• How to Learn:
  • 리눅스의 O(1) 스케줄러나 CFS(Completely Fair Scheduler)의 가상 실행 시간(vruntime) 물리 로직 분석 실습
  • 특정 프로세스가 CPU를 독점하려고 할 때(Gaming), MLFQ가 이를 어떻게 하위 큐로 물리적으로 격리하는지 추적
• Implement: 실행 이력에 따라 프로세스의 우선순위를 동적으로 조정하는 피드백 큐 로직

Advanced

Core: 멀티코어 스케줄링과 선호도 (Affinity & Balance)

• Why to Learn: CPU가 여러 개일 때, 어느 코어에 일을 줄지가 전체 시스템 전력과 발열, 성능을 좌우하기 위함입니다.
• What to Learn:
  • Load Balancing: 특정 코어만 뜨거워지지 않게 작업을 물리적으로 옮기는 기술
  • Cache Affinity: 이전에 실행되던 코어에서 다시 실행되어 '따뜻한 캐시'를 활용하는 물리 이득
  • Real-time Constraints: 특정 작업이 절대적 물리 시간 내에 완료되도록 보장하는 예약 물리
• How to Learn:
  • 작업을 다른 코어로 옮길(Migration) 때 발생하는 캐시 미스와 버스 트래픽의 물리적 손실량 측정 실습
  • nice 명령어로 프로세스 가중치를 조절했을 때 실제 CPU 점유 시간 비율의 수리적 변화 분석
• Implement: 코어별 부하 상태를 감시하여 한가한 코어로 프로세스 PCB를 사상하는 부하 분산 스크립트

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) 발생하는 캐시 손실 비용을 기술할 수 있는 가?