으랏차

선점 스케줄링에 해당하는 선점 우선순위, SRT, RR, 다단계 큐, 다단계 피드백 큐 알고리즘에 대하여 알아보자.

>선점 스케줄링은 대부분 비선점 스케줄링을 보완한 것이다.

1. 선점 우선순위

* 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.

* 비선점 우선순위 기법을 선점 형태로 변경한 것으로, 준비상태 큐에 새로 들어온 프로세스의 순위가 높을 경우 현재의 프로세스를 보류하고 새로운 프로세스를 실행한다.

2. SRT(Shortest Remaining Time)

* 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법으로, 선점 SJF 기법이라고도 한다.

* 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법으로, 시분할 시스템에 유용하다.

* 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다.

>SRT는 SJF를 변경한 것으로, 두 개의 알고리즘을 비교하는 문제가 출제됨.

SJF는 실행시간이 가장 짧은 프로세스.

SRT는 현재 실행중인 프로세스의 남아 있는 실행 시간과 새로운 프로세스의 실행 시간을 비교하여 짧은 것.

3. RR(Round Robin)

* 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형한 기법이다.

* FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량(Time Slice, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치된다.

* 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생한다.

* 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리하다.

>RR은 전반적인 내용을 묻는 문제가 출제됨. RR은 시간 할당량을 사용하는 데 할당된 시간이 클수록 FCFS와 같고, 할당되는 시간이 작을수록 문맥 교환과 오버헤드가 자주 발생된다.

예제]

4. 다단계 큐(MQ, Multi-level Queue)

* 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법이다.

* 일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비상태 큐를 상위, 중위, 하위 단계로 배치한다.

[그림]

>다단계 큐와 다단계 피드백 큐의 차이점을 알아두자.

* 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있다.

* 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다.

* 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 한다.

5. 다단계 피드백 큐(MFQ, Multi-level Feedback Queue)

* 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법이다.

* 각 준비상태 큐마다 시간 할당량을 부여하여 그 시간 동안 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동된다.

* 상위 단계 준비상태 큐일수록 우선순위가 높고, 시간 할당량이 적다.

* 요구하는 시간이 적은 프로세스, 입ㆍ출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스를 기준으로 높은 우선순위를 할당한다.

* 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당하며, 마지막 단계 큐에서는 작업이 완료될 때까지 RR 스케줄링 기법을 사용한다.

선점(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스케쥴링기법의 약점인 긴 작업과 짧은 작업간의 지나친 불평등들을 어느 정도 보완한 방법

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

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