CPU 스케쥴링 알고리즘 Re

CPU 스케쥴링 알고리즘

 

비선점형 방식

비선점형 방식(non-preemptive)은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며,

강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

 

FCFS(First Come, First Saved)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 길게 수행되는 프로세스 때문에 '준비 큐에서

오래 기다리는 현상(convoy effect)가 발생하는 단점이 있다.

 

SJF(Shortest Job First) 

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다.

긴 시간을 가진 프로세스가 실행되지 않는 형상이 일어나며 평균 대기 시간이 가장 짧다.

실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용한다.

 

우선순위

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있다.

이 단점을 오래된 작업일수록 우선순위를 높이는 방법을 사용해 보완한 알고리즘이다.

 

선점형 방식

라운드 로빈(RR, Round Robin)

프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로

가는 알고리즘이다.

→ 할당 시간이 충분히 크면 FCFS가 될 것이고 너무 짧으면 그만큼 컨텍스트 스위칭이 잦아질 것이다.

 

SRF(Shortest Remaining Time First)

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음

짧은 작업을 이어나가는데, SRF(Shortest Remainng Time Fisrt)는 중간에 더 짧은 작업이 들어오면

수행하던 프로세스를 중지하고 해당 프로세스를 수행한다.

 

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS등 다른 스케줄링

알고리즘을 적용하는 것이다. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만

유연성이 떨어지는 특징이 있다.