Basic scheduling

The scheduler is the part of the OS that picks which job runs next on the CPU.

Turnaround and response time

Turnaround time is a job's finish time minus its arrival time. Response time is the time it first runs minus its arrival time. Turnaround matters for long work, like a backup. Response time matters for apps you type into, which should react at once.

First come, first served

FIFO (first in, first out), also called first come, first served, runs jobs in arrival order, each one to the end. It is simple, and fine when jobs are about the same length. But if a 100 second job arrives just before two 10 second jobs, they end at 100, 110 and 120. The average turnaround is 110. Short jobs stuck behind a long one is the convoy effect.

Shortest job first

SJF runs the shortest job first, then the next shortest. For the same three jobs, they end at 10, 20 and 120, so the average turnaround drops to 50. When all jobs arrive together, SJF gives the best average turnaround. The catch: a real OS rarely knows how long a job will run.

Round robin

Round robin gives each job a short time slice, then moves to the next, again and again. Every job starts soon, so response time is good. But each job finishes late, so turnaround is worse. A shorter slice makes response even better, but each switch costs time with no useful work.

Overlapping I/O

When a job waits for the disk or network, it doesn't need the CPU. So the scheduler runs another job meanwhile, which keeps the CPU busy.

Remember

• Turnaround = finish minus arrival; response = first run minus arrival.
• FIFO is simple but suffers the convoy effect.
• SJF is best for turnaround, if you know job lengths.
• Round robin is good for response, bad for turnaround.
• Run another job while one waits for I/O.