process scheduling(프로세스 스케쥴링) - FIFO, SPN, Round Robin, SRT

 

long term schesuling - job scheduler

 

- 프로세스가 시스템에 들어갈지 말지 결정

 

 

medium term scheduler - swaper

 

- disk에 존재하는 어떤 프로세스를 메인 메모리에 올릴 것인지 결정

 

 

short term scheduler - cpu scheduler

 

- 어떤 프로세스가 cpu를 사용하여 실행될 것인지 결정

 

 

i/o scheduling

 

- 어떤 프로세스가 i/o request에 대해 pending 될 것인지 결정

 

level of scheduling

 

 

short term scheduler 단계에서 실행되는 스케쥴링이 흔히 말하는 CPU Scheduling이다.

 

밑의 내용은 CPU Scheduling을 설명한 것이다.

 

 

 

CPU Scheduling에는 어떻게 프로세스 스위치 하냐에 따라 다양한 방식이 있는데 각 방식마다 selection fuction과 dicision mode가 무엇인지에 따라 여러 구조가 탄생함

 

 

---

 

selection fucntion

 

프로세스를 스위칭 할 때 사용되는 함수로

ready 상태인 프로세스 중에서 다음에 실행할 프로세스를 다음과 같은 기준을 사용하여 결정한다.

 

W(working time) : 프로세스가 시스템을 사용한 시간

E(excute time) : 프로세스를 실행한 시간

S(service time) : 프로세스가 전체적으로 요구하는 시간 (실행 ~ 종료까지) 

 

 

dicision mode

 

프로세스 스위칭에는 어떻게 프로세스가 전환되는지에 따라 두가지 dicision mode가 존재한다

 

nonpreemptive(비선점)

running 중인 프로세스가 알아서 종료될 때 까지, 해당 프로세스의 system call에 의해 알아서 종료되기를 기다림

 

preemptive(선점)

선택함수의 기준을 만족할 때 마다 상태를 바꿔서 뺐음 ready queue에 존재하는 프로세스에서 실행, interrupt 발생시 선택함수 실행 

 

 

 

selection fuction과 dicision mode가 무엇인지에 따라 여러 구조가 탄생함

 

 

---

 

 

FIFO 구조

 

초기 CPU Scheduling 방식으로, FIFO(first in first out) 구조를 사용하여 queue의 가장 첫번째 프로세스를 먼저 종료시키고 다음 프로세스를 실행

 

dicision mode : nonpreemtive

selection function : Max[W] (w : 시스템을 사용한 시간)

 

 

A, B, C, D, E 순으로 queue에 존재한다고 했을 때 프로세스는 다음과 같이 진행된다.

 

queue에 진입한 시간 :

A : 0,  B : 2,  C : 4,  D : 6,  E : 8

 

각 프로세서가 요구하는 실행 시간 :

A : 3,  B : 6,  C : 4,  D : 5,  E : 2

 

진입한 순서대로 실행하기 때문에 실행 순서는 그대로

A - B - C - D - E

 

위 표를 보고 응답시간을 계산해보면 다음과 같다(프로세스 queue 진입부터 종료까지 걸린 시간) : 

A : 3(3-0)

B : 7(9-2)

C : 9(13-4)

D : 12(18 - 6)

E : 12(20 - 8)

 

E의 관점에서 요구하는 실행시간은 2초 뿐인데, 응답 시간은 12초를 가지게 된다.

 

 

모든 프로세스의 평균 반환 시간은 = (3 + 7 + 9 + 12 + 12) / 5 = 8.6

단점 : 요구하는 수행시간이 짧아서 먼저 진행해도 되는 프로세스도 늦게 queue에 진입하면 늦게 실행됨

 

 

SPN(Shortest Process Next)

 

fifo의 단점을 극복하기 위해 만들어짐 프로세스가 요구하는 시간이 가장 짧은 프로세스를 선택하여 실행

 

dicision mode : nonpreemtive

selection function : Min[S] (S - 프로세스가 요구하는 실행 시간)

 

 

 

 

 

 

queue에 진입한 시간을 다음과 같이 가정

A : 0,  B : 2,  C : 4,  D : 6,  E : 8

 

각 프로세서가 요구하는 시간을 다음과 같이 가정

A : 3,  B : 6,  C : 4,  D : 5,  E : 2

 

A가 진입했을 때 A 밖에 없으므로 A를 실행하고 A 실행 중 B 진입하고 A가 끝난 후 B 실행

B 실행 중 나머지 모든 프로세스가 queue에 진입, 그 때 부터 요구 시간이 가장 짧은 프로세스를 선택하여 실행

A - B - E - C - D

 

위 표를 보고 반환시간을 계산해보면 다음과 같다(프로세스 queue 진입부터 종료까지 걸린 시간) : 

