03_intro_to_scheduling

index

os virtualisation cpu

Intro to Scheduling

high level scheduling policies os implements

Assumptions

1. each job runs for the same amount of time
2. all jobs arrive at the same time
3. once started, each job runs to completion
4. all jobs only use the cpu, no i/o
5. the run time of each job is known

these sound unrealistic, and we will shed them one by one

metrics

1. turnaround time: a performance metric $T_{turnaround}=T_{completition}-T_{arrival}$
   • since all jobs arrive together ⇒ $T_{arrival}=0$
2. fairness → Jain’s Fairness Index¹ (jainwin baat)
3. response time $T_{response}=T_{firstrun}-T_{arrival}$

First In, First Out (FIFO)

convoy effect: relatively-short potential customers get held up by a heavyweight customer

Shortest Job First (SJF)

greedy behavious → optimal with assumption 2

non-preemptive: job must run to end

Shortest Time-to-Completion First

relax assumption 3 (tasks need to run to completion)

also called “preemptive shortest job first”

Round Robin

the earlier algs do not consider response time, i.e. the user should get a response from the process they run asap

RR runs a job for a time slice until all jobs are finished

pretty (very) bad for turnaround time though

turnaround vs response time fight

Incorporating i/o

relax assumption 4 (no i/o)

basically just PSJF → choose the shortest job at any given time

1. do A
2. A is busy
3. switch to B
4. A is free again
5. switch to A

we’ve dealt with all the assumptions except the last → you never actually know the run time of a process

Footnotes

1. https://en.wikipedia.org/wiki/Fairness_measure ↩