운영체제 - 스케쥴링 기법

프로세스 관련 Scheduler 

가. 프로세스의 분류

① Job scheduler (Long Term Scheduler)

프로세스를 생성하고 제거하는 동작을 하는 스케쥴러이다. 이 스케쥴러는 보류 상태 에 있는 작업들을 준비(Ready) 상태로 전이 시키며 프로세스의 제어 코드와 PCB를 연 결지어 주기억장치로 이동시킨다.

② Process Scheduler

= Dispatcher(=CPU scheduler, Short Term Scheduler)

준비 상태에 있는 여러개의 프로세스들 중에서 어떤 프로세스에게 CPU를 배당할 것인 가를 결정하는 스케쥴러이다. 준비(Ready) - 실행(Run)

③ Mid-level scheduler(Mid Term Scheduler)

실행 중인 프로세스를 블록화(=중지)하거나 또는 다시 활성화시키는 기법을 사용하여 시스템에 대한 부하의 양을 조절하는 기능을 담당한다. 실행상태에서 보조기억으로 이동한다. Swapping 기법을 사용하여 부하의 양을 조절하며 실제로 구현하지 않은 시 스템이 많다.

 
나. CPU 스케쥴러

① 공정성을 가져야 한다.

② 효율성을 가져야 한다.

③ 빠른 응답시간을 제공해야 한다.

④ 균형 있는 자원의 사용이 가능하도록 해야 한다.

⑤ 핵심자원을 차지하는 프로세스들에게 우선권을 주어야 한다.

⑥ 오버헤드를 최소화해야 한다.

⑦ 무한정 대기를 피해야 한다.

⑧ 대기 시간이 긴 작업에게 우선순위를 높여주는 방식인 Aging기법을 이용한다.

⑨ 우선순위가 주어진 경우 더 높은 우선순위를 가진 프로세스를 먼저 실행해야 한다.

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

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

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