비선점형(Non-Preemptive) 스케줄링 일단 CPU 를 할당받으면, CPU burst 가 완료될 때까지 CPU 를 반환하지 않는 방식입니다.
문제점
convoy effect 스케쥴러 평가 기준에 Ready queue에서 기다린 총 시간을 나타내는 waiting time이라는 것이 있는데, 먼저 온 순서대로 처리하다보니 수행시간이 짧은 프로세스가 긴 프로세스를 기다리게 되면서, average waiting time이 늘어나는 현상입니다.
SJF(Shortest - Job - First)
특징
다른 프로세스가 먼저 도착했어도 CPU burst가 짧은 프로세스에게 먼저 할당
비선점형(Non-Preemptive) 스케줄링
문제점
starvation SJF 특징 상 짧은 프로세스에게 계속 먼저 할당 되기 때문에, 수행시간이 긴 프로세스는 계속 할당을 못받는 상황을 의미합니다.
SRTF(Shortest Remaining Time First)
특징
선점형 (Preemptive) 스케줄링 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
문제점
starvation
실행시간을 예측해야된다는 문제가 있는데, 실행 시간은 프로세스마다 다르며, 같은 프로세스라 할지라도 다른 입력 값에 따라 실행 시간이 달라질 수 있기 때문에 예측하기 어렵다.
Round Robin
특징
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
장점
CPU를 처음 할당 받는데 까지 걸리는 시간인 Response time이 빠르다. n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
단점
time quantum이 너무 짧을 경우 context switch가 자주 일어나 오버헤드가 커진다.