Chapter 9:
Scheduling
• Aim: select processes to be executed by the processor in a way that meets system objectives
• Can be broken down into three separate functions:
o Long term scheduling
o Medium term scheduling
o Short term scheduling
• Affects the performance of the system because it determines which processes will wait and
which will progress
• Fundamentally: scheduling is a matter of managing queues to minimize queueing delay and to
optimize performance in a queueing environment
Types of scheduling
• Long term scheduling: the decision to add to the pool of processes to be executed
• Medium term scheduling: the decision to add to the number of processes that are partially or
fully in main memory
• Short term scheduling: the decision as to which available process will be executed by the
processor
• I/O scheduling: the decision as to which process’s pending I/O request shall be handled by an
available I/O device
Long Term Scheduler
• Determines which programs are admitted to the system for processing
• Controls the degree of multiprogramming:
o The more processes that are created, the smaller the percentage of time that each
process can be executed
o Additional processes may be limited to provide efficient service to the current set of
processes
• Once admitted a job or user program becomes a process and is added to the queue for the
short-term scheduler
• Some systems: a newly created process begins in a swapped-out condition, in which case it is
added to a queue for the medium-term scheduler
• Batch systems / batch portion of the OS: newly submitted jobs are routed to disk and held in a
batch queue.
o Long-term scheduler creates processes from queue when it can
• Two decisions involved:
1. When the OS can take on additional processes
2. Which jobs to accept and turn into processes
Medium Term Scheduler
• Part of swapping function
• Manage the degree of multiprogramming
• Swapping decisions are based on:
o The availability of main memory
o The memory requirements of suspended processes
Short Term Scheduler
• Also known as the dispatcher
• Execute most frequently
• Makes fined-grained decision of which process to execute next
• Is invoked when:
o The currently executing process finishes or becomes blocked
o The OS pre-empts a currently running process in favour of another
Short-Term Scheduling Criteria
• Main objective of short-term scheduling is to allocate processor time in such a way as to
optimize one or more aspects of system behaviour
• A set of criteria is needed to evaluate the scheduling policy
• User-Oriented criteria:
o Relate to the behaviour of the system as perceived by the individual user or process
o Important on virtually all systems
• System-Oriented criteria:
o Focus on the effective and efficient utilization of the processor
o Generally, of minor importance on single-user systems
• Performance related criteria:
o Quantitative
o Can easily be measured
• Non-performance related criteria:
o Qualitative
o Are hard to measure
User Oriented, Performance Related Criteria
• Turnaround Time
• Response Time
• Deadlines
User Oriented, Other Criteria
• Predictability
System Oriented, Performance Related Criteria
• Throughput
• Processor utilization
System Oriented, Other Criteria
• Fairness
• Enforcing Priorities
• Balancing resources
The Use of Priorities (via Priority Queueing)
• Scheduler selects processes from the highest priority queue first
• If this queue is empty the scheduler considers the next lower priority queue
• Problem with a purely priority scheduling scheme: lower-priority processes may suffer
starvation
Selection Function
• Determines which process among ready processes is selected next for execution
• May be based on priority, resource requirements or time aspects
• Times aspects involve:
o w = waiting time (time spent waiting so far)
o e = execution time ( time spent executing so far)
o s = total service time (total time required)
o s – e = remaining execution time (time still required)
Decision Mode
• Specifies the instants in time at which the selection function is exercised (when to select the
next process)
• Non pre-emptive:
o A running process continues until it terminates or blocks itself
• Pre-emptive:
o A running process may be interrupted by the OS
o Decision to pre-empt may be performed when a new process arrives, when another
process becomes ready or periodically based on a clock interrupt
o Incur greater overhead, but may provide better service to the total population of
processes as they prevent any one process from controlling the processor for very long
Turnaround time
• The residence time or total time spent that the item spends in the system (waiting time +
service time)
• More useful figure is the normalised turnaround time => the ratio of turnaround time to service
time
o Indicates the relative delay experienced by a process
First-Come-First-Served (FCFS)
• Simplest scheduling policy
• Also known as First-In, First Out (FIFO) or a strict queueing scheme
• As a process becomes ready, it joins the ready queue
• When the currently running process stops to execute, the process that has been waiting in the
ready queue the longest time is selected next for running
• No pre-emption: processes are allowed to run until termination or until they are blocked
• Performs much better for longer processes than shorter ones
• Tends to favour processor-bound processes over I/O bound processes
Round Robin
• Uses pre-emption based on a clock
• At each clock interrupt, the running process is placed in the ready queue, and the next ready
process is selected based on FCFS
• Also known as time slicing
• Time quantum q determines how frequently clock interrupts occur
Shortest Process Next (SPN)
• Non pre-emptive policy
• Selects the process with shortest expected service time next
• Shortest process will jump to the head of the queue
• Starvation of longer processes is possible
• Only works if service times can be properly estimated
• Calculation of estimations may involve computational overhead (thus overall performance
decreases)
Shortest Remaining Time (SRT)
• Pre-emptive version of SPN
• Policy chooses process that has the shortest expected remaining service time (s – e) at:
o Completion of current process
o Arrival of new process
• Chosen process can be either the one that is currently pre-empted, or a process in the ready
queue
o New ready process in the queue if shorter
o Shortest ready process earlier in the queue
• Starvation of longer processes is possible
• Overhead due to computation of execution time e
• Better turnaround-time performance in comparison to SPN because short processes are
favoured over running longer processes
Highest Response Ratio Next (HRRN)
• No pre-emption
• Policy chooses process with the maximum response ratio next
𝑡𝑖𝑚𝑒 𝑠𝑝𝑒𝑛𝑡 𝑤𝑎𝑖𝑡𝑖𝑛𝑔 + 𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑 𝑠𝑒𝑟𝑣𝑖𝑒 𝑡𝑖𝑚𝑒
𝑅𝑎𝑡𝑖𝑜 =
𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑡𝑖𝑚𝑒
• Generally favours short processes
• Also ensures that eventually long-waiting processes will be favoured (balancing)
• Service times must be estimated
Feedback Scheduling
• Works without having an estimation of service times
• Pre-emption at time quantum q
• Dynamic priority mechanism:
o Assign priority 0 (highest) to all new processes
o After each pre-emption of a process assign next lowest priority to process
• Short processes indirectly favoured by penalizing long-running processes