CPU 스케줄링 알고리즘 - 비선점형 스케줄링 (FCFS, SJF)에 대해 설명하세요
Keyword
선입 선처리, 비선점형, 호위 효과, 최단 작업 우선
Script
가장 단순한 스케줄링 알고리즘은 선입 선처리 스케줄링인, FCFS 스케줄링(First Come First Served Scheduling)입니다. 단순히 ready queue에 삽입된 순서대로 process들을 처리하는 비선점형 스케줄링 방식입니다.
그리고 FCFS 스케줄링의 문제점인 '호위 효과'를 개선한 스케줄링 알고리즘이 최단 작업 우선 스케줄링(SJF, Shortest Job First Scheduling)입니다. ready queue에 삽입된 process 중에서 CPU의 이용 시간의 길이가 가장 짧은 process부터 실행하는 스케줄링 방식을 말합니다. 일반적으로는 비선점형 스케줄링 방식이지만, 선점형 최단 작업 우선 스케줄링 방식도 구현이 가능합니다.
Additional
convoy effect(호위 효과)
처리 시간이 긴 Process가 먼저 도착하게 되면, 평균 대기 시간이 매우 길어진다. 즉, 처리시간이 짧은 process가 늦게 들어 오면, 앞에 들어온 처리 시간이 긴 process에 의해 대기 시간이 너무 길어지게 된다.
Priority Scheduling(우선순위 스케줄링)과 aging(에이징)
우선순위 스케줄링은 process들에 우선순위를 부여해서, 가장 높은 우선순위를 가진 process부터 실행하는 스케줄링 알고리즘이다.
여기에는 근본적인 문제가 있는데, 우선순위가 낮은 process는 다른 process가 계속해서 들어오면, 끊임없이 실행이 연기될 수 있다. 이를 기아(starvation)현상이라고 하는데, 이 문제를 해결하기 위해 에이징(aging) 기법이 있다.
에이징 기법은 오랫동안 대기한 process의 우선순위를 점차 높이는 방식이다. 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)은 에이징 기법이 적용된 스케줄링 알고리즘이다.
Reference
