CPU 스케줄링 기초

학습 목표

CPU 스케줄러가 Ready Queue에서 프로세스·스레드를 고르는 이유를 설명할 수 있다.

반환 시간·대기 시간·응답 시간·처리량 등 스케줄링 지표를 비교할 수 있다.

FCFS, SJF, Round-Robin, 우선순위의 동작과 트레이드오프를 설명할 수 있다.

선점(preemptive) 과 비선점(non-preemptive) 의 차이를 설명할 수 있다.

문제 상황

• 코어는 8개인데 Runnable 프로세스가 수백 — 누가 먼저 CPU를 쓰는가
• 배치 job은 느려도 되지만 API는 p99 지연이 SLA — 같은 큐로 스케줄하면 안 된다
• nice 값을 올렸더니 CPU 사용률은 줄었는데 응답이 더 나빠 보인다
  • 지표(대기 vs 응답)를 구분하지 못하면 튜닝이 감에 의존한다
• SJF가 이론상 최적인데 실제 OS는 RR·CFS 를 쓴다
  • 실행 시간을 미리 알 수 없기 때문

스레드까지 봤다. 이번 편은 CPU를 누구에게 줄지 정하는 스케줄링 기초다.

1. 스케줄러와 Ready Queue

Ready 상태 프로세스·스레드는 Ready Queue에 있다. 스케줄러가 하나를 골라 CPU에 올린다.

구성요소	역할
Short-term scheduler	Ready → Running, 매 컨텍스트 스위치마다
Dispatcher	컨텍스트 스위치, 모드 전환, 인터럽트 재개
Ready Queue	CPU 할당 대기 (메모리에 상주)
Wait Queue	I/O·이벤트 대기

• I/O-bound: CPU보다 대기가 많음 — 응답 시간 민감
• CPU-bound: 연산 위주 — 처리량·코어 활용 민감
• 실제 OS는 여러 큐·우선순위로 두 종류를 섞는다

2. 스케줄링 목표

지표	의미	누가 신경 쓰나
CPU 이용률	유휴 시간 최소화	데이터센터·배치
처리량	단위 시간 완료 job 수	배치·워크로드
반환 시간	제출 → 완료	배치 사용자
대기 시간	Ready Queue에서 기다린 시간 합	공정성
응답 시간	요청 → 첫 반응	대화형·웹 API

• 목표는 상충한다 — 처리량 최대 vs 응답 최소를 동시에 완벽히 맞추기 어렵다
• Linux CFS는 가상 런타임으로 공정성에 가깝게, RR은 시분할에 가깝게 동작

3. FCFS (First-Come, First-Served)

도착 순서대로 CPU를 준다. 비선점 — 한 번 CPU를 잡으면 끝날 때까지.

• 구현 단순, 공정해 보임
• Convoy effect: 긴 CPU-bound 프로세스 뒤에 짧은 job이 줄 서면 대기 시간 폭증
• 대화형 시스템에는 부적합

예: P1(24ms), P2(3ms), P3(3ms) 순 도착 → P2·P3 평균 대기 27ms

4. SJF (Shortest-Job-First)

다음 CPU burst가 가장 짧은 프로세스를 선택. 비선점·선점 버전 모두 있음.

• 평균 대기 시간을 최소화하는 것으로 알려짐 (burst 길이를 안다고 가정)
• Starvation: 긴 job이 영원히 CPU를 못 받을 수 있음 → 에이징(aging) 으로 완화
• 실제 OS: burst 길이를 추정(과거 exponential averaging) — Unix·Linux 스케줄러의 기초 아이디어

5. Round-Robin (RR)

시간 할당량 time quantum (예: 10~100ms)마다 선점하고 큐 끝으로 보낸다.

quantum	효과
매우 큼	FCFS에 가까움
적당	응답 시간·공정성 균형
너무 작음	컨텍스트 스위치 오버헤드 증가

• 선점 — 대화형·타임셰어링의 기본
• Linux CFS는 RR과 달리 가상 런타임 기반이지만, 시분할·공정성 목표는 같다

6. 우선순위 스케줄링

각 프로세스에 우선순위 — 숫자가 낮을수록 높은 우선순위(OS마다 반대인 경우 있음).

• 선점: 높은 우선순위가 오면 현재 프로세스를 내림
• 비선점: 현재 프로세스가 끝날 때까지 유지
• Starvation → 에이징: 오래 기다린 프로세스의 우선순위를 점진 상승
• nice(-20~19): Linux에서 우선순위 조정 — 낮은 nice = 더 많은 CPU

7. 정리

• Ready Queue에서 고르는 단기 스케줄러 + Dispatcher가 CPU 할당을 수행
• FCFS는 단순하지만 convoy, SJF는 평균 대기 최소(추정 필요), RR은 응답·공정성
• 선점·비선점, starvation·aging은 실무 튜닝의 핵심 어휘
• 다음: 경쟁 상태를 막는 동기화 도구

다음에 다룰 것

• 동기화 도구
• 뮤텍스, 세마포어, 모니터

---

해당 내용은 Operating System Concepts, 10/E (Avraham Silberschatz, Peter Baer Galvin, Greg Gagne) 의 내용을 기반으로 합니다.