[ OS ] 3. Process Scheduling

들어가며

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

워크로드에 대한 가정

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

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

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

비현실적인 가정들이다. 매우 이상적인 가정이다.

스케줄링의 평가 항목

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

반환 시간(turnaround time)

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

모든 작업은 동시에 도착한다고 가정해서 T_arrival = 0으로 생각할 수 있다.

그렇다면 T_turnaround = T_completion 이다. 좀 비현실적이지만, 가정은 완화해 갈 것이다.

공평성(fairness)

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

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

선입선출(FIFO)

위에서 베이지 색은 10, 하늘색은 20, 초록색은 30에 종료함

FCFS(First Come First Served) 평균 반환 시간(Average turnaround time)

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

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

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

이 경우엔 이렇게 될 수도 있다.

이 경우의 평균 반환 시간 average turn arround time

이런 경우를 convoy effect라고 부른다. CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상을 말한다.

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

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

SJF 평균 반환 시간

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

SJF의 문제

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

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

그러면 다음과 같이 될수도 있다.

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

이 경우 평균 반환 시간

최소 잔여 시간 우선(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 평균 반환 시간

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

응답 시간(response time)

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

STCF의 응답 시간

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

라운드 로빈(Round Robin)

라운드 로빈은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 기간동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice)또는 스케줄링 퀀텀(scheduling quantum)이라 부른다.

이러한 이유로 RR은 타임 슬라이싱이라고 부른다. 타임 슬라이싱의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 10msec 마다 인터럽트를 발생시키면, 타임 슬라이스는 10의 배수가 될 수 있다.

RR의 평균 응답 시간

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

RR의 평균 반환 시간

셋 다 늦게 끝나기 때문에 반환시간은 최악이다.

이제 나머지 가정들을 없애보자.

입출력 연산 고려

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

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

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

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

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

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