[운영체제] Scheduling

개념

- 일련의 프로세스들이 실행하는 상황을 워크로드(Workload)라고 한다.

각 작업들에는 도착 시간(arrival time) 과 실행 시간(run time) 같은 정보가 있다.

프로세스는 실행 도중에 CPU 작업과 입출력(I/O) 작업을 번갈아 수행하며, 이에 따라 Ready 상태와 Blocked 상태를 오가게 된다.

 

- 여러 프로세스들 중에 어떤 것을 CPU에 할당할지 결정하는 로직을 스케줄러(Scheduler)라고 한다.

 

- 스케줄링의 품질을 평가하는 기준을 Metric이라고 한다.

---

선입선출(FIFO)

가장 기초적인 알고리즘 중에 선입선출(First In First Out, FIFO)가 있다.

위의 간단한 예시를 통해 더 알아보자.

현재 작업 A, B, C는 거의 동시에 도착했다.(T arrival = 0) 단, 순서는 A → B → C이고, 모두 10초 동안 작업 실행 시간을 갖는다.

FIFO이기 때문에 도착한 순서로 작업을 수행한다.

따라서 평균 반환 시간을 구한다면  (10 + 20 + 30) / 3 으로 20이 된다.

실행 시간 가정을 바꿔보자.

작업 A가 60초, B가 10초, C가 10초 동안 실행되는 것이다.

그렇게 된다면 평균 반환 시간은 (60 + 70 + 80) / 3 으로 70이 된다.

 

이 문제점은 convoy effect라고 칭하며, 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 의미한다.

---

최단 작업 우선(SJF)

이와 같은 문제점을 해결하기 위해 가장 짧은 실행 시간을 가진 작업을 먼저 실행시키는 스케줄링이 바로 최단 작업 우선(Shortest Job First, SJF)이다.

바로 위에서 들었던 예시에 SJF 스케줄링을 적용한다면 

가장 짧은 실행 시간을 가진 작업 B와 C가 먼저 수행되고, 작업 A가 수행될 것이다.

그러면 평균 반환 시간은 (80 + 10 + 20) / 3 인 36.7로 약 2배 정도 향상시킨 것을 볼 수 있다.

 

모든 작업이 동시에 도착한다면 SJF가 최적의 알고리즘이겠지만, 실제로는 그렇지 않을 확률이 높다.

만약에 작업 A가 t=0에 도착하고, B와 C가 t=10에 도착한다면 이 작업들은 A가 끝날 때까지 기다릴 수밖에 없어서 이전의 convoy 문제가 다시 발생한다.

---

최단 잔여시간 우선(STCF)

SJF에 선점 기능을 추가한 것이 최단 잔여시간 우선(Shortest Time to Completion First, STCF)이다.

즉, 언제든 새로운 작업이 시스템에 들어오면, 이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄하는 것이다.

위 표처럼 작업 A, B, C가 들어왔을 때 어떻게 되는지 알아보자.

작업 A가 t=0에 도착했기 때문에 A를 실행을 한다.

t=10이 되었을 때 작업 B와 C가 들어오는데 잔여 실행 시간을 계산해보았을 때 A는 50, B는 10, C는 10이다.

따라서 B와 C가 가장 짧으므로 먼저 실행 후, t=30에 A의 남은 작업을 수행한다.

 

평균 반환 시간을 계산해보면 { (80 - 0) + (20 - 10) + (30 - 10) } / 3 이므로 36.7이 된다.

 

만약, 이 예시로 SJF 스케줄링을 택하면 평균 반환시간은 63.3이기에 STCF가 더 최적임을 알 수 있다.

---

라운드 로빈(RR)

우리가 작업의 길이를 미리 알기 어렵기 때문에 응답 시간(Response time)으로 평가를 해본다면 어떻게 될까.

응답 시간이란, 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간을 의미한다.

 

바로 위에서 들었던 예시로 알아보자면 (A는 t=0에 도착, B와 C는 t=10에 도착) 각 작업의 응답 시간은 A는 0, B는 0, C는 10이 된다.

 

세 번째 작업 입장에서는 먼저 들어온 작업이 끝날 때까지 기다려야 하기 때문에 응답 시간 측면에서는 별로 좋지 않다. 이런 응답 문제를 해결하기 위해 라운드 로빈(Round Robin, RR) 스케줄링이 도입되었다. 

 

RR은 작업이 끝날 때까지 기다리는 것이 아니라, 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스 또는 스케줄링 퀸텀이라고 부른다.

RR도 간단한 예시를 통해 알아보자.

작업 A, B, C가 동시에 도착하고, 각각 실행 시간은 5초이다. 1초의 타임 슬라이스를 가진 RR은 작업을 빠르게 순환하여 평균 응답 시간은 (0 + 1 + 2) / 3 으로 1이다.

만약, 동일한 예시로 SJF 스케줄링을 적용한다면 SJF의 평균 응답 시간은 (0 + 5 + 10) / 3으로 5가 되었을 것이다.

---

입출력 연산

지금까지의 작업들은 입출력을 하지 않는다는 가정을 하였다. 그러나 모든 프로그램은 입출력 작업을 수행한다. 

두 개의 작업 A와 B가 있다고 해보자.

A는 10 msec 동안 실행된 후 입출력 요청을 한다. (입출력 시간은 10 msec으로 가정) 반면, B는 입출력을 수행하지 않는다.

스케줄러는  위 그림처럼 A를 먼저 실행시키고 B를 다음에 실행시킨다. 이렇게 될 경우 A가 I/O하는 동안 CPU는 아무 작업도 하지 않게 되기 때문에 비효율적이다. 

여기서 STCF 스케줄러를 적용해보자. A가 5개의 10 msec의 작업으로 분할이 되고 B 하나의 50 msec가 있는 셈이다.

그러면 STCF는 가장 짧은 작업을 선택하게 되므로 작업 A를 선택하면 B만 남게 되어 B를 선점하여 10 msec 동안 실행한다. 

이렇게 된다면 자원을 효율적으로 사용할 수 있게 된다.