2-3장. 스케줄링 : 개요

이제부터 다양한 스케줄링 정책(Scheduling policy)을 소개할 것이다. 이러한 정책은 원칙이라고도 불리며 많은 똑똑하고 부지런한 사람들이 오랫동안 개발한 정책이다.

 

스케줄링의 기원은 컴퓨터 시스템 개발 이전으로 거슬러 올라간다. 초기의 방법들은 생산 관리 분야에서 개발되었으며 컴퓨터에 적용되었다. 이 사실은 그렇게 놀라운 일은 아니다. 생산 공정과 기타 많은 인간의 행동 역시 스케줄링이 필요하고, 효율성에 대한 요구 등, 공통된 해결 사항이 존재하기 때문이다. 스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 할까? 핵심 과정은 무엇일까?

 

워크로드에 대한 가정

가장 먼저 프로세스에 대해서 몇 가지 가정을 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드(Workload)라고 부르기로 한다. 워크로드를 결정하는 일은 정책 개발에 매우 중요한 부분이다. 워크로드에 대해 더 잘 알수록 그에 맞게 정책을 정교하게 손볼 수 있다.

 

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

 

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다. (즉, 입출력을 수행하지 않는다.)
5. 각 작업의 실행 시간은 사전에 알려져 있다.

이 가정들은 굉장히 비현실적이다. 특히, 각 작업의 실행 시간이 미리 알려져 있다는 가정은 더욱 그렇다. 이 가정은 스케줄러가 모든 것을 다 알 수 있다는 것을 의미한다. 좋은 일이기는 하지만 가까운 미래에 나올 것 같지는 않다.

 

스케줄링 평가 항목

워크로드에 대한 가정 이외에 스케줄링 정책의 비교를 위해 스케줄링 평가 항목(Scheduling metric)을 결정해야 한다. 스케줄링의 경우 다양한 평가 기준이 존재한다.

 

우선, 문제를 간단하게 하기 위해 반환 시간(Turnaround time)이라는 하나의 평가 기준을 사용한다. 작업 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시각을 뺀 시간으로 정의된다. 

반환 시간은 성능 측면에서의 평가 기준이라는 것을 주목해야 한다. 다른 평가 기준으로 공정성(Fairness)이다. 성능과 공정성은 스케줄링에서는 서로 상충되는 목표이다. 예를 들어, 스케줄러는 성능을 극대화하기 위해 몇몇 작업의 실행을 중지하며, 결과적으로 공정성이 약화된다. 

 

선입선출(FIFO)

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

 

간단한 예를 스케줄 해 보자. 시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자 (T도착시간 = 0). 간발의 차이로 A, B, C 순서대로 도착했다고 가정하자. 또한, 각 작업은 10초 동안 실행된다고 가정하자. 이 작업들의 평균 반환 시간은 얼마인가?

 

A는 10, B는 20, C는 30에 종료했다는 것을 알 수 있다. 세 작업의 평균 반환 시간은 (10 + 20 + 30) / 3 = 20이다. 반환 시간의 계산은 쉽다.

 

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

 

FIFO 스케줄링이 어떤 문제를 야기하는지 보자. 구체적으로 다시 A, B, C 세 개의 작업을 가정하자. 그러나 이번에는 A는 100초, B와 C는 10초 동안 실행된다.

 

작업 A가 B와 C보다 100초 동안 실행된다. 따라서 시스템의 평균 반환 시간은 110초로 늘어난다. (100 + 110 + 120) / 3 = 110

 

이 문제점은 Convoy effect라고 부르며 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다. 이 스케줄링 시나리오는 슈퍼마켓에서 줄 서서 계산을 기다릴 때, 앞사람이 카트 세 개에 물건을 가득 싣고 있는 경우와 느낌이 비슷하다. 

 

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

 

최단 작업 우선(SJF)

