[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 7. CPU Scheduling
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
이제 프로세스를 싱행시키기 위한 문맥 교환 등의 저수준 기법에 대해서는 분명하게 이해할 수 있기에 운영체제 스케줄러의 고수준 정책에 관해서는 이해가 필요하다. 이제부터는 다양한 스케줄링 정책(scheduling policy)을 소개하고 그에 관한 이해를 높일 것이다. 이러한 정책은 원칙(discipline)이라고도 불린다.
사실 스케줄링의 기원은 컴퓨터 시스템 개발 이전으로 거슬러 올라간다. 초기의 방법들은 생산 관리 분야에서 개발되었으며 컴퓨터에 적용되었다. 생산 공정과 기타 많은 인간의 행동 역시 스케줄링이 필요하고, 효율성에 대한 요구 등, 공통된 해결 사항이 존재하기 때문이다.
그럼 스케줄링 정책은 어떻게 개발하는가?
스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가?
핵심 가정은 무엇은가?
어떤 평가 기준이 중요한가?
컴퓨터 시스템의 초창기에 사용되었던 기본 접근법은 무엇인가?
워크로드에 대한 가정
먼저 프로세스에 대하여 몇 가지 가정을 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드(workload)라고 부르기로 한다. 워크로드를 결정하는 것은 정책 개발에 매우 중요한 부분이다. 워크로드에 관해 더 잘 알수록 그에 맞게 정책을 정교하게 손질할 수 있다.
설명을 위해 워크로드에 대한 비현실적인 가정을 할 것인데, 점점 가정을 완화시켜 나가면서 제대로 동작하는 스케줄링 정책을 만들 게 될 것이다.
우리는 시스템에서 실행 중인 프로세스 혹은 작업(job)에 대해 다음과 같은 가정을 한다.
1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다 (즉, I/O 작업이 없다).
5. 각 작업의 실행 시간은 사전에 알려져 있다.
스케줄링 평가 항목
워크로드에 대한 가정 이외에 스케줄링 정책의 비교를 위해 스케줄링 평가 항목(scheduling metric)을 결정해야 한다. 스케줄링의 경우 다양한 평가 기준이 존재한다.
우선, 문제를 간단하게 하기 위해 반환 시간(turnaround time)이라는 하나의 평가 기준을 사용한다. 작업 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간으로 정의된다
모든 작업은 동시에 도착한다고 가정했으므로 $T_{arrival} = 0$으로 생각할 수 있다. $T_{turnaround} = T_{completion}$ 이다. 이 가정은 완화해 나갈 것이다.
반환 시간은 성능 측면에서의 평가 기준이라는 것을 주목해야 한다. 다른 평가 기준으로 공정성(fairness)이다. 예를 들면 Jain’s Fairness Index에 따라 측정된다. 성능과 공정성은 스케줄링에서 서로 상충되는 목표이다. 예를 들어, 스케줄러는 성능을 극대화하기 위해 몇몇 작업의 실행을 중지하며, 결과적으로 공정성이 악화된다.
선도착선처리 (First Come First Served, FCFS)
가장 기초적인 알고리즘은 선입선출(First In First Out, FIFO) 또는 선도착선처리(First Come First Served, FCFS) 스케줄링이라고 알려져 있다. FIFO는 단순하고 구현하기 쉽다.
가장 간단한 예를 스케줄 해보자.
시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정해보자. ($T_{arrival} = 0$) 간발의 차이로 A, B, C 순서대로 도착했다고 가정하자. 또한, 각 작업들은 10초 동안 실행된다고 가정하자. 이 작업들의 평균 반환 시간은 얼마인가?
그림에서 A는 10, B는 20, C는 30에 종료했다는 것을 알 수 있다. 세 작업의 평균 반환 시간은 20이다.
이제 1번 가정을 완화하여 작업의 실행 시간이 모두 같지 않다고 해보자.
a는 100초, B와 C는 10초 동안 실행된다.
그림에서 볼 수 있듯이, 작업 A가 B와 C보다 먼저 100초 동안 실행되고, 시스템의 평균 반환 시간은 110초로 늘어난다.
이 문제점은 호위 효과(convoy effect)라고 칭해지며 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다.
최단 작업 우선 (Shortest Job First, SJF)
이 문제는 간단히 해결할 수 있다.
최단 작업 우선(Shortest Job First, SJF) 스케줄링은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.
동일한 예를 SJF로 스케줄 함으로써 B, C, A 순서로 실행시키고 평균 반환 시간을 110초에서 50초로 2배 이상 향상시켰다. 모든 작업이 동시에 도착한다면 SJF가 최적의 스케줄링 알고리즘임을 증명할 수 있다.
SJF라는 좋은 스케줄링 기법을 개발하였지만, 아직 비현실적인 가정들이 있다. 이제 2번 가정을 완화하여 모든 작업은 동시에 도착하는 것이 아니라 임의의 시간에 도착할 수 있다고 가정한다.
이번에는 동일한 실행 시간을 가지되 A는 0초에, B와 C는 10초에 도착한다고 가정하자.
B와 C가 바로 뒤에 도착한다고 하더라도 A가 끝날 떄까지 기다릴 수 밖에 없어서 호위 효과 문제가 다시 발생한다. 이 경우 평균 반환 시간은 103.33이다.
선점형 스케줄러와 비선점형 스케줄러
선점형 스케줄러는 현재 실행 중인 프로세스를 강제로 중단시키고 다른 프로세스에게 CPU를 할당할 수 있는 방식이다.
- 시분할 시스템에서 주로 사용한다.
- 응답성이 좋고 대화형 시스템에 적합하다.
- 멀티태스킹 환경에서 효율적이다.
- 문맥 교환 비용이 발생한다.
예시로는 Round Robin, Shortest Time-to-Completion First (STCF), Priority Scheduling with preemption 등이 있다.
비선점형 스케줄러는 프로세스가 자발적으로 CPU를 반납할 때까지 기다리는 방식이다.
- 구현이 간단하고 오버헤드가 적다.
- 처리량이 높을 수 있다.
- 응답 시간을 예측하기 어렵다.
- 호위 효과가 발생할 수 있다.
예시로는 First Come First Served (FCFS), Shortest Job First (SJF), Priority Scheduling without preemption 등이 있다.
최소 잔여시간 우선 (Shortest Time-to-Completion First, STCF)
SJF에서 호위 효과 문제를 해결하기 위해 작업은 끝날 때까지 계속 실행된다는 3번 가정을 완화해보자.
SJF에 선점 기능을 추가한 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF) 또는 선점형 최단 작업 우선(PSJF)으로 알려진 스케줄러이다. 언제든 새로운 작업이 시스템에 들어오면, 이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.
평균 반환 시간이 단축되어 50초가 된다. 새로운 가정 하에 STCF가 최적의 스케줄러이다.
새로운 평가 기준 : 응답 시간
작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 매우 훌륭한 정책이다. 초기 일괄처리 컴퓨터 시스템에서는 이러한 스케줄링 알고리즘이 의미가 있었다.
그러나 시분할 컴퓨터의 등장이 모든 것을 바꾸었다. 이제 사용자는 터미널에서 작업하게 되어 시스템에게 상호작용을 원활히 하기 위한 성능을 요구하게 되었다.
응답 시간(response time)이라는 새로운 평가 기준이 태어나게 된다. 응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때 까지의 시간으로 정의된다.
$T_{response} = T_{firstrun} - T_{arrival}$
예를 들어, 도착 시간 A는 0, B와 C는 10이라면, 각 작업의 응답 시간은 A와 B는 0, C는 10, 평균 3,33이 된다.
STCF를 비롯하여 비슷한 류의 정책들은 응답 시간이 좋다고 생각할 수 없기에 이 문제를 해결해야 한다.
라운드 로빈 (Round Robin)
응답 시간 문제를 해결하기 위해 라운드 로빈(Round Robin, RR) 스케줄링 알고리즘을 도입한다.
라운드 로빈은 일정 시간 동안 실행한 휴 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)이라 부른다. 이러한 이유로 RR은 타임 슬라이싱이라고도 불린다.
타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 10msec마다 인터럽트를 발생시킨다면 타임 슬라이스는 10msec의 배수가 될 수 있다.
예시 그림에서 RR의 평균 응답 시간은 1이고, SJF였다면 5이게 된다.
타임 슬라이스의 길이는 RR에서 매우 중요하다. 타임 슬라이스가 너무 짧을수록, 응답 시간 기준으로 RR의 성능은 더 좋아진다. 그러나 타임 슬라이스를 너무 짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다. 시스템 설계자는 시스템이 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 결정해야 한다. 문맥 교환 비용을 상쇄할 수 있을 만큼 길어야 하지만 그렇다고 너무 길어지면 안된다.
문맥 교환 비용에는 레지스터를 저장/복원하는 작업 뿐만 아니라 CPU 캐시, TLB, 분기 예측 등을 비롯하여 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다. 작업이 전환되면 이 정보들은 모두 갱신되어야 한다. 갱신 작업이 매우 큰 성능 비교를 유발한다.
적당한 길이의 응답 시간이 유일한 평가 기준인 경우 RR은 매우 훌륭한 스케줄러이다. 하지만 반환 시간 기준으로는 RR이 최악의 정책임을 알 수 있다. RR은 각 작업을 잠깐 실행하고 다음 작업으로 넘어가고 하면서 가능한 한 각 작업을 늘리는 것이 목표다. 반환 시간은 작업 완료 시간만을 고려하기에 RR은 반환 시간 기준으로 좋은 정책이 될 수 없다.
일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 당연히 나쁘다. 불공정하게 한다면 하나의 작업을 끝까지 실행하고 종료할 수 있지만 나머지 작업들에 대한 응답 시간은 포기해야 한다. 반대로 공정성을 더 중요하게 여긴다면 응답 시간은 줄어들지만 반환 시간은 나빠지게 된다. 이러한 유형의 절충은 시스템에서는 흔히 있는 일이다.
입출력 연산의 고려
이제 작업은 입출력을 하지 않는다라는 4번 가정을 완화해보자.
입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야 한다. 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않은 것이기 때문이다.
입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다. 입출력이 하드 디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 동안 블록될 것이다. 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄 해야 한다.
마찬가지로 스케줄러는 입출력 완료 시에도 의사 결정을 해야 한다. 입출력이 완료되면 인터럽트가 발생하고 운영체제가 실행되어 입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 다시 이동시킨다. 물론, 인터럽트가 발생했을 때 요청 프로세스를 즉시 실행시키기로 결정할 수도 있다. 운영체제는 각 작업을 어떻게 처리해야 하는가?
예시로 두 개의 작업 A와 B가 있다고 하자. 각 작업은 50msec의 CPU 시간을 필요로 하지만, A는 10msec동안 실행된 후, 입출력 요청을 한다. (입출력 시간은 100msec라고 가정한다.) 반면에 B는 입출력을 수행하지 않는다. 스케줄러는 A를 먼저 실행시키고 B를 다음에 실행시킨다.
STCF 스케줄러를 구축하려고 한다고 가정하자. A가 5개의 10msec 작업으로 분할되는 반면에 B는 하나의 50msec의 CPU를 요청한다는 사실을 어떻게 활용할까? 분명 입출력을 고려하지 않고 작업을 하나씩 실행시키는 것은 의미가 없다.
일반적인 접근 방식은 A의 5개의 10msec 작업을 각각 하나의 독립적인 작업으로 취급하는 것이다. 시스템이 시작할 때 5개의 10msec 작업들과 1개의 50msec 작업을 스케줄하는 것이다.
그렇다면 STCF의 경우 스케줄링은 당연히 가장 짧은 작업을 선택하고, A가 선택된다. 그러면 A의 첫 번째 작은 작업이 완료되면 B만 남게 되어 B가 실행을 시작한다. A의 입출력이 끝나면 다음 CPU 작업이 시작할 수 있기에 B를 선점하여 10msec 동안 실행한다.
이렇게 하면 프로세스의 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다.
입출력을 고려한 스케줄러 방법에 대해서 알아보았다. 각 CPU 버스트를 하나의 작업으로 간주함으로써 스케줄러는 대화형 프로세스가 더 자주, 유리하게 실행되는 것을 보장한다. 이러한 대화형 작업이 입출력을 실행하는 동안 다른 CPU-집중 작업들이 실행되고 CPU의 이용률은 더 높아진다.
만병통치약은 없다 (No More Oracle)
각 작업의 실행 시간은 사전에 알려져있다. 라는 5번 가정을 생각해보자. 이 가정은 우리가 할 수 있는 최악의 가정인게, 범용 운영체제에서 작업의 길이에 대해서 알 수 있는 길은 없다. 하지만 가까운 과거를 이용하여 미래를 예측하는 멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)라고 불리는 스케줄러를 다음 장에서 배워보자.
정리
평가 기준
- 반환 시간(turnaround time)
- 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간
- $T_{turnaround} = T_{completion} - T_{arrival}$
- 응답 시간(response time)
- 작업이 도착할 때부터 처음 스케줄 될 때 까지의 시간
- $T_{response} = T_{firstrun} - T_{arrival}$
스케줄링 정책
- 선도착선처리(First Come First Served, FCFS)
- 가장 간단한 스케줄링 알고리즘
- 호위 효과(convoy effect) 문제 발생
- 최단 작업 우선(Shortest Job First, SJF)
- 가장 짧은 실행 시간을 가진 작업을 먼저 실행
- 호위 효과 문제 발생
- 반환 시간은 좋지만 응답 시간은 나쁨
- 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)
- SJF에 선점 기능을 추가한 스케줄러
- 새로운 작업이 들어오면 잔여 실행 시간을 계산하여 가장 짧은 작업을 실행
- 반환 시간은 좋지만 응답 시간은 나쁨
- 라운드 로빈(Round Robin, RR)
- 일정 시간 동안 실행한 후 다음 작업으로 전환
- 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)을 사용하여 실행 시간을 조절
- 응답 시간은 좋지만 반환 시간은 나쁨
참고