Chapter 6: CPU Scheduling

Basic Concepts
Scheduling Criteria
Scheduling Algorithms
 Objectives

To introduce CPU scheduling, which is the basis for

multiprogrammed operating systems

To describe various CPU-scheduling algorithms

To discuss evaluation criteria for selecting a CPU-

scheduling algorithm for a particular system
 Basic Concepts
Scheduling is a fundamental
operating system function.
Maximum CPU utilization
obtained with
multiprogramming.
The algorithm, the scheduler
uses is called scheduling
algorithm.
Several processes are kept in
memory at one time.
CPU–I/O Burst Cycle –
Process execution consists of
a cycle of CPU execution and
I/O wait
CPU burst followed by I/O
burst
CPU burst distribution is of
main concern
 CPU-Scheduling
(with multiprograming)
In a single processor system, only one process can run at a time.
Others must wait until CPU is free and can be rescheduled.

Whenever the CPU becomes idle, the operating system must

select one of the processes in the ready queue to be executed (the
records in the queues are generally PCBs of the pocesses).

The short term scheduler (or CPU scheduler- a part of OS) selects
a process to get the processor (CPU) among the processes which
are already in memory. (i.e. from the ready queue).

Processor scheduling algorithms try to answer the following crucial

question.
Which process in the ready queue will get the processor?

In order to answer this, one should consider the relative

importance of several performance criteria.
 CPU Scheduler
CPU scheduler selects from the processes in memory that are
ready to execute, and allocates the CPU to one of them.

CPU scheduling decisions may take place when a process:

[Link] from running to waiting state.
[Link] from running to ready state.
[Link] from waiting to ready.
[Link].
5.A new process joins the ready queue

5 2 4

3 1
Preemptive – Nonpreemptive Scheduling
Interrupt: Scheduler

5 2 4 picks another
process
Scheduler dispatch:
Scheduler picks
this process to
execute

3 1
In (1) and (4), a new process must be selected from the ready queue.
In (2), (3) and (5), previously running process or a new process may
be selected.
Scheduling algorithms that act only in circumstances (1) and (4) are
called nonpreemptive(or cooperative). Once CPU has been
allocated to a process, that process keeps the CPU until it releases
the CPU (either by termination or by requesting I/O). This scheduling
method was used by Microsoft Windows 3.x.
Otherwise it is preemptive. Windows 95 and all subsequent versions
of Windows operating systems have used preemptive scheduling.
Preemptive – Nonpreemptive Scheduling
A scheduling algorithm which acts on all circumstances is called
preemptive. (i.e. such an algorithm can select a new process in
circumstances 2, 3 and 5).
The CPU is allocated to the highest-priority process among all
ready processes. The scheduler is called each time a process
enters the ready state.
Advantages of non-preemptive scheduling algorithms:
They cannot lead the system to a race condition.
They are simple.

Disadvantage of non-preemptive scheduling algorithms:

They do not allow real multiprogramming.

Advantage of preemptive scheduling algorithms:

They allow real multiprogramming.

Disadvantages of preemptive scheduling algorithms:

They can lead the system to a race condition.
 Dispatcher

Dispatcher module (invoked during every process

switch) gives control of the CPU to the process
selected by the short-term scheduler; this involves:
switching context
switching to user mode
jumping to the proper location in the user program to
restart that program

Dispatch latency – time it takes for the dispatcher to

stop one process and start another running.
 Scheduling Criteria
CPU utilization - keep the CPU as busy as possible. It is
defined as:
(processor busy time) / (processor busy time +
processor idle time)
Throughput – # of processes that complete their
execution per time unit.

Turnaround time – The interval from the time of

submission to the time of completion of a process.

Waiting time – amount of time a process has been waiting

in the ready queue (waiting for I/O device is not counted)

Response time – amount of time it takes from when a

request was submitted until the first response is
produced, not output.
 Performance Criteria

It is desirable that we,

Maximize CPU utilization

Maximize throughput
Minimize turnaround time
Minimize waiting time
Minimize response time
 CPU Scheduling Algorithms

First- Come, First-Served (FCFS) - Non preemptive

Shortest-Job-First (SJF) - Non preemptive
Shortest-Remaining-Time-First (SRTF) - Preemptive
Priority Scheduling - Non preemptive, Preemptive
Round Robin (RR) - Preemptive
Priority – RR (Multilevel Queue Scheduling, Multilevel Feedback
Queue Scheduling)

