CPU Scheduling In OS

CPU scheduling is the process by which the operating system selects one process from the ready queue and assigns the CPU to it for execution. Since a CPU can execute only one process at a time (on a single-core system), CPU scheduling determines which process should run next. Its main goal is to keep the CPU busy, improve system performance, and ensure that all processes receive CPU time efficiently.

CPU scheduling is the foundation of a multiprogramming operating system. It allows multiple processes to share the CPU efficiently, which improves the overall system performance. 

Objectives of CPU Scheduling

The main objectives of CPU scheduling are:

  • Maximize CPU utilization.
  • Increase system throughput.
  • Minimize waiting time.
  • Minimize turnaround time.
  • Minimize response time.
  • Ensure fairness among processes.
  • Prevent process starvation.

Importance of CPU Scheduling

CPU scheduling is an essential function of the operating system because it efficiently manages CPU resources. Whenever the CPU becomes idle, the scheduler selects the next process from the ready queue and assigns it to the CPU. This reduces CPU idle time, improves overall system performance, and allows multiple processes to execute efficiently in a multiprogramming environment.

Terminologies Used in CPU Scheduling

Understanding the following terms is essential for solving CPU scheduling problems and evaluating the performance of scheduling algorithms.

1. Arrival Time (AT)

Arrival Time (AT) is the time at which a process enters the ready queue and becomes ready for CPU execution.

  • Example: If Process P1 enters the ready queue at time 2 ms, then its Arrival Time = 2 ms.

2. Burst Time (BT)

Burst Time (BT) is the total amount of CPU time required by a process to complete its execution.

  • Example: If Process P1 requires 6 ms of CPU time, then its Burst Time = 6 ms.

3. Completion Time (CT)

Completion Time (CT) is the time at which a process finishes its execution.

  • Example: If Process P1 finishes execution at 12 ms, then its Completion Time = 12 ms.

4. Turnaround Time (TAT)

Turnaround Time (TAT) is the total time taken by a process from its arrival in the ready queue until its completion.

  • Formula: Turnaround Time = Completion Time − Arrival Time

5. Waiting Time (WT)

Waiting Time (WT) is the total time a process spends waiting in the ready queue before getting CPU execution.

  • Formula: Waiting Time = Turnaround Time − Burst Time

6. Response Time (RT)

Response Time (RT) is the time between the arrival of a process and the first time it gets the CPU.

It measures how quickly the system responds to a process, especially in interactive systems.

  • Formula: Response Time = First CPU Start Time − Arrival Time

CPU Scheduling Criteria

CPU scheduling algorithms are evaluated using several performance criteria. These criteria help determine how efficiently the CPU is allocated to processes.

1. CPU Utilization

CPU utilization is the percentage of time the CPU remains busy executing processes. A good scheduling algorithm aims to keep the CPU busy and reduce idle time.

  • Goal: Maximize CPU utilization.

2. Throughput

Throughput is the number of processes completed by the CPU in a given period. Higher throughput indicates better system performance.

  • Goal: Maximize throughput.

3. Turnaround Time

Turnaround time is the total time taken by a process from arrival to completion.

  • Goal: Minimize turnaround time.

4. Waiting Time

Waiting time is the total time a process spends waiting in the ready queue.

  • Goal: Minimize waiting time.

5. Response Time

Response time is the time taken for a process to receive the CPU for the first time after arriving in the ready queue.

  • Goal: Minimize response time.

6. Fairness

Fairness ensures that every process gets a reasonable opportunity to use the CPU and prevents process starvation.

  • Goal: Ensure fair CPU allocation.

Types of CPU Scheduling

CPU scheduling algorithms are broadly classified into two types based on whether a running process can be interrupted.

Types of CPU Scheduling in Operating Systems

1. Preemptive Scheduling

In preemptive scheduling, the operating system can interrupt a running process and allocate the CPU to another process, usually one with higher priority or a shorter remaining execution time.  Preemptive Scheduling Algorithms are given below

  • Priority Scheduling
  • Shortest Remaining Time First (SRTF)
  • Longest Remaining Time First (LRTF)
  • Round Robin (RR)

2. Non-Preemptive Scheduling

In non-preemptive scheduling, once a process starts executing, it continues until it completes or enters the waiting state. The operating system does not interrupt it. It contains the following characteristics. Non-Preemptive Scheduling Algorithms are given below

  • Priority Scheduling
  • First Come First Served (FCFS)
  • Shortest Job First (SJF)
  • Longest Job First (LJF)
  • Highest Response Ratio Next (HRRN)