[Operating System] – “스케줄링(Scheduling)”
[Operating System] – “스케줄링(Scheduling)”
이 글은 도서 Operating Systems: Three Easy Pieces 를 읽고, 제가 이해한 방식대로 정리한 것임을 밝힙니다.
blog-driven-development 나 blog-driven-learning 은 위험합니다. 저의 글을 끊임없이 의심하고, 검증하고, 혹시라도 틀린 내용이 있거나, 논리적 비약이 있다면 가감없이 알려주시면 감사하겠습니다 :)
워크로드(Workload)
이전 글 을 포함해 지금까지, 우리는 운영체제가 CPU 가상화를 구현하기 위해 사용하는 저수준 기법들(예컨대, context switch) 에 대해서 상세하게 알아보았습니다. 어떻게 운영체제가 통제를 잃지 않으며 프로세스를 실행시킬 수 있는지, 특정 순간에 여러 실행시킬 수 있는 프로세스가 존재할 때 어떻게 현재 실행 중인 프로세스를 중지하고 다른 프로세스를 실행시키는지 등에 대해 말이죠. 저수준 기법에 대해 논의해왔으니, 이번에는 “어떤” 에 관한 것입니다. 특정 순간에 운영체제는 “어떤” 프로세스를 선택해 실행시켜야 할까요? 이를 스케줄링이라고 하는데, 운영체제를 위한 스케줄링 정책은 어떻게 개발해야 할까요?
이를 위해서 몇 가지 가정을 하겠습니다. 프로세스가 수행하는 상황을 워크로드(Workload) 라고 부르기로 약속합시다.
A workload, in the most general sense, is the amount of time and computing resources a system or network takes to complete a task or generate a particular output. It refers to the total system demand of all users and processes at a given moment.
가장 일반적인 의미의 워크로드는 시스템이나 네트워크가 작업을 완료하거나 특정 결과물을 생성하는 데 걸리는 시간과 컴퓨팅 리소스의 양을 말합니다. 이는 특정 시점에 모든 사용자와 프로세스의 총 시스템 수요를 나타냅니다.
그리고, 아래의 몇 가지 가정을 합시다. 우리가 논의할 시스템에서 프로세스나 작업(job) 은 이러한 특징을 가집니다.
- 모든 작업은 같은 시간 동안 실행됩니다.
- 모든 작업은 동시에 도착합니다.
- 모든 작업은 시작되면, 완료될 때까지 실행됩니다.
- 모든 작업은,
CPU만 사용합니다. - 각 작업의 실행 시간은 사전에 알려져 있습니다.
맞습니다, 조금 비현실적이죠? 괜찮습니다. 우리는 차차 이 비현실적인 가정들을 부숴나갈 겁니다.
스케줄링 평가 항목(Scheduling Metric)
우리가 알아볼 스케줄링이라는 것들은 알고리즘으로 구현됩니다. 아시다시피 알고리즘에는 평가 항목이라는 것이 존재합니다. 익숙하실 시간 복잡도, 공간 복잡도와 같은 것들 말이죠. 스케줄링 알고리즘은 어떤 척도로 평가할 수 있고, 어떤 것이 좋은 스케줄링일까요? 먼저 스케줄링 정책들을 비교하기 위해서, 우리는 그들을 비교하는 기준을 세울 필요가 있습니다. 이를 Scheduling Metric 이라고 합니다.
반환 시간(Turnaround Time)
“시스템의 입장에서, 특정 순간에 어떤 작업을 처리해야 하는가?” 는 우리가 글의 처음에서 목도한 핵심 질문이었습니다. 작업이 시스템에 도착할 때의 시각을 Arrival, 작업이 완료한 시각을 Completion 이라고 할 때, “도착한 후 작업이 완료될 때까지 걸린 시간” 을 반환 시간(TurnAround Time, TAT) 라고 합시다. 작업은 빠르게 처리되면 처리될수록 좋으므로, TAT 는 짧을수록 좋겠죠? TAT 는 스케줄링의 성능을 평가하는 데에 중요한 지표가 됩니다.
다음과 같은 식을 통해 반환 시간을 구할 수 있습니다. 간단하죠?Turnaround = Completion - Arrival
공정성(Fairness)
실행할 여러 프로세스가 존재할 때, 그 프로세스들이 얼마나 시스템의 자원을 공평하게 할당받는지에 대한 지표를 공정성(Fairness) 라고 합니다. 예컨대 프로세스 A가 CPU 를 10초 동안 점유하고, 프로세스 B 가 CPU 를 3초 동안 점유한다면, 각각 5초씩 점유하는 것에 비해 공정성이 떨어진다고 할 수 있죠.
대기 시간(Wating Time)
실행될 프로세스는 커널 내부에서 대기 큐라는 자료구조에 쌓이게 됩니다. 대기 큐에 쌓이고, 실제로 CPU 를 점유해 실행되기까지 기다린 시간을 대기 시간(Wating Time, WT) 라고 합니다. 각 작업의 대기 시간이 짧다는 것은 시스템이 그만큼 빠르게 자원을 사용해 응답을 준다는 것이므로, 시스템의 응답성에 영향을 끼치는 지표입니다.
응답 시간(Response Time)
프로세스가 시스템에 도착하고 나서, 맨 처음으로 CPU 를 점유해 작업을 시작할 때까지 기다린 시간을 응답 시간(Response Time) 이라고 합시다. 프로세스 A 가 0에 시스템에 도착하고 처음으로 CPU 를 3 후에 할당받았다면, Response Time 은 3이 됩니다.
처리량(Throughput)
“단위 시간당 시스템이 작업을 얼마나 처리했는가?” 를 평가하는 지표가 바로 처리량(Throughput) 입니다. 예상하셨다시피, 처리량이 높을수록 성능은 좋아질 겁니다. 스케줄링 알고리즘의 효율성을 평가할 수 있는 지표 중 하나입니다.
CPU 활용률(CPU Utilization)
스케줄링의 목적 중 하나는 시스템의 자원을 최대한 효율적으로 사용하는 것입니다. 그런 의미에서, 중요한 자원 중 하나인 CPU 가 쓸데없이 놀고 있는 시간이 있으면 안 되겠죠? 스케줄링이 CPU 를 얼마나 바쁘게 유지하는가를 판단하는 지표를 CPU 활용률(CPU Utilization) 이라고 합니다. 당연히 시스템에 과부하를 주지 않는다는 가정 하에, CPU 는 바쁘면 바쁠수록 성능은 좋아지겠죠?
선입선출(FIFO – First In, First Out)
선입 선출(先入先出, first in, first out, 줄여서 FIFO)은 시간과 우선 순위와 관련된 데이터를 정리하고 이용하는 방식을 줄여 말하는 것이다. 이러한 표현은 선입선처리 행위에 따라 순서대로 처리함으로써 기술을 처리하거나 수요 충돌을 관리하는 대기의 원칙을 말한다. 다시 말해, 먼저 온 것은 먼저 처리되고, 처리가 끝날 때까지 다음 것은 대기 상태에 놓이게 된다.
https://ko.wikipedia.org/wiki/%EC%84%A0%EC%9E%85_%EC%84%A0%EC%B6%9C
선입선출은 그 이름에서 알 수 있듯이 시스템에 먼저 도착한 작업이 먼저 처리되고, 나머지 작업들은 그 작업이 끝날 때까지 대기 상태에 놓이게 되는 스케줄링 방식입니다. 아래처럼 프로세스 A, B, C 의 순서대로(거의 동시에) 도착했을 때, 도착한 순서인 A, B, C 의 순서대로 작업이 처리되는 방식이죠. 우리의 비현실적인 가정에서 모든 작업은 같은 시간 동안 처리된다고 했습니다. 모든 프로세스가 시간 10 동안 처리될 때, FIFO 스케줄링은 아래와 같이 동작할 겁니다.
Arrival: A -> B -> C
Completion: (A:10, B:20, C:30)
0 20 40 60 80 100 120
+---------+---------+---------+
| A | B | C |
+---------+---------+---------+---------+---------+---------+
A 는 10에, B 는 20에, C 는 30에 완료되었습니다. 알아봤던 첫 번째 평가 항목인 반환 시간을 알아보면, 모든 프로세스는 거의 동시에 도착하였고(Arrival=10) 각각 반환 시간이 10, 20, 30 이므로 평균 반환 시간은 20이 될 겁니다.
하지만 우리의 비현실적인 가정 과 달리 현실 세계는 고통의 연속입니다. 도대체가 어떻게 되어먹은 것인지는 몰라도 내 생각과는 정반대로 흘러가는 일이 다반수죠. 프로세스도 마찬가지입니다. 프로세스의 실행 시간은 모두 각각 다릅니다. 예를 들면, 프로세스 A 가 완료되기까지 30이라는 시간을 필요로 한다면 어떨까요?
Arrival: A -> B -> C
Completion: (A:100, B:110, C:120)
0 20 40 60 80 100 120
+---------+---------+---------+---------+---------+---------+
| A | B | C |
+---------+---------+---------+---------+---------+---------+
이 경우 평균 반환 시간은 (100 + 110 + 120) / 3 = 110 이 될 겁니다. 위의 상황에선 어떻죠? 내가 살 건 단지 운동 전 도핑하기 위한 에너지 음료 하나일 뿐인데 내 앞에 다른 고객이 좀비 사태를 대비해 반년치 식량과 물품을 구매하는 상황입니다. 이처럼, B, C 와 같이 짧은 시간 동안 자원을 사용할 프로세스들이 A 와 같은 프로세스의 종료를 기다리는 상황을 Convoy Effect 라고 합니다. B 와 C 같이, 구매하고자 하는 항목이 적은 고객들을 배려할 수 있는 스케줄링이 있을까요?
최단 작업 우선(SFS - Shortest Job First)
그러면 반년치 물건들을 구매할 A 라는 고객을 뒤로 서게 한 다음, B, C 처럼 빨리빨리 구매를 처리할 수 있는 고객들부터 구매를 처리토록 합시다. 이처럼, 가장 짧은 작업시간을 가진 작업들을 먼저 실행시키는 스케줄링 방식을 최단 작업 우선(Shortest Job First) 방식이라고 합니다.
Arrival: A -> B -> C
Completion: (A:10, B:20, C:120)
0 20 40 60 80 100 120
+---------+---------+---------+---------+---------+---------+
| B | C | A |
+---------+---------+---------+---------+---------+---------+
최단작업 우선 스케줄링 방식을 적용하면, 평균 반환 시간은 50 이 됩니다. FIFO 방식에 비하면, 엄청난 성능 향상이죠. 모든 작업이 동시에 도착한다는 우리의 비현실적인 가정 하에, SJF 스케줄링은 최적의 스케줄링 방식입니다.
안타깝게도, 우리의 비현실적인 가정은 현실이라는 선명한 시련의 연속체 앞에서 처참하게 깨집니다. 실제 시스템에서 모든 작업의 도착 시각은 동일하지 않죠. 예컨대 A 는 0 에 도착하고, B, C 는 각각 10에 도착할 수도 있는 노릇입니다. 이 상황에서, SJF 스케줄을 적용하면 어떻게 될까요?
Arrival: A -> B -> C
Completion: (A:100, B:100, C:110)
0 20 40 60 80 100 120
+---------+---------+---------+---------+---------+---------+
| A | B | C |
+---------+---------+---------+---------+---------+---------+
ㄴ> B, C 도착
A 가 먼저 도착하는 이상, B, C 는 A 가 끝날 때까지 기다릴 수밖에 없습니다. 평균 반환 시간은 103.33 으로, “도착 시간이 동일하다는 가정” 만 부쉈을 뿐인데 성능이 다시 안 좋아져 버리죠. 이 문제를 해결합시다.
최소 잔여시간 우선(STCF - Shortest Time-to-Completion First)
“작업이 한 번 시작하면 끝날 때까지 실행된다” 라는 우리의 비현실적인 가정 때문에, 프로세스 A 는 한번 실행되고 나서 100이라는 너무나도 긴 시간 동안 CPU 를 점유할 수밖에 없습니다. 이처럼, 각 작업이 종료될 때까지 계속 실행되는 방식을 비선점(non-preemitive) 스케줄러라고 합니다.
맞아요, 우리가 글의 처음에서 했던 비현실적인 가정, “모든 작업은 시작되면, 완료될 때까지 실행됩니다.” 는 비선점형 스케줄러의 동작을 위해 했던 것입니다. 현대의 스케줄러는 모두 선점형(preemitive) 스케줄러이고, 이들은 우리가 이전 글들에서 배웠던 운영체제가 사용하는 저수준 기법들, 예컨대 문맥 교환과 같은 것들을 사용해 현재 실행 중인 프로세스를 종료하고, 다른 프로세스를 새로 시작하거나 재개할 수 있습니다.
네, “모든 작업은 시작되면, 완료될 때까지 실행됩니다.” 라는 비현실적인 가정을 깨 버립시다. 그러면, 이렇게 되면 어떨까요? 시각 10에 B, C 가 도착하기 전까지 A 를 실행시키고, B, C 가 10밖에 안 걸리는 짧은 작업 시간을 가지므로 A 를 잠시 중단시키고 B, C 를 완료시켜 버리는 거죠. 아래처럼요:
Arrival: A -> B -> C
Completion: (A:120, B:10, C:20)
0 20 40 60 80 100 120
+---------+---------+---------+---------+---------+---------+
| A | B | C | A |
+---------+---------+---------+---------+---------+---------+
ㄴ> B, C 도착
이 경우, 평균 반환 시간은 50이 됩니다. “모든 작업은 시작되면, 잠시 중지되고 다른 작업이 실행될 수 있습니다.” 라는 새로운 가정을 붙인다면, 최소 잔여시간 우선(Shortest Time-to-Completion First) 스케줄링은 최적의 방식이 됩니다.
라운드 로빈(RR - Round-Robin)
현대의 시분할 시스템에서는, 수행해야 할 작업이 프로세스에 도착하고 나서 처음으로 CPU 를 점유하는 시간 또한 중요하게 되었습니다. 평균 반환 시간은 중요하지만, 시스템의 응답성도 중요해진 거죠. 우리는 이것을 평가하기 위한 지표가 응답 시간(Response Time)임을 알고 있습니다.
이제 우리가 마주하게 된 문제는 다음과 같습니다. “응답 시간에 민감한 스케줄러를 어떻게 작성할 수 있을까요?”
라운드 로빈(Round Robin) 스케줄링의 아이디어는 작업이 끝날 때까지 기다리지 않고, 일정 시간이 끝난 후 다른 작업으로 전환하는 것입니다. 작업이 실행되는 일정 시간을 time slice 혹은 scheduling quantum 이라고 부릅니다.
Arrival: A -> B -> C
Completion: (A:10, B:10, C:20)
0 20 40 60 80 100 120
+---------+---------+---------+---------+---------+---------+
| A | B | C | A | B | C | A | B | C | A | B | C |
+---------+---------+---------+---------+---------+---------+
| | -> time slice그러면 이 time slice 의 길이를 어떻게 지정하는 것이 좋을까요? 당연히 time slice 의 길이가 짧을수록, 시스템의 응답 시간은 좋아질 것입니다. 하지만 time slice 를 너무 짧게 지정하면 이를 수행하는 데 필요한 context switch 의 비용이 너무나 커져 버리고, 이는 시스템의 성능에 큰 영향을 끼치게 됩니다. 다시 말해, 우리는 시스템의 성능도 응답성도 놓지 않은 채로, 최적의 상태로 동작할 수 있도록 time slice 의 길이를 결정해야 한다는 겁니다.
반환 시간, 그러니까 어떤 작업이 도착한 시간에서 작업이 완료되기까지의 시간으로 평가한다면, 라운드 로빈 스케줄러는 최악의 선택이 될 겁니다. 어떤 작업을 완료하지 않고 쪼개고 쪼개 가능한 많은 작업을 실행시키는 것이 목표이기 때문이죠. 이와 같이 주로 자원을 공정하게 사용하는 스케줄러는 성능이 나쁩니다. 우리는 여기서 절충안을 선택해야 합니다.
SJF, STCF-> 반환 시간을 최적화하지만, 응답 시간은 나쁩니다.RR-> 응답 시간을 최적화하지만, 반환 시간은 나쁩니다.
이쯤에서 우리가 위에서 했던 비현실적인 가정 중 하나를 다시 살펴봅시다: “모든 작업은, CPU 만 사용합니다.” 말예요. 모든 프로그램은 입출력 작업을 수행합니다. 입력을 받아야 알고리즘에 의해 다른 출력들을 생성해 내겠죠. 입력도 받지 않고, 출력도 하지 않는 프로그램이 실행된다 한들 어떤 의미가 있겠습니까?
어떤 프로세스의 입출력 작업이 수행될 때, 프로세스는 그 시간 동안 CPU 가 할당되어도 사용할 수 없는 상태인 대기 (Blocked) 상태가 됩니다. 자원을 효율적으로 사용할 책임이 있는 스케줄러는, 그 시간 동안 다른 작업들을 할당해줘야 합니다. 이는 입출력이 완료된 이후에도 마찬가지죠. 입출력이 완료되면, 프로세스는 CPU 가 할당되면 사용할 수 있는 Ready 상태로 전이되고, 스케줄러는 이 상황에서도 작업을 어떻게 수행할지 결정해야 합니다. CPU 를 최대한 효율적으로, 활용해야 합니다.
- Process A: 50ms CPU 시간 필요, 각 CPU 10ms 이후 I/O 작업 수행 필요
- Process B: 50ms CPU 시간 필요, I/O 작업을 수행하지 않음
0 20 40 60 80 100 120 140
+---------+---------+---------+---------+---------+---------+---------+
CPU | AA | | AA | | AA | | AA | | AA | BB | BB | BB | BB | BB |
+---------+---------+---------+---------+---------+---------+---------+
Disk | | AA | | AA | | AA | | AA | | | | | | |
+---------+---------+---------+---------+---------+---------+---------+
예를 들면, 위처럼 A 를 실행시키고 B 를 실행시키는 식으로 스케줄링을 하는 것은 자원을 비효율적으로 활용한 것입니다. 분명히 CPU 는 A 프로세스가 디스크 입출력 작업을 수행하고 있을 때 놀고 있습니다.
만약 STCF 작업을 수행한다면 – 최소 잔여시간 스케줄링을 적용한다면, 어쩌면 우리는 이 문제를 해결할 수 있을지도 모릅니다. 프로세스 A 가 10ms 의 CPU 시간 이후 10ms 의 I/O 작업을 수행한다는 것을 알고 있다면, 10ms 의 CPU 시간을 하나의 작업으로 처리하는 것입니다. 아래처럼 말이죠!
- Process A: 50ms CPU 시간 필요, 각 CPU 10ms 이후 I/O 작업 수행 필요
- Process B: 50ms CPU 시간 필요, I/O 작업을 수행하지 않음
0 20 40 60 80 100 120 140
+---------+---------+---------+---------+---------+---------+---------+
CPU | AA | BB | AA | BB | AA | BB | AA | BB | AA | BB | | | | |
+---------+---------+---------+---------+---------+---------+---------+
Disk | | AA | | AA | | AA | | AA | | | | | | |
+---------+---------+---------+---------+---------+---------+---------+
각 CPU 가 실행되는 시간을 하나의 작업으로 간주하므로서, 스케줄러는 응답 시간이 중요한 대화형 프로세스가 유리하게 실행되는 것을 보장할 수 있게 됩니다. 입출력이 실행되는 동안, CPU-Bound 작업들을 잘 처리할 수 있는 것이죠.
요약
이번 포스팅에서 우리는 몇 가지 스케줄링 접근 방식에 대해 알아보았습니다.
- 남아있는 작업 중 실행 시간이 제일 짧은 작업을 수행함으로서 반환 시간을 최소화하는 방법(
STCF) - 모든 작업을 번갈아 실행시키고 응답 시간을 최소화하는 방법(
RR)
위의 글을 읽으셨다면 아시겠다시피, “반환 시간을 최소화하기” 와 “응답 시간을 최소화하기” 는 시소와 같이 하나를 최적화하면 하나가 나빠지는 문제가 발생합니다. 은탄환은 없다는 말과 같이, 우리는 둘의 장단점간에서 절충안을 찾아야 한다는 것입니다.
글의 마무리에 이르렀지만, 우리는 어쩌면 가장 비현실적인 가정인 “각 작업의 실행 시간은 사전에 알려져 있습니다.” 를 깨부수지 않았습니다. 스케줄러는 어떻게 미래를 예측하여 문제를 해결할 수 있을까요? 다음 글에서, 우리는 그 방법에 대해 알아볼 것입니다.