Operating System Concepts

 First-Come, First-Served (FCFS) Scheduling

This is the simplest one. In this algorithm the set of

ready processes is managed as FIFO (first-in-first-
out) Queue. The processes are serviced by the
CPU until completion in the order of their entering in
the FIFO queue.

Once allocated the CPU, each process keeps it until

releasing either due to termination or requesting
I/O.
Average waiting time under FCFS policy is often
quite long.

FCFS scheduling algorithm is nonpreemptive.

 Example: FCFS Scheduling
Consider the following set of processes that arrive at time 0, with the
length of the CPU burst given in milliseconds (ms).
Process CPU Burst Time (ms)
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1 P2 P3

0 24 27 30
W(P1) = 0; W(P2) = 24ms; W(P3 )= 27ms
Average waiting time: (0 + 24 + 27)/3 = 17ms
CPU utilization = (30/(30+0))x100 = 100 %
Gantt Chart is a bar chart that illustrates a particular schedule, including
the start and finish times of each of the participating processes.
 FCFS Scheduling (Cont.)

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

W(P1)= 6ms; W(P2) = 0; W(P3) = 3ms

Average waiting time: (6 + 0 + 3)/3 = 3ms
tat(P1)= 30ms; tat(P2) = 3ms; tat(P3) = 6ms
Much smaller wait time than previous case.
 Shortest-Job-First (SJF) Scheduling
Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest
next CPU burst time. If the next CPU bursts of two processes
are the same, FCFS scheduling is used to break the tie.
Two versions:
nonpreemptive – once CPU given to the process it cannot be
preempted until completes its CPU burst.
preemptive – if a new process arrives with CPU burst length less
than remaining time of current executing process, then preempt
the current one. This scheme is known as
Shortest-Remaining-Time-First (SRTF).
SJF is optimal – gives minimum average waiting time for a
given set of processes.
The main problem with the SJF algorithm is to know for each
process the next CPU burst time!!! However some techniques
exist to predict this next CPU burst time (could ask to the
user).
Another problem is that starvation of long processes may
occur.
 Example of Non-Preemptive SJF

Process Arrival Time CPU Burst Time(ms)

P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (non-preemptive)

P1 P3 P2 P4

0 7 8 12 16

W(P1) = 0; W(P2) = 8-2 = 6ms;

W(P3 ) = 7-4 = 3ms ; W(P4 ) = 12-5 = 7ms

Average waiting time = (0 + 6 + 3 + 7)/4 = 4ms

 Example of SJF
ProcessArri Arrival Time l CPU Burst Time(ms)
P1 0 6
P2 0 8
P3 0 7
P4 0 3

SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

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

 Example of Preemptive SJF (SRTF)
Process Arrival Time CPU Burst Time(ms)
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (preemptive)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

Process P1 is started at time 0, since it is the only process in the

queue. Process P2 arrives at time 2. The remaining time for process
P1 (5ms) is larger than the time required by process P2 (4ms), so
process P1 is preempted, and process P2 is scheduled.
W(P1) = (0-0)+(11-2)=9ms; W(P2) = (2-2)+(5-4)=1ms;
W(P3 )= 4-4=0; W(P4 )= 7-5=2ms
Average waiting time = (9 + 1 + 0 +2)/4 = 3ms
 Example of Shortest-remaining-time-first

Now we add the concepts of varying arrival times and preemption to the
analysis
ProcessAarri Arrival TimeT CPU Burst Time(ms)
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF 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 ms.

 Round Robin (RR) (preemptive)

This scheduling algorithm is designed specially for time

sharing systems. It is similar to FCFS scheduling, but
preemption is added to switch between processes.
Each process gets a small unit of CPU time (time
quantum), usually 10-100 milliseconds. After this time
has elapsed, the process is preempted and added to the
end of the ready queue.
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 at once. No process
waits more than (n-1)q time units.
Performance
q very large  FIFO
q small  q must be large with respect to context switch,
otherwise overhead is too high.
 Round Robin (continue)

The scheduler allocates the CPU to each process in the

ready queue for a time interval of up to 1 time quantum in
FIFO (circular) fashion. If the process still running at the
end of the quantum; it will be preempted from the CPU.

A context switch will be executed, and the process will be

put at the tail of the ready queue. Then the scheduler will
select the next process in the ready queue. However, if
the process has blocked or finished before the quantum
has elapsed, the scheduler will then proceed with the
next process in the ready queue.
 Example: RR with Time Quantum = 20
