CS 334: Principles of Operating

System

Lecture 3: Process Scheduling

 Outline
• Introduction
• Non-pre-emptive scheduling
• Pre-emptive scheduling
• Scheduling algorithms
• Multi-level scheduling algorithms
 Introduction
• Process scheduling is an OS mechanism that allocates
and manages CPU time to multiple processes running
simultaneously
• It is the mechanism used to implement OS advanced
features such as multi-programming, multi-user and
multi-tasking
 Introduction
• In a multi-tasking system, a user can open many
applications and run them in parallel with acceptable
response times
 Introduction
• In a multiuser system, multiple numbers of users can
access different resources of a computer at the same
time and with acceptable response time.
 Introduction
• In real-time systems, processes are executed within
prescribed deadlines.
• A higher-priority process (with a closer deadline) must
always be able to pre-empt the low priority one
 Introduction
Several events can trigger process
scheduling
i. When an executing process
finishes its execution and exits
ii. When the executing process needs
to wait for an I/O or resource
iii. When an I/O or resource being
used by any process is released
iv. When a process finishes its
allotted time slice
v. When an executing process
creates a child process
vi. When a newly added process in
the ready queue has higher
priority compared to that of the
running process
vii. If there is an error or exception in
the process or hardware
viii. When there is need to suspend
some blocked process and make
space for a new process
 Introduction
In the previous lecture we discussed the three levels of
scheduling
i. Long term scheduling: For scheduling jobs entering a
system for the first time
ii. Medium term scheduling: Swapping processes back
and forth between the blocked queue and blocked-
suspend queue
iii. Short term scheduling: Selecting the next process to
be executed by the processor

In this lecture we will be referring to the Short-Term

Scheduling
 Scheduling Types
There are two main types of scheduling
i. Pre-emptive
ii. Non-pre-emptive scheduling

NON-PREEMPTIVE
 Scheduling Types
Non-pre-emptive scheduling
• A process assigned to processor is allowed to execute to
completion.
• The system cannot take away the processor from the
process until it exits or voluntarily release the
processor, for example, when waiting for I/O
CPU

Non-pre-emptive
Schedular
 Scheduling Types
Non-pre-emptive scheduling
• Disadvantage: A long process can hog a system for a long
time blocking other ready processes from executing

CPU

Non-pre-emptive
Schedular
 Scheduling Types
Pre-emptive
• A running process can be interrupted in between.
• The interrupted process is put back into the ready
queue and will be re-scheduled according to the
scheduling policy
CPU
 Scheduling Types
Pre-emption takes place in the following situations:
i. A timer interrupt occurs.
ii. When a new process with higher priority arrives in the
ready queue.
iii. When a resource or I/O being waited upon is released
 Scheduling Types
Pre-emptive
• Pre-emptive scheduling is used to implement features
like multi-user, multi-tasking and real time systems,
where more than one user process needs to get
computing resources.
• A timer clock is implemented to send interrupts to the
running process after a fixed period of time.
• For real time systems, higher priorities are assigned to
critical modules so that the critical processes can pre-
empt the less critical running process
 Scheduling Types
Advantage of pre-emptive scheduling
• Better process management in a multiprogramming and
multiuser environment

Disadvantages of pre-emptive scheduling

• High cost/complexity in implementation due to addition
of timer clock
• Reduced CPU performance due to time wasted in the
frequent context switching
 Scheduling Algorithms
• Scheduling algorithms are used by the operating system
to manage the execution of processes
• Different scheduling algorithms are available
 Scheduling Algorithms
Design Requirements
Scheduling algorithms are designed to satisfy one of the
following requirements

1. Waiting Time
• The total time spent in the ready queue by a process.
• Scheduling algorithms are designed to have a minimum
waiting time.

2. Response Time
• The time period between the submission of a process
and the first response given by the process to the user.
• Scheduling algorithms are designed to have a response
time that is within a prescribed range.
 Scheduling Algorithms
