Operating systems


Prashanth L.A.


Lecture 6 continues here

How to develop scheduling policy?

Workload assumptions

  1. Each job runs for the same amount of time  

  2. All jobs 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

Scheduling Metrics

\[ T_{turnaround}\ = T_{completion} − T_{arrival} \] All jobs arrive at the same time \(\Rightarrow\) \(T_{turnaround}\ =\)

Lecture 7 starts here

First In, First Out (FIFO)

FIFO is a poor scheduling scheme

FIFO is not the way out


Shortest Job First (SJF)

If all jobs do not arrive at the same time

SJF with Late Arrivals

Aside: Preemptive Schedulers

Non-preemptive scheduler: run each job to completion  

Preemptive scheduler: stop one process from running in order to run another

SJF variant: Shortest Time-to-Completion First

Alternate scheduling metric: Response time

\[ T_{response}\ = T_{firstrun} − T_{arrival} \]

Round Robin (RR) Scheduling

RR vs SJF: An Example

RR vs SJF: A summary

Lecture 8 starts here

Some notes on RR

The length of the time slice is critical


Should OS keep time slice very low?


Incorporating I/O

Overlap enables higher utilization