Consider the following set of processes that arrive at time 0 in the
order P1, P2, P3, P4, with the length of the CPU burst given in
milliseconds.

Process Burst Time(ms)

P1 53
P2 17
P3 68
P4 24

The Gantt chart is:

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

Example: RR with Quantum=10ms
Consider the following set of process that arrive at time 0 in the
order A,B,C,D with the following given CPU burst time. Find the
average waiting time with RR of quantum : 10 ms
Process CPU burst time (ms)
A 20
B 40
C 14
D 6

Gantt Chart:

A B C D A B C B B
0 10 20 30 36 46 56 60 70 80

W (A) = 36-10 =26 ms W (B) = (10-0) + (46-20) + (60-56)= 40 ms

W (C) = (20-0) + (56-30) = 46 ms W (D) = 30-0 = 30 ms
Average waiting time = (26+40+46+30) /4 = 142/4 = 35.5 ms
 Example: RR with Quantum = 10ms
Consider the following set of process that arrive at time 0 in the
order A,B,C,D with the following given CPU burst time. Find the
average waiting time with RR of quantum = 10 ms and context
switch time = 2ms
Process CPU burst time I/O CPU burst time
A 10 40 10
B 40 - -
C 14 - -
D 6 - -

A B C D B C A B B

0 10 12 22 24 34 36 42 44 54 56 60 62 72 74 84 86 96

idle A
0 10 50
Wait (A) = 62-50 = 12 ms Wait (B) = 12+22+20+2 = 56 ms
Wait (C) = 24 + 22 = 46 ms Wait (D) = 36 ms

Average waiting time = 150/4 = 37.5 ms

 Example of RR with Time Quantum = 4

Process Burst Time

P1 24
P2 3
P3 3
The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Typically, higher average turnaround than SJF, but better

response
q should be large compared to context switch time
q usually 10ms to 100ms, context switch < 10 microsecond
Time Quantum and Context Switch Time

Figure showing how smaller time quantum increases context

switches.
 Priority Scheduling
A priority number (integer) is associated with each
process

The CPU is allocated to the process with the highest

