들어가며#

컴퓨터의 자원은 한정되어 있고, 여러 프로세스가 동시에 실행되는 환경에서 효율적으로 자원이 분배되어야 한다. 이 글에서는 프로세스 스케줄링의 기본 개념부터, 다양한 스케줄링 알고리즘에 대해 살펴보려 한다. 또한, 스케줄링 알고리즘을 평가하는 다양한 기분들도 살펴볼 예정이다. 그리고 가장 적합한 스케줄링 알고리즘이 무엇인지도 알아보자.

워크로드에 대한 가정#

프로세스가 동작하는 일련의 행위를 워크로드(workload)라 한다. 적절한 워크로드의 선정은 스케줄링 정책 개발에 매우 중요한 부분이다. 워크로드에 대한 이해도가 높을 수록, 그에 최적화된 스케줄링 정책을 정교하게 개발할 수 있다.

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

워크로드 가정

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

비현실적이지만, 매우 이상적인 가정이다. 예를 들어, 각 작업의 실행 시간을 미리 알 수 있다는 건 말이 안되지만, 스케줄링을 이해하기 위한 것이므로 일단 넘어가자.

스케줄링의 평가 항목#

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

반환 시간(turnaround time)#

반환 시간은 작업이 완료된 시각에서 작업이 도착한 시간을 뺀 시간이다.

$T_{turnaround} = T_{completion} - T_{arrival}$

2번 가정에 모든 작업은 동시에 도착한다고 가정했기 때문에 $T_{arrival} = 0$으로 생각할 수 있다. 그렇다면 $T_{turnaround} = T_{completion}$인데, 좀 비현실적이지만 가정은 완화해 갈 것이다.

공평성(fairness)#

Jain’s Fairness Index 라는 지표가 공정성 예의 한 예이다.

성능과 공정성은 스케줄링에서는 서로 상충된다. 예를 들어, 스케줄러는 전체 시스템의 성능을 극대화하기 위해 몇몇 작업들에 대해 실행기회를 주지 않을 수 있다. 결과적으로 공정성이 약화된다.

평가기준들에 대해 알아보았으니, 이제부터 기본적인 알고리즘부터 하나씩 알아보자.

선입선출(FIFO)#

가장 기본적인 알고리즘은 FIFO, 혹은 FCFS라고 불리는 스케줄링이다. 말 그대로 먼저 도착한 프로세스를 먼저 실행시키고, 완료가 되면 다음 프로세스를 실행시키는 알고리즘이라고 생각하면 된다. 그러면 이제 프로세스가 3개가 순차적으로 도착하였다고 가정해보자.(베이지, 하늘색, 초록색 순서대로 들어왔다고 하자.)

그러면 위 그림과 같이 실행될 것이다. 위에서 베이지 색은 10, 하늘색은 20, 초록색은 30에 종료한 것을 알 수 있다. 이제 위에서 알아보았던 평가항목중 반환 시간의 평균을 계산해보자.

평균 반환 시간(Average turnaround time)#

${(10 + 20 + 30) \over 3 } = 20$

위와 같은 수식으로 20이라는 결과값이 나온 것을 알 수 있다.

FCFS(FIFO)가 그렇게 좋은 스케줄링이 아닌 이유#

앞서 말한 가정중 1번 가정을 하나 지워보겠다.

워크로드 가정

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

이제는 작업시간이 모두 같지 않다. 극단적인 경우에 다음과 같이 나올 수도 있다.

이제는 베이지색이 100초, 하늘색과 초록색은 10초동안 실행된다.

극단적인 경우, 평균 반환 시간(average turn arround time)#

${(100 + 110 + 120) \over 3} = 110$
전과 달리, 평균 반환 시간은 110초로 늘어난다. 이런 경우를 convoy effect라고 부른다. convoy effect는 CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상을 말한다.

최단 작업 우선(Shortest Job First, SJF)#

앞서 말한 convoy effect 문제는 간단히 해결할 수 있다. 기본 아이디어는 오퍼레니션 리서치 분야에서 개발되었다. 이 스케줄링 개념의 이름은 최단작업 우선(SJF)이다.

SJF에서는 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

SJF 평균 반환 시간#

${(10 + 20 + 120) \over 3} = 50$

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

SJF의 문제#

이번에는 앞서 말한 가정중 2번을 지워보겠다.

워크로드 가정

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

그러면 다음과 같은 문제가 생긴다.

