Unit 9: Principles of Scheduling

Unit 9: Principles of Scheduling (9hrs)

Introduction
In this unit, you will be learning the principles of scheduling algorithm and its role in the
operating system. A Process Scheduler schedules different processes to be assigned to the CPU
based on particular scheduling algorithms. There are four popular process scheduling
algorithms which we are going to discuss in this unit −
First-Come, First-Served (FCFS) Scheduling
Shortest-Job-First (SJF) Scheduling
Priority Scheduling
Round Robin(RR) Scheduling
These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are
designed so that once a process enters the running state, it cannot be preempted until it
completes its allotted time, whereas the preemptive scheduling is based on priority where a
scheduler may preempt a low priority running process anytime when a high priority process
enters into a ready state.
The process scheduling activity of the process manager that handles the removal of the
running process from the CPU and the selection of another process on the basis of a particular
strategy.
Process scheduling is an essential part of a Multiprogramming operating systems. Such
operating systems allow more than process to be loaded into the executable memory at a time
and the loaded process shares the CPU using time multiplexing.

Unit Learning Outcomes

At the end of this unit, you will be able to:
a. Discuss CPU scheduling and its relevance to operating systems;
b. Explain the general goals of CPU scheduling;
c. Describe the differences between preemptive and non-preemptive scheduling; and
d. Discuss the different types of scheduling algorithms.

Topic 1. CPU Scheduling

Learning Objectives
At the end of this session, you will be able to:
a. Define CPU scheduling;
b. Explain the role of CPU scheduling for maximum optimization in the operating
system; and
c. Discuss the function of Dispatcher as a component of CPU scheduling.

1
 Unit 9: Principles of Scheduling

Presentation of Content

What is CPU Scheduling?

CPU scheduling is a process which allows one process to use the CPU while the execution of
another process is on hold (in waiting state) due to unavailability of any resource like I/O etc,
thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient,
fast and fair.
Whenever the CPU becomes idle, the operating system must select one of the processes in
the ready queue to be executed. The selection process is carried out by the short-term scheduler
(or CPU scheduler). The scheduler selects from among the processes in memory that are ready
to execute, and allocates the CPU to one of them.
Important CPU scheduling Terminologies
• Burst Time/Execution Time: It is a time required by the process to complete
execution. It is also called running time.
• Arrival Time: when a process enters in a ready state
• Finish Time: when process complete and exit from a system
• Multiprogramming: A number of programs which can be present in memory at
the same time.
• Jobs: It is a type of program without any kind of user interaction.
• User: It is a kind of program having user interaction.
• Process: It is the reference that is used for both job and user.
• CPU/IO burst cycle: Characterizes process execution, which alternates between
CPU and I/O activity. CPU times are usually shorter than the time of I/O.
CPU Scheduling Criteria
A CPU scheduling algorithm tries to maximize and minimize the following:

Maximize:
CPU utilization: CPU utilization is the main task in which the operating system needs to make
sure that CPU remains as busy as possible. It can range from 0 to 100 percent. However, for
the RTOS, it can be range from 40 percent for low-level and 90 percent for the high-level
system.

2
 Unit 9: Principles of Scheduling

Throughput: The number of processes that finish their execution per unit time is known
Throughput. So, when the CPU is busy executing the process, at that time, work is being done,
and the work completed per unit time is called Throughput.
Minimize:
Waiting time: Waiting time is an amount that specific process needs to wait in the ready queue.
Response time: It is an amount to time in which the request was submitted until the first
response is produced.
Turnaround Time: Turnaround time is an amount of time to execute a specific process. It is the
calculation of the total time spent waiting to get into the memory, waiting in the queue and,
executing on the CPU. The period between the time of process submission to the completion
time is the turnaround time.
Interval Timer
Timer interruption is a method that is closely related to preemption. When a certain process
gets the CPU allocation, a timer may be set to a specified interval. Both timer interruption and
preemption force a process to return the CPU before its CPU burst is complete.
Most of the multi-programmed operating system uses some form of a timer to prevent a process
from tying up the system forever.
CPU Scheduling: Dispatcher
Another component involved in the CPU scheduling function is the Dispatcher. The dispatcher
is the module that gives control of the CPU to the process selected by the short-term scheduler.
This function involves:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program from where
it left last time.
The dispatcher should be as fast as possible, given that it is invoked during every process
switch. The time taken by the dispatcher to stop one process and start another process is known
as the Dispatch Latency. Dispatch Latency can be explained using the below figure:

3
 Unit 9: Principles of Scheduling

Types of CPU Scheduling

