[OS] 운영체제 아주 쉬운 세 가지 이야기 7장 스케줄링

참고 자료 

[책] 운영체제 아주 쉬운 세 가지 이야기 

7장 스케줄링 개요 

다양한 스케줄링 정책(scheduling policy) 을 소개하고 그에 관한 이해를 높일 것이다. 

7.1 워크로드에 대한 가정 

일련의 프로세스들이 실행하는 상황을 워크로드(workload)라고 부르기로 한다. 워크로드를 결정하는 것은 정책 개발에 매우 중요한 부분이다. 

 

우리는 시스템에서 실행 중인 프로세스 혹은 작업(job)에 대해 다음과 같은 비현실적인 가정을 한다.

1. 모든 작업은 같은 시간 동안 실행된다.

2. 모든 작업은 동시에 도착한다.

3. 각 작업은 시작되면 완료될 때까지 실행된다. (비선점)

4. 모든 작업은 CPU 만 사용한다(I/O 작업 X).

5. 각 작업의 실행 시간은 사전에 알려져 있다.

 

몇몇 가정은 다른 가정에 비해 더 비현실적이다. 특히, 각 작업의 실행 시간이 미리 알려져 있다는 가정은 더욱 그렇다. 

7.2 스케줄링 평가 항목 

워크로드에 대한 가정 이외에 스케줄링 정책의 비교를 위해 스케줄링 평가 항목(scheduling metric)을 결정해야 한다. 스케줄링의 경우 다양한 평가 기준이 존재한다. 우선, 문제를 간단하게 하기 위해 반환 시간(turnaround time)이라는 하나의 평가 기준을 사용한다.

 

작업 반환 시간 = 작업 완료 시간 - 시스템에 도착한 시간 

T turnaround=Tcompletion−Tarrival 

모든 작업은 동시에 도착한다고 가정: Tarrival = 0

→  Tturnaround=Tcompletion

 

반환 시간은 성능 측면에서의 평가 기준이다. 다른 평가 기준으로 공정성(fairness)이 존재 

성능과 공정성은 스케줄링에서는 서로 상충되는 목표이다.

7.3 선입선출 

가장 기초적인 알고리즘은 선입선출(First In First Out, FIFO) 또는 선도착선처리(First Come First Served, FCFS) 스케줄링이라고 알려져 있다. FIFO 는 많은 장점을 가진다. 단순하고 구현하기 쉽다. 현재의 가정 하에서는 매우 잘 동작한다.

간단한 FIFO 스케줄 example

시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자 (T arrival= 0). 간발의 차이로 A, B, C 순서대로 도착했다고 가정

또한 각 작업들은 10초 동안 실행된다고 가정. 이 작업들의 평균 반환 시간은 얼마인가?

A: 10 B: 20 C: 30

평균 반환 시간 = (10 + 20 + 30) / 3 = 20 

 

자 이제 가정 중 한 가지를 완화하자. 구체적으로 1 번 가정을 완화하여 작업을 실행 시간이 모두 같지 않다고 가정하자. FIFO는 어떻게 동작하는가? FIFO는 어떤 워크로드에서 좋지 않은 성능을 보일까?

 

다시 3개의 작업 A, B, C 가정 이번에는 A는 100초, B와 C는 10초 동안 실행

A: 100 B: 110 C: 120

평균 반환 시간 = (100 + 110 + 120) / 3 = 110

이 문제점은 호위 효과(convoy efect) 라고 칭해지며 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다. 

 

그러면 어떻게 해야 할까? 작업 실행 시간이 다른 경우 더 좋은 알고리즘은 무엇인가?

7.4 최단 작업 우선 

최단 작업 우선(Shortest Job First, SJF) 원칙은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

위의 예를 이번에는 SJF로 스케줄 해 보자. SJF가 평균 반환 시간 기준으로 더 나은 성능을 보이는지 보인다.

A:120 B: 10 C: 20

평균 반환 시간 = (120 + 10 + 20) / 3 = 50

 

SJF는 평균 반환 시간을 110초에서 50초로 2배 이상 향상시켰다. 

