Process Scheduling 2(기본 스케줄링 및 알고리즘)

 

FCFS (선착순 알고리즘) (비선점)

=> 도착시간을 기준으로 하며, 들어온 순서대로 일만하기 때문에 자원을 효율적으로 사용,

즉 스케줄링 오버헤드가 작다. 배치시스템(일괄처리)에 적합하며, interactive에는 부적합한 방식

 

RR (Round Robin) (선점)

=> 도착시간을 기준으로 하며, 자원 사용에 대한 제한시간(time quantum)이 있음.

제한시간이 지나면 자원을 반납해야하며, context switch 오버헤드가 크다.

interactive 시스템에 적합하고, 제한시간이 성능을 결정하는 핵심 요소이다.

 

---

 

SPN (Shortest process next) (비선점)  ====> 변형된 것이 SRTN(선점)(잔여시간 추적)

=> 실행시간을 기준으로 대기 프로세스들 중 Burst time이 가장 작은 프로세스를 먼저 처리,

이로 평균 대기시간을 최소화 및 메모리 절약 스케줄링 부하를 감소시킬 수 있지만 

무한 대기(Starvation)현상 발생할 수 있으며 정확한 실행시간을 알 수 없다.(예측해야함)

 

HRRN(Hight-response-ration-next)(비선점)

=> 스케줄링을 할 때 Response ration(응답률)이 높은 프로세스를 우선한다.

이는 곧 SPN의 장점을 살리면서 starvation을 방지하기 위함이다.

 

 

---

 

 

FCFS, RR => 공평성을 위함이라면 SPN, SRTN, HRRN => 효율성 및 성능을 위함이다.

하지만 실행시간을 예측하는데 있어서 부하가 있고, 이를 대안으로 나온 것이 MLQ, MFQ이다.

 

MLQ(Multi level queue)

=> 큐가 여러개로 작업별 별도의 레디큐를 가지고 큐마다 각각 스케줄링을 사용한다.

큐 사이에는 우선순위 기반의 스케줄링을 사용한다.

 

하지만 여러개의 큐가 관리가 힘들고 우선순위가 낮은 큐는 starvation 현상이 일어나서

이를 보완하여 나온것이

 

MFQ(Multi level feedback queue) 

=> 프로세스 큐간 이동이 허용된 MLQ로 동적 우선순위를 가진다. 

하지만 이 또한 복잡하고 starvation 현상이 일어날 수 있다.

 

스케줄링 알고리즘