priority ((smallest or largest integer value may be
defined as the highest priority)
Preemptive
Nonpreemptive

SJF is priority scheduling where priority is the inverse of

predicted next CPU burst time

Problem  Starvation – low priority processes may never

execute

Solution  Aging – as time progresses increase the

priority of the process
 Example - Priority Scheduling
Process Arrival time CPU burst time Priority

A 0 100 3

B 0 10 1 5 highest
C 0 300 3 1 lowest
D 0 60 5

E 80 150 4

Non-preemptive priority Algorithm:

D A E C B

0 60 160 310 610 620

W (A) = 60ms, W (B) = 610ms, W (C) = 310ms, W (D) = 0 ms, W (E) = 80ms

Preemptive priority Algorithm (if a job come with high priority there is a switching):
D A E A C B

0 60 80 230 310 610 620

W(A) = 210 ms, W(B) = 610 ms, W(C) = 310 ms, W(D)=0ms, Wait (E) = 0 ms
 Example - Priority Scheduling

ProcessAarri Burst TimeT Priority

P1 10 3
P2 1 1 (highest)
P3 2 4
P4 1 5
P5 5 2

Priority scheduling Gantt Chart

P1 P2 P1 P3 P4
0 1 6 16 18 19

Average waiting time = 8.2 msec

 Multilevel Queue Scheduling
Another class of scheduling algorithms has been created for
situations in which processes are easily classified into different
groups(classes).
Among classes a priority scheduling algorithm is used, inside a
class RR is used.
A ready queue is used for each class.
The following shows a system with five priority classes where RR
is used in each class. As long as there are runnable processes in
priority class 5, just run each one for one quantum (i.e. round robin
fashion), and never bother with lower priority classes. If priority
class 5 in empty , then run the class 4 processes in round robin
fashion , and so on. If priorities are not adjusted from time to time,
lower priority classes may all starve.
While a class 3 process is running if a highest queue process
arrives, class 3 process would be preempted.
Time quantum value can be different for classes.
Each queue may have its own scheduling algorithm.
Multilevel Queue Scheduling

(Priority 5)

(Priority 1)
 Multilevel Queue Scheduling
Process Arrival time CPU burst time (ms) Priority
A 0 10 2
B 3 7 1
C 4 6 2
D 12 5 1
E 18 8 1

Assume that Quantum=4 ms for Queue 1 and Quantum =3 ms for Queue

2. Assume that Queue 1 has higher priority when compared to Queue 2.

A B B A D D C E E A C A C

0 3 7 10 12 16 17 18 22 26 29 32 34 36

W (A) = 24ms W (B) = 0ms W (C) = 26ms W (D) = 0ms

W (E) = 0ms W (F) = 10ms
Multilevel Feedback Queue Scheduling

Normally, when the multilevel queue scheduling algorithm is used,

processes are permanently assigned to a queue when they enter
the system.
The multilevel feedback queue scheduling algorithm allows a
process to move between queues.
The scheduler first executes all processes in Queue 1. Only when
Queue 1 is empty will it execute processes in Queue 2. Similarly,
processes in Queue 3 will be executed only if Queues 1 and 2 are
empty. A process that arrives for Queue 1 will preempt a process
in Queue 2.
A process entering the ready queue is put in Queue 1. If it does not
finish within one quantum, it is moved to the tail of Queue 2. If it
does not complete there in one quantum, it is then preempted and
put into Queue 3.
Multilevel Feedback Queue Scheduling

Queue 1

Queue 2

The figure above shows an example for multilevel feedback queue where
Queue 1 uses RR with Quantum = 8ms, Queue 2 uses RR with
Quantum = 16 and Queue 3 uses FCFS.
 Multilevel Feedback Queue Scheduling
Process Arrival time CPU burst time I/O CPU burst time
A 0 5 6 0
B 3 4 2 3
C 4 2 3 4
D 7 5 2 7
E 14 3 2 4

Assume Queue 1 with Quantum =4 ms and Queue 2 with Quantum =

7ms, both use Round Robin.

Queue_1 : ABCDBCEED
Queue_2 : AD

A B C D B C E A D E idle D
CPU
0 4 8 10 14 17 21 24 25 26 30 34 41

I/O idle B C idle E A D

0 8 10 13 24 26 32 34
 Thread Scheduling

❑ Distinction between user-level and kernel-level threads

❑ When threads supported, threads scheduled, not
processes
❑ Many-to-one and many-to-many models, thread library
schedules user-level threads to run on LWP
❑ Known as process-contention scope (PCS) since
scheduling competition is within the process
❑ Typically done via priority set by programmer
❑ Kernel thread scheduled onto available CPU is
system-contention scope (SCS) – competition
among all threads in system
 Pthread Scheduling

❑ API allows specifying either PCS or SCS during

thread creation
❑ PTHREAD_SCOPE_PROCESS schedules threads
using PCS scheduling
❑ PTHREAD_SCOPE_SYSTEM schedules threads using
SCS scheduling
❑ Can be limited by OS – Linux and macOS only
allow PTHREAD_SCOPE_SYSTEM
 Multiple-Processor Scheduling

❑ CPU scheduling more complex when multiple

CPUs are available
❑ Multiprocess may be any one of the following
architectures:
❑ Multicore CPUs
❑ Multithreaded cores
❑ NUMA systems
❑ Heterogeneous multiprocessing
 Multiple-Processor Scheduling

❑ Symmetric multiprocessing (SMP) is where each

processor is self scheduling.
❑ All threads may be in a common ready queue (a)
❑ Each processor may have its own private queue of
threads (b)
 Multicore Processors

❑ Recent trend to place multiple processor cores on

same physical chip
❑ Faster and consumes less power
❑ Multiple threads per core also growing
❑ Takes advantage of memory stall to make progress on
another thread while memory retrieve happens
 Multithreaded Multicore System

Each core has > 1 hardware threads.

If one thread has a memory stall, switch to another thread!

 Multithreaded Multicore System

❑ Chip-multithreading (CMT) assigns

each core multiple hardware threads.
(Intel refers to this as
hyperthreading.)

❑ On a quad-core system with 2

hardware threads per core, the
operating system sees 8 logical
processors.
 Multithreaded Multicore System

❑ Two levels of scheduling:

1. The operating system deciding

which software thread to run on a
logical CPU

2. How each core decides which

hardware thread to run on the
physical core.
 Multiple-Processor Scheduling –
Load Balancing

❑ If SMP, need to keep all CPUs loaded for

efficiency
❑ Load balancing attempts to keep workload evenly
distributed
❑ Push migration – periodic task checks load on
each processor, and if found pushes task from
overloaded CPU to other CPUs
❑ Pull migration – idle processors pulls waiting task
from busy processor
 Multiple-Processor Scheduling –
Processor Affinity

❑ When a thread has been running on one processor, the cache contents of that
processor stores the memory accesses by that thread.
❑ We refer to this as a thread having affinity for a processor (i.e. “processor
affinity”)
❑ Load balancing may affect processor affinity as a thread may be moved from
one processor to another to balance loads, yet that thread loses the contents of
what it had in the cache of the processor it was moved off of.
❑ Soft affinity – the operating system attempts to keep a thread running on the
same processor, but no guarantees.
❑ Hard affinity – allows a process to specify a set of processors it may run on.
 NUMA and CPU Scheduling

If the operating system is NUMA-aware, it will assign

memory closes to the CPU the thread is running on.
 Real-Time CPU Scheduling

❑ Can present obvious challenges

❑ Soft real-time systems – Critical real-time tasks
have the highest priority, but no guarantee as to
when tasks will be scheduled
❑ Hard real-time systems – task must be serviced
by its deadline
 Real-Time CPU Scheduling

❑ Event latency – the amount of time that elapses

from when an event occurs to when it is serviced.
❑ Two types of latencies affect performance
❑ Interrupt latency – time from arrival of interrupt to start
of routine that services interrupt
❑ Dispatch latency – time for schedule to take current
process off CPU and switch to another
Interrupt Latency
 Dispatch Latency

❑ Conflict phase of
dispatch latency:
❑ Preemption of any
process running in
kernel mode
❑ Release by low-
priority process of
resources needed
by high-priority
processes
 Priority-based Scheduling
❑ For real-time scheduling, scheduler must support
preemptive, priority-based scheduling
❑ But only guarantees soft real-time

❑ For hard real-time must also provide ability to meet

deadlines
❑ Processes have new characteristics: periodic
ones require CPU at constant intervals
❑ Has processing time t, deadline d, period p
❑ 0≤t≤d≤p
❑ Rate of periodic task is 1/p
 Operating System Examples

❑ Linux scheduling

❑ Windows scheduling

❑ Solaris scheduling
 Algorithm Evaluation
How to select CPU-scheduling algorithm for an OS?
Determine criteria, then evaluate algorithms
Takes a particular predetermined workload and defines the
performance of each algorithm for that workload
Consider 5 processes arriving at time 0, in the order given,
with the length of the CPU burst given in ms.

Consider the FCFS, SJF and RR(quantum = 10 ms)

scheduling algorithms for this set of processes. Which
algorithm would give the minimum average waiting time?
 Algorithm Evaluation

For each algorithm, calculate minimum average waiting time

Simple and fast, but requires exact numbers for input, applies
only to those inputs
FCFS is (0+10+39+42+49)/5=28ms:

Non-preemptive SJF is (10+32+0+3+20)/5=13ms:

RR is (0+32+20+23+40)/5=23ms:
 Queueing Models

❑ Describes the arrival of processes, and CPU and I/O bursts

probabilistically
❑ Commonly exponential, and described by mean
❑ Computes average throughput, utilization, waiting time, etc
❑ Computer system described as network of servers, each with queue of
waiting processes
❑ Knowing arrival rates and service rates
❑ Computes utilization, average queue length, average wait time, etc
 Little’s Formula

❑ n = average queue length

❑ W = average waiting time in queue
❑ λ = average arrival rate into queue
❑ Little’s law – in steady state, processes leaving queue must equal
processes arriving, thus:
n=λxW
❑ Valid for any scheduling algorithm and arrival distribution
❑ For example, if on average 7 processes arrive per second, and
normally 14 processes in queue, then average wait time per process =
2 seconds
 Simulations

❑ Queueing models limited

❑ Simulations more accurate
❑ Programmed model of computer system
❑ Clock is a variable
❑ Gather statistics indicating algorithm performance
❑ Data to drive simulation gathered via
❑ Random number generator according to probabilities
❑ Distributions defined mathematically or empirically
❑ Trace tapes record sequences of real events in real systems
Evaluation of CPU Schedulers by Simulation
 Implementation
❑ Even simulations have limited accuracy
❑ Just implement new scheduler and test in real systems
❑ High cost, high risk
❑ Environments vary
❑ Most flexible schedulers can be modified per-site or per-system
❑ Or APIs to modify priorities
❑ But again environments vary