Understanding CPU Scheduling in Operating Systems

Introduction

CPU scheduling is a fundamental concept in operating systems that ensures efficient use of the CPU by managing the execution of processes. The CPU is a limited resource and multiple processes often compete for its time. The scheduling algorithm determines the order in which processes access the CPU, impacting the overall system performance, response time, and throughput. This article explores the principles of CPU scheduling, key terminologies, different types of scheduling algorithms, and their significance in operating systems.

Key Terminologies in CPU Scheduling

• Process: A program in execution, which requires CPU time and other resources to complete its task.
• Burst Time (BT): The time required by a process for its execution on the CPU.
• Arrival Time (AT): The time at which a process enters the ready queue and is ready for execution.
• Completion Time (CT): The time at which a process finishes its execution.
• Turnaround Time (TAT): The total time taken from the arrival of the process to its completion. It is calculated as:
  Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT)
• Waiting Time (WT): The total time a process spends waiting in the ready queue. It is calculated as:
  Waiting Time (WT) = Turnaround Time (TAT) - Burst Time (BT)
• Response Time (RT): The time from the arrival of a process to the first time it gets executed on the CPU.

Objectives of CPU Scheduling

The primary goals of CPU scheduling include:

• Maximizing CPU Utilization: Keeping the CPU as busy as possible.
• Maximizing Throughput: Increasing the number of processes that complete execution per unit time.
• Minimizing Turnaround Time: Reducing the time taken to execute a process.
• Minimizing Waiting Time: Decreasing the time a process spends in the ready queue.
• Minimizing Response Time: Ensuring that processes start execution as quickly as possible after arriving in the ready queue.

Types of CPU Scheduling Algorithms

First-Come, First-Served (FCFS)

Description: The simplest scheduling algorithm where the process that arrives first is executed first. It follows a non-preemptive approach.

Advantages: Easy to implement and understand.

Disadvantages: It can lead to the “convoy effect,” where a shorter process has to wait for a longer process to complete, resulting in increased average waiting time.

Shortest Job First (SJF)

Description: Processes are scheduled based on the burst time, with the shortest job being executed first. SJF can be either preemptive (Shortest Remaining Time First, SRTF) or non-preemptive.

Advantages: Minimizes the average waiting time.

Disadvantages: May lead to starvation, where longer processes are indefinitely postponed if shorter processes keep arriving.

Priority Scheduling

Description: Each process is assigned a priority, and the CPU is allocated to the process with the highest priority. It can be preemptive or non-preemptive.

Advantages: Ensures critical tasks are executed first.

Disadvantages: May cause starvation for lower-priority processes, although aging can be used to prevent this.

Round Robin (RR)

Description: Each process is assigned a fixed time slot (quantum) and processes are executed in a cyclic order. It’s a preemptive algorithm.

Advantages: Provides a good response time for interactive systems and prevents starvation.

Disadvantages: The performance depends heavily on the size of the time quantum. A very large quantum degenerates RR into FCFS, while a very small quantum can cause excessive context-switching overhead.

Longest Job First (LJF)

Description: The process with the longest burst time is executed first. Like SJF, LJF can be preemptive or non-preemptive.

Advantages: Ensures that large processes get executed without waiting too long.

Disadvantages: High average waiting time and may lead to the “convoy effect.”

Highest Response Ratio Next (HRRN)

Description: A dynamic priority scheduling algorithm that calculates the response ratio of each process, which is the ratio of the sum of waiting time and burst time to the burst time. The process with the highest response ratio is selected.

Advantages: Balances between SJF and FCFS, reduces starvation.

Disadvantages: More complex to implement compared to simpler algorithms.

Multilevel Queue Scheduling

Description: Processes are divided into different queues based on certain criteria (e.g., process type), and each queue can have its own scheduling algorithm.

Advantages: Flexible and can cater to different types of processes.

Disadvantages: This can lead to starvation if lower-priority queues are not adequately managed.

Multilevel Feedback Queue Scheduling

Description: Similar to multilevel queue scheduling but allows processes to move between queues based on their behaviour and requirements.

Advantages: Highly flexible and can dynamically adjust to process needs.

Disadvantages: Complex to implement and manage.

Numerical Examples

Example 1: FCFS Scheduling

Consider three processes P1, P2, and P3 with the following arrival and burst times:

• P1: Arrival Time = 0, Burst Time = 24
• P2: Arrival Time = 3, Burst Time = 3
• P3: Arrival Time = 5, Burst Time = 3

Using the FCFS algorithm, the order of execution will be P1 → P2 → P3. The Gantt chart will look like this:

0 ---- 24 ---- 27 ---- 30

• P1: Waiting Time = 0, Turnaround Time = 24
• P2: Waiting Time = 21, Turnaround Time = 24
• P3: Waiting Time = 24, Turnaround Time = 27

Example 2: SJF Scheduling

Consider the same processes with the SJF (non-preemptive) algorithm. The order will be P2 → P3 → P1. The Gantt chart will be:

3 ---- 6 ---- 9 ---- 33

• P2: Waiting Time = 0, Turnaround Time = 3
• P3: Waiting Time = 3, Turnaround Time = 6
• P1: Waiting Time = 6, Turnaround Time = 33

Conclusion

CPU scheduling is a vital aspect of operating systems that directly impacts system performance and user experience. By understanding and choosing appropriate scheduling algorithms, system administrators and developers can optimize CPU usage, reduce process waiting times, and improve overall efficiency. Each algorithm has its strengths and weaknesses, making it crucial to select the one that aligns with the specific needs of the system and its workload.