CPU Scheduling

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:

  1. Long-term or Job Scheduler: Selects processes from the pool of new processes and admits them to memory for execution.

  2. Short-term or CPU Scheduler: Chooses the next process to run on the CPU from the pool of ready processes.

  3. 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:

  1. Maximize CPU Utilization: Keep the CPU busy as much as possible.

  2. Fair Allocation: Ensure fairness in allocating CPU time to processes.

  3. Maximize Throughput: Maximize the number of processes completed per unit of time.

  4. Minimize Turnaround Time: Reduce the time taken for a process to finish execution.

  5. Minimize Waiting Time: Minimize the time a process spends waiting in the ready queue.

  6. 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:

AlgorithmAllocation isComplexityAverage waiting time (AWT)PreemptionStarvationPerformance
FCFSAccording to the arrival time of the processes, the CPU is allocated.Simple and easy to implementLarge.NoNoSlow performance
SJFBased on the lowest CPU burst time (BT).More complex than FCFSSmaller than FCFSNoYesMinimum Average Waiting Time
LJFSBased on the highest CPU burst time (BT)More complex than FCFSDepending on some measures e.g., arrival time, process size, etc.NoYesBig turn-around time
LRTFSame as LJFS the allocation of the CPU is based on the highest CPU burst time (BT). But it is preemptiveMore complex than FCFSDepending on some measures e.g., arrival time, process size, etc.YesYesThe preference is given to the longer jobs
SRTFSame as SJF the allocation of the CPU is based on the lowest CPU burst time (BT). But it is preemptive.More complex than FCFSDepending on some measures e.g., arrival time, process size, etcYesYesThe preference is given to the short jobs
RRAccording to the order of the process arrives with fixed time quantum (TQ)The complexity depends on Time Quantum sizeLarge as compared to SJF and Priority scheduling.YesNoEach process has given a fairly fixed time
Priority Pre-emptiveAccording to the priority. The bigger priority task executes firstThis type is less complexSmaller than FCFSYesYesWell performance but contain a starvation problem
Priority non-preemptiveAccording to the priority with monitoring the new incoming higher priority jobsThis type is less complex than Priority preemptivePreemptive Smaller than FCFSNoYesMost beneficial with batch systems
MLQAccording to the process that resides in the bigger queue priorityMore complex than the priority scheduling algorithmsSmaller than FCFSNoYesGood performance but contain a starvation problem
MFLQAccording to the process of a bigger priority queue.It is the most Complex but its complexity rate depends on the TQ sizeSmaller than all scheduling types in many casesNoNoGood performance

Did you find this article valuable?

Support Narottam Choudhary by becoming a sponsor. Any amount is appreciated!