7. Scheduling : Introduction
운영체제 개념에서 가장 중요하다고 생각되는 몇 가지 주제 중 하나 scheduling
7.1 Workloak Assumption
1. 모든 작업의 수행 시간은 동일하다.
2. 모든 작업은 같은 시각에 도착한다.
3. 모든 작업은 CPU 사용만을 필요로 한다(즉, 입출력 요구 등 없음)
4. 모든 작업의 런타임은 사전에 알 수 있다.
- 이 네 가지 사항을 가정한 상태에서 스케줄링 policy 개념을 시작
7.2 Scheduling Metrics
- 스케줄링을 하는 데에 필요한 평가 지표(metric)로써 반환시간(turnaround time)을 이용
- T_turnaround=T_completion-T_arrival
- 가정 2에 의해, T_turnaround=T_completion이 됨
7.3 First In, First Out(FIFO)
- 세 개의 작업 A, B, C가 A --> B --> C의 순서로 도착했다면 도착한 순서대로 실행해주는 것
- 문제점(by 평가지표 : 평균반환시간)
- 앞서 했던 가정 1, 2(작업 도착시간 동일, 수행시간 동일)를 무시
- 작업 A가 가장 먼저 도착하는데 가장 긴 수행시간을 가진 경우
- 평균 반환 시간 : (100+110+120)/3=110
- 비효율('약간 늦게 도착했지만 금방 끝날 수 있는 작업 B와 C'가 A 때문에 상당히 긴 시간을 기다려야만 한다.)
--> convoy effect
7.4 Shortest Job First(SJF)
- 위 문제에 대한 가장 간단한 해결책
- 가장 짧은 작업부터 처리(A, B, C가 동시에 도착했다는 가정 하에서)
- 평균 반환 시간은 50으로 줄어듦
- 그렇지만, B와 C가 A보다 늦게 도착하는 경우, FIFO과 같은 비효율 문제 발생
7.5 Shortest Time-to-Completion First(STCF)
- 위 문제점을 해결하기 위해서는 늦게 들어오는 작업에 대해서도 고려해야 함
| Non-Preemptive(비선점) | Preemptive(선점) |
|
First In First Out, FIFO(First Come, First Served) Shortest Job First, SJF |
Shortest Time-to-Completion First(STCF) |
|
현재 실행 중인 프로그램에게 수행이 끝날 때까지 CPU 할당 |
현재 실행 중인 프로그램이 있더라도, 기준에 충족되는 다른 프로그램이 있으면 그 프로그램에 CPU 할당 |
- A 반환시간 : 120-0=120 / B 반환시간 : 20-10=10 / C 반환시간 : 30-10=20
- 평균 반환시간 : 50
- 지금까지는 STCF가 가장 이상적인 스케줄러
- 하지만, metric에 response time(응답시간)을 포함시킨다면?
- 응답시간 : T_response=T_firstrun-Tarrival(도착한 후 얼마나 빠르게 첫 실행이 되는지에 대한 지표)
- STCF에서 A 응답시간 : 0 / B 응답시간 : 0 / C 응답시간 : 10 / 평균 응답시간 : 3.33
- 하지만 A, B, C가 동시에 도착했다면? --> 응답시간 훨씬 비효율
7.6 Round Robin(RR)
- 응답시간 문제 해결
- 일정한 time slice(scheduling quantam)을 할당하고 그 시간이 지나면 다음 작업을 수행하게 함
- time slice=1이라면 위 STCF에 비해 평균 응답시간이 줄어든다. --> (0+1+2)/3=1
- 그렇다면, time slice는 작을수록 좋을까? --> No(오버헤드)
- RR의 단점 : 평균 반환시간에서는 worst performance(계속해서 여러 작업을 교체 수행하므로, 한 작업이 끝나는 데까지는 오랜 시간이 걸릴 수밖에 없음)
==> 결과적으로, scheduling policy에서 turnaround time과 response time 간의 trade-off는 본질적인 문제임
7.7 Incorporating I/O
- 가정 3 무시(작업 중 I/O request와 CPU demand가 번갈아가며 있음)
| Poor Use | Better Use |
 |
 |
| A의 모든 I/O작업 및 CPU 작업이 모두 끝난 후 다른 작업 B 수행 | A가 I/O작업 시에, 남는 CPU를 B에게 할당 |
-출처-
<OPERATING SYSTEMS three easy pieces>
REMZI H. ARPACI-DUSSEAU
ANDREA C. ARPACI-DUSSEAU
UNIVERSITY OF WISCONSIN-MADISON