위 그림같은 경우에는 B와 C가 도착한다고 하더라도 A가 끝날 때까지 기다릴 수 밖에 없다. 그래서 이전의 convoy 문제가 다시 발생한다.

이 경우 평균 반환 시간#

${(100 + (110 - 10) + (120 - 10)) \over 3} = 103.33$

최소 잔여 시간 우선(Shortest Time-to-Completion First, STCF)#

위 문제를 해결하기 위해서 이번에는 3번 가정을 지우겠다.

워크로드 가정

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

이제부터는 작업이 실행 도중에 중단될 수 있다. 이제는 타이머 인터럽트가 발생하고, context switching이 가능하다. 앞서 다룬 SJF는 비선점형 스케줄러이기 때문에, 실행중인 작업을 중지하고 다른 작업을 실행하지 못한다.

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

### STCF 평균 반환 시간

${((120 - 0) + (20 - 10) + (30 - 10)) \over 3} = 50$

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

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 매우 훌륭한 정책이다. 초기 일괄처리 컴퓨터 시스템에서는 이런 스케줄링 알고리즘이 의미가 있었다. 그러나 시분할 컴퓨터가 등장하면서부터 모든 것을 바꾸었다. 이제는 사용자가 터미널에서 작업하게 되어 시스템에게 상호작용을 원활히 하기 위한 성능을 요구하게 되었다. 이에 따라 응답시간(response time)이라는 새로운 평가 기준이 등장하게 된다.

응답 시간(response time)#

$T_{response} = T_{firstrun} - T_{arrival}$
응답 시간은 작업이 도착하는 시점부터 처음으로 스케줄 될 때까지의 시간으로 정의된다.

STCF의 응답 시간#

${(0 + 0 + 10) \over 3} = 3.33$

간단하게 생각해보자. 당신이 터미널 앞에 앉아 입력한 후, 단지 다른 작업이 당신의 작업보다 먼저 스케줄되었다는 이유로 요청후 답이 올때까지 10초를 기다린다고 생각해보자. 그렇게 좋지는 않다.

라운드 로빈(Round Robin)#

이제 응답 시간 문제를 해결하기 위해 라운드 로빈(Round-Robin, RR) 스케줄링이라고 불리는 스케줄링 알고리즘이 도입된다. 라운드 로빈은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 기간동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice)또는 스케줄링 퀀텀(scheduling quantum)이라 부른다.

이러한 이유로 RR은 타임 슬라이싱이라고 부른다. 타임 슬라이싱의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 10msec 마다 인터럽트를 발생시키면, 타임 슬라이스는 10의 배수가 될 수 있다. 다음과 같은 예시를 보자. A, B, C가 각각 10초씩 실행된다고 가정하고 라운드 로빈을 실행하면 다음과 같이 나온다.

RR의 평균 응답 시간#

${(0 + 2 + 4) \over 3} = 2$

적당한 길이의 응답 시간이 유일한 평가 기준인 경우, 타임 슬라이스를 가진 RR은 매우 훌륭한 스케줄러이다. 하지만 반환 시간이 유일한 측정 기준인 경우 RR은 확실히 최악의 정책이다.

RR의 평균 반환 시간#

${(26 + 28 + 30) \over 3} = 28$

셋 다 늦게 끝나기 때문에 반환시간은 최악이다. 이제 가정4를 없애보자.

입출력 연산 고려#

워크로드 가정

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

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

예를 들어 위 그림처럼 두개의 작업이 있다고 하자. 각 작업은 50msec의 CPU 시간을 필요로 한다. 그런데 위 사진중 첫번째처럼 실행하게 되면 비효율적이다.

그래서 I/O 작업을 하는 도중, 사이에 파란색 작업을 실행시킨다.

만병 통치약은 없다(No More Oracle)#

이제 마지막 가정이 남았다. 이 가정은 가장 비현실적이다. 어떻게 작업의 길이를 미리 알 수 있을까. 아무런 사전 지식 없이 SJF/STCF 처럼 행동하는 알고리즘을 짤 수 있을까?

이 문제를 해결하기 위해서는 멀티 레벨 피드백 큐(multi-level feedback queue)를 통해 문제를 해결한다.

기존 문제들#

기존에 우리가 배운 스케줄링 알고리즘에는 아래 3가지를 모두 만족하는 스케줄러가 없었다.

