CPU Scheduling Made Easy: Understanding CPU Algorithms

CPU Scheduling:

To maximize CPU use, how does the CPU choose which process in the ready queue should be carried out next? The CPU scheduling method comes into the picture, which is the process of “scheduling” the processes.

“CPU Scheduling is a process in which the operating system determines which process will get allocated the CPU next.”

It selects which of the processes in the ready queue will be assigned the CPU, hence maximizing system performance. It is essential to make sure that resources are used as efficiently as possible and that the system functions properly even when there is a high demand for it.

There are mainly two types of scheduling methods:

• Preemptive Scheduling: Preemptive scheduling occurs 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 takes place when a process terminates or switches from the running state to the waiting state.

Some important terminologies relevant to CPU scheduling are: Arrival Time (AT): The time at which a process enters the ready queue. It determines when the process is available for execution.

Burst Time (BT): The total time required by a process on the CPU. It is also called the execution time of the process.

Completion Time (CT): The time at which a process finishes its execution. It includes all waiting and execution periods.

Turn Around Time (TAT): The total time taken by a process from arrival to completion. Calculated as: TAT = CT - AT

Waiting Time (WT): The total time a process spends waiting in the ready queue. Calculated as: WT = TAT - BT.

Response Time (RT): The time from process arrival to the first time it gets CPU. It measures the responsiveness of a scheduling algorithm.

CPU scheduling has certain criteria that it uses to schedule processes most efficiently: CPU utilization (maximise) Throughput (maximise) Turn Around Time (minimise) Waiting Time (minimise) Response Time (minimise)

CPU scheduling algorithms

To effectively allocate the CPU’s available processing time among several computing processes for its resources, a CPU scheduling technique is required. They choose the sequence in which processes run and the amount of CPU time allotted to each task. Every algorithm has advantages and disadvantages, and the ones used depend on the goals and needs of the system.

Types of CPU Scheduling Algorithms

There are several types of CPU scheduling algorithms, each with its own strengths and weaknesses. Some of the most common types of CPU scheduling algorithms include: First-Come, First-Served (FCFS): The simplest CPU scheduling algorithm, in which processes are executed in the order in which they arrive.

Table 1: First Come First Serve(FCFS) with respect to Arrival Time

Gantt Chart for FCFS

Shortest Job First (SJF): This algorithm schedules processes based on their expected CPU burst time. The process with the shortest expected burst time is executed first.

Table 3: Shortest Job First (SJF)

Gantt Chart for SJF

shortest remaining job first: The shortest remaining job first algorithm selects the process with the shortest remaining burst time (processing time remaining for completion) from the operating system.

Table 4: Shortest Remaining Job First (SRJF)

Gantt Chart for SRJF

Round Robin (RR): This algorithm allocates a fixed time slice (quantum) to each process in a cyclic order. If a process has not completed its execution within its allotted time slice, it is preempted, and the next process in the queue is executed.

Table 5: Round Robin (RR)

Gantt Chart for Round Robin

Importance of CPU Scheduling The purpose of CPU scheduling is to ensure that the operating system has at least chosen a process from the ready-to-run line whenever the CPU is idle. This process is needed to efficiently utilise the maximum performance of the CPU and get the best output from it. Here are some of the important aspects of CPU scheduling:

1. It helps in producing the maximum output from the CPU performance, thereby increasing the maximum CPU utilisation.
2. It ensures that the CPU is not idle and is still working to get new processes.
3. It helps in reducing the system overhead, including less idle times, task prioritisation, context switching, etc.
4. When using CPU scheduling, it also ensures that each process in the ready queue gets a fair chance to be executed by the CPU.

Challenges in CPU Scheduling Having the benefits of CPU scheduling also comes with numerous challenges that need to be addressed. Here are some of the common challenges in CPU scheduling:

1. It may introduce overhead when switching between different processes in a small interval of time. This is known as context-switching overhead.
2. It can be difficult to make sure that real-time processes are completed by the deadline.
3. When a priority process comes into the queue, the system may give preference to that process, and therefore, some processes may never be carried out.
4. When processes are not properly scheduled, they might come to a state where they are waiting for infinite periods for each other to release each of their resources. As the number of processes increases, scheduling techniques must scale effectively

Authors:

Alina Batool, Umama Amir and Sana