Design Requirements
3. Turnaround Time
• The time elapsed between the submission of a job and
its termination is called the turnaround time.
• It includes the time spent in waiting in the ready queue,
blocked queue and the execution time.
• Scheduling algorithms are designed for a minimum
turnaround time.
 Scheduling Algorithms
Design Requirements

4. Throughput
• The number of processes completed in a unit time.
• Scheduling algorithm are designed to maximize the
throughput of the system.

5. CPU Utilization
• The percentage of time that the CPU is busy in executing
the processes.
• The fundamental requirement is that the processor
should be busy most of the time.
 Scheduling Algorithms
Design Requirements

6. Fairness
• All processes in the system should get a chance to the
CPU, lower priority processes should not be ignored
indefinitely.
• A scheduling algorithm should not allow any process to
starve.

7. Balance
• At a particular instant of time, all resources should be
used in balance.
• A scheduling algorithm should select a proper mix of
CPU-bound and I/O-bound processes
 Scheduling Algorithms
First Come First Served (FCFS)
• The process that comes first to the ready queue will be
served first.
• The arriving process is added onto the tail of the queue
and the process at the head of the queue is dispatched
to the processor for execution.
• In this way, a ready queue is implemented as a linked list
wherein the order of arrival of the processes is
maintained with the simple logic of first in, first out
(FIFO).
• This scheduling policy is non pre-emptive, a process
which has arrived first will be executed first, to its
completion
• A running process is moved back to the tail of the ready
queue if it gives up the CPU.
 Scheduling Algorithms
First Come First Served (FCFS)
Example 3.1
 Scheduling Algorithms
First Come First Served (FCFS)
Example 3.1 solution
Process Arrival Execution Execution Waiting Turn Normalized
Time Time (x) Start Time Time around Turn
Time (t) around
Time (t/x)
P1 0 5 0 0 5 1
P2 2 4 5 3 7 1.75
P3 3 7 9 6 13 1.85
P4 5 6 16 11 17 2.84
Average Average Average
waiting turnaround normalized
time = 5 time = 10.5 turnaround
time = 1.86
 Scheduling Algorithms
First Come First Served (FCFS)
Advantages
Simple to implement

Disadvantages
• With no pre-emption, it cant be used in multi-user or
real-time systems
• Shorter processes surfer longer waiting times due to
long processes
 Scheduling Algorithms
Priority Scheduling
• The order of arrival of processes does not matter.
• This algorithm is pre-emptive, when a process with
higher priority has arrived late it will be executed first
according to its priority.
• Priorities are defined as a number associated with a
process.
• In most cases, lower numbers are considered as high
priorities but some systems implement a different
number scheme
• Disadvantages: Low priority processes may be starved
 Scheduling Algorithms
Priority Scheduling
Example 3.2
 Scheduling Algorithms
Priority Scheduling
Example 3.2 solution
Process Priority Arrival Execution Execution Waiting Turn Normalize
Time Time (x) Start Time Time around d Turn
Time (t) around
Time (t/x)
P1 2 0 5 0,6 4 9 1.8
P2 1 2 4 2 0 4 1
P3 3 3 7 9 6 13 1.85
P4 4 5 6 16 11 17 2.84
Average Average Average
waiting turnaroun normalize
time = d time = d
5.25 10.75 turnaroun
d time =
1.87
 Scheduling Algorithms
Shortest Process Next (SPN)
• The process with the shortest execution time is executed
first.
• After a given instance of time, processes are compared
to get short processes.
• SPN is a non-pre-emptive scheduling algorithm. If a
process with the shortest execution time appears, it
cannot pre-empt a process with longer execution time.
• Disadvantage: Long processes can be starved
 Scheduling Algorithms
Shortest Process Next (SPN)
Example 3.3
 Scheduling Algorithms
