Operating System Scheduling Algorithms

5 min readJun 27, 2022

Process switching between processors in a computer is handled by the operating system. The operating system suspends a running process and controls the continuation of another process. Suspended process is saved in memory, during suspend the running process is not actually stopped. When the processor is ready for the continuation of this process, it reloads the process and the process continues to run. This process is executed by Process Scheduler based on certain scheduler algorithms.

Algorithms used in the process are non-preemptive or preemptive. While preemptive algorithms can suspend a process and continue another process according to certain priority states defined by the algorithms while a process is in the running state, non-preemptive algorithms do not prevent the running process in any way until the processing time of the process is completed.

I will use some concepts below when writing about scheduling algorithms. For this reason, you should pay attention to the following concepts while learning algorithms.

Arrival Time: The moment when a request is sent to the processor to run the process.
Execute Time / CPU cycle : The running time of the process.
Service Time: The moment the process is run by the processor.
Wait Time: Service Time-Arrival Time
Turnaround Time: It can be thought of as the time taken until a transaction is completed. (Time to completion — Arrival Time)
Starvation: In an operating system, starvation refers to the lack of access of a process that has started running to the resources it needs to continue. When the process executed by the Processor is suspended, the longer the time until the process completes, the more hungry the process becomes.

First Come First Serve (FCFS)

Processes are run in the order of the run request sent to the processor by the process. It was created based on the first in first out queue structure. Once a process has started, it cannot be suspended, it must wait for the running process to complete its runtime before the next process can run. Since it is an algorithm with a high average waiting time, its performance is poor.

It is also a non-preemptive algorithm. Whether the processes take priority or not is not important during the execution of the processes.

At the same time, the Convoy Effect may occur when a long process is queued first, as processes cannot run in parallel on the processor. The Convoy Effect is when many processes that need to use a resource (in this case the processor) for a short time are blocked by a single process that holds that resource for a long time. When several processes with long execution times are assigned to the processor, the processors are used inefficiently when short-term transactions wait for a long time, which causes bad performance.

Table 1 : First Come First Served Scheduling

Figure 1 : Processes are completed by the processor in the order in which processes are received.

Avg. Wait Time : (0+5+7+11)/4 = 5.75

Avg. Turnaround Time : (6+8+12+15)/4 = 10.25

Shortest Job Next / Shortest Job First ( SJN / SJF)

Among the processes added to the queue, the process with the shortest total execution time is given priority. For this reason, the processor must know how long a process will take before the process starts. For this reason, it is impossible to implement this algorithm in interactive systems where the CPU time required for the process is unknown. It is convenient to use in batch systems. If you do not know about batch systems, it is explained quite clearly in the link.

Table 1 : Shortest Job Next (SJN) Scheduling

Figure 2 : Processes are ordered by execution time, and the processor completes the processes in this order.

Avg. Wait Time : (0+5+11+6)/4 = 5.5

Avg. Turnaround Time : (6+8+16+10)/4 = 10

Shortest Remaining Time (SRT)

It is a preventive version of the Shortest Job First algorithm. The processor prioritizes the process with the closest completion time. As with SJF, long-running, high-priority processes starve because processes that take shorter execute time are prioritized.

Table 3 : Shortest Remaining Time Scheduling

Figure 3: If there is a process in progress and another process with a shorter completion time is in the queue, the ongoing process is suspended and the process with the shortest completion time is run. Likewise, for example, if there was a process with an execution time equal to 2 during the P3 run, this process would be prioritized.

Avg. Wait Time : (8+0+11+1)/4 = 5

Avg. Turnaround Time : (13+3+16+5)/4 = 9.25

Round Robin

In this algorithm, the processor’s time is divided equally for all operations. In other words, after a process has started, even if the process is not completed, it is suspended and the next process continues. Although the waiting times of Processes are reduced, the fact that the processing times are divided into small parts for too many processes creates a disadvantage in terms of prolonging the completion time of long-running priority processes.

for time quadrant = 3

Figure 4 : Processes are sorted in the order of arrival time. Each process is run in the time interval determined in accordance with this order, if the process is not finished within this time period, it continues to run in the next period.

Suspending and continuing processes increases the average turnaround time considerably. When calculating the waiting times of processes, service time-arrival time is calculated first, then the difference between the time the process was started and the time the process was last suspended is added each time the process is started.

Avg. Wait Time : (9+0+10+11)/4 = 7.5

Avg. Turnaround Time : (15+3+15+15)/4 = 12

The Multilevel Feedback Queue

It uses the queue structure for processes with different priorities. processes are selected from different queues based on priority. When assigning a new process to the processor, it is assigned to one of the queues of the processor according to the process priority information (low-mid-high). Processes can be moved from their current queue to other queues.
It is a very complex algorithm to use and explain. You can check the link for detailed explanation. Although I still have question marks in my mind, I can say that I understand some of them.

Since I assigned the arrival time and execution time values for the processes myself, the decrease or increase of the wait time and turnaround time values between the algorithms may not be sufficiently explanatory. I hope you enjoyed reading it.

Resources :

1- For Scheduling Algorithm: https://isaaccomputerscience.org/concepts/sys_os_scheduling?examBoard=all&stage=all

2- First Come First Serve Method: https://iq.opengenus.org/first-come-first-serve-cpu-scheduling/

3- Another Example of FCFS : https://www.guru99.com/fcfs-scheduling.html

4- Non-Preemptive vs Preemptive Scheduling : https://www.geeksforgeeks.org/preemptive-and-non-preemptive-scheduling/