CPU scheduling decisions may take place under the following four circumstances:
1. When a process switches from the running state to the waiting state (for I/O request or
invocation of wait for the termination of one of the child processes).
2. When a process switches from the running state to the ready state (for example, when
an interrupt occurs).
3. When a process switches from the waiting state to the ready state (for example,
completion of I/O).
4. When a process terminates.
In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one
exists in the ready queue) must be selected for execution. There is a choice, however in
circumstances 2 and 3.
When Scheduling takes place only under circumstances 1 and 4, we say the scheduling
scheme is non-preemptive; otherwise the scheduling scheme is preemptive.

Topic 2. Preemptive and Non-preemptive Scheduling Algorithm

Learning Objectives
At the end of this session, you will be able to:
a. Discuss the different scheduling algorithms and synchronization techniques;
b. Draw the Gantt chart of each scheduling algorithm; and
c. Compute the average waiting time and turnaround time for each process.

Presentation of Content
Classification of Scheduling Algorithm
Non-Preemptive Scheduling
Under non-preemptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by switching
to the waiting state.
This scheduling method is used by the Microsoft Windows 3.1 and by the Apple
Macintosh operating systems.
It is the only method that can be used on certain hardware platforms, because It does
not require the special hardware (for example: a timer) needed for preemptive
scheduling.

4
 Unit 9: Principles of Scheduling

Preemptive Scheduling
In this type of Scheduling, the tasks are usually assigned with priorities. At times it is
necessary to run a certain task that has a higher priority before another task although it
is running. Therefore, the running task is interrupted for some time and resumed later
when the priority task has finished its execution.
A good scheduler should optimize the following performance criteria:
• Turnaround time – the interval from the time a process is submitted until it is
completed; compute for the time the process is in the ready queue, executing & doing
I/O;
– Time Finished minus Arrival Time
• Response time – for an interactive process, this refers to the time between the
submission of the process until it starts responding.

• Waiting time – the total amount of time a process spends in the ready queue;
– Turnaround Time minus CPU Burst

CPU Scheduling Algorithm

1. First Come First Serve

In the "First come first serve" scheduling algorithm, as the name suggests, the process
which arrives first, gets executed first, or we can say that the process which requests the
CPU first, gets the CPU allocated first.

First Come First Serve, is just like FIFO (First in First out) Queue data structure, where
the data element which is added to the queue first, is the one who leaves the queue first.

A perfect real life example of FCFS scheduling is buying tickets at ticket counter.

Calculating Average Waiting Time

• For every scheduling algorithm, Average waiting time is a crucial parameter
to judge its performance.
• AWT or Average waiting time is the average of the waiting times of the
processes in the queue, waiting for the scheduler to pick them for execution.
• Lower the Average Waiting Time, better the scheduling algorithm.
Example 1:
Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in
the same order, with Arrival Time 0, and given Burst Time, let's find the average
waiting time using the FCFS scheduling algorithm.

5
 Unit 9: Principles of Scheduling

Gantt Chart:

Compute for the Average Turnaround Time

Turnaround time
(Time Finished minus Arrival Time)

P1 = 21 – 0 = 21ms
P2 = 24 – 0 = 24ms
P3 = 30 – 0 = 30ms
P4 = 32 – 0 = 32ms

The average turnaround time is

(21 + 24 + 30 + 32) / 4 = 107 / 4 = 26.85ms

Compute for the Average Waiting Time

Waiting time
(Turnaround Time minus CPU Burst)

P1 = 21 – 21 = 0ms
P2 = 24 – 3 = 21ms
P3 = 30 – 6 = 24ms
P4 = 32 – 2 = 30ms

The average waiting time is

(0 + 21 + 24 + 30) / 4 = 75 / 4 = 18.75ms

• For the above given processes, first P1 will be provided with the CPU resources,
• Hence, waiting time for P1 will be 0
• P1 requires 21ms for completion, hence waiting time for P2 will be 21ms
• Similarly, waiting time for process P3 will be execution time of P1 + execution time
for P2, which will be (21 + 3)ms = 24ms.
• For process P4 it will be the sum of execution times of P1, P2 and P3.
• The GANTT chart above perfectly represents the waiting time for each process.
• Here we have simple formula for calculating various times for given processes:

6
 Unit 9: Principles of Scheduling

• Completion Time: Time taken for the execution to complete, starting from arrival
time.
• Turn Around Time: Time taken to complete after arrival. In simple words, it is
the difference between the Completion time and the Arrival time.
• Waiting Time: Total time the process has to wait before it's execution begins. It is
the difference between the Turn Around time and the Burst time of the process.

Example 2:

Gantt Chart:

Compute for the Average Turnaround Time

Turnaround time
(Time Finished minus Arrival Time)

P1 = 8 – 0 = 8ms
P2 = 12 – 3 = 9ms
P3 = 17 – 4 = 13ms
P4 = 20 – 6 = 14ms
P5 = 22 – 10 = 12ms