모든 작업이 동시에 도착한다면 SJF가 최적(optimal)의 스케줄링 알고리즘임을 증명할 수 있다.

 

SJF라는 좋은 스케줄링 기법을 개발하였지만 가정이 아직 비현실적이다. 이제 가정을 완화해 보자. 특히, 가정 2를 완화하여 이제 모든 작업은 동시에 도착하는 것이 아니라 임의의 시간에 도착할 수 있다고 가정한다. 이러면 어떤 문제가 발생하는가?

 

A는 t = 0에 도착하고 100초의 실행 시간 B, C는 t = 10에 도착하고 각각 10초의 실행 시간을 가진다고 가정 

순수한 SJF로 스케줄 했을 경우의 스케줄 

 

그림에서 알 수 있듯이 B와 C가 A 바로 뒤에 도착한다고 하더라도 A가 끝날 때까지 기다릴 수밖에 없어서 이전의 convoy 문제가 다시 발생한다.

A: 100 B: 100 C: 110 

평균 반환 시간 = (100 + 100 + 110) / 3 = 103.33

 

스케줄러는 어떻게 스케줄링 해야 할까?

7.5 최소 잔여시간 우선 

이 문제를 해결하기 위해서는 가정 3(작업은 끝날 때까지 계속 실행된다)을 완화해야 한다. 타이머 인터럽트와 문맥 교환을 고려하면 B와 C 가 도착했을 때 스케줄러는 다른 일을 할 수 있다. 작업 A를 중지하고 지금 도착한 B나 C를 실행하기로 결정할 수도 있다. 물론, 선점된 A는 나중에 다시 실행된다. SJF는 비선점형 스케줄러이기 때문에 이와 같은 동작을 하지 못한다.

 

이를 해결하는 스케줄러가 이미 존재한다. SJF에 선점 기능을 추가한 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF) 또는 선점형 최단 작업 우선(PSJF)

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

 

STCF == PSJF

PSJF는 SJF(Shortest Job First)의 선점형 버전이라는 의미로, 들어오는 시점의 전체 작업 시간 기준으로 판단하는 듯 보일 수 있음.

하지만 실제로는 STCF와 동일하게 남은 시간 기준으로 선점한다.

 

STCF는 A를 선점하고 B와 C를 끝날 때까지 실행시킨다. 두 작업이 모두 끝난 후에 A가 스케줄되어 남은 실행 시간 만큼 실행된다.

A:120 B:10 C:10

평균 반환 시간: (120 + 10 + 10) / 3= 50

 

새로운 가정 하에서 STCF 가 최적의 스케줄러이다.

7.6 새로운 평가 기준: 응답 시간 

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 매우 훌륭한 정책이다.

하지만 시분할 컴퓨터의 등장이 모든 것을 바꾸었다. 이제 사용자는 시스템에게 상호작용을 원활히 하기 위한 성능을 요구하게 되었다. 응답 시간(response time)이라는 새로운 평가 기준이 태어나게 된다.

 

응답 시간은 작입이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다. Tresponse=Tfirstrun−Tarrival

 

STCF를 비롯하여 비슷한 류의 정책들은 응답 시간이 짧다고 할 수 없다. 예를 들어, 3 개의 작업이 동시에 도착한 경우, 세 번째 작업은 딱 한 번 스케줄 되기 위해 먼저 실행된 두 작업이 완전히 끝날 때까지 기다린다. 반환 시간 기준으로는 매우 훌륭한 반면, 응답 시간과 상호작용 측면에서는 매우 나쁜 방법이다.

 

7.7 라운드 로빈 

응답 시간 문제를 해결하기 위하여 라운드 로빈(Round-Robin, RR) 스케줄링이라 불리는 스케줄링 알고리즘을 도입한다.

RR 은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)이라 부른다.

 

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.

타임 슬라이스가 타아머 인터럽트 주기의 배수이면 이는 작업 전환(컨텍스트 스위칭)시에 타이머 인터럽트 발생 횟수(count)를 기준으로 쉽게 제어할 수 있기 때문이다.

 

