Ch.

5 CPU Scheduling
 Basic Concepts
o In a system with a single CPU core, only one process can run at a time
o The objective of multiprogramming is to have some process running at all times, to
maximize CPU utilization
o The execution of a process consists of a cycle of
 CPU burst (execution on CPU)
 I/O burst (waiting for the completion of I/O operation)

 CPU Scheduler
o Whenever the CPU becomes idle, the OS selects one of the processes in the ready
queue to be executed. This is done by the CPU scheduler.
o The CPU scheduler is an OS component that selects a process from the processes
in memory that are ready to execute and allocates the CPU to that process
o CPU scheduling decisions take place when a process
 switches from the running state to the waiting state
 switches from the running state to the ready state
 switches from the waiting state to the ready state
 terminates
o Preemptive and non-preemptive scheduling
 Preemptive scheduling: A form of scheduling in which the CPU can be
preempted (removed involuntarily) from a running process by the OS
 Non-preemptive scheduling: Under non-preemptive scheduling, once the
CPU has been allocated to a process, the process keeps the CPU until it
releases it either by terminating or by switching to the waiting state
o Modern OSs including Windows, macOS, Linux, and UNIX use preemptive
scheduling algorithms
 Dispatcher
o The dispatcher is the module that gives control of the CPU to the process selected
by the CPU scheduler. This function involves the following steps:
 Switching context from one process to another
 Switching to user mode
 Jumping to the proper location in the user program to resume that
program
o The time it takes for the dispatcher to stop one process and start another running
is known as the dispatch latency
 Scheduling Criteria
o CPU utilization: keep the CPU as busy as possible
o Throughput: number of processes completed per time unit
o Turnaround time: amount of time to execute a particular process
o Waiting time: amount of time a process has been waiting in the ready queue
o Response time: amount of time when a request was submitted until the first
response is produced
 It is desirable to maximize CPU utilization and throughput, and to minimize turnaround
time, waiting time, and response time.
 Scheduling Algorithms – FCFS, SJF, RR, Priority
o CPU scheduling deals with the problem of deciding which of the processes in the
ready queue is to be allocated the CPU
o For simplicity, we discuss scheduling algorithms in the context of a uniprocessor
system (i.e., single CPU having one processing core) that is capable of running
only one process at a time
o For each process, we consider only one CPU burst (in milliseconds)
o The measure of comparison of scheduling techniques is the average waiting time
 First-Come, First-Served (FCFS) Scheduling
o It is the simplest CPU scheduling algorithm
o With this scheme, the process that requests the CPU first is allocated the CPU
first. In other words, the first process in the ready queue will get the CPU first.
o Example: Consider the following set of processes that arrive at time 0, with the
length of the CPU burst given in milliseconds:
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1, P2, P3
The Gantt Chart for the FCFS schedule is:

P1 P2 P3

0 24 27 30

Waiting time for P1 = 0; P2 = 24; P3 = 27

Average waiting time: (0 + 24 + 27)/3 = 17 milliseconds

o Suppose that the processes arrive in the order: P2, P3, P1

The Gantt chart for the schedule is:
P2 P3 P1

0 3 6 30

Waiting time for P1 = 6; P2 = 0; P3 = 3

Average waiting time: (6 + 0 + 3)/3 = 3 milliseconds
Definitely, it is much better than the previous case
 Shortest Job First (SJF) Scheduling / Shortest Job Next (SJN) Scheduling
o A scheduling algorithm that associates with each process the length of its next
CPU burst and uses these lengths to schedule the process with the shortest time
o If the next CPU bursts of two (or more) processes are the same then FCFS
scheduling is used to break the tie
o SJF is optimal – gives minimum average waiting time for a given set of processes
o SJF scheduling is non-preemptive. But it also has preemptive version often called
as shortest-remaining-time-first scheduling
 o How do we determine the length of the next CPU burst?
 Could ask the user
 Estimate
o Example: Consider the following set of processes, with the length of the CPU
burst given in milliseconds.
Process Burst Time
P1 6
P2 8
P3 7
P4 3
Using SJF scheduling, we would schedule these processes according to the
following Gantt chart:

P4 P1 P3 P2

0 3 9 16 24

Average waiting time = (3 + 16 + 9 + 0) / 4 = 7 milliseconds

For the sake of comparison, see that if we were using the FCFS scheduling
scheme, the average waiting time would be 10.25 milliseconds.
 Shortest Remaining Time First Scheduling
o It is the preemptive version of SJF Scheduling
o Recall that the SJF scheduling can be either preemptive or non-preemptive. The
choice arises when a new process arrives at the ready queue while a previous
process is still executing. The next CPU burst of the newly arrived process may
be shorter than what is left of the currently executing process. A preemptive SJF
scheduling algorithm will preempt the currently executing process, whereas a
non-preemptive SJF scheduling algorithm will allow the currently running
process to finish its CPU burst. Preemptive SJF scheduling is known as the
Shortest-Remaining-Time-First scheduling.
o Example: Consider the following four processes with their arrival time (in the
ready queue) as well as the burst time in milliseconds:
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Process P1 is started at time 0, since it is the only process in the queue. Process P 2
arrives at time 1. The remaining time for process P 1 (7 milliseconds) is larger than
the time required by the process P2 (4 milliseconds), so process P1 is preempted,
and process P2 is scheduled. The resulting preemptive SJF schedule is depicted in
the following Gantt chart:

P1 P2 P4 P1 P3

0 1 5 10 17 26

Average waiting time = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5 milliseconds.

Observe that if we were using the non-preemptive SJF scheduling scheme then
the average waiting time would be 7.75 milliseconds.
 Round Robin (RR) Scheduling