The average turnaround time is

(8 + 9 + 13 + 14 + 12) / 5 = 56 / 5 = 11.2ms

Compute for Average Waiting Time

Waiting time
(Turnaround Time minus CPU Burst)

P1 = 8 – 8 = 0ms
P2 = 9 – 4 = 5ms
P3 = 13 – 5 = 8ms
P4 = 14 – 3 = 11ms
P5 = 12 – 2 = 10ms

The average waiting time is

(0 + 5 + 8 + 11 + 10) / 5 = 34 / 5 = 6.8ms

7
 Unit 9: Principles of Scheduling

2. Shortest Job First Scheduling Algorithm (Non preemptive)

• This is a non-preemptive, pre-emptive scheduling algorithm.

• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in
advance.
• Impossible to implement in interactive systems where required CPU time is
not known.
• The processer should know in advance how much time process will take.

Example 1:

Consider the below processes available in the ready queue for execution,
with arrival time as 0 for all and given burst times.

Gantt Chart:

Compute for the Average Turnaround Time

Turnaround time
(Time Finished minus Arrival Time)

P1 = 32 – 0 = 32ms
P2 = 5 – 0 = 5ms
P3 = 11 – 0 = 11ms
P4 = 2 – 0 = 2ms

The average turnaround time is

(32 + 5 + 11 + 2) / 4 = 50 / 4 = 12.5ms

Compute for the Average Waiting Time

Waiting time
(Turnaround Time minus CPU Burst)

8
 Unit 9: Principles of Scheduling

P1 = 32 – 21 = 11ms
P2 = 5 – 3 = 2ms
P3 = 11 – 6 = 5ms
P4 = 2 – 2 = 0ms

The average waiting time is

(11 + 2 + 5 + 0) / 4 = 18 / 4 = 4.5ms

Example 2:

Gantt Chart
P1 P4 P5 P2 P3
0 8 11 13 17 22

Compute for the Average Turnaround Time

Turnaround time
(Time Finished minus Arrival Time)

P1 = 8 – 0 = 8ms
P2 = 17 – 3 = 14ms
P3 = 22 – 4 = 18ms
P4 = 11 – 6 = 5ms
P5 = 13 – 10 = 3ms

The average turnaround time is

(8 + 14 + 18 + 5 + 3) / 5 = 48 / 5 = 9.6ms

Compute for the Average Waiting Time

Waiting time
(Turnaround Time minus CPU Burst)

P1 = 8 – 8 = 0ms
P2 = 14 – 4 = 10ms
P3 = 18 – 5 = 13ms
P4 = 5 – 3 = 2ms
P5 = 3 – 2 = 1ms

The average waiting time is

(0 + 10 + 13 + 2 + 1) / 5 = 26 / 5 = 5.2ms

9
 Unit 9: Principles of Scheduling

3. Shortest Job First Scheduling Algorithm(Preemptive)

• In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they
arrive, but as a process with short burst time arrives, the existing process is
preempted or removed from execution, and the shorter job is executed first.

Example 1

Gantt Chart
P1 P2 P4 P5 P1 P3
0 3 7 10 12 17 22

Compute for the Average Turnaround Time

Turnaround time
(Time Finished minus Arrival Time)

P1 = 17 – 0 = 17ms
P2 = 7 – 3 = 4ms
P3 = 22 – 4 = 18ms
P4 = 10 – 6 = 4ms
P5 = 12 – 10 = 2ms

The average turnaround time is

(17 + 4 + 18 + 4 + 2) / 5 = 45 / 5 = 9ms

Compute for the Average Waiting Time

Waiting time
(Turnaround Time minus CPU Burst)

P1 = 17 – 8 = 9ms
P2 = 4 – 4 = 0ms
P3 = 18 – 5 = 13ms
P4 = 4 – 3 = 1ms
P5 = 2 – 2 = 0ms

The average waiting time is

(9 + 0 + 13 + 1 + 0) / 5 = 23 / 5 = 4.6ms

4. Priority Scheduling Algorithm

• Each process is assigned a priority and the CPU scheduler selects the process in the
ready queue with the highest priority to execute next. Note: The lower the number,
the higher the priority.

10
 Unit 9: Principles of Scheduling

Arrival CPU
Process ID Priority
Time Burst
P1 0 8 4
P2 3 4 3
P3 4 5 1
P4 6 3 2
P5 10 2 2

Gantt Chart (Non preemptive)

P1 P3 P4 P5 P2
0 8 13 16 18 22

Compute for the Average Turnaround Time

(Time Finished minus Arrival Time)

