운영체제 | CPU Scheduling

🥔 CPU 스케줄링 알고리즘이란?

운영체제는 한정된 CPU 자원을 여러 프로세스가 공정하고 효율적으로 사용할 수 있도록 스케줄링 알고리즘을 사용한다.

특히 Ready Queue에 있는 프로세스 중 어떤 것을 선택해 실행할지 결정하는 정책이 스케줄링 알고리즘의 핵심이다.

🥔 주요 CPU 스케줄링 기준

스케줄링 알고리즘은 일반적으로 다음과 같은 기준을 기반으로 성능을 평가한다.

지표	설명
CPU 이용률	CPU가 실제로 일을 수행하는 비율
처리량(Throughput)	단위 시간당 처리된 프로세스 수
대기 시간	Ready Queue에서 대기한 시간 총합
응답 시간	최초 요청부터 첫 응답까지 걸린 시간
Turnaround Time	프로세스 생성부터 종료까지 걸린 전체 시간

🥔 FCFS (First Come First Served)

선입선출 방식으로, 먼저 도착한 프로세스를 먼저 처리한다.

• 간단한 구현
• 비선점(Non-Preemptive) 스케줄링
• Convoy Effect 발생 가능: 실행 시간이 긴 프로세스가 앞에 오면 전체가 지연됨

예시

도착 순서: P1(24), P2(3), P3(3)
Gantt Chart: | P1 | P2 | P3 |

🥔 SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식

• 평균 대기 시간이 최소
• 비선점 방식
• 단점: 실행 시간을 예측해야 함, 긴 프로세스는 기아(Starvation) 현상 가능

🥔 SRTF (Shortest Remaining Time First)

SJF의 선점(Preemptive) 버전

• 현재 실행 중인 프로세스보다 짧은 Job이 도착하면 선점함
• 응답 시간이 짧음
• 역시 실행 시간 예측이 필요하고, 컨텍스트 스위칭 비용 증가

예시

P1(8), P2(4 at t=1), P3(2 at t=2)
→ P3가 가장 먼저 실행됨 → 그 후 P2 → 마지막에 P1

🥔 Round Robin (RR)

고정된 시간 할당량(Time Quantum)을 기준으로 프로세스를 순환 실행

• 선점형 스케줄링
• 모든 프로세스에 공정하게 CPU 시간 분배
• 타임 퀀텀이 너무 작으면 컨텍스트 스위칭이 많아져 오버헤드 증가
  너무 크면 FCFS와 유사해짐

예시

타임 퀀텀: 4ms
P1(10), P2(5), P3(8)
→ P1(4) → P2(4) → P3(4) → P1(6) ...

🥔 Multilevel Queue Scheduling

프로세스를 여러 개의 Queue로 나누고, 각 Queue마다 우선순위와 알고리즘을 다르게 설정

• 예: 시스템 프로세스 vs 사용자 프로세스
• Queue 간 이동이 불가능한 고정형 멀티큐
• Queue 간 이동이 가능한 Feedback Queue 구조도 있음

예시 구조

Queue	Priority	Algorithm
시스템 프로세스	높음	FCFS
사용자 프로세스	중간	Round Robin
배치 작업	낮음	SJF

운영체제가 다양한 성격의 작업을 처리하기 위해 실질적으로 사용되는 전략이다.

🥔 알고리즘 비교 요약

알고리즘	선점 여부	특징	단점
FCFS	X	구현이 쉽고 순서 보장	Convoy 현상
SJF	X	평균 대기 시간 최소화	실행 시간 예측 필요, 기아 가능
SRTF	O	평균 응답 시간 향상	오버헤드 증가, 예측 필요
Round Robin	O	공정성 높음, 모든 프로세스가 실행 보장	타임 퀀텀 선택 중요, 오버헤드
Multilevel Queue	경우에 따라	다양한 특성의 프로세스 분리 처리 가능	구조 복잡, starvation 가능

🥔 마무리

• CPU 스케줄링은 시스템 자원을 효율적으로 사용하고, 사용자 반응 속도를 높이는 데 핵심
• 모든 알고리즘은 장단점이 존재하며, 사용 환경에 따라 적절한 선택이 필요
• 실전에서는 여러 알고리즘을 조합한 Hybrid 방식을 채택하는 경우가 많다