A : 3(3-0)

B : 7(9-2)

C : 11(15-4)

D : 14(20 - 6)

E : 3(11 - 8)

 

 

모든 프로세스의 평균 반환 시간은 = (3 + 7 +11 + 14 + 3) / 5 = 7.6

FIFO 보다 적은 평균 반환 시간을 가진다.

단점 : 프로세스가 요구하는 시간을 예측하기 어려움 - 프로세스 history로 계산

 

round robin

 

 

현재 OS 까지 사용되는 방식으로 FIFO와 동일하지만 프로세스에게 프로세서를 사용할 수 있는 일정한 시간을 할당한다.(time slice) timer intterupt로 시간을 계산하여 주어진 time slice가 소진되면 프로세스를 전환한다. - 프로세서 사용을 적절히 분배해 수행 시간이 짧은 프로세스가 받는 손해가 줄어듬 (시분할 시스템)

 

 

dicision mode - preemtive(프로세스가 time slice를 다 소진하면 다른 프로세스가 프로세서를 선점)

selection function : Constant(일정한 time slice)

 

 

각 프로세스에게 주어지는 time slice가 4초라고 가정

 

queue에 진입한 시간을 다음과 같이 가정

A : 0,  B : 2,  C : 4,  D : 6,  E : 8

 

각 프로세서가 요구하는 시간을 다음과 같이 가정

A : 3,  B : 6,  C : 4,  D : 5,  E : 2

 

1. A가 queue 진입 시 다른 프로세스가 없으므로 4초 동안 A실행, B가 queue에 진입

 

2. A의 수행시간은 3초이므로 주어진 time slice내에 종료되고 B실행

 

3. B가 수행되고 C, D가 queue에 진입, B의 수행시간은 6초이므로 3초에 주어진 시간 내에 종료되지 못하여 다시 queue에 진입하여 D 뒤로 감

 

4. C가 수행됨 수행시간은 4초이므로 주어진 time slice내에 종료, E가 queue에 진입

 

5. D가 수행됨 수행시간은 5초이므로 주어진 time slice내에 종료되지 못하고 다시 queue에 진입하여 E 뒤로 감

 

6. 다시 B가 수행됨 남은 수행시간은 2초이므로 주어진 time slice내에 종료

 

7. E가 실행됨 수행시간은 2초이므로 주어진 time slice내 종료, 다시 D가 실행되고 남은 수행시간은 1초이므로 모든 프로세스 종료

 

 

time slice가 줄어들수록 짧은 수행시간을 가진 프로세스가 이득이고 늘어날수록 수행시간이 긴 프로세스가 이득

- large time slice => FIFO,   small time slice => SPN

- 그만큼 timer intterupt도 빈번하게 일어나서 추가 비용이 발생

 

 

평균 반환시간  : (3 + 5 + 7  + 14 + 11) / 5 = 10

 

 

SRT(Shortest Remaing Time)

 

SPN과 동일하지만 선점 모드를 도입하여 새로운 프로세스가 queue에 진입할 때마다 실행중인 프로세스의 남은 수행시간을 계산하여 더 짧은 수행시간을 가진 프로세스를 실행 -  remainng time 계산

 

 

dicision mode : preemtive

selection function : Min[S-E] (프로세스가 요구하는 실행 시간 - 남은 실행시간) - remainng time 

 

 

queue에 진입한 시간을 다음과 같이 가정

A : 0,  B : 2,  C : 4,  D : 6,  E : 8

 

각 프로세서가 요구하는 시간을 다음과 같이 가정

A : 3,  B : 6,  C : 4,  D : 5,  E : 2

 

 

A가 실행되고 2초에 B 진입시 B의 remainng time은 6, A의 remaining time은 1이므로 A 실행

다음 B가 실행되고 4초에 C의 remaining time은 4, B의 remaing time은 5이므로 C 실행

.

.

.

모든 프로세스의 평균 반환ㄴ 시간은 = (3 + 13 + 4 + 14 + 2) / 5 = 7.2

가장 빠른 평균 반환 시간을 가짐

단점 - 새로운 프로세스가 진입할 때마다 프로세스들의 남은 수행시간을 계산하는 추가 비용이 발생

 

 

HRRN

 

각 프로세스 마다 늦은 진입, 스위칭으로 인해 생기는 대기시간을 계산하여 제일 높은 대기시간을 가지는 프로세스를 선택

 

dicision mode : nonpreemtive

selection function : Max[ (q+s)/s ] ( q: 프로세스가 기다린 시간 - queue에 존재한 시간,  s: 프로세스가 요구하는 시간)

 

 

대기시간이 길어질수록 q가 늘어나 해당 프로세스의 경쟁력이 올라감