References: Text and Course WWW Page notes (Look at the course notes for last years 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.
Preemptive and non-preemptive.
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.
Comparing methods performance criteria
Response time | Interval between service requested and when it begins to be received |
Turnaround time | Interval between submission of a process and completion of execution |
Meeting deadlines | Meet specific time requirements for job completion - realtime OS (e.g QNX) |
Predicatbility | Similar to meeting deadlines. Guaranteed response time regardless of system load. |
Througput | Processes completed per unit time. - i.e how much work is performed. |
Scheduling methods
Non-preemptive first
FCFS - Aka FIFO - First Come First Served
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.
Shorter wait time is a good thing.
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.
Extremely important and useful concept: preemption.
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.
Definitions:
Context Switch | Saving the process state and switching to another process |
Time Slice/Quantum | The amount of time a process runs for before being preempted. |
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.
Preemptive methods
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.
SRTN (Shortest remaining time next)
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 processs 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.
Summary and Comparison
Preemtpive or not? | Pros | Cons | |
FCFS | Non-preemptive |
|
|
RR | Preemptive |
|
|
SPN | Non-preemptive |
|
|
SRTN | Preemptive |
|
Risk of starvation Time remaining is needed |
Discussion of real OS scheduling policies. UNIX & NT. See course notes for description of UNIX scheduling.