몇 가지 가정
프로세스가 동작하는 일련의 행위를 워크로드 (workload) 라고 한다. 프로세스 스케쥴링을 이해하기 위해, 먼저 현실과는 동떨어진 워크로드를 가정하고 해당 가정들을 하나하나 제거할 수 있는 스케쥴링 정책들을 알아볼 것이다.
- 모든 작업은 같은 시간 동안 실행 된다.
- 모든 작업은 동시에 도착한다.
- 작업은 일단 시작하면 최종적으로 종료될 때 까지 실행된다.
- 모든 작업은 CPU만 사용하며, 입출력을 수행하지 않는다.
- 각 작업의 실행 시간은 사전에 알려져 있다.
평가 항목
스케쥴링 정책의 평가를 위해서는 스케쥴링 평가 항목 (scheduling metric)을 결정해야 한다. 책에서 언급한 몇가지 대표적인 평가 항목에 대해서 알아보자. 각 항목들은 성능 측면 혹은 공정성 측면에서 스케쥴링 정책을 평가한다.
반환 시간
반환 시간 (turnaround time)은 작업이 완료된 시간에서 작업이 도착한 시간을 뺀 시간이다. 즉, 어떤 프로세스가 완료될 때 까지 걸린 시간이라고 이해하면 된다. 철저히 성능 측면에서 평가하는 지표이다.
응답 시간
응답 시간 (response time)은 작업이 처음 실행되는 시간에서 작업이 도착한 시간을 뺀 시간이다. 예를 들어 1번 프로세스가 2초에 도착하여 대기 후 6초에 처음으로 실행 되었다면 응답 시간은 4초가 된다. 시스템이 얼마나 상호작용을 잘 하는가를 평가하는 지표라고 할 수 있겠다.
공정성
공정성 (fairness)은 여러 개의 작업들의 완료 시간이 얼마나 비슷한지 비교하는 지표이다. 예를 들어 1번 프로세스는 1초만에 완료되었는데 2번 프로세스는 10초만에 완료되었다면, 이는 공정성이 좋지 못한 스케쥴러라고 할 수 있다. 성능과 공정성은 서로 상충하는 지표이다. 전체 시스템의 성능을 극대화 하기 위해 몇몇 작업들에 대해서 기회를 주지 않는다면 이는 공정성이 악화되는 것이다.
선입선출 알고리즘
가장 기본적인 알고리즘으로, 선입선출 (First In First Out) 혹은 선도착선처리 (First Come First Served, FCFS) 스케쥴링 이라고 부른다. 자료구조 Queue와 같은 원리로 동작한다.
예를 들어서 세 개의 작업 A,B,C가 거의 동시에, 그러나 알파벳 순서대로 도착했다고 가정하자. 각 작업은 10초동안 실행된다. FCFS 알고리즘으로 해당 작업들을 스케쥴링하면 위와 같은 그림처럼 실행된다. 가장 먼저 도착한 A가 10초동안 실행되고 종료, 그다음이 B로 10초동안 실행되고 종료, 그리고 마지막으로 C가 10초동안 실행되고 종료된다. 이제 각 작업에 대하여 반환 시간과 응답 시간을 계산해 보자.
- A는 0초에 도착해서 10초에 완료되었다. 그러므로 반환 시간은 10초, 응답 시간은 0초이다.
- B는 0초에 도착해서 10초에 시작되었으며, 20초에 완료되었다. 그러므로 반환 시간은 20초, 응답 시간은 10초이다.
- C는 0초에 도착해서 20초에 시작되었으며, 30초에 완료되었다. 그러므로 반환 시간은 30초, 응답 시간은 20초이다.
- 평균 반환 시간은 20초이고, 평균 응답 시간은 10초이다.
FCFS 알고리즘으로 계산한 결과를 보니 꽤 나쁘지 않아 보인다. 흠… 이제 제일 처음 가정하였던 작업 실행 시간에 대한 부분을 제거해서 문제점을 알아보자.
위의 예시는 앞선 예시와 대부분의 조건이 동일하나, 작업 A가 100초동안 실행되는 것만 다르다. 모든 작업이 같은 시간동안 실행된다는 가정을 제거한 것이다. 이때 앞선 예시처럼 각 작업에 대해 반환 시간과 응답 시간을 구해 보자.
- A는 0초에 도착해서 100초에 완료되었다. 그러므로 반환 시간은 100초, 응답 시간은 0초이다.
- B는 0초에 도착해서 100초에 시작되었으며, 110초에 완료되었다. 그러므로 반환 시간은 110초, 응답 시간은 100초이다.
- C는 0초에 도착해서 110초에 시작되었으며, 120초에 완료되었다. 그러므로 반환 시간은 120초, 응답 시간은 110초이다.
- 평균 반환 시간은 110초이고, 평균 응답 시간은 70초이다.
이제 FCFS 알고리즘의 단점이 명확하게 보인다. 위의 예시처럼 시간이 많이 필요한 작업이 먼저 수행되면, 빨리 끝날 수 있었던 작업들이 한없이 기다린다. 그래서 결과적으로 평균 반환 시간이 심각한 수준으로 증가한다. 이러한 현상을 convoy effect라고 한다. 유튜브에서 해당 현상을 설명한 영상을 보았는데, 일명 똥차 효과라고 하더라. 똥차가 앞에서 길막고 있으면 뒤에 아무리 슈퍼카가 있어도 못지나간다는..ㅋㅋㅋ 대형마트에서도 이런 현상이 벌어진다. 나는 생수 한병 살려고 하는데 내 앞에 한 3일치 식량을 사는 분이 계시다면 ㅠㅠ 한병은 금방 계산해서 나갈 수 있는건데 계속 기다려야 하기에 효율성에서 문제가 생기겠지?
최단 우선 작업 알고리즘
최단 우선 작업 (Shortest Job First, SJF) 알고리즘은 위 convoy effect를 간단하게 해결하는 알고리즘이다. 이름을 보고 바로 동작 원리를 이해할 수 있는데, 가장 짧은 실행 시간을 가진 작업을 먼저 실행시키는 것이다. 위의 convoy effect가 발생한 예시를 해당 알고리즘으로 다시 돌려보자.
SJF 알고리즘은 위와 같이 실행 시간이 짧은 작업 B와 C를 먼저 실행시킨 후, 실행 시간이 긴 작업 A를 실행한다. 각 작업의 반환 시간과 응답 시간을 구한 후 평균을 구해보면, 평균 반환 시간은 50초, 평균 응답 시간은 10초이다. 똑같은 상황에서 월등한 성능 향상을 보이고 있다..!!
모든 작업이 동시에 도착한다면, SJF는 최적의 스케쥴링 알고리즘이다. 하지만 해당 가정은 우리가 위에서 두번째로 가정한 워크로드로, 매우 비현실적이다. 이를 제거해 보면 SJF의 단점이 바로 보인다. 위의 예시와 동일한데 작업 A가 작업 B, C보다 일찍 도착했다고 가정해 보자. 작업 B와 C가 도착하였을 때는 이미 작업 A가 cpu를 점유하고 있다. 작업 A는 완료될 때 까지 수행되므로 B와 C는 SJF 알고리즘을 적용하였음에도 계속 기다려야한다. 앞의 FCFS 알고리즘처럼 convoy effect가 다시 발생하는 것이다.
FCFS 알고리즘과 SJF 알고리즘 모두 비 선점형 (non-preemptive) 스케쥴러에 해당한다. 이 시스템은 각 작업이 종료될 때 까지 계속 실행한다. 문맥 교환을 할 수 없는 것이다. 실행 중인 프로세스를 잠시 중단하고 다른 프로세스를 시작할 수 있는 선점형 (preemptive) 스케쥴러를 사용해야 위 문제를 해결할 수 있다.
최소 잔여시간 우선 알고리즘
이제 3번째 가정 이었던 “작업은 끝날 때 까지 계속 실행된다” 를 제거해 보자. 최소 잔여시간 우선 (Shortest Time-to-Completion First, STCF) 알고리즘은 새로운 작업이 도착할 경우, 현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 가장 작은 작업을 스케쥴링하는 비 선점형 방식이다.
위 예시처럼 긴 실행 시간을 가진 작업 A가 먼저 도착해서 10초간 실행이 되었다. 이후 실행 시간이 짧은 작업 B와 C가 도착하니, STCF 알고리즘에 의해 잔여시간이 긴 작업 A를 중단하고, 잔여시간이 짧은 작업 B가 실행 되었다. 마찬가지로 잔여시간이 짧은 작업 C가 실행된 후, 작업 A가 남은 90초간 실행된다. 평균을 구해보면, 평균 반환 시간은 50초로 SJF와 동일한 성능을 보이면서 평균 응답 시간은 무려 3.3초로 짧아졌음을 확인할 수 있다.
지금까지는 주로 반환 시간을 줄이기 위한, 즉 성능 향상을 위한 알고리즘을 소개했다. 하지만 응답 시간 또한 매우 중요한 기준으로, 스케쥴러의 효율을 판단한다. 효율을 향상시킬 수 있는 알고리즘은 어떤 것이 있을까?
라운드 로빈
응답 시간 (response time)은 시스템에게 상호 작용을 원할히 하기 위한 성능을 측정하는 지표이다. 여러 가지를 보완한 STCF 알고리즘도 응답 시간 측면에서는 좋지 않다. 예를 들어 작업 3개가 동시에 도착한 경우, 세 번째 작업은 앞의 첫 번째와 두 번째 작업이 종료된 이후에야 비로소 cpu를 점유할 것이다. 응답 시간이 뒤로 갈수록 처참해진다.
해당 문제를 해결하기 위해 라운드 로빈 (Round-Robin, RR)이라는 알고리즘이 도입되었다. RR 알고리즘은 어떤 작업이 끝날 때까지 기다리는 것이 아니라 정해진 시간 (time slice)만큼만 수행한다. 해당 타임 슬라이스만큼 시간이 지나면, 스케쥴러는 수행하고 있던 작업을 멈추고 다른 작업을 가져온다.
위 그림은 타임 슬라이스가 1초로 설정된 RR 알고리즘 스케쥴러이다. 각 작업은 0초에 동시에 도착하였고, 실행 시간은 5초로 동일하다. 이전의 알고리즘들과는 달리 작업 A,B,C가 번갈아가면서 실행됨을 확인할 수 있다. 평균 응답 시간을 구해보면 1초로, 동일한 조건에서의 SJF 스케쥴러의 평균 응답 시간이 5초인 것과 비교하면 매우 상호 작용이 원할하게 이루어졌음을 알 수 있다.
응답 시간을 더욱 줄이려면 어떻게 해야할까? 타임 슬라이스를 1초가 아니라 0.01초로 줄이면 된다. 그렇다면 마냥 줄이기만 하면 좋은걸까? 그렇지는 않다. 타임 슬라이스가 작아진다는 것은 그만큼 문맥 교환이 자주 발생한다는 뜻이다. 문맥 교환 시 들어가는 비용은 생각보다 크다. 시스템의 오버헤드가 발생하지 않도록 타임 슬라이스의 크기를 적절하게 정하는 것이 중요하다.
RR은 평균 반환 시간의 기준으로 평가하면 최악의 알고리즘이다. 반환 시간이 짧아질 수 있음에도 불구하고 문맥 교환을 통해 작업을 번갈아가면서 수행하는 알고리즘이기에 이런 결과는 당연하다. 일반적으로 RR과 같은 공정한 정책은 반환 시간과 같은 지표와는 서로 상충하고 있음을 알 수 있다.
입출력 연산의 고려
이번에는 네 번째 가정이었던 “모든 작업은 CPU만 사용하며, 입출력을 수행하지 않는다” 을 제거해 보자. 입출력 (I/O) 작업은 cpu를 사용하지 않는다. 그래서 입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다. 그러면 스케쥴러는 다른 작업을 할당해야한다. 마찬가지로 입출력이 종료되었을 때도 해당 작업을 언제 다시 진행할지 스케쥴링이 필요하다.
위 그림은 작업 A 수행 중에 disk에 입출력 요청이 10초마다 들어올 때의 작업 스케쥴링을 보여준다. 만약 스케쥴러가 입출력 요청이 들어온 10초 동안 다른 작업을 할당하지 않으면, 위의 그림처럼 cpu가 놀게 된다. 이런 상태를 busy waiting이라고 한다.
하지만 A 작업에서 입출력 요청을 수행하는 동안 사이사이에 작업 B를 수행한다면 어떨까? busy waiting이 발생하지 않고 훨씬 빠르고 효율적으로 작업을 수행할 수 있다. A 작업을 입출력 연산을 고려하여 작은 작업 5개로 나누어서 스케쥴링하면, 위와 같이 연산을 중첩시켜 시스템 사용율을 향상시킬 수 있다.
만병 통치약은 없다!!
지금까지 알아본 스케쥴러는 크게 두가지 이다. 첫번째는 남아있는 작업 중 실행 시간이 제일 짧은 작업을 수행하여 평균 반환 시간을 최소화 하는 방법이고, 두번째는 모든 작업을 번갈아 실행시켜 평균 응답 시간을 최소화 하는 방법이다. 반환 시간과 응답 시간 중 하나를 최적화 하면 나머지 하나는 좋지 않다.. 이를 적당히 절충하는 방식의 스케쥴러를 우리는 현재 사용하고 있다.