Process Scheduling

프로세스 스케줄링이란?

스케줄링 알고리즘을 통해 다음에 실행할 프로세스를 결정하는 것

 

<프로세스 스케줄링은 시간적인 frequency를 기준으로 크게 3가지로 나뉜다.>

- Long-term scheduling(job scheduling) : 프로세스가 처음 생성되어 system에 추가될 지 말 지를 결정

- medium-term scheduling(swapper) : 어떤 프로세스를 다시 memory로 올려놓을 것인지를 결정

- short-term scheduling(CPU scheduler) : processor scheduler(일반적인 프로세스 스케줄링)

 

+ I/O scheduling : I/O request할 때, pending하고 있는 프로세스 중 어떤 request를 선택할 지 결정

 

 

schedule함수 안에는 new process를 선택하는 알고리즘이 있다.

[selection function]

ready list에 있는 프로세스중 다음에 수행될 프로세스를 결정한다.

w : 시스템에서 지금까지 수행되는 시간

e : 시스템에서 지금까지 실행을 위해서 수행되는 시간

s : 프로세스가 요구하는 서비스 시간

 

<example>

max[w] => FIFO

w는 가장 오래된 시간이다 즉 가장 먼저 들어온 것 FIFO

 

selection function이 정해지면 decision mode에 따라 다르게 동작한다.

[decision mode]

- nonpreemptive : 프로세스가 종료되거나 스스로 block되기 전까지 수행을 지속한다.

- preemptive : 현재 running상태인 프로세스가 OS에 의해 수행권을 빼앗길 수 있다.

---

Scheduling Algorithm

• FIFO
• SPN
• Round Robin
• SRT
• HRRN

---

FIFO

first in first out

- queue에 가장 먼저 진입한 프로세스에 우선권을 준다.

- FCFS라고도 부름

- decision mode : non-preemption

- selection function : Max[w]

[장점]

구현이 쉽고 복잡도가 낮다. 오버헤드가 적다.

[단점]

long process가 우선시 된다 즉 fair하지 않다.

큰 프로세스로 인해 작은 job들이 몰려있다.

FIFO는 먼저 들어온 프로세스 순으로 실행되기에 A-B-C-D-E 순으로 실행된다.

---

SPN

shortest process next

- service time이 가장 짧은 process에 우선권을 준다.

- SJF라고도 부름

- decision mode : non-preemption

- selection function : min[s] ;s는 service time

[장점]

응답성에 있어 성능이 많이 개선되었다.

[단점]

긴 process가 CPU자원 할당을 오랫동안 못받을 수 있다.

구현이 어렵다(대기중인 process의 service time을 모두 알 수 없기 때문)

우선 non-preemption이기에 실행 중간에 프로세스가 끼어들지 않는다.

B가 2시점에 들어오고 A가 끝난 3 시점에서는 대기하는 프로세스가 B밖에 없기 때문에 B가 수행된다.

B의 service time인 6만큼 진행 후 9 시점에서는 4,6,8 시점에 ready list에 들어온 C,D,E중 service time이 가장 적은 E가 수행된다.

이런 알고리즘으로 반복된다.

 

turn around time = A:3, B:7, C:9, D:14, E:7

average turn around time = (3+7+9+14+7)/5 = 8

---

Round-Robin

- 기본적으로는 FIFO를 따른다.

- time quantum을 결정하는 것이 중요한 issue!

- 짧은 프로세스들이 받는 피해를 줄이기 위해 타이머 인터럽트를 통해 시간 할당량을 준다.

- decision mode : preemption

- select function : constant

[장점]

오버헤드가 적다.

짧은 프로세스가 받는 피해가 비교적 줄었다.

[단점]

time quantum이 작아질수록 SPN과 결과가 비슷해진다.

또한 time quantum이 작아질수록 타이머 인터럽트가 빈번해지고 프로세스 스위치가 자주 일어나게 된다. 즉 오버헤드가 커진다.

그렇다고 time quantum을 크게하면 FIFO와 비슷해진다.

일단 preemption이 일어날 수 있다!

time quantum이 4이기 때문에 각 프로세스의 최대 시간은 4이다.

0에서 A가 들어오고 실행된다.

2에서 B가 들어왔지만 A의 시간할당량이 아직 남아있기에 preeption이 일어나지 않는다.

3에서 A가 끝나고 기다리는 프로세스가 B밖에 없기에 B가 수행된다.

4에서 C가 들어오지만 B의 시간할당량이 남아있기에 B를 계속 수행한다.

