[운영체제] 8. 스케줄링 (2) - Batch System 스케줄링

지난 글에서 정리한 것처럼, 배치 시스템은 프로세스 스위칭을 최소화하고 성능을 높이는 것을 목표로 한다.

배치 시스템에서 사용하는 다양한 스케줄링 알고리즘을 정리해보자.

 

 

FCFS (First-Come-First-Served)

선입 선처리 스케줄링 또는 FCFS 스케줄링라고 부른다.

이름 그대로 CPU 사용을 요청한 순서대로 할당해주는 방식의 알고리즘이다.

 

이를 위해서 하나의 큐를 사용하며, 현재 실행중인 프로세스가 Blocked 상태로 가면 큐의 맨 앞에 있는 프로세스를 running 상태로 올린다. 만약 blocked 상태에 있던 프로세스가 ready상태가 되면, 큐의 맨 뒤에 해당 프로세스를 넣는다.

 

이 스케줄링 알고리즘은 비선점 스케줄링 알고리즘이다.

큐에 들어온 순서대로 순차적으로 실행만 하고, 실행하는 시간에 제한을 걸어두지는 않기 때문이다.

 

알고리즘이 간단해서 이해하기 쉽다는 장점이 있지만, 다음과 같은 상황에서는 문제가 발생할 수 있다.

CPU-bound process 가 하나 있다. 이 프로세스는 1초동안 실행된 뒤 disk 데이터를 읽기 위해 blocked 상태로 빠진다.

I/O-bound process 가 여러개 있다. 각각의 프로세스는 CPU burst는 작지만 1000번의 disk 데이터를 읽어야 작업을 완료한다.

 

이 상황에서 FCFS 스케줄링을 사용하게 되면, CPU bound 프로세스가 한번 실행되고, 1초 뒤에 I/O bound 프로세스가 실행되어서 1번 디스크 데이터를 읽기 위해 blocked 상태로 빠지고, 다시 CPU bound 프로세스가 한번 실행되고, 1초뒤에 I/O bound 프로세스가 2번째 디스크 데이터를 읽기 위해 blocked 상태로 빠지고.. 가 반복된다.

따라서 I/O bound 프로세스가 실행을 마치기 위해서는 무려 1000초의 시간을 기다려야 하는 문제가 발생한다.

 

 

 

Shorted Job First (SJF Scheduling)

이름 그대로 실행시간이 제일 짧은 프로세스부터 먼저 실행하는 스케줄링 알고리즘이다.

이 스케줄링도 비선점형 스케줄링 알고리즘이며, 각 프로세스의 실행 시간을 알고 있어야 사용할 수 있다.

 

이 스케줄링은 '모든 프로세스가 동시에 도착했을 때' 를 가정한 경우, 최적의 평균 turnaround time 을 만든다.

turnaround time 은 내가 실행되기를 요청하고나서 실제 실행되고 종료가 될 때까지의 시간을 말한다.

 

 

그림과 같은 상황을 생각해보자.

(a) 상황에서 각 프로세스의 turnaround time 은 다음과 같다.

 

A = 8

B = 8 + 4

C = 8 + 4 + 4

D = 8 + 4 + 4 + 4

 

모두 동시에 도착해서 요청을 보냈다고 가정하기 때문에 turnaround time의 계산 시작점이 모두 동일하다.

이제 이 시간의 평균을 구해보면 (8 + (8 + 4) + (8 + 4 + 4) + (8 + 4 + 4 + 4)) / 4 = 56 / 4 = 14 가 나온다.

 

(b) 상황에서도 같은 방법으로 계산하면, (4 + 8 + 12 + 20) / 4 = 11 로 더 짧은 시간이 나온다.

(그리고 이 시간보다 더 짧아질 수 없다.)

 

만약 계산 시작점이 다른 경우를 보면

A, B, C, D, E 5개 프로세스가 있고, 각각의 실행 시간은 2, 4, 1, 1, 1 이라고 해보자.

A, B 는 0에 도착하고 C, D, E 가 모두 3에 도착할 때 똑같이 SJF 스케줄링을 사용해보자.

 

시점 0에서 스케줄링을 할 때는 A, B 중에서 짧은 A를 선택한다.

A를 실행하고나면 시점 2가 된다.

시점 2에서 스케줄링을 할 때는 아직 C, D, E 가 도착하지 않았으므로 B를 선택한다.

B를 실행하고나면 시점 6이 된다.

이때부터는 모든 C, D, E 프로세스가 도착했으므로 각각 실행하면 7, 8, 9 에 실행이 완료된다.

 

이 경우에 대해 평균 turnaround 시간을 계산해보면

A = 2 - 0 = 2

B = 6 - 0 = 6

C = 7 - 3 = 4

D = 8 - 3 = 5

D = 9 - 3 = 6

 

따라서 (2 + 6 + 4 + 5 + 6) / 5 = 23 / 5

 

그런데 만약 맨 처음에 B를 먼저 실행했다면 어떻게 됐을까?

 

시점 0에서 B를 선택한다.

B를 실행하고나면 시점 4가 된다.

시점 4에서는 C, D, E 가 모두 도착했으므로 C, D, E를 실행한다.

시점 7에서 A를 실행하면 시점 9에 종료된다.

 

이 경우에 대해 평균 turnaround 시간을 계산해보면

A = 9 - 0 = 9

B = 4 - 0 = 4

C = 5 - 3 = 2

D = 6 - 3 = 3

E = 7 - 3 = 4

 

따라서 (9 + 4 + 2 + 3 + 4) / 5 = 22 / 5

 

앞서 SJF를 정직하게 돌린 알고리즘보다 더 낮은 평균 turnaround 시간이 나온다.

따라서 SJF가 평균 turnaround 시간의 최적을 보장하는 것은 모든 프로세스가 같은 시점에 도착했을 때를 전제한다는 것을 기억하자.

 

 

Shorted Remaining Time Next (SRT Scheduling)

SJF Scheduling의 선점형 스케줄링 버전이다.

이름 그대로 남은 잔여시간이 제일 짧은 프로세스를 다음에 실행하는 알고리즘으로, '최소 잔여 시간 우선 스케줄링' 이라고 부르기도 한다.

 

이 스케줄링은 현재 CPU에서 실행하고 있는 프로세스가 작업을 실행하는 도중 새로운 프로세스가 도착했다면,

도착한 프로세스의 실행 시간과 현재 프로세스의 남은 잔여 시간을 비교하고,

만약 새로 도착한 프로세스의 실행 시간이 더 짧다면 현재 프로세스의 동작을 중지시키고 새로 도착한 프로세스를 실행하는 알고리즘이다.

 

(혼공운체에서는 정해진 시간만큼 실행시키고, 다음에 실행시킬 프로세스를 결정할 때 남은 잔여 시간을 고려하여 선택하는 것으로 설명하였다.)

 

 

 

Three-level Scheduling

(수업에서는 설명하지 않고 일단 넘어가셨다.)