Shortest Process Next (SPN)
Example 3.3 solution
Process Arrival Execution Execution Waiting Turn Normalized
Time Time (x) Start Time Time around Turn
Time (t) around
Time (t/x)
P1 0 5 0 0 5 1
P2 2 4 5 3 7 1.75
P3 3 7 9 12 19 2.7
P4 5 6 15 4 10 1.67
Average Average Average
waiting turnaround normalized
time = 4.75 time = turnaround
10.25 time = 1.78
 Scheduling Algorithms
Shortest Remaining Time Next (SRN)
• This algorithm gives higher priority to shorter processes
as SPN, but it is a pre-emptive version of SPN.
• The process with the shortest execution time will always
pre-empt other processes.
• The criteria for pre-emption is based on the remaining
execution time of the processes.
 Scheduling Algorithms
Shortest Remaining Time Next (SRN)
Example 3.4
 Scheduling Algorithms
Shortest Remaining Time Next (SRN)
Example 3.4 solution
Process Arrival Time Execution Execution Waiting Turn around Norm. Turn
Time (x) Start Time Time Time (t) Around Time (t/x)

P1 0 9 0,13 12 21 2.34
P2 1 5 1,5 3 8 1.6
P3 2 3 2 0 3 1
P4 3 4 9 6 10 2.5
Av = 5.25 Av = 10.5 Av = 1.86

SRN
 Scheduling Algorithms
Round Robin Scheduling (RR)
• The scheduling methods discussed so far do not
guarantee fair response times to all processes hence can
cause starvation to some processes
• With FCFS, tasks are processed according to the order of
their arrivals. A process arriving late may not get
response for a long time especially if earlier processes
are longer.
• With Priority scheduling, low priority processes can wait
for longer times before getting access to a processor
• With SPN/SRN, long processes may need to wait for a
long period before getting access to a processor
 Scheduling Algorithms
Round Robin Scheduling (RR)
• With round robin algorithm, each arriving process gets
the same amount of time for execution.
• If each process gets the same processor time, neither
the short nor long process can suffer from starvation.
• To implement the round robin algorithm, the following
design issues are considered
i) The ready queue is maintained as a FIFO queue.
ii) A fixed time period is allotted to every arriving
process in the queue. This time period is known as time
slice or time quantum.
 Scheduling Algorithms
Round Robin Scheduling (RR)
iii) The first arriving process is selected and dispatched
to the processor. But if it is not able to complete its
execution within its time slice, then an interrupt is
generated.
iv) As soon as the timer interrupt arrives, the running
process is stopped temporarily, and placed back in the
ready queue at the end of the queue.
v) The scheduler selects another process from the
queue and dispatches it to the processor. It is executed
until the allotted time slice expires.
vi) When a process finishes before the time slice
expires, the timer will stop and send the interrupt
signal, so that the next process can be scheduled.
 Scheduling Algorithms
Round Robin Scheduling (RR)
Example 3.5
 Scheduling Algorithms
Round Robin Scheduling (RR)
Example 3.5 solution
Process Arrival Executio Execution Waiting Turn Normalized
Time n Time Start Time Time around Turn
(x) Time (t) around
Time (x/t)
P1 0 9 0,8,15,18,20 12 21 2.34
P2 1 5 2,10,17 12 17 3.4
P3 2 3 4,12 8 11 3.67
P4 3 4 6,13 8 12 3
Average Average Average
waiting turnaround normalized
time = 10 time = turnaround
15.25 time = 3.10
 Scheduling Algorithms
Round Robin Scheduling (RR)
• Optimum values of the time quantum must be selected
for good performance of the RR algorithm
• If the time quantum chosen is too large, the response
time of processes will increase
• if it is too small, context switch time will increase due to
the frequent process switching
• The quantum time should not be too long or too short,
the rule of thumb below can be used in selecting the
quantum time
i. 80% of the CPU bursts should be smaller than the
time quantum.
ii. Context switch time should be 10% or less of time
quantum.
 Scheduling Algorithms
