Tutorial #4: Scheduling

References: Text and Course WWW Page notes (Look at the course notes for last year’s course on the web)

Scheduling types:

Long term: Which programs are admitted to the system for execution and when, also which ones should be exited

Medium term: Suspends and resumes processes (deals a lot with memory management especially paging processes out to disk) more on this later on in course.

Short term: Determines which process in the set of ready processes should run next and for how long.

Non-preemptive scheduling methods have low overhead (i.e. not much work done by OS to handle the scheduling) but they can be unfair i.e. one process can monopolize the CPU.

Preemptive techniques can be more fair because it is hard for any one process to monopolize the system at the expense of others. However the overhead is greater.

treats everyone equally...therefore 'fair'?

Not necessarily good if different processes need different amounts of CPU time.

1. Fair can mean treat everyone the same OR

2. Have the lowest average waiting time.

(2) Takes into account the good of the group of processes. To reduce average waiting time.

SJF aka. SJN is based on philosophy (2). Shortest Job First/Next.

For the purposes of this discussion:

Job == Process== Thread == Person waiting in line

SJN favors short jobs and minimizes average waiting time.

e.g compare FCFS and SJN

Two Processes P1 needs 10min P2 1min

P1 runs first.

with FCFS wait time for P1 = 0 min

wait time for P2 = 10 min

avg wait time = 10/2 = 5min

with SJN

wait time for P2 = 0 min

wait time for P1 = 1 min

avg wait time = 1/2 min = 30sec.

Apparent problem with SJF:

How can you tell which job is shortest? How do you know how long a process will run for in advance?

You can't - what you can do is look at how long the process has run before and use that as an estimate of how long it will run. Therefore mainly useful if the same processes are run over and over again to provide historical data – e.g payroll

More serious problem:

long jobs are very heavily penalized – starvation (hungry for CPU time)

There are lots of variants of these - Just be aware of this fact, the specific variants are less important.

e.g Highest response ratio next

Response Ratio = Wait time+ Job time/Job time. This helps remedy the problem with SJN - i.e long jobs can be heavily penalized.

These are all good but in real-life processes can be pre-empted. I.e. machine state can be saved and restored allowing the OS to switch between running processes even before the process has finished executing.

There is an overhead to context switching (it takes time to save the state of the process, uses a clock interrupt so there is some time spent in interrupt handlers etc..)

Context Switch time in a modern OS is typically on the order of microseconds.

Simplest is RR (Round Robin) each process runs for a specific amount of time before being preempted - then the next process runs and so on.

RR often implemented with a queue. Processes at the head are run for a quantum then sent to then end of the queue.

Big Problem with RR. Let's look at an example. 500 processes (large but not totally unreasonable) 20ms quantum.

Each process gets a quantum every 500*20ms = 10s.

This is very bad. Especially in an interactive system.

One solution (used in many common real OS) is to use a priority system. Processes at a given priority are scheduled RR.

Preemptive version of SPN. Scheduler dispatches process with shortest remaining time to completion.

Since this is preemptive completion here means running until the process will leave the ready state e.g. waiting on IO. Not necessarily the ‘end’ of the process’s life.

Gives better turnaround than SPN.

Risk of starvation.

Past running times are used as an indication of future running times.

Scheduling decision is only made when a new process is submitted. Or when a process completes.

In a real OS hybrids of these methods are often used. Another important concept is that of priority class.