UNIT 2
CPU Scheduling
CPU scheduling is a method process or task that the CPU will run at any given moment. It
is an essential part of modern operating systems as it enables multiple processes to run
at the same time on the same processor. In short, the CPU scheduler decides the order
and priority of the processes to run and allocates the CPU time based on various
parameters such as CPU usage, throughput, turnaround, waiting time, and response time.
CPU scheduling is essential for the system’s performance and ensures that processes are
executed correctly and on time. Different CPU scheduling algorithms have other
properties and the choice of a particular algorithm depends on various factors. Many
criteria have been suggested for comparing CPU scheduling algorithms.
Criteria of CPU Scheduling
CPU Scheduling has several criteria. Some of them are mentioned below.
CPU utilization
The main objective of any CPU scheduling algorithm is to keep the CPU as busy as
possible. Theoretically, CPU utilization can range from 0 to 100 but in a real-time system,
it varies from 40 to 90 percent depending on the load upon the system.
Throughput
A measure of the work done by the CPU is the number of processes being executed and
completed per unit of time. This is called throughput.
Turnaround Time
For a particular process, an important criterion is how long it takes to execute that
process. The time elapsed from the time of submission of a process to the time of
completion is known as the turnaround time. Turn-around time is the sum of times spent
waiting to get into memory, waiting in the ready queue, executing in CPU, and waiting for
I/O.
Turn Around Time = Completion Time - Arrival Time.
Waiting Time
A scheduling algorithm does not affect the time required to complete the process once it
starts execution. It only affects the waiting time of a process i.e. time spent by a process
waiting in the ready queue.
Waiting Time = Turnaround Time - Burst Time.
Response Time
In an interactive system, turn-around time is not the best criterion. A process may produce
some output fairly early and continue computing new results while previous results are
being output to the user. Thus another criterion is the time taken from submission of the
process of the request until the first response is produced. This measure is called
response time.
Response Time = CPU Allocation Time(when the CPU was allocated for the
first) - Arrival Time
Completion Time
The completion time is the time when the process stops executing, which means that the
process has completed its burst time and is completely executed.
Priority
If the operating system assigns priorities to processes, the scheduling mechanism should
favor the higher-priority processes.
What are the different terminologies to take care of in any
CPU Scheduling algorithm?
● Arrival Time: Time at which the process arrives in the ready queue.
● Completion Time: Time at which process completes its execution.
● Burst Time: Time required by a process for CPU execution.
● Turn Around Time: Time Difference between completion time and arrival time.
Turn Around Time = Completion Time – Arrival Time
● Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time
There are mainly two types of scheduling methods:
● Preemptive Scheduling: Preemptive scheduling is used when a process switches
from running state to ready state or from the waiting state to the ready state.
● Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a
process terminates , or when a process switches from running state to waiting
state.
1. First Come First Serve:
FCFS considered to be the simplest of all operating system scheduling algorithms. First
come first serve scheduling algorithm states that the process that requests the CPU first
is allocated the CPU first and is implemented by using FIFO queue.
Characteristics of FCFS:
● FCFS supports non-preemptive and preemptive CPU scheduling algorithms.
● Tasks are always executed on a First-come, First-serve concept.
● FCFS is easy to implement and use.
● This algorithm is not much efficient in performance, and the wait time is quite
high.
Disadvantages of FCFS:
● FCFS suffers from Convoy effect.
● The average waiting time is much higher than the other algorithms.
● FCFS is very simple and easy to implement and hence not much efficient.
●
Shortest Job First(SJF):
Shortest job first (SJF) is a scheduling process that selects the waiting process with the
smallest execution time to execute next. This scheduling method may or may not be
preemptive. Significantly reduces the average waiting time for other processes waiting to
be executed. The full form of SJF is Shortest Job First.
Advantages of Shortest Job first:
● As SJF reduces the average waiting time thus, it is better than the first come first
serve scheduling algorithm.
● SJF is generally used for long term scheduling
Disadvantages of SJF:
● One of the demerit SJF has is starvation.
● Many times it becomes complicated to predict the length of the upcoming CPU
request
. Round robin:
Round Robin is a CPU scheduling algorithm where each process is cyclically assigned a
fixed time slot. It is the preemptive version of First come First Serve CPU Scheduling
algorithm. Round Robin CPU Algorithm generally focuses on Time Sharing technique.
Characteristics of Round robin:
● It’s simple, easy to use, and starvation-free as all processes get the balanced
CPU allocation.
● One of the most widely used methods in CPU scheduling as a core.
● It is considered preemptive as the processes are given to the CPU for a very
limited time.
● Round robin seems to be fair as every process gets an equal share of CPU.
● The newly created process is added to the end of the ready queue.
Multiple Queue Scheduling:
Processes in the ready queue can be divided into different classes where each class has
its own scheduling needs. For example, a common division is a foreground (interactive)
process and a background (batch) process. These two classes have different scheduling
needs. For this kind of situation Multilevel Queue Scheduling is used.
The description of the processes in the above diagram is as follows:
● System Processes: The CPU itself has its process to run, generally termed as
System Process.
● Interactive Processes: An Interactive Process is a type of process in which there
should be the same type of interaction.
● Batch Processes: Batch processing is generally a technique in the Operating
system that collects the programs and data together in the form of a batch
before the processing starts.
Advantages of multilevel queue scheduling:
● The main merit of the multilevel queue is that it has a low scheduling overhead.
Disadvantages of multilevel queue scheduling:
● Starvation problem
● It is inflexible in nature
