스케줄링 알고리즘

알고리즘	선점/비선점	원리	장점	단점	시스템
FCFS	비선점	큐에 등록된 순서대로 처리	스케줄링 오버헤드가 적기 때문에 자원을 효율적으로 사용 가능	긴 평균 응답 시간
Convoy effet	Batch 👍
Interactive 👎
RR	선점	큐에 등록된 순서대로 처리하되, 자원 사용 제한 시간이 지나면 다시 큐의 마지막으로 들어감	자원 사용 제한 시간이 있기 때문에 자원의 독점을 방지 가능	자주 프로세스를 교체해야 하므로 Context switch overhead 증가	Interactive, Time-sharing 👍
SPN (SJF) - Shortest Process Next (Shortest Job First)	비선점	Burst time이 가장 작은 프로세스를 먼저 처리	평균 대기시간 최소화, 프로세스 수 최소화 (메모리 절약 → 시스템 효율 향상), 빠른 응답 시간	BT가 긴 프로세스는 무한 대기 (Starvation → Aging으로 해결), 실행 시간 예측 기법 필요	비현실적
SRTN (Shortest Remaining Time Next)	선점	잔여 실행 시간이 더 적은 프로세스가 Ready되면 프로세서 선점	SJF 장점 극대화	BT 예측 필요, 잔여 실행을 계속 추적, Context switching overhead, 실행 시간 예측 기법 필요	비현실적
HRRN (High Response Ratio Next)	비선점	SPN + Aging	SJF + 프로세스 대기 시간을 고려, Response Ratio = (WT + BT) / BT	실행 시간 예측 기법 필요

FCFS (First Come First Service)

비선점 스케줄링
스케줄링 오버헤드가 적기 때문에 자원을 효율적으로 사용 가능
Batch System 👍 / Interactive System 👎
단점: 긴 평균 응답시간, Convoy effect
- Convoy effect: 하나의 긴 프로세스가 나머지 짧은 프로세스들을 block해버리는 현상

선점 스케줄링
먼저 도착한 프로세스를 먼저 처리
자원 사용 제한 시간이 존재 → 자원 독점 방지
- 성능에 중요한 영향 (너무 크면 FCFS, 너무 작으면 context switch overhead 커짐)
- 시간이 종료되면 Ready Queue의 맨 뒤로 감
Interactive, Time-sharing System 👍
단점: Context switch overhead가 큼