이 문제는 간단하게 해결할 수 있다. 사실 이 아이디어는 오퍼레이션 리서치 분야에서 차용하여 컴퓨터 시스템의 작업 스케줄링에 적용한 것이다. 이 새로운 스케줄링 개념용 최단 작업 우선(Shortest Job First, SJF)으로 이름 자체가 정책을 설명하고 있기 때문에 기억하기 쉽다. 이 원칙은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

 

위의 예를 SJF로 스케줄 해 보자. A, B, C를 실행시킨 결과를 보이고 있다. SJF가 평균 반환 시간 기준으로 더 나은 성능을 보이는지 보인다. B, C, A 순서로 실행시킴으로써 SJF는 평균 반환 시간을 110초에서 50초 ( (10 + 20 + 120) / 3 = 50)로 2배 이상 향상했다.

 

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

 

문제가 무엇인지 설명하기 위하여 예를 들어보자. 이번에는 A는 t = 0에 도착하고 100초의 실행 시간을 가지고 있고, 반면에 B와 C는 t = 10에 도착하고 각각 10초의 실행 시간을 가진다고 가정하자. 순수한 SJF로 스케줄 했을 경우 다음 그림과 같다.

 

그림에서 알 수 있듯이 B와 C가 A 바로 뒤에 도착한다고 하더라도 A가 끝날 때까지 기다릴 수밖에 없어서 이전의 convoy 문제가 다시 발생한다. 이 경우 반환 시간은 103.33 ( (100+(110-10) +(120-10)) / 3)이다. 스케줄러는 어떻게 스케줄링해야 할까?

 

최소 잔여시간 우선(STCF)

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

 

다행히도 이렇게 동작할 수 있는 스케줄러는 이미 존재한다. SJF에 선점 기능을 추가한 최단 잔여시간 우선(Shortest Time-to Completion First, STCF) 또는 선점형 최단 작업 우선 (PSJF)으로 알려진 스케줄러이다. 언제든 새로운 작업이 시스템에 들어오면, 이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄 한다.

 

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

 

그 결과 평균 반환 시간이 단축되어 50초 ( ((120-0)+(20-10)+(30-10)) / 3)가 된다. 새로운 가정 하에서 STCF가 최적의 스케줄러이다. 작업들이 동시에 도착할 경우, SFJ가 최적의 결과를 낸다는 것을 고려하면, STCF가 최적의 스케줄링이 되는 이유를 쉽게 알 수 있을 것이다.

 

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

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 매우 훌륭한 정책이다. 초기 일괄처리 컴퓨터 시스템에서는 이러한 스케줄링 알고리즘이 의미가 있었다.

 

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

 

응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다. 다음과 같다.

 

예를 들어, 위와 같은 스케줄의 (A는 시간 0, B와 C는 시간 10에 도착) 경우, 각 작업의 응답 시간은 A는 0, B는 0, C는 10, 평균 3.33이 된다. 

 

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

 

터미널 앞에 앉아 입력한 후, 단지 다른 작업이 당신의 작업보다 먼저 스케줄 되었다는 이유로 시스템의 응답이 올 때까지 10초 기다리는 것을 상상해 보자. 별로 즐거운 일은 아니다. 응답 시간에 민감한 스케줄러를 어떻게 만들 수 있을까?

 

라운드 로빈(RR)

응답 시간문제를 해결하기 위하여 라운드 로빈(Round-Robin, RR) 스케줄링이라 불리는 스케줄링 알고리즘을 도입한다. 기본 발상은 간단하다. RR은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 

 

이때 작업이 실행되는 일정 시간을 타임 슬라이스(Time slice) 또는 스케줄링 퀀텀(Scheduling quatum)이라 부른다. 작업이 완료될 때까지 이런 식으로 계속 진행된다. 이러한 이유로 RR은 때때로 타임 슬라이싱이라고 불린다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 10 msec마다 인터럽트를 발생시킨다면 타임 슬라이스는 10, 20 등 10 msec의 배수가 될 수 있다.

 