• 상호작용 작업에 대한 응답 시간을 최소화한다.
• 반환시간을 최소화한다.
• 작업 길이에 대한 사전 지식 없이 수행 가능하다.

하지만, 이 3가지를 동시에 만족하는 스케줄러가 있다. 바로 MLFQ이다.

Multi-Level Feedback Queue(MLFQ)#

MLFQ의 주요 특징#

• 여러 개의 우선순위 큐를 사용
• 프로세스의 행동에 따라 우선순위 동적 조정
• CPU 집중 프로세스와 I/O 집중 프로세스를 효과적으로 구분
• 응답 시간과 처리량 사이의 균형 유지

기본 규칙#

MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다. 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다. MLFQ는 실행할 프로세스를 결정하기 위해서 우선순위를 사용한다. 높은 우선순위를 가진 작업이, 즉 높은 우선순위 큐에 존재하는 작업이 선택된다.

큐에 둘 이상의 작업이 존재할 수 있다. 이들은 모두 같은 우선순위를 가지고, 이 작업들 사이에서는 Round Robin 스케줄링 알고리즘이 사용된다. MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. MLFQ는 각 작업에 고정된 우선순위를 부여하는 게 아니라, 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.

MLFQ의 두 가지 기본 규칙은 다음과 같다.

MLFQ 기본 규칙

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.

그리고, MLFQ가 작업의 우선순위를 어떻게 바꿀 것인지 결정해야 한다. 작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지다. 이제는 우선순위를 결정하기 위해 워크로드의 특성을 반영해야 한다. 그래서 다음과 같은 기본 규칙을 추가해보자.

MLFQ 기본 규칙

3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

현재 MLFQ의 문제점#

Starvation#

시스템에 많은 상호 작업(interactive jobs)이 존재한다면 그들이 모든 CPU 시간을 소모하게 될 것이고, 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.

Gaming the scheduler#

똑똑한 사용자라면 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다. 만약 타임 슬라이스(time slice)가 끝나기 전에 I/O 작업을 요청하는 경우, 우선순위가 낮아지지 않는다. 예를들어, 타임 슬라이스의 99%를 실행하고 CPU를 양도하게 되면 CPU를 거의 독점할 수 있다.

Priority Boost: 해결책1#

위 문제들을 해결할 수 있는 간단한 해결책 하나는 Priority Boost이다. 장시간 대기하여 starvation 상태에 빠진 작업들을 위해 주기적으로 모든 작업의 우선순위를 최상위로 끌어올린다. 새로운 6번 규칙으로 적합하다.

MLFQ 기본 규칙

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
5. b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
6. 일정 주기 S 이후, 모든 작업들을 시스템의 최상위 큐에 이동시킨다.

Priority Boost는 두가지 문제를 한번에 해결한다. 최상위 큐에 존재하는 동안 작업은 다른 높은 우선순위 작업들과 Round Robin 방식으로 CPU를 공유하게 되고 서비스를 받게 된다. 그리고 CPU 위주의 작업이 상호작업(interactive jobs)으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 맞는 스케줄링 방법을 적용한다.

Better Acounting: 해결책2#

해결해야 할 문제가 하나 더 있다. 스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까? 이 문제는 규칙 4a, 5b로 인해 생겼다. 두 규칙은 작업이 타임 슬라이스가 끝나기 전에 CPU를 양보하여 우선순위를 유지할 수 있게 한다.

이 문제의 해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다. 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 이렇게 되면, 타임 슬라이스를 한번에 소진하든 짧게 여러 번 소진하든 상관 없다. 규칙을 하나로 합쳐 재정의해보면,

MLFQ 최종 규칙

1. 만약 Priority(A) > Priority(B) 일 때, A가 실행,B는 실행되지 않는다.
2. 만약 Priority(A) = Priority(B) 일 때, A와 B는 RR로 실행된다.
3. 작업이 시스템에 들어가면 최상위 큐에 배치된다.
4. 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다.(즉, 한 단계 아래 큐로 이동한다.)
5. 일정 주기 S 이후, 모든 작업들을 시스템의 최상위 큐에 이동시킨다.

그래서 규칙 4를 적용하게 되면, 위 그림과 같이 타임슬라이스에 해당하는 시간을 소진할 때마다 우선순위가 내려가는 것을 볼 수 있다.

출처#

• Operating system three easy pieces
• System Software Lab Konkuk Operating System Lecture