Highest Response Ratio Next Scheduling (HRRN)
• A metric called response ratio is used for making
scheduling decision
𝑃𝑟𝑜𝑐𝑒𝑠𝑠 𝑡𝑖𝑚𝑒 𝑒𝑙𝑎𝑝𝑠𝑒𝑑 𝑖𝑛 𝑡ℎ𝑒 𝑠𝑦𝑠𝑡𝑒𝑚
response ratio =
𝐶𝑃𝑈 𝑡𝑖𝑚𝑒 𝑐𝑜𝑛𝑠𝑢𝑚𝑒𝑑 𝑏𝑦 𝑡ℎ𝑒 𝑝𝑟𝑜𝑐𝑒𝑠𝑠
• The response ratio indicates how much service a process
has received.
• Higher ratio indicates a process has received less service
and needs to get access to the CPU immediately.
• The system schedule a process with the highest
response ratio.
• The HRRN algorithm distributes the processor time more
fairly when compared to the simple round robin
algorithm
 Scheduling Algorithms
Highest Response Ratio Next Scheduling (HRRN)
Example 3.6
 Scheduling Algorithms
Highest Response Ratio Next Scheduling (HRRN)
Example 3.6 Solution
RR scenario
Process Arrival Time Execution Execution Start Waiting Turn around Normalized
Time (x) Time Time Time (t) Turn around
Time (x/t)

P1 0 3 0,1,8 6 9 3
P2 2 3 2,9,12 8 11 3.67
P3 3 2 3,4 0 2 1
P4 5 4 5,6,10,13 5 9 2.25
P5 7 2 7,11 3 5 2.5
Average Average Average
waiting time turnaround normalized
= 4.4 time = 7.2 turnaround
time = 2.484
 Scheduling Algorithms
Highest Response Ratio Next Scheduling (HRRN)
Example 3.6 Solution
HRRN scenario
Response ratio calculation
 Scheduling Algorithms
Highest Response Ratio Next Scheduling (HRRN)
Example 3.6 Solution
HRRN scenario
Process Arrival Time Execution Execution Start Waiting Turn around Normalized
Time (x) Time Time Time (t) Turn around
Time (x/t)

P1 0 3 0,1,4 2 5 1.67
P2 2 3 2,6,10 6 9 3
P3 3 2 3,8 4 6 3
P4 5 4 5,9,12,13 5 9 2.25
P5 7 2 7,11 3 5 2.5
Average Average Average
waiting time turnaround normalized
=4 time = 6.8 turnaround
time = 2.484
 Scheduling Algorithms
Multi level Queue Scheduling
• The basic idea behind multiple queues is that all
processes are not of the same nature.
• Processes can be categorized into:
i. Interactive processes
ii. Non-interactive processes
iii. CPU-bound processes
iv. I/O-bound processes
v. Foreground processes
vi. Background processes

• Instead of a single ready queue storing all the processes,

there are multiple queues with different levels.
• Each queue store processes of the same category
• Queues are assigned different priorities
 Scheduling Algorithms
Multi level Queue Scheduling
• Instead of a single ready queue storing all the processes,
there are multiple queues with different levels.
• Each queue store processes of the same category
• Scheduling is done
i. Among the queues.
ii. Between the processes in the selected queue.
• Interactive processes demand very
quick response time and have high
priority.
• I/O-bound processes are less
important hence stored in a second
queue.
• Background processes are of lowest
priority and are stored in a third
queue.
• Each queue has an absolute priority
over the one after it.
• If there is a process in the first
queue, any process of the second
queue cannot execute until the first
queue is empty.
 Home Work
1. Go to https://teach-sim.com/tutorials/
2. Perform HW 2:
Investigating Process Scheduling 1
Investigating Process Scheduling 2
3. Upload the results (1 per group) in the LMS