7. Scheduling: Introduction

 

Workload assumptions

1. Each job runs for the same amount of time
2. All job arrive at the same time
3. All jobs only use the CPU(i.e., they perform no I/O)
4. The run-time of each job is known

=> 현실에선 충족되긴 어렵지만, 간단하게 정의하기 위해 만든 가정들

=> 모든 process 들은 실행시간이 같고, 동시에 시작하며, CPU만 사용하고, 총 수행시간을 알고 있다.

 

 

Scheduling Metrics 

 

Performance metric: Turnaround time

T(turnaround) = T(completion) - T(arrival)

 

• 끝나는 시간 - 도착 시간

New scheduling metric: Response time

T(response) = T(first_run) - T(arrival)

 

• 처음 시작한 시간 - 도착 시간 

 

Turnaround time과 Response time은 trade-off 관계이다 (반비례하다)

 

 

Another metric: fairness

• turnaround time과 관계없이, 각 process들이 CPU를 공평하게 사용했는지, 아닌지 판단

 

 

 

** job == process

Scheduling Policy

1. First In, First Out (FIFO) == First Come, First Served(FCFS)
2. Shortest Job First(SJF)
3. Shortest TIme-to-Completion First(STCF)
4. Round Robin(RR)

 

 

First In, First Out (FIFO) == First Come, First Served(FCFS)

• 먼저 도착한 process를 먼저 실행하는 정책
• 앞 가정에서 살짝 바꿔서, process들이 거의 동시에 도착했으나, 아주 살짝 먼저 도착한 process를 먼저 실행
• 구현이 간단하고 쉽다

• 가정 1을 relax해서, 각 process가 수행 시간이 다를 수 있다고 해보자.
• Convoy effect 발생

==> 수행 시간이 긴 job이 먼저 도착하면, 나중에 도착한 job은 수행 시간이 짧아도 turnaround time 관점에서 좋지 않다.

 

 

 

** Non-preemptive scheduler : 어떤 job이 실행 중일 때, 다른 job이 끼어들지 못함, 끝날 때까지 기다려야함

** preemptive scheduler: 앞선 job의 수행 시간이 끝나지 않았는데, 다른 job이 선점할 수 있는 것

 

Shortest Job First(SJF)

• 가장 수행시간이 짧은 job부터 수행
• Non-preemptive scheduler
• FIFO(FCFS)에 비해 turnaround time이 상대적으로 좋다

• 가정 2를 relax해서, 각 job의 도착시간이 다를 수 있다고 해보자.  + 가정 1은 이미 relax
• 마찬가지로 수행 시간이 긴 job이 먼저 도착하면, 나중에 도착한 job은 turnaround time이 좋지 않다.

 

 

Shortest Time-to-Completion First(STCF) == Preemptive Shortest Job First(PSJF)

• SJF 에서 prremption을 추가한 것
• preemptive scheduler
• 나중에 도착한 process가 있으면, 남은 수행 시간을 비교하여 짧은 job이 선점할 수 있게 해줌
• 위의 정책들보다 turnaround time이 좋다

• response time의 관점에서는 별로 좋지 않다.

=> response time은 어떻게 좋게 만들 수 있을까?

 

 

Round Robin(RR)

• Time slicing Scheduling (== scheduling quantum)
• job들을 context switching하기 전, 이미 거의 고정 된 값으로 각 job들이 cpu를 쓰는 시간을 동일하게 정해둔다
• 모든 job들이 끝날 때까지 계속 switching 반복  
• time slice의 길이는 반드시 timer-interrupt 주기의 n배가 되어야 한다
• => 만약에 interrupt를 1s마다 준다고 하면, 다음 1s가 되기 전까지 time slice가 올 수가 없음 (interrupt를 줘야 switching이 발생 되니까..)

• RR 정책은 fair 하나, turnaround time 관점에서는 좋지 않다. 
• time slice가 짧으면 response time 관점에서 좋으나, 잦은 context switching으로 인한 overhead의 cost 발생 
• => overhead? : reg들을 kernel stack과 PCB에 저장하는데 있어 load/store 사용 => 메모리 접근 잦음 => 느리다
• time slice가 길면 context switching overhead를 줄일 수 있으나, response time이 좋지 않다.

=> time slice의 길이가 critical한 요소가 됨

 

 

 

Incorporating I/O

• 가정 3을 relax 해서, 모든 program이 I/O 작업을 수행 할 수 있다고 하자.

그러하다...