Operating Systems:
Internals and Design Principles, 6/E
William Stallings
Chapter 9
Uniprocessor Scheduling
Patricia Roy
Manatee Community College, Venice, FL
©2008, Prentice Hall
Aim of Scheduling
• Assign processes to be executed by the
processor(s)
• Response time
• Throughput
• Processor efficiency
Types of Scheduling
Scheduling and Process State
Transitions
Levels of Scheduling
Long-Term Scheduling
• Determines which programs are admitted
to the system for processing
• Controls the degree of multiprogramming
• More processes, smaller percentage of
time each process is executed
Medium-Term Scheduling
• Part of the swapping function
• Based on the need to manage the degree
of multiprogramming
Short-Term Scheduling
• Known as the dispatcher
• Executes most frequently
• Invoked when an event occurs
– Clock interrupts
– I/O interrupts
– Operating system calls
– Signals
Short-Term Scheduling Criteria
• User-oriented
– Response Time
• Elapsed time between the submission of a request
until there is output.
• System-oriented
– Effective and efficient utilization of the
processor
Short-Term Scheduling Criteria
• Performance-related
– Quantitative
– Measurable such as response time and
throughput
Scheduling Criteria
Scheduling Criteria
Queuing Diagram
Priorities
• Scheduler will always choose a process of
higher priority over one of lower priority
• Use multiple ready queues to
representmultiiple levels of priority
• Lower-priority may suffer starvation
– Allow a process to change its priority based
on its age or execution history
Priority Queuing
Decision Mode
• Nonpreemptive
– Once a process is in the running state, it will
continue until it terminates or blocks itself for
I/O
Decision Mode
• Preemptive
– Currently running process may be interrupted
and moved to the Ready state by the
operating system
– Allows for better service since any one
process cannot monopolize the processor for
very long
Process Scheduling Example
First-Come-First-Served
• Each process joins the Ready queue
• When the current process ceases to
execute, the longest process in the Ready
queue is selected
First-Come-First-Served
• A short process may have to wait a very
long time before it can execute
• Favors CPU-bound processes
– I/O processes have to wait until CPU-bound
process completes
Round Robin
• Uses preemption based on a clock
Round Robin
• Clock interrupt is generated at periodic
intervals
• When an interrupt occurs, the currently
running process is placed in the ready
queue
– Next ready job is selected
• Known as time slicing
Effect of Size of Preemption
Time Quantum
Effect of Size of Preemption
Time Quantum
Queuing Diagram
Shortest Process Next
• Nonpreemptive policy
• Process with shortest expected processing
time is selected next
• Short process jumps ahead of longer
processes
Shortest Process Next
• Predictability of longer processes is
reduced
• If estimated time for process not correct,
the operating system may abort it
• Possibility of starvation for longer
processes
Exponential Smoothing
Coefficients
Use Of Exponential Averaging
Use Of Exponential Averaging
Shortest Remaining Time
• Preemptive version of shortest process
next policy
• Must estimate processing time
Highest Response Ratio Next
• Choose next process with the greatest
ratio
Feedback
• Penalize jobs that have been running
longer
• Don’t know remaining time process needs
to execute
Feedback Scheduling
Scheduling Policies
Scheduling Policies
Comparison of Scheduling
Policies