1. 워크로드에 대한 가정
일련의 프로세스들이 실행하는 상황을 워크로드라고 부르기로 하자. 우리는 시스템에서 실행 중인 프로세스 혹은 작업에 대해 다음과 같은 가정을 한다.
- 모든 작업은 같은 시간 동안 실행된다.
- 모든 작업은 동시에 도착한다.
- 각 작업은 시작되면 완료될 때까지 실행된다.
- 모든 작업은 CPU만 사용한다. 즉 입출력을 수행하지 않는다.
- 각 작업의 실행 시간은 사전에 알려져 있다.
이러한 가정은 비현실적이지만, 점차 가정을 완화시키고 제대로 동작하는 스케줄링 정책이 소개될 것이다.
2. 스케줄링 평가 항목
작업 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시각을 뺀 시간으로 정의된다.
3. First In First Out(FIFO)
선입 선출 알고리즘. 단순하고 구현하기 쉽다.
짧은 작업 시간을 가진 프로세스가 긴 작업 시간을 가진 프로세스를 기다리는 현상(convoy effect). 앞선 작업이 오래 걸릴 수록, 평균 반환 시간이 늘어나는 문제가 발생한다.
4. Shortest Job First(SJF)
FIFO의 문제를 해결하기 위해, 짧은 작업 시간을 가진 작업을 먼저 실행 시킨다.
모든 작업이 동시에 도착한다면, SJF는 최적(optimal)의 스케줄링 알고리즘이다. 그러나 프로세스가 동시에 도착하는 것은 비현실적이다.
위 경우 B와 C는 A가 끝날 때까지 기다려야하고, convoy 문제가 다시 발생한다. 평균 반환 시간 또한 증가된다.
5. Shortest Time-to-Completion First - 최소 잔여시간 우선
비선점형 스케줄링 알고리즘인 SJF에 선점 기능을 추가했다. 새로운 작업이 시스템이 들어오면, 남아있는 작업 시간과 새로운 작업의 실행 시간을 비교하여 잔여 시간이 제일 적은 작업을 실행한다.
SJF에 비해 평균 반환 시간이 단축된다.
6. 새로운 평가 기준: 응답 시간(Response Time)
작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면 STCF는 매우 훌륭한 스케줄링 알고리즘이다.
하지만 시분할 컴퓨터가 등장이 모든 것을 바꾸었다. 이제 터미널에서 작업하게 되어 시스템에게 상호작용을 원활히 하기 위한 성능을 요구하게 되었다. 이에 응답 시간이라는 새로운 평가 기준이 등장하게 된다. 응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다.
7. Round-Robin (RR)
응답시간 문제를 해결하기 위해 라운드 로빈 스케줄링 방식이 도입되었다. RR은 작업이 끝날 때까지 기다리지 않고 일정 시간 동안 실행한 후 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 또는 타임 퀀텀(scheduling quantuam) 이라고 부른다.
타임 슬라이스가 작을 수록 응답시간이 향상되긴 하겠지만, 문맥 교환 비용으로 인해 성능이 크게 저해될 수 있다.
만약 반환시간이 유일한 측정 기준이라면, RR은 최악의 알고리즘이라고 할 수 있다.
8. 입출력 연산의 고려
우선 가정 4를 완화하자. 모든 프로그램은 입출력 작업을 수행한다.
현재 입출력이 수행 중이라면 완료까지 CPU를 사용하지 않기 때문에 그 시간 동안에 다른 작업을 스케줄 해야 한다.
9. 만병 통치약은 없다. (No More Oracle)
스케줄러가 각 작업의 실행시간을 알고있다는 가정은 최악의 가정이다. 범용 운영체제에서 작업에 길이에 대해서 알 수 있는 길은 없다.
