[CS] CPU 스케줄링 알고리즘

CPU 스케줄링 목표: CPU 사용률 극대화, 처리량 증가, 응답 시간 최소화, 대기 시간 감소, 공정한 자원 분배
스케줄러 역할: 프로세스의 준비 큐(Ready Queue)에서 어떤 프로세스에 CPU를 할당할지 결정

---

CPU 스케줄링 분류

분류	설명	특징
비선점형	프로세스가 스스로 CPU 반납	컨텍스트 스위칭 부하 적음
선점형	운영체제가 CPU를 강제로 회수	실시간성, 반응성 우수

 

비선점형 방식

알고리즘	설명	장점	단점
FCFS (First Come First Served)	먼저 온 순서대로 처리	구현 간단, 공정성↑	긴 작업이 앞에 오면 convoy effect 발생
SJF (Shortest Job First)	실행 시간이 짧은 순	평균 대기 시간 최소화	긴 작업 기아(starvation), 실행 시간 예측 어려움
우선순위 스케줄링	우선순위 높은 순서	유연한 자원 배분 가능	기아 발생 가능 → aging 기법으로 보완

---

선점형 방식

알고리즘	설명	장점	단점
RR (Round Robin)	정해진 시간(q) 동안 실행, 다음 큐로 이동	응답 시간 빠름, 공정성	q 크기에 따라 오버헤드/비효율 발생
SRF (Shortest Remaining Time First)	남은 실행 시간 가장 짧은 작업 선처리	이론적으로 최적 대기 시간	기아 발생 가능, 실행 시간 예측 어려움
다단계 큐	우선순위 큐 여러 개 운영 + 각 큐마다 알고리즘 다름	클래스 분리 용이	큐 간 이동 불가 → 유연성↓

---

참고: 북스터디 - 면접을 위한 CS 전공지식 노트 (Chapter 3-4)