P1 = 8 – 0 = 8ms
P2 = 22 – 3 = 19ms
P3 = 13 – 4 = 9ms
P4 = 16 – 6 = 10ms
P5 = 18 – 10 = 8ms

The average turnaround time is

(8 + 19 + 9 + 10 + 8)/5 = 54/5 = 10.8ms

Compute for the Average Waiting time

(Turnaround Time minus CPU Burst)

P1 = 8 – 8 = 0ms
P2 = 19 – 4 = 15ms
P3 = 9 – 5 = 4ms
P4 = 10 – 3 = 7ms
P5 = 8– 2 = 6ms

The average waiting time is

(0 + 15 + 4 + 7 + 6)/5 = 32/5 = 6.4ms

Gantt chart (Preemptive)

P1 P2 P3 P4 P5 P2 P1
0 3 4 9 12 14 17 22

Compute for the Average Turnaround time

(Time Finished minus Arrival Time)

P1 = 22 – 0 = 22ms
P2 = 17 – 3 = 14ms
P3 = 9 – 4 = 5ms
P4 = 12 – 6 = 6ms
P5 = 14 – 10 = 4ms

11
 Unit 9: Principles of Scheduling

The average turnaround time is

(22 + 14 + 5 + 6 + 4)/5 = 51/5 = 10.2ms

Compute for the Average Waiting time

(Turnaround Time minus CPU Burst)

P1 = 22 – 8 = 14ms
P2 = 14 – 4 = 10ms
P3 = 5 – 5 = 0ms
P4 = 6 – 3 = 3ms
P5 = 4 – 2 = 2ms

The average waiting time is

(14 + 10 + 0 + 3 + 2)/5 = 29/5 = 5.8ms

5. Round Robin Algorithm (RR)

• The processes are selected on a first-come, first-served basis. However, each process
is given a time limit to execute at the CPU.

Using the same given, assume a time quantum of 3ms.

Arrival CPU
Process ID Priority
Time Burst
P1 0 8 4
P2 3 4 3
P3 4 5 1
P4 6 3 2
P5 10 2 2

Gantt chart

P1 P2 P1 P3 P4 P2 P1 P5 P3
0 3 6 9 12 15 16 18 20 22

Compute for the Average Turnaround time

(Time Finished minus Arrival Time)

P1 = 18 – 0 = 18ms
P2 = 16 – 3 = 13ms
P3 = 22 – 4 = 18ms
P4 = 15 – 6 = 9ms
P5 = 20 – 10 = 10ms

The average turnaround time is

(18 + 13 + 18 + 9 + 10)/5 = 68/5 = 13.6ms

12
 Unit 9: Principles of Scheduling

Compute for the Average Waiting time

(Turnaround Time minus CPU Burst)

P1 = 18 – 8 = 10ms
P2 = 13 – 4 = 9ms
P3 = 18 – 5 = 13ms
P4 = 9 – 3 = 6ms
P5 = 10– 2 = 8ms

The average waiting time is

(10 + 9 + 13 + 6 + 8)/5 = 46/5 = 9.2ms

UNIT SUMMARY
In this unit, you have covered the following main points:
 CPU scheduling is a process of determining which process will own CPU for execution
while another process is on hold.
 In Preemptive Scheduling, the tasks are mostly assigned with their priorities.
 In the Non-preemptive scheduling method, the CPU has been allocated to a specific
process.
 Burst time is a time required for the process to complete execution. It is also called
running time.
 CPU utilization is the main task in which the operating system needs to make sure that
CPU remains as busy as possible
 The number of processes that finish their execution per unit time is known Throughput.
 Waiting time is an amount that specific process needs to wait in the ready queue.
 It is an amount to time in which the request was submitted until the first response is
produced.
 Turnaround time is an amount of time to execute a specific process.
 Timer interruption is a method that is closely related to preemption,
 A dispatcher is a module that provides control of the CPU to the process.
 The different types of process scheduling algorithms are:
 First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling 3) Shortest
Remaining Time 4) Priority Scheduling 5) Round Robin Scheduling 6) Multilevel
Queue Scheduling
 In the First Come First Serve method, the process which requests the CPU gets the CPU
allocation first.
 In Priority Scheduling the scheduler selects the tasks to work as per the priority.
 In this Round robin scheduling works on principle, where each person gets an equal
share of something in turn
 In Shortest job first the shortest execution time should be selected for execution next
 The CPU uses scheduling to improve its efficiency.

13
 Unit 9: Principles of Scheduling

REFERENCES
Abraham Silberschatz, Greg Gagne and Peter Baer Galvin, “Operating System Concepts
Eight Edition”, Chapter 5
Online References
https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/ (Retrieved July 2020)
https://www.guru99.com/cpu-scheduling-algorithms.html/(Retrieved July 2020)

14