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