스케쥴링 기법

선점(preemptive)스케쥴링과 비선점(nonpreemptive)스케쥴링

 

가. 선점 스케쥴링

특정 프로세스가 중앙처리장치를 효율적으로 사용할 수 없는 시점에 이를 때마다 중 앙처리장치의 사용권이 다른 프로세스로 옮겨지는 방식으로 높은 우선순위의 프로세 스들이 급하게 실행해야 할 경우에 유용하다.

① 대화식 시분할 시스템에서 빠른 응답시간을 유지하는 데에 필요하다.

② 경비가 많이 들고 오버헤드까지 초래한다.

③ 효과적인 선점을 하려면 준비 상태의 프로세스가 많아야한다.

④ 우선순위를 고려해야 한다.

⑤ 문맥교환의 횟수가 비선점 방식에 비해서 많다.

 

나. 비선점 스케쥴링

어떤 자원이 어떤 프로세스에 할당이 되면 실행을 종료할 때까지 그 프로세스가 중앙처 리장치의 사용권을 독점하여 사용하는 것으로 짧은 작업들을 기다리게 되는 경우가 있 지만 모든 프로세스 관리에 공정하다.

① 응답시간의 예측이 쉽다.

② 문맥교환의 횟수가 적다.

③ 일괄처리 방식에 적합한 방식이다.

참조) 우선순위(Priority)

① 정적 우선순위(static priority): 프로세스 실행중 우선순위가 변하지 않는 것으로 구현이 용이하고 동적 우선순위에 비해 오버헤드가 적다.

② 동적 우선순위(dynamic priority): 처음에 정해진 우선순위를 상황에 맞게 계속조정하여 사용하므로 구현이 복잡하고 정적 우선순위에 비해 오버헤드가 크다.

 

 

 

프로세서 스케쥴링의 종류

 

선점( Preemption)

 

1. RR (Round Robin )

① FIFO스케쥴링과 같이 도착 순으로 디스패치되는 방식

② 타임 슬라이스(time slice) 혹은 시간 할당량(time quantum)에 의해 시간제한을 받음

시간할당량이 클 경우 : FIFO스케쥴링 방법과 차이가 없게 됨

시간할당량이 적은 경우 : 문맥교환 오버헤드가 상대적으로 커지게 되어 시스템은 대부분의 시간을 문맥교환(context switching)에 소비하게 됨

③ 대화식으로 사용하는 시분할 시스템에 적합

④ FIFO를 선점 스케쥴링으로 변형시킨 방법

 

2. SRT (Shortest Remaing Time)

① SJF스케쥴링기법을 선점 기법으로 변형시킨 방법

② 시분할 시스템에 유용하다.

③ 작업이 끝나기까지 남아 있는 실행시간의 추정치가 가장 작은 프로세스를 먼저 실행함

④ SJF스케쥴링기법보다 오버헤드가 큼

 

3. Multilevel Feedback Queue

① 짧은 작업에 우선권

② 입출력 위주의 작업들에게 우선권

③ 큐에서 FIFO 형태로 이동

(마지막 단계의 큐에서는 프로세스가 종료될 때까지 RR방식으로 순환)

④ 낮은 단계로 내려갈수록 프로세스의 시간 할당량이 커짐

 

 

 

비선점 ( Non - preemption )

 

1. FIFO ( First In First Out )

① 준비 큐(ready queue)에서 도착한 순서에 따라 디스패치 됨

② 응답시간 차가 적기 때문에 예측이 쉬움

③ 대화식 시스템에는 적합하지 않음

 

2. SJF ( Shortest Job First )

① 작업이 끝나기까지의 실행시간의 추정치가 가장 적은 작업을 먼저 실행 함 (짧은 작업들에 우선적으로 서비스)

② 평균 대기시간을 최소화 시킬수 있음

 

3. 우선순위 ( Priority )

① 각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리함

② 우선순위가 같을 때는 FIFO또는 SJF을 도입하여 실행 함

 

4. 기한부 ( Deadline Scheduling )

작업들을 마감시간까지 완성하도록 계획한 스케쥴링

 

5. HRN ( Highest Response Ratio Next )

① SJF스케쥴링기법의 약점인 긴 작업과 짧은 작업간의 지나친 불평등들을 어느 정도 보완한 방법

② 각 작업의 우선순위는 그 작업이 서비스를 받을 시간뿐 아니라 그 작업이 서비스를 기다린 시간 두 가지의 함수로 결정됨

응답률 = (대기한 시간 서비스 받을 시간)/ 서비스 받을 시간