CPU scheduling is a critical task of operating systems that optimizes work completion within a computing system. It ensures that while one process is actively using the CPU, others may temporarily wait, often due to resource unavailability like I/O operations. This strategy maximizes CPU utilization, thereby enhancing system efficiency, speed, and fairness.

Whenever the CPU becomes available after executing a process, the operating system must choose the next process to run from the pool of ready processes. This selection is carried out by a temporary CPU scheduler. This scheduler evaluates the ready processes in memory and assigns the CPU to the most suitable candidate, ensuring the smooth flow of tasks within the system.

Benefits of CPU Scheduling

Effective CPU scheduling can provide a number of benefits, including:

Improved system performance: CPU scheduling can help to improve system performance by ensuring that the CPU is always busy and that processes are not waiting for too long to be executed.
Increased fairness: CPU scheduling can help to increase fairness by ensuring that all processes get a chance to run.
Reduced response time: CPU scheduling can help to reduce response time by ensuring that processes are not waiting for too long to be executed.
Improved resource utilization: CPU scheduling can help to improve resource utilization by ensuring that the CPU is always busy and that processes are not waiting for too long for resources.

What is a process?

In computing, a process is the instance of a computer program that is being executed by one or many threads. It contains the program code and its activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.

What is Process Scheduling?

Process scheduling is a fundamental aspect of operating systems that manages the execution of multiple processes efficiently on a single CPU. It involves selecting the next process to run based on a specific strategy. Here's a breakdown of key points related to process scheduling:

Definition: Process scheduling is the mechanism by which the operating system manages the allocation of the CPU to different processes, allowing one process to execute while others may be waiting or in a standby state due to resource unavailability, such as I/O operations. The primary goals are to improve system efficiency, speed, and fairness.

Types of Process Schedulers

There are three main types of process schedulers:

Long-term or Job Scheduler: Selects processes from the pool of new processes and admits them to memory for execution.
Short-term or CPU Scheduler: Chooses the next process to run on the CPU from the pool of ready processes.
Medium-term Scheduler: Temporarily removes processes from memory (swaps them out) to manage memory resources effectively.

Importance of Process Scheduling: Process scheduling is crucial for several reasons:

Efficient CPU Utilization: It ensures that the CPU is utilized as much as possible, preventing idle time.
Responsiveness: It keeps the CPU busy, reducing response times for running programs.
Resource Allocation: It allocates CPU time fairly among competing processes.
Context Switching: It involves the efficient switching of processes in and out of the CPU to provide the illusion of concurrent execution.

Need for CPU Scheduling Algorithms:

To maximize CPU utilization by selecting the next process to execute.
To minimize response time and turnaround time for processes.
To prevent system resources from being underutilized.
To prevent processes from starving or waiting indefinitely.

Objectives of CPU Scheduling Algorithms:

Maximize CPU Utilization: Keep the CPU busy as much as possible.
Fair Allocation: Ensure fairness in allocating CPU time to processes.
Maximize Throughput: Maximize the number of processes completed per unit of time.
Minimize Turnaround Time: Reduce the time taken for a process to finish execution.
Minimize Waiting Time: Minimize the time a process spends waiting in the ready queue.
Minimize Response Time: Reduce the time taken for a process to produce its first output.

Terminologies in CPU Scheduling:

Arrival Time: The time at which a process enters the ready queue.
Completion Time: The time when a process completes its execution.
Burst Time: The time required by a process for CPU execution.
Turnaround Time: The total time taken by a process from arrival to completion.
Waiting Time: The time a process spends waiting in the ready queue.

Waiting Time = Turnaround Time - Burst Time
or
Turnaround Time = Waiting Time + Burst Time

Types of CPU Scheduling Algorithms:

Two main categories of scheduling algorithms are:

Preemptive Scheduling: Preemptive scheduling is used when a process switches from the running state to the 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 a running state to a waiting state.