1초의 타임 슬라이스를 가지는 RR은 작업을 빠르게 순환하게 된다(그림 10.7). RR의 평균 응답 시간은 (0+1+2) 3 = 1 이고, SJF의 평균 응답 시간은 (0+5+10) 3 = 5 이다.

 

타임 슬라이스의 길이는 RR 에게 매우 중요하다. 타임 슬라이스가 짧을수록, 응답 시간 기준으로 RR의 성능은 더 좋아진다. 그러나 타임 슬라이스를 너무 짧게 지정하면 문제가 생긴다. 짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다. 시스템 설계자는 시스템이 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 결정해야 한다. 문맥 교환 비용을 상쇄할 수 있을 만큼 길어야 하지만 그렇다고 응답 시간이 너무 길어지면 안 된다.

 

반환 시간이 유일한 측정 기준인 경우 RR이 최악의 정책이다. 반환 시간은 작업 완료 시간만을 고려하기 때문에, RR은 거의 최악이며, 많은 경우 단순한 FIFO 보다도 성능이 좋지 않게 된다. 일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 나쁘다. 불공정하게 한다면 하나의 작업을 끝까지 실행하고 종료할 수 있지만 나머지 작업들에 대한 응답 시간은 포기해야 한다. 반대로 공정성을 더 소중히 여긴다면 응답 시간은 줄어들지만 반환 시간은 나빠지게 된다.

7.8 입출력 연산의 고려 

이제 가정 4를 완화한다. 모든 프로그램은 입출력 작업을 수행한다. 입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야 한다. 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU 를 사용하지 않을 것이기 때문이다. 입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다. 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄 해야 한다. 스케줄러는 입출력 완료 시에도 의사 결정을 해야 한다. 입출력이 완료되면 (하드웨어) 인터럽트가 발생하고 운영체제가 실행되어 입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 다시 이동시킨다. 운영체제는 각 작업을 어떻게 처리해야 하는가?

 

두 개의 작업 A,B 존재 각 작업은 50msec의 CPU 시간이 필요 

A는 10 msec 동안 실행된 후, 입출력 요청을 한다(여기서 입출력 시간은 10 msec 라고 가정).

B는 입출력을 수행하지 않는다. 

 

STCF(Shortest Time-to-Completion First) 스케줄러를 구축한다고 가정 A가 5개의 10msec 작업으로 분할되는 반면에 B는 하나의 50msec의 CPU를 요청한다는 사실을 어떻게 활용할까?

 

입출력을 고려하지 않고 작업을 하나씩 실행시키는 것은 의미가 없다. 일반적인 접근 방식은 A의 각 10msec 하위 작업을 독립적으로 다루는 것. 시스템이 시작할 때 10msec 작업들과 50msec를 스케줄하는 것이다. STCF의 경우 선택은 자명하다. 가장 짧은 작업을 선택하라. 이 경우에는 A가 된다. 그러면 A의 첫 번째 소 작업이 완료되면 B만 남게 되어 실행을 시작한다.

 

 

 

 

프로세스의 입출력이 끝나기를 기다리는 동안 CPU 는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다.

입출력을 고려한 스케줄러 방법에 대해서 알아보았다. 각 CPU 버스트를 하나의 작업으로 간주함으로써 스케줄러는 대화형 프로세스가 더 자주, 즉 유리하게 실행되는 것을 보장한다. 이러한 대화형 작업이 입출력을 실행하는 동안 다른 CPU-집중 작업들이 실행되고 CPU의 이용률은 더 높아진다.

7.9 만병통치약은 없다

스케줄러가 각 작업의 실행 시간을 알고 있다는 가정은 최악의 가정이다. 현재 운영체제에서 작업의 길이에 대해서 알 수 있는 길은 없다. 

따라서 아무런 사전 지식 없이 SJF/STCF 처럼 행동하는 알고리즘을 구축할 수 있을까? 게다가, 응답 시간도 좋게 하기 위하여 RR 스케줄러의 경우에 보았던 아이디어를 어떻게 하면 포함시킬 수 있을까?