CPU Scheduling in Operating System

In this tutorial, we will explore the fundamental concepts of CPU scheduling, the role of dispatchers in the scheduling process, and how to evaluate the efficiency of scheduling algorithms. We will also discuss Gantt charts and how they are used to visualize and calculate various scheduling criteria. By the end of this tutorial, you will gain a comprehensive understanding of these key concepts and their applications in operating systems.

Contents:

1. What is CPU Scheduling?
2. CPU Scheduling Types
3. CPU Scheduling Key Terminologies
4. Role of the Dispatcher in Scheduling
5. Criteria for Evaluating Scheduling Algorithms
6. What is a Gantt Chart?
7. Calculating Scheduling Criteria Using Gantt Charts

What is CPU Scheduling?

• CPU scheduling is the basis of multiprogramming operating system. In a multiprogramming operation system, several processes which are ready to execute are kept in the main memory.
• When CPU is idle and a process executing on CPU is leaving CPU for some I/O or is terminating, another process has to be scheduled.
• As there are multiple processes available to be scheduled onto CPU, a choice has to be made.
• CPU scheduling algorithm makes this choice. According to the specific need of the system, a CPU scheduling algorithm is implemented on it.

CPU Scheduling Types

• First-Come, First-Served (FCFS): Processes are scheduled in the order they arrive. Simple but can cause delays for shorter processes.
• Shortest Job Next (SJN): Process with the shortest execution time is scheduled next. Reduces average wait time but needs knowledge of process duration.
• Priority Scheduling: Processes are scheduled based on priority. Can be preemptive (higher priority interrupts lower priority) or non-preemptive.
• Round Robin (RR): Each process gets a fixed time slot. Fair but can lead to high wait times for some processes.
• Multilevel Queue Scheduling: Processes are categorized into queues based on priority or type, with each queue using its own scheduling method.
• Multilevel Feedback Queue Scheduling: Processes move between queues based on behavior, allowing dynamic adjustment to scheduling needs.

CPU Scheduling Key Terminologies

• Process: A program in execution, which requires CPU time, memory, and other resources.
• Burst Time: The total time a process requires on the CPU.
• Waiting Time: The total time a process spends waiting in the ready queue before it gets CPU time.
• Turnaround Time: The total time from the arrival of a process in the ready queue to its completion.
• Response Time: The time from the arrival of a process to the first time it gets the CPU.
• Time Quantum: In Round Robin scheduling, the fixed time interval during which a process can execute before being moved to the back of the queue.
• Preemptive Scheduling: Scheduling in which a process can be interrupted and moved to the ready queue if a higher priority process arrives.
• Non-Preemptive Scheduling: Scheduling in which a process continues its execution until it finishes or voluntarily relinquishes the CPU.

Role of the Dispatcher in Scheduling

A dispatcher, like CPU scheduler, is involved in the scheduling process and has the following functions:

• Context Switch: As a new process is being scheduled onto CPU, the dispatcher saves the context of the process which was executing on the CPU and loads the context of the process chosen by CPU scheduler to execute on the CPU.
• User Mode: As scheduling is a service provided by the operating system, it takes place in the kernel mode of operation. The dispatcher switches the operation from kernel mode to user mode.
• Set up execution: Finally, the dispatcher, according to the value of program counter in PCB of the process, jumps to appropriate location on the program so that process can start executing from where it left.

Criteria for Evaluating Scheduling Algorithms

Following scheduling criteria are considered:

• CPU Utilization: CPU utilization is the ratio of time CPU was busy to the total time of execution of a set of processes. A scheduling algorithm resulting in a high CPU utilization is considered a good CPU scheduling algorithm.
• Throughput: Throughput is the number of processes executed per unit time. The better the throughput, the better the CPU scheduling algorithm.
• Turnaround time: Turnaround time (TAT), is the time duration for each process from arrival to completion of execution. The lesser the average turnaround time, the better the scheduling algorithm.
• Waiting time: Waiting time is the time for which the process waits and is not executing. The scheduling algorithm resulting in a lower average waiting time is considered a good scheduling algorithm.
• Response time: Response time is the time duration from the arrival of the process to the first response i.e. the time when the process gets scheduled for the first time.

What is a Gantt Chart?

A Gantt chart is a visual tool used to represent the execution sequence of processes over time. It provides a graphical view of the scheduling process, helping to understand and analyze the performance of different scheduling algorithms.

Example of a Gantt Chart:

The following diagram shows an example of a Gantt chart:

• A Gantt chart is a horizontal bar chart which represents the execution sequence of a group of processes loaded in the CPU in a duration of time.
• The Gantt chart represents the time duration for which each process gets scheduled onto the CPU.
• From the Gantt chart, several CPU scheduling criteria can be calculated.
• If we move from right to left in a Gantt chart, the completion time of each process can be known from the first encounter of that process.
• If we move from left to right, the first response time of each process can be known from the first encounter of that process.
• The completion times of the processes are: P1:6; P2:3; P3:15; P4:10.

Calculating Scheduling Criteria Using Gantt Charts

The following steps are followed to calculate various CPU scheduling criteria:

• A Gantt chart is made according to the scheduling algorithm and the arrival and burst times of the processes.
• In the Gantt chart, we trace from right to left to find the first occurrence of each process and that time is noted as the completion time of each process.
• Turnaround time is calculated as the difference between completion time and arrival time of each process.
• Waiting time is calculated as the difference between the turnaround time and burst time of each process.
• In the Gantt chart, we trace from left to right and the first occurrence of each process is noted as first response time.
• Response time is calculated as the difference between the first response and the arrival time.