- Workload assumptions:
- Each job runs for the same amount of time.
- All jobs arrive at the same time.
- All jobs only use the CPU (i.e., they perform no I/O)
- The run-time of each job is known.
Scheduling Metrics
-
Turnaround time = Completion time - arrive time
-
Fairness : job이 CPU time을 공정하게 나누어 가졌는가?
Performance와 fairness는 가끔 상충되는 개념이다. -
Response time = 1st Scheduling time - arrive time
First in, First out (FIFO)
먼저 도착한 process가 먼저 실행된다 -> 구현이 쉬움
- Example :
A, B, C가 거의 동시에 도착했는데 A->B->C 순서로 도착했다.
각각의 job은 10초 동안 실행된다.
FIFO에서는 도착한 순서대로 실행되며, 하나의 process가 실행되고 있는 중간에 도착하더라도 이미 실행된 process가 끝나야 다음 process가 진행되는, 비선점형(Non-preemptive) scheduling이다.
A의 turnaround time = 10-0 = 10
B의 turnaround time = 20-0 = 20
C의 turnaround time = 30-0 = 30 이므로
만약 4개의 assumption 중 1번을 완화시켜 process들의 run time이 다르다고 생각해보자
위의 예제에서 A만 100초로 run time이 늘어났다고 하면
위와 같다.
A의 turnaround time = 100-0 = 100
B의 turnaround time = 110-0 = 110
C의 turnaround time = 120-0 = 120 이므로
이 때 B와 C의 run time은 10초밖에 안 되지만 A의 run time때문에 turnaround time이 크게 증가하는 문제가 발생한다.
앞선 process가 나머지 process의 영향을 주는 이러한 효과를 convoy effect라고 부른다.
Shortest Job First (SJF)
run time이 짧은 순서대로 process를 실행하며 FIFO와 마찬가지로 Non-preemptive scheduler이다.
- Example:
A->B->C 순서대로 거의 동시에 도착한다.
A는 100초, B와 C는 10초 실행된다.
위와 같은 예제이다. SJF 방식과 FIFO 방식의 차이를 확인해보자
B와 C의 run time이 짧기 때문에 A보다 먼저 실행된다.
A의 turnaround time = 120-0 = 120
B의 turnaround time = 10-0 = 10
C의 turnaround time = 20-0 = 20 이므로
FIFO scheduler에서의 convoy effect가 해결되는 모습을 확인할 수 있다.
만약 2번 assumption을 조금 완화해서 job들이 동시에 도착하지 않아도 된다고 해보자
- Example:
A는 0초에 도착하고 100초동안 실행된다.
B와 C는 10초에 도착하고 10초동안 실행된다.
Non-preemptive 방식이기 때문에 B와 C의 run time이 짧음에도 불구하고 A가 먼저 실행되는 모습이다.
turnaround time이 크게 증가한 모습이다.
Shortest Time-to-Completion First (STCF)
SJF를 preemptive 방식으로 바꾼 것, Preemptive Shortest Job First (PSJF)로 불리기도 한다.
- 실행되고 있는 job의 남은 run time과 새로운 job의 run time을 비교한다.
- Example:
A는 0초에 도착하고 100초동안 실행된다.
B와 C는 10초에 도착하고 10초동안 실행된다.
B와 C가 10초에 도착하고, A의 남은 run time은 90초이다.
이는 B와 C의 run time인 10초보다 긴 시간이므로 B와 C가 CPU를 선점해 먼저 실행된다.
A의 turnaround time = 120-0 = 120
B의 turnaround time = 20-10 = 10
C의 turnaround time = 30-10 = 20
preemptive 방식을 사용하여 위의 문제를 해결할 수 있다.
지금까지 FIFO, SJF, STCF는 turnaround time에 sensitive한 방식이다.
아래에서 설명할 RR 방식은 response time에 sensitive한 방식이다.
Round Robin (RR)
Time slicing Scheduling : time slice를 설정하고 time slice만큼 job들이 돌아가며 실행된다.
Time slice는 scheduling quantum이라고 불리기도 한다.
RR 방식은 fair하지만 turnaround time과 같은 여러 metrics에 대해 poor하다.
- Length of time slice = multiple of timer interrupt period
timer interrupt가 발생해야 switch를 할 수 있기 때문이다.
- Example:
A,B,C는 동시에 도착하며 run time은 5초이다.
time slice = 1초
위의 예제에서 SJF 방식과 RR 방식에 대해 response time을 비교해보면 위와 같다.
반면에 turnaround time을 비교해보면 SJF 방식에서 더 짧다.
The length of the time slice is critical
- The shorter time slice
better response time
high context switching overhead - The longer time slice
worse response time
low context switching overhead
response time vs overhead trade-off
Incorporating I/O
3번째 assumption을 완화해서 모든 job이 I/O 작업을 수행한다고 해보자
- Example:
A와 B의 CPU time은 50ms
A는 10ms 실행 후 I/O request(10ms)
B는 50ms를 CPU에서 실행한다.
A를 먼저 실행한다.
A가 10ms 실행 후 I/O 작업을 수행할 때 CPU는 낭비되는 상태이기 때문에
A를 blocked 상태로 만들고 ready queue에 있던 B를 실행시켜 CPU utilization을 최대로 만든다.
I/O 작업이 끝나면 interrupt를 발생시켜 OS가 기존 blocked된 process를 ready queue로 이동시킨다.
