The CPU Scheduling
Algorithms
THEORY, BRIEF INTRODUCTION &
COMPARISON OF THE ALGORITHMS
PRESENTERS:
AMAR JEET [BECS/H/F10/0117]
UZAIR AHMED [BECS/H/F10/0118]
What are CPU scheduling algorithms?
Definition Algorithms that set the schedule for
the CPUs processing and resource allocation
Role To decide in what order shall the processes
be sent to CPU for processing
The Need for Scheduling
o
o
o
o
Multi-tasking
Multiplexing
Efficiency
Quality of service
Types of CPU Schedulers
Long-term Scheduling
o
o
Decides which process will go to ready queue
Used in Batch-processing systems, supercomputers, etc.
Medium-term Scheduling
o
o
Swaps the processes between Main & Secondary memory
Frees-up the main memory resources for waiting processes
Short-term scheduling
o
Decides which process shall be allocated to CPU following next
interrupt/system call
Pre-emptive and fast scheduler, works with high frequency
Scheduling Disciplines
Definition Algorithms responsible for distributing
resources among parties which request them
Role To share the CPU time among different
threads and processes
Types:
FCFS First-Come, First-Served
SJF Shortest Job First
FPPS Fixed Priority Pre-emptive Scheduling
RR Round-Robin scheduling
MQS Multi-level Queue Scheduling
FCFS First-Come, First-Served
Also known as FIFO First-In, First-Out
Simplest scheduling algorithm
Throughput and system efficiency can be low in case
long processes hog the resources
Turnaround time, waiting time and response time
can be high for the same reasons above
No prioritization, non-preemptive, based on Queues
FCFS First-Come, First-Served
Advantages:
Easy to understand
Easy to implement
Disadvantages:
Doesnt pay heed to processing time or priority
Turnaround time can become much higher
Long processes can hog the system resources
SJF Shortest Job First
Also known as SRT Shortest Remaining Time
Requires advanced knowledge and estimation of the
remaining-time of a job/process
Pre-Emptive type: Can interrupt an already-running
process if a process with shorter burst-time arrives
Non-Preemptive type: Cannot interrupt an alreadyrunning process
Designed for maximum throughput
SJF Shortest Job First
Advantages:
Provides relatively good throughput
No biasing in the favor of long processes
Disadvantages:
Need advance knowledge of preemption and estimation
Harder to implement
Longer processes can starve
RR Round-Robin scheduling
The scheduler assigns a fixed time unit per process
(called Quantum), and cycles through them
Involves extensive overhead, especially with a small
time unit
Shorter jobs are completed faster than FCFS and
longer processes are completed faster than SJF
Poor average response time
Waiting time is dependent on number of processes,
and not average process length.
RR Round-Robin scheduling
Advantages:
RR scheduling is fair
Provides equal amount of time to every process
Starvation does not occur
Disadvantages:
Even the shorter processes need to wait if number of processes
is large
Selecting quantum time is a huge issue.
MQS Multi-level Queue Scheduling
Also known as the MFQ Multi-level Feedback
Queue algorithm
Gives preference to short and I/O-bound jobs
Separates processes into categories based on their
need for the processor, involves pre-emption
Different levels of queues are involved, like top-level,
high-level and low-level job queues
Widely used in Windows, MAC OS X, LINUX,
Solaris, NetBSD and FreeBSD
MQS Multi-level Queue Scheduling
Advantages:
Provides categorization feature
Highly effective and efficient
Disadvantages:
Starvation can occur
Hard to implement
Excessive knowledge is required for implementation
Inefficient in older, slower (single-core) systems
Overview of the Scheduling Disciplines
Algorithm
CPU
Overhead
Throughput
Turnaround
Time
Response
Time
FCFS/FIFO
Low
Low
High
Low
SJF/SRT
Medium
High
Medium
Medium
Round-Robin
High
Medium
Medium
High
Prioritybased
Medium
Low
High
High
MQS
High
High
Medium
Medium
QUESTIONS?
THANK YOU!
