CPU 스케줄링의 종류와 장단점

스케줄링 방식	동작 방식	특징	장점	단점
FCFS (First Come, First Served)	- 먼저 도착한 순서대로 프로세스 실행 - 비선점형 방식	- 대기열(Queue) 기반의 단순한 스케줄링	구현이 매우 간단함 오버헤드가 거의 없음 (선점 없음) 일괄 처리 시스템에 적합함 공정성 유지 (먼저 온 작업 우선)	Convoy 현상 발생 (긴 작업이 뒤 작업을 모두 지연) 응답 시간이 길어질 수 있음 짧은 작업이 긴 작업에 막혀 기아 상태 유발 가능 대화형 시스템에는 부적합
SJF (Shortest Job First)	- CPU 버스트 시간이 짧은 작업부터 먼저 실행 - 비선점형 또는 선점형 가능	- 평균 대기 시간 최소화 (이론적으로 최적)	평균 대기 시간을 가장 낮게 유지 짧은 작업 우선 처리 → 전체 처리량 증가 효율적인 자원 사용 가능 CPU 집약적 작업을 뒤로 미룸	실행 시간 예측이 필요함 (현실적으로 어려움) 긴 작업은 계속 대기할 수 있음 (기아 상태) 실시간/반응성이 중요한 환경에는 부적절 변동성 높은 시스템에는 비효율적
SRTF (Shortest Remaining Time First)	- 현재 실행 중인 작업보다 남은 시간이 짧은 작업이 도착하면 선점 - SJF의 선점형 확장	- 반응성 높음, 이론적으로 가장 빠른 응답 시간	짧은 작업이 빠르게 끝남 → 사용자 만족도 향상 반응 시간이 매우 짧음 긴 작업은 적절히 분할 실행 가능	선점 빈도 ↑ → 문맥 전환 비용 증가 예측 정확도 부족 시 비효율 발생 긴 작업이 계속 밀릴 수 있음 (기아) 구현 복잡도 증가
RR (Round Robin)	- 시간 할당량(time quantum) 단위로 프로세스 순환 실행 - 선점형 스케줄링	- 공정성 강조, 대화형 시스템에 적합	모든 프로세스에 CPU 기회 제공 (공정성) 기아 상태 방지 응답 시간이 일정하고 예측 가능 대화형/실시간 시스템에 적합 Time quantum 조정 가능 → 유연함	time quantum 설정이 매우 중요 (너무 작으면 문맥 전환↑) 긴 작업 처리 시 반복 회전으로 오버헤드↑ 짧은 작업이 길게 느껴질 수 있음 전체 처리량은 SJF보다 낮을 수 있음
Priority Scheduling	- 우선순위가 높은 프로세스부터 실행 - 선점형 또는 비선점형 모두 가능	- 시스템/사용자 우선순위 기반 차등 실행	중요 작업에 우선순위 부여 가능 다양한 정책으로 유연한 시스템 구성 가능 선점형일 경우 빠른 응답 가능	우선순위 낮은 작업은 무한 대기 가능 (기아) 우선순위 설정 기준이 명확하지 않을 수 있음 우선순위 역전 문제 발생 가능 선점 시 문맥 전환 오버헤드 발생
Multilevel Queue (MLQ)	- 프로세스 성격별로 큐를 나누고 큐 간에 절대 우선순위 부여	- 각 큐의 특성에 맞는 스케줄링 사용 큐 간 이동 불가	큐별 최적화된 스케줄링 가능 CPU, IO 집약적 작업을 분리 처리 가능 정적 시스템에 예측 가능한 동작	유연성이 낮음 (큐 간 이동 불가) 큐 간 자원 분배 불균형 발생 가능 기아 상태 발생 가능 (낮은 큐 무시)
Multilevel Feedback Queue (MFQ)	- MLQ의 확장형으로 프로세스가 다른 큐로 이동 가능	- CPU 사용 시간에 따라 동적 우선순위 조정 기아 방지	CPU/IO 집중형에 적절한 분류 가능 기아 방지 (낮은 큐로 내려가도 다시 올라올 수 있음) 인터랙티브/배치형 작업 동시 처리 가능	설계 복잡, 튜닝 난이도 높음 실행 흐름 분석 어려움 큐 이동 전략이 비효율적이면 오히려 성능 저하
Lottery Scheduling	- 프로세스에 티켓을 부여하고 랜덤 추첨으로 실행 결정	- 공정성과 우선순위를 동시에 고려 가능	확률적 공정성 보장 티켓 수 조절로 우선순위 조정 가능 기아 상태 없음 가벼운 구현 가능	예측성 부족 → 실시간 처리 어려움 성능 보장 어려움 (확률 기반) 랜덤성에 의존 → 신뢰성 낮음
EDF (Earliest Deadline First)	- 마감 기한이 가장 빠른 작업부터 스케줄링 - 실시간 시스템에서 사용	- 동적 우선순위 기반 하드/소프트 실시간 시스템 적용 가능	마감 기한 준수율이 높음 자원 활용률 100%에 가까움 동적으로 유연하게 우선순위 조정	과부하 상태에서 deadline 보장 어려움 마감 시간 예측 및 설정이 필요 우선순위 계산 오버헤드 존재