The choice of scheduling algorithm depends on system requirements, priorities, and the characteristics of the workload.

Different types of CPU Scheduling Algorithms

First-Come, First-Serve (FCFS):

Simplest scheduling algorithm.
Follows a FIFO queue for process execution.
Can suffer from the convoy effect.
Easy to implement but not highly efficient.

Shortest Job First (SJF):

Selects the process with the smallest execution time.
Minimizes average waiting time.
Can lead to starvation for longer processes.

Longest Job First (LJF):

Opposite of SJF, selects the process with the longest burst time.
Prone to high average waiting time.
May result in the convoy effect.

Priority Scheduling:

Assigns priorities to processes and allocates CPU to the highest-priority process.
May lead to priority inversion and starvation.
Useful for real-time and priority-based systems.

Round Robin (RR):

Allocates fixed time slices (quantum) to each process in a cyclic manner.
Ensures fairness and prevents starvation.
Inefficient for CPU-bound or long-running processes.

Shortest Remaining Time (SRT):

Preemptive version of SJF, where the smallest remaining time is executed.
Reduces response time but increases context switch overhead.

Longest Remaining Time (LRT):

Preemptive version of LJF, focusing on the longest remaining time.
Often leads to high waiting times and convoy effect.

Highest Response Ratio Next (HRRN):

Non-preemptive algorithm based on response ratios.
Aims to balance priority and waiting time.
Reduces waiting times for shorter jobs.

Multiple Queue Scheduling:

Divides processes into classes with different scheduling needs.
Useful for managing interactive and batch processes separately.
Low scheduling overhead but may face the starvation problem.

Multilevel Feedback Queue Scheduling:

Allows processes to move between different queues based on their behavior.
Offers flexibility but can be complex.
Suitable for dynamic workloads with varying requirements.

Comparison between various CPU Scheduling algorithms

Here is a brief comparison between different CPU scheduling algorithms:

Algorithm	Allocation is	Complexity	Average waiting time (AWT)	Preemption	Starvation	Performance
FCFS	According to the arrival time of the processes, the CPU is allocated.	Simple and easy to implement	Large.	No	No	Slow performance
SJF	Based on the lowest CPU burst time (BT).	More complex than FCFS	Smaller than FCFS	No	Yes	Minimum Average Waiting Time
LJFS	Based on the highest CPU burst time (BT)	More complex than FCFS	Depending on some measures e.g., arrival time, process size, etc.	No	Yes	Big turn-around time
LRTF	Same as LJFS the allocation of the CPU is based on the highest CPU burst time (BT). But it is preemptive	More complex than FCFS	Depending on some measures e.g., arrival time, process size, etc.	Yes	Yes	The preference is given to the longer jobs
SRTF	Same as SJF the allocation of the CPU is based on the lowest CPU burst time (BT). But it is preemptive.	More complex than FCFS	Depending on some measures e.g., arrival time, process size, etc	Yes	Yes	The preference is given to the short jobs
RR	According to the order of the process arrives with fixed time quantum (TQ)	The complexity depends on Time Quantum size	Large as compared to SJF and Priority scheduling.	Yes	No	Each process has given a fairly fixed time
Priority Pre-emptive	According to the priority. The bigger priority task executes first	This type is less complex	Smaller than FCFS	Yes	Yes	Well performance but contain a starvation problem
Priority non-preemptive	According to the priority with monitoring the new incoming higher priority jobs	This type is less complex than Priority preemptive	Preemptive Smaller than FCFS	No	Yes	Most beneficial with batch systems
MLQ	According to the process that resides in the bigger queue priority	More complex than the priority scheduling algorithms	Smaller than FCFS	No	Yes	Good performance but contain a starvation problem
MFLQ	According to the process of a bigger priority queue.	It is the most Complex but its complexity rate depends on the TQ size	Smaller than all scheduling types in many cases	No	No	Good performance

CPU Scheduling

Table of contents