Lecture 6 continues here

How to develop scheduling policy?

• How should we develop a basic framework for thinking about scheduling policies?  

• What are the key assumptions?  

• What metrics are important?  

• What basic approaches have been used in the earliest of computer systems?

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

• Turnaround time

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

• Fairness
  • Performance and fairness are often at odds in scheduling
  • Focus only on turnaround time

Lecture 7 starts here

First In, First Out (FIFO)

• First Come, First Served \(FCFS\)
  • Very simple and easy to implement  
    
• Example:

• Average turnaround time \(=\ \frac{10 + 20 + 30}{3}=20\)

• menti poll

FIFO is a poor scheduling scheme

• Let’s relax the assumption that each job runs for the same amount of time
• Think of an example where FIFO performs poorly

FIFO is not the way out

• Average turnaround time \(=\ \frac{100 + 110 + 120}{3}=110\)

• This is the convoy effect

• WITA?

Shortest Job First (SJF)

• Run the shortest job first, then the next shortest, and so on
• Same example as before

• Average turnaround time \(=\ \frac{10 + 20 + 120}{3}=50\)

• If all jobs arrive at the same time, SJF is the best

If all jobs do not arrive at the same time

SJF with Late Arrivals

• Average turnaround time \(=\ \frac{100 + (110-10) + (120-10)}{3}=103.33\)

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

• SJF is non-preemptive \(\Rightarrow\) late arrivals make it sub-optimal

• Make SJF preemptive

  • When a new job enters the system, schedule the job which has the lest time left

• menti poll

• Average turnaround time \(=\ \frac{120 + (20-10) + (30-10)}{3}=50\)

Alternate scheduling metric: Response time

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

• Response time: \(0\) for \(A,B\), \(10\) for C, average \(=\ 3.33\)

• STCF is not good for response time. Why care about response time?

• A new problem: How to build a scheduler that is sensitive to the response time?

Round Robin (RR) Scheduling

• Run a job for a time slice and then switch to the next
  • Repeat until the jobs are finished.
  • Length of time slice must be a multiple of the timer-interrupt period.

RR vs SJF: An Example

• Response time \(=\ \frac{0+5+10}{3}=5\), turnaround time \(=\ \frac{5+10+15}{3}=10\)

• Response time \(=\ \frac{0+1+2}{3}=1\), turnaround time \(=\ \frac{13+14+15}{3}=14\)

RR vs SJF: A summary

• SJF does poorly on response time, but has good turnaround time
• RR goes the other way

Lecture 8 starts here

Some notes on RR

The length of the time slice is critical

• Shorter time slice \(\Rightarrow\) better response time
• Longer time slice \(\Rightarrow\) longer response time

Should OS keep time slice very low?

• No as the cost of context switching will dominate

• A policy (such as RR) that is fair will perform poorly on metrics such as turnaround time. This presents a tradeoff for an OS designer

Incorporating I/O

• Let’s relax assumption 3, i.e., all jobs only use the CPU
• Example:

• Problem: Poor use of resources
• Solution: Allow overlap

Overlap enables higher utilization

• When a job initiates an I/O request.
  • The job is blocked waiting for I/O completion.
  • The scheduler puts another job on the CPU.
• When the I/O completes
  • An interrupt is raised.
  • The OS moves the process from blocked back to the ready state.

• Are we done with process scheduling? Did we relax all the assumptions?

• The scheduler knows the length of each job \(\Leftarrow\) the worst assumption one could make
  • How can we build an approach that behaves like SJF/STCF without such a priori knowledge?
  • How can we incorporate some ideas from RR so that response time is also good