Please enable JavaScript.
Coggle requires JavaScript to display documents.
CPU SCHEDULING ALGORITHMS, IMPORTANT TERMINOLOGIES - Coggle Diagram
CPU SCHEDULING ALGORITHMS
FCFS
FIRST COME FIRST SERVE
CRITERIA
ARRIVAL TIME
MODE
NON-PREEMPTIVE
ADVANTAGES
Easy to implement
well suited for batch systems
DISADVANTAGES
average waiting time in the FCFS is much higher than in the others
It suffers from the Convoy effect.
Not very efficient due to its simplicity
CONVOY EFFECT
The convoy effect in operating systems refers to the phenomenon where a group of processes, or a "convoy," are blocked behind a single slow-performing process.
When a slow-performing process arrives and begins execution, it can hold up the execution of all the other processes that arrive behind it, creating a convoy of blocked processes. This can lead to increased waiting times for the processes in the convoy, and can also lead to poor overall performance of the system.
SJF
SHORTEST JOB FIRST
CRITERIA
BURST TIME
MODE
NON-PREEMPTIVE (DEFAULT)
ADVANTAGES
better than the First come first serve(FCFS) algorithm as it reduces the average waiting time.
suitable for the jobs running in batches, where run times are already known.
.
DISADVANTAGES
Un-implementable
- job completion time must be known earlier, but sometimes it is hard to predict.
It leads to the starvation of long processes
PREEMPTIVE SJF
SRTF
SHORTEST REMAINING TIME FIRST
CRITERIA
Remaining
BURST TIME
MODE
PREEMPTIVE
ADVANTAGES
Short processes are handled very quickly.
The system also requires very little overhead since it only makes a decision when a process completes or a new process is added.
DISADVANTAGES
Long processes may be held off indefinitely if short processes are continually added i.e.
STARVATION
Likewise we have
LJF
Longest Job First
which schedules on the basis of burst time and it may suffer from the convoy effect, it's preemptive version is known as Longest Remaining Time First
ROUND ROBIN
SCHEDULING (TIME-SLICING OR TIME-SHARING )
CRITERIA
ARRIVAL TIME + TIME QUANTUM
MODE
PREEMPTIVE
ADVANTAGES
Each process is served by CPU for a fixed time, so priority is the same for each one
Starvation does not occur because of its cyclic nature.
DISADVANTAGES
May lead to poor performance if the time quantum is too large or too small.
If the quantum time is very large then it is equivalent to FIFO
If we want to give some process priority, we cannot.
HRRN
HIGHEST RESPONSE RATIO NEXT ALGORITHM
MODE
NON-PREEMPTIVE
CRITERIA
RESPONSE RATIO
(W + S) / S
W is waiting time
S is service time or burst time
ADVANTAGES
it gives more priority to the process that has been waiting for a longer time.
Reduction in waiting time for longer jobs and also it encourages shorter jobs.
DISADVANTAGES
The on ground implementation of HRRN scheduling is not possible as it is not possible know the burst time of every job in advance.
In this scheduling, there may occur overload on the CPU.
PRIORITY BASED SCHEDULING
MODE
PREEMPTIVE as well as NON-PREEMPTIVE
CRITERIA
PRIORITY
ADVANTAGES
Priorities can be assigned based on the critical nature of the process, ensuring that important tasks are executed first.
DISADVANTAGES
Starvation of low-priority processes is a possibility, if higher-priority processes are always ready to execute.
Priorities can be difficult to assign and maintain, particularly in dynamic systems with changing priorities.
Priority inversion
is a situation where a lower-priority process holds a resource needed by a higher-priority process, leading to the higher-priority process being blocked.
Aging
technique should be implemented to
avoid the starvation of lower priority process
for a longer time.
AGING
Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.
Multilevel Queue (MLQ)
CPU Scheduling
Ready Queue is divided into
separate queues
for each class of processes.
Processes are
permanently assigned
to a
queue
on entry to the system and processes are
not allowed to move between queues
.
All three different type of processes has their own queue.
Each queue has its own Scheduling
algorithm.
INTERACTIVE PROCESSES
Interactive processes are processes that
interact
directly with the user through a
user interface
BATCH PROCESSES
Batch processes are processes that run
non-interactively
and typically have
no user interface
. These processes are typically used to perform
repetitive
or time-consuming tasks, such as
data processing, backups, and system maintenance.
SYSTEM PROCESSES
processes that run in the
background
of an operating system and perform
important system-level tasks.
ADVANTAGES
The processes are permanently assigned to the queue, so it has advantage of
low scheduling overhead
.
DISADVANTAGES
Lower priority
processes may
starve
for CPU if some higher priority queues are never becoming empty.
inflexible.
Solving the issue of starvation of low priority processes
Multilevel Feedback Queue Scheduling (MLFQ)
It is like MLQ scheduling but in this the
processes can move between the queues
thus making it much more efficient
ADVANTAGES
It is more flexible.
allows different processes to move between different queues.
prevents starvation of lower priority processes
DISADVANTAGES
produces more CPU overheads.
most complex algorithm
IMPORTANT TERMINOLOGIES
Burst Time
Time required by a process for CPU execution
Turn Around Time
Time Difference between completion time and arrival time.
TAT = CT - AT
Completion Time
Time at which process completes its execution
Arrival Time
Time at which the process arrives in the ready queue.
WAITING TIME
Time Difference between turn around time and burst time.
WT = TAT - BT
THROUGHPUT
Number of processes completed in a given time
Throughput = n / SL(Schedule Length)