o A scheduling algorithm similar to FCFS, but with preemption added to
enable the system to switch between processes on the basis of a time
quantum (or time slice)
 This scheduling is especially useful for time-sharing systems
o A time quantum or time slice is a small unit of time, generally 10 to 100
milliseconds in length
o In RR scheduling, the ready queue is treated as a simple queue of
processes. New processes are added to the tail of the ready queue. The
CPU scheduler picks the first process from the ready queue, sets a timer to
interrupt after 1 time quantum, and dispatches the process. One of the two
things will then happen:
 The process may have a CPU burst of less than 1 time quantum. In
this case, the process itself will release the CPU voluntarily. The
scheduler will then proceed to the next process in the ready queue.
 If the CPU burst of the process is longer than 1 time quantum, the
timer will go off and will cause an interrupt to the operating
system. A context-switch will be executed, and the process will be
put at the tail of the ready queue. The CPU scheduler will then
select the next process in the ready queue.
o The average waiting time under the RR policy is often long. Consider the
following set of processes that arrive at time 0, with the length of the CPU
burst given in milliseconds:
Process Burst Time
P1 24
P2 3
P3 3
If we use a time quantum of 4 milliseconds, then the process P 1 gets the
first 4 milliseconds. Since it requires another 20 milliseconds, it is
preempted after the first time quantum, and the CPU is given to the next
process in the queue, process P2. The process P2 needs only 3 milliseconds
to execute, so it terminates before its time quantum expires. The CPU is
then given to the next process, process P3. Once each process has received
1 time quantum, the CPU is returned to process P1 for an additional time
quantum. The resulting RR schedule is as follows:

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

Let’s calculate the average waiting time for this schedule. P1 waits for 6
milliseconds (10-4), P2 waits for 4 milliseconds, and P3 waits for 7
milliseconds. Thus, the average waiting time is 17/3 = 5.66 milliseconds.
o If there are n processes in the ready queue and the time quantum is q, then
each process gets 1/n of the CPU time in chunks of at most q time units.
Each process must wait no longer than (n-1) × q time units until its next
time quantum. For example, with five processes and a quantum of 20
milliseconds, each process will get up to 20 milliseconds every 100
milliseconds.
 o The performance of the RR scheduling algorithm depends on the size of
the time quantum.
 If the time quantum is extremely large, the RR policy is the same
as the FCFS policy.
 If the time quantum is extremely small (say, 1 millisecond), the RR
scheduling can result in a large number of context-switches.
Assume, for example, that we have only one process of 10 time units. If
the quantum is 12 time units, the process finishes in less than 1 time
quantum, with no overhead. If the quantum is 6 time units, however, the
process requires two quanta, resulting in a context-switch. If the time
quantum is 1 time unit, then nine context-switches will occur, slowing the
execution of the process accordingly.

Thus, we want the time quantum to be large with respect to the context-
switch time. The time required for a context-switch is usually less than 10
microseconds.
1 microsecond = 10-6 seconds = one millionth of a second
1 millisecond = 10-3 seconds = one thousandth of a second
o Turnaround time also depends on the size of the time quantum.
o Although, the time quantum should be large compared with the context-
switch time, it should not be too large. As pointed out earlier, if the time
quantum is too large, RR scheduling behaves like an FCFS scheduling. A
rule of thumb is that 80 percents of the CPU bursts should be shorter than
the time quantum.
 Priority Scheduling
o A scheduling algorithm in which a priority is associated with each process
and the CPU is allocated to the process with the highest priority.
 Equal-priority processes are scheduled in FCFS order.
o Priority of a process is generally indicated by some fixed range of
numbers, such as 0 to 7 or 0 to 4095.
 Here, we assume that low numbers represent high priority.
o Example: Consider the following set of processes, with their assigned
priority values: Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
 Using priority scheduling, we would schedule these processes according to
the following Gantt chart:

The average waiting time is 8.2 milliseconds.

o The priority of a process can be set by considering some measurable
quantities such as its memory requirements, time limits, the number of
open files, and the ratio of average I/O burst to average CPU burst.
o Priority scheduling can be either preemptive or non-preemptive. Suppose a
process arrives at the ready queue and its priority is compared with the
priority of the currently-running process:
 A preemptive priority scheduling algorithm will preempt the CPU
if the priority of the newly-arrived process is higher than the
priority of the currently-running process.
 A non-preemptive priority scheduling algorithm will simply put the
new process at the head of the ready queue
o A major problem in priority scheduling is the possibility of indefinite
blocking or starvation – one (or more processes) left to wait indefinitely.
 In a heavily-loaded computer system, a steady stream of higher-
priority processes can prevent a low-priority process from ever
getting the CPU.
 A solution to the problem of indefinite blockage of low-priority
processes is aging – gradually increasing the priority of processes
that wait in the system for a long time. For instance, we could
periodically (say, every second) increase the priority of a waiting
process by 1 so that eventually the process would get CPU time.
o We can combine round-robin and priority scheduling in such a way that
the system executes the highest-priority process and runs processes with
the same priority using round-robin scheduling.
Example: Let’s consider the following set of processes:
Process Burst Time Priority
P1 4 3
P2 5 2
P3 8 2
P4 7 1
P5 3 3
Using a time quantum of 2 milliseconds, we would schedule processes as:

In this example, process P4 has the highest priority, so it will run to

completion. Processes P2 and P3 have the next-highest priority, and they
will execute in a round-robin fashion. Notice that when process P2 finishes
at time 16, process P3 is the highest-priority process, so it will run until it
completes execution. Now, only processes P1 and P5 remain, and as they
have equal priority, they will execute in round-robin order till completion.