오퍼레이팅시스템 6주차 / Processor Scheduling(9단원)

Types of processor schedulig
Selection Function

준비 상태인 프로세스들 중에서 다음으로 실행될 프로세스를 결정하는 함수

( CPU가 다음에 어떤 프로세스를 실행할지 정할 때 사용하는 기준 )

 

• w: 지금까지 시스템에 머문 시간, 즉 대기 시간(waiting time)
• e: 지금까지 실행된 시간
• s: 전체 서비스 시간, 실행시간 e를 포함하고 유저가 추정하거나 제공해야 함. 즉 e <= s
• TAT (Turn-Around Time): w + s, 한 프로세스가 도착해서 완료될 때까지의 총 시간 / 반환시간

Decision Mode

선택함수가 언제 실행될 지 정하는 시간적 순간

① Non-preemptive (비선점형) : 프로세스가 실행상태에 들어가면 (a) 종료되거나, (b) 스스로 입출력을 위해 blocked상태로 들어갈 때 까지 계속 실행된다. 즉, 운영체제가 강제로 중단시키지 않는다. ex) FIFO

② Preemptive (선점형) :  현재 실행 중인 프로세스를 운영체제가 강제로 Ready 상태로 이동시킬 수 있음.

새로운 프로세스가 도착했을 때, Blocked 상태였던 프로세스가 Ready로 돌아왔을 때, 시계 인터럽트(clock interrupt) 에 따라 주기적으로

 

Scheduling Criteria
Scheduling Algorithms for Unirocessor

스케줄링 알고리즘
FIFO(first in, first out)  : 먼저 들어온 프로세스 부터 먼저 실행한다. (=FCFS)

Selection Function: max[w] (가장 오래 기다린 = 가장 먼저 도착한)

Decision Mode : 비선점모드 non - preemptive

장점 : 구현이 쉽고 ,긴 작업에 유리하다.(long process)

단점 : 짧은 작업이 기다릴 수 있다(평균대기시간 늘어남). , I/O-bound 프로세스에 불리 ,

          Convey effect ( burst time이 큰 프로세스가 먼저 실행되면,  그 뒤에 있는 짧은 작업들이 오래 기다리는 현상 )

y는 서비스 시간이 1인데 100이나 기다림 비효율적 convey effect

 

SPN(shortest process next) : 실행 시간이 가장 짧은 프로세스를 먼저 실행

Selection Function : min[s]

Decision mode : 비선점모드 non - preemptive

장점 : 평균 대기시간이 줄어듬 (convey effect완화)

단점 : 서비스 시간을 미리 알아야함. 기아(starvation) 가능성 : 긴작업은 계속 뒤로 밀림.

평균반환시간

α = 0.8 (하늘색 선) : 최근 값 반영을 많이 함 → 빠르게 따라감

 

FIFO vs SPN

작업량에 따라 FIFO가 더 나은 반환시간을 가질수 있다.

 

SRT(shortest remaining time) : 남은 실행시간이 가장 짧은 프로세스를 먼저 실행

현재 실행중인 프로세스보다 더 짧은 남은 시간을 가진 프로세스가 도착하면 선점함

Selection Function : min[s-e]

Decision mode : 선점모드 preemptive (SPN의 선점버전)

장점 : SPN보다도 더 우수한 평균 반환 시간(TAT) 제공 가능, 짧은 작업이 빠르게 끝남 → 응답성 향상

단점 : 오버헤드가 높다.(쓸데없이 자원이 낭비된다.), 기아가 발생할 수 있다. 여전히 시간을 예측해야한다.(s)

SPN보다 향상된 평균반환시간

 

HRRN(highest respense ratio next) : 응답 비율(Response Ratio)이 가장 높은 프로세스를 선택하는 방식

짧은 작업과 긴 작업의 균형을 잘 맞추는 비선점형 알고리즘

R = (w + s) / s : w: 기다린 시간 (waiting time), s: 예상 실행 시간 (service time)

Selection Function : max[(w + s)/s]

Decision mode : 비선점모드 non- preemptive 

장점 : 짧은 작업을 선호하면서도, 오래 기다린 긴 작업에게도 기회를 줌, 기아현상이 발생하지 않음.

단점 : 여전히 시간을 예측해야한다.(s)

Round-Robin

time quantum 길이를 결정하는 것이 중요한 디자인 이슈.

-> 짧게 할수록 SPN과 비슷해지고, 핸들러 overhead 증가한다.

-> 길게 할수록 FIFO와 비슷해진다.

Selection Function : constant 

Decision Mode : 선점형 preemptive

장점 : 기아현상이 발생하지 않음, 

단점 : Processor-bound process( CPU를 계속 차지하려는 경향 ), I/O-bound process( 짧게 CPU를 사용한 후 바로 I/O로 넘어가므로 비효율적인 큐 대기 현상 ) >> 해결방안: virtual Round Robin, Multi-Level Feedback Queues

 

Virtual Round Robin (VRR)

더 긴 프로세스를 위해 bias(편향)을 줄인다. → short process에 favor를 주는 방식

auxiliary(보조) queue의 프로세스가 main ready queue의 프로세스보다 우선시 한다

 

 

Multi Level Feedback Queue (VRR)