RR을 자세하게 이해하기 위해 하나의 예를 살펴보자. 3개의 작업 A, B, C가 시스템에 동시에 도착하고(T도착시간=0), 각각 5초간 실행된다고 가정한다. SJF 스케줄러는 다른 작업을 실행하기 전에 각 작업을 종료할 때까지 실행한다. 대조적으로 1초의 타임 슬라이스를 가지는 RR은 작업을 빠르게 순환하게 된다. RR의 평균 응답 시간은 1이고, SJF의 평균 응답 시간은 5이다.

 

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

 

입출력 연산의 고려

가정 4를 완화해보자. 모든 프로그램은 입출력 작업을 수행한다. 아무런 입력도 받아들이지 않는 프로그램을 상상해 보자. 매번 같은 출력을 만들어 낼 것이다. 출력하지 않는 프로그램을 상상해 보자. 그건 속담에도 나올 법한 아무도 보는 사람이 없이 숲에서 잎이 떨어지는 것과 같다. 실행되었다는 사실이 아무 의미가 없다. 

 

입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야 한다. 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않을 것이기 때문이다. 입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다. 입출력이 하드 디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 동안 블록 될 것이다. 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄 해야 한다.

 

마찬가지로 스케줄러는 입출력 완료 시에도 의사 결정을 해야 한다. 입출력이 완료되면 인터럽트가 발생하고 운영체제가 실행되어 입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 다시 이동시킨다. 물론, 인터럽트가 발생했을 때 요청 프로세스를 즉시 실행시키기로 결정할 수도 있다. 운영체제는 각 작업을 어떻게 처리해야 하는가?

 

이 쟁점을 더 잘 이해하기 위해 두 개의 작업 A와 B가 있다고 하자. 각 작업은 50 msec의 CPU 시간을 필요로 한다. 그러나 둘은 한 가지 큰 차이를 가진다. A는 10 msec동안 실행된 후, 입출력 요청을 한다. (여기서 입출력 시간은 10msec라고 가정한다) 반면에 B는 입출력을 수행하지 않는다. 스케줄러는 A를 먼저 실행시키고 B를 다음에 실행시킨다.

 

자원의 비효율적인 활용

STCF 스케줄러를 구축하려고 한다 가정하자. A가 5개의 10msec 작업으로 분할되는 반면에 B는 하나의 50msec의 CPU를 요청한다는 사실을 어떻게 활용할까? 분명히 입출력을 고려하지 않고 하나씩 실행시키는 것은 의미가 없다.

 

일반적인 접근 방식은 A의 각 10 msec 하위 작업을 독립적인 작업으로 다루는 것이다. 시스템이 시작할 때 10msec 작업들과 50msec를 스케줄하는 것이다. STCF의 경우 선택은 자명하다. 가장 짧은 작업을 선택하라. 이 경우에는 A가 된다. 그러면 A의 첫 번째 소 작업이 완료되면 B만 남게 되어 실행을 시작한다. A의 다음 작업이 제출되고 B를 선점하여 10msec 동안 실행한다. 이렇게 하면 프로세스의 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다. 

 

 

요약

우리는 스케줄링의 기본적인 개념과 두 가지 부류의 접근법을 살펴보았다. 첫 번째 부류는 남아 있는 작업 중 실행 시간이 제일 짧은 작업을 수행하고, 반환 시간을 최소화한다. (STCF) 두 번째 부류는 모든 작업을 번갈아 실행시키고 응답 시간을 최소화한다. (RR) 안타깝게 반환 시간과 응답 시간 중 하나를 최적화하면 나머지 하나는 좋지 않은 특성을 나타낸다. 이는 시스템에서 흔히 보이는 절충을 요구하는 상황이다. 전체적인 그림에 입출력을 어떻게 통합해야 하는지도 보았다. 

 

그렇지만 미래를 예측할 수 없는 운영체제의 근본적인 문제는 해결할 수 없었다. 가까운 과거를 이용해 미래를 예측하는 스케줄러를 구현하여 이 문제를 어떻게 해결하는지 곧 보게 될 것이다.