6에서 D가 들어오지만 B의 시간할당량이 아직 남아있기에 B를 계속 수행한다.

7에서 B가 시간할당량을 모두 소진하였기에 2의 service time을 남기고 preemption된다. ready중인 C,D중 먼저 들어온 C부터 수행된다.

8에서 E가 들어왔지만 C의 시간할당량이 아직 남아있기에 C를 계속 수행한다.

11의 시점에서 C가 수행을 완료하고 기다리는 D,E,B중 먼저 들어온 D를 수행한다.

15시점에서 D가 1만큼을 남기고 preemption된다. ready list중 먼저들어온 E를 수행한다.

이어서 E가 남은 수행시간을 완료하고 마지막 남은 D가 수행된다.

 

turn around time = A:3, B:15, C:7, D:14, E:11

average turn around time = (3+15+7+14+11)/5 = 10

---

SRT

shortest-remaining time

- 가장 최적인 스케줄링 방법

- SPN의 preemptive mode라고 볼 수 있다.

- 가장 remaining time이 짧은 프로세스를 선택한다,

- decision mode : preemption

- select function : min[s-e] -> 실행중간에 new process가 들어오면 재계산한다.

[장점]

가장 turnaround time이 짧다.

[단점]

- 계속 재계산하는 연산때문에 overhead가 크다.

- Queue에 계속 shortest process가 도착하면 starvation이 일어날 수도 있다.

우선 preemption이 일어날 수 있다!

A가 시작되고 2시점에 B가 들어온다. A의 remaining time = 1, B의 remaining time = 6이기에 A가 선점한다.

A가 재개되고 3시점에 끝난다. 대기중이던 B가 들어온다.

B가 수행되다가 4시점에 C가 들어온다. B와 C중 B의 remaining time = 5, C의 remaining time = 4이기에 더 작은 C를 선택한다.

C가 수행되다가 6시점에 D가 들어온다. B,C,D중 B의 remaining time = 5, C의 remaining time = 2,D=5이기에 가장 작은 C선택한다.

이런 식으로 계속 수행되다가 만약 s-e값이 같은 프로세스가 있으면 pid값 등의 적절한 기준에 의해 프로세스가 선택된다.

 

turn around time = A:3, B:13, C:4, D:14, E:2

average turn around time = (3+13+4+14+2)/5 = 7.2

---

HRRN

highest response ratio next

R이 가장 큰 값인 프로세스에 우선권 부여

R = (q+s)/s 

- R값이 큰 것을 next process로 한다.(q는 기다린 시간)

- decision mode : non-preemption

- selection function : max[(q+s)/s]

[장점]

shortest job을 우선하는 철학을 유지하면서 대기시간이 길어질수록 우선권을 부여하기에 starvation을 회피할 수 있다.

[단점]

SPN,SRT보다 응답성이 떨어질 수 있다.

여전히 S를 사용하기에 구현이 어렵다(대기중인 process의 service time을 모두 알 수 없기 때문)

일단 non-preemption이다!

q는 기다린 시간, s는 service time 이며 (q+s)/s가 큰 값이 우선권을 갖는다.

A가 수행되고 2시점에 B가 들어오지만 A가 아직 수행중이기에 기다린다.

3시점에서 A가 끝나고 기다리는 프로세스가 B밖에 없기에 B가 수행된다.

4,6,8에서 C,D,E가 들어오지만 프로세스 B수행중이기에 모두 대기한다.

9시점에서 B프로세스가 종료되고 각 프로세스의 R값을 계산한다. C=9/4, D=8/5, E=3/2 가장 큰 값인 C선택

이런 방식으로 계속 수행된다.

 

turn around time = A:3,B:7,C:9,D:14,E:7

average turn around time = (3+7+9+14+7)/5 = 8

 

 

---

 

각각의 스케줄링 방식을 비교해보자.

프로세스 B의 수행시간이 가장 길고, E의 수행시간이 가장 짧다.

Tr/Ts는 1에 가까울 수록 좋은 성능을 나타낸다.

응답성을 보았을 때, 7.2로 SRT가 가장 좋았고

 

FCFS는 긴 프로세스에 대해 Tr/Ts값이 1에 가깝지만 짧은 프로세스에 대해서는 매우 낮은 성능을 보인다.

short와 long일 때의 차이가 확실하게 드러난다.

 

그에 비해 long의 관점에서 SPN과 SRT는 좋은 성능을 보이고 short의 입장에서는 다소 낮은 성능을 보인다.

 

이런 차이점들을 잘 파악해두자.