[운영체제] CPU 스케줄링

1. CPU 스케줄링이란?

CPU는 한 번에 하나의 프로세스(정확히는 스레드)만 실행할 수 있다. 그래서 Ready 상태의 여러 프로세스 중 다음에 누구에게 CPU를 줄지 결정하는 것이 CPU 스케줄링이다.

필요한 이유는 프로세스가 CPU 연산(CPU burst)과 I/O 대기(I/O burst)를 번갈아 하기 때문이다. 한 프로세스가 I/O를 기다리는 동안 CPU가 놀지 않도록 다른 프로세스를 실행시켜 CPU 이용률을 높이는 것이 목적이다.

2. 프로세스 상태와 스케줄러

프로세스 상태

New → Ready → Running → Terminated
        ↑        │
        │        ↓
        └── Waiting(Blocked)

스케줄링은 Ready 큐에 있는 프로세스 중 하나를 Running으로 보내는 일이다.

스케줄러 종류

종류	역할	비고
장기 스케줄러	어떤 프로세스를 메모리에 올릴지 결정	현대 OS에선 거의 없음
중기 스케줄러	메모리 부족 시 프로세스를 디스크로 내림(swap out)
단기 스케줄러	Ready 큐에서 CPU 줄 프로세스 선택	CPU 스케줄러 = 보통 이것

디스패처(Dispatcher)와 문맥 교환(Context Switch)

• 디스패처: 스케줄러가 고른 프로세스에 실제로 CPU를 넘겨주는 모듈
• 문맥 교환: 현재 프로세스의 상태(레지스터, PC 등)를 PCB에 저장하고 다음 프로세스의 상태를 불러오는 과정
• 문맥 교환 자체는 실제 작업을 하지 않는 오버헤드라서, 너무 자주 일어나면 성능이 떨어진다.

3. 선점형 vs 비선점형

비선점형 (Non-preemptive)

• 프로세스가 CPU를 스스로 놓을 때(종료 또는 I/O 요청)까지 뺏지 않음
• 장점: 구현이 단순하고 문맥 교환이 적음
• 단점: 긴 작업이 CPU를 독점할 수 있음

선점형 (Preemptive)

• OS가 실행 중인 프로세스에서 CPU를 강제로 뺏을 수 있음 (타이머 인터럽트, 더 높은 우선순위 도착 등)
• 장점: 응답성이 좋음 → 현대 OS는 대부분 선점형
• 단점: 문맥 교환이 잦고, 공유 데이터 접근 시 동기화 문제가 생길 수 있음

4. 스케줄링 평가 기준

기준	의미	목표
CPU 이용률	CPU가 일한 시간의 비율	높을수록 좋음
처리량 (Throughput)	단위 시간당 완료한 프로세스 수	높을수록 좋음
반환 시간 (Turnaround Time)	도착부터 완료까지 걸린 전체 시간	낮을수록 좋음
대기 시간 (Waiting Time)	Ready 큐에서 기다린 시간의 합	낮을수록 좋음
응답 시간 (Response Time)	도착부터 처음 CPU를 받기까지 시간	낮을수록 좋음 (대화형 시스템에서 중요)

이 기준들은 서로 트레이드오프 관계라서, 알고리즘마다 어떤 기준을 우선하는지가 다르다.

5. 스케줄링 알고리즘

5.1 FCFS (First-Come, First-Served) — 비선점

• 먼저 온 순서대로 처리
• 단순하지만 호위 효과(Convoy Effect) 발생: 긴 작업이 앞에 있으면 짧은 작업들이 줄줄이 기다림

예시: P1(24ms), P2(3ms), P3(3ms)

• P1 → P2 → P3 순서: 평균 대기 시간 = (0 + 24 + 27) / 3 = 17ms
• P2 → P3 → P1 순서: 평균 대기 시간 = (0 + 3 + 6) / 3 = 3ms

5.2 SJF (Shortest Job First) — 비선점

• CPU burst가 가장 짧은 작업부터 처리
• 평균 대기 시간이 최소인 최적 알고리즘
• 문제점
  1. 다음 burst 길이를 미리 알 수 없음 → 과거 기록으로 예측(지수 평균)
  2. 긴 작업이 계속 밀려서 영원히 실행 못 되는 기아(Starvation) 발생 가능

5.3 SRTF (Shortest Remaining Time First) — 선점

• SJF의 선점형 버전
• 새 프로세스가 도착했을 때, 남은 시간이 현재 실행 중인 것보다 짧으면 CPU를 뺏음

5.4 Priority Scheduling — 선점 / 비선점 둘 다 가능

• 우선순위가 높은 프로세스부터 실행
• SJF도 "burst가 짧을수록 우선순위가 높은" 특수한 경우
• 기아 문제 존재 → 해결책: 에이징(Aging) (오래 기다린 프로세스의 우선순위를 점점 올림)

5.5 RR (Round Robin) — 선점

• 각 프로세스에 타임 퀀텀(Time Quantum)만큼만 CPU를 주고, 시간이 다 되면 Ready 큐 맨 뒤로 보냄
• 응답 시간이 좋아서 시분할 시스템의 기본
• 핵심은 퀀텀 크기
  • 너무 크면 → FCFS와 같아짐
  • 너무 작으면 → 문맥 교환 오버헤드 증가

5.6 MLQ (Multi-Level Queue)

• Ready 큐를 여러 개로 나눔 (예: 포그라운드 큐는 RR, 백그라운드 큐는 FCFS)
• 프로세스는 처음 배정된 큐에 고정
• 큐 사이에도 우선순위가 있어서 하위 큐는 기아가 생길 수 있음

5.7 MLFQ (Multi-Level Feedback Queue)

• MLQ에서 프로세스가 큐 사이를 이동할 수 있게 한 방식
  • CPU를 오래 쓰는 프로세스 → 아래 큐로 내려감
  • 오래 기다린 프로세스 → 위로 올라감 (에이징)
• 결과적으로 짧은/대화형 작업은 빠르게, 긴 작업은 뒤에서 처리
• 가장 범용적이고 실제 OS 설계에 가까운 개념

5.8 한눈에 비교

알고리즘	선점	장점	단점
FCFS	X	단순, 공정	호위 효과
SJF	X	평균 대기 시간 최소	burst 예측 불가, 기아
SRTF	O	SJF보다 더 짧은 대기	기아, 잦은 문맥 교환
Priority	O / X	중요 작업 우선	기아 → 에이징으로 해결
RR	O	응답 시간 좋음, 공정	퀀텀 크기에 민감
MLQ	O	작업 유형별 정책 분리	큐 고정, 하위 큐 기아
MLFQ	O	유연, 실용적	구현·튜닝이 복잡

6. 실제 OS의 스케줄링

개념 공부 단계에서는 "이런 게 있다" 정도만 알면 충분

• 리눅스 CFS (Completely Fair Scheduler): 각 프로세스가 CPU를 쓴 시간(vruntime)을 추적해서, 가장 적게 쓴 프로세스에게 CPU를 주는 "공정성" 중심 방식. 커널 6.6부터는 이를 발전시킨 EEVDF로 교체됨
• 멀티코어 환경에서 추가되는 개념
  • 코어별 Ready 큐
  • 부하 분산 (Load Balancing): 코어 간 작업량을 고르게 분배
  • 프로세서 친화성 (Processor Affinity): 캐시 효율을 위해 같은 코어에서 계속 실행하려는 성질