Process Scheduling in Operating System

To start with this tutorial, I will introduce you first to what is an operating system, process, and process scheduling.

Illustration of CPU, source: Pixabay by: ColiN00B

An operating system (OS) acts as the bridge between computer hardware and users, facilitating interactions between applications and devices. It manages crucial functions like memory, files, and processes. Given the OS’s responsibility for handling multiple tasks simultaneously, efficient scheduling algorithms become essential. These algorithms guide the OS in prioritizing processes, optimizing CPU usage, and ensuring seamless resource utilization.

This tutorial comprehensively covers scheduling in OS, delving into its fundamentals, significance, and its role in achieving optimal CPU utilization. It further explores various methods and types of scheduling in OS.

What is a Process in Programming?

In programming, a process is an actively executing program. Programs remain dormant until the CPU initiates their instructions. In essence, a process represents a program in execution. This raises the question of determining the sequence and timing of program executions. The answer, as anticipated, lies with the process scheduler.

What is Process Scheduling in Operating System?

Process scheduling involves determining the order and timing of process execution, guided by a specific strategy or algorithm. The process manager conducts this task, temporarily removing an active process from the CPU and selecting another from the queue. Scheduling in the OS becomes essential due to the multi-programming nature of most applications, allowing multiple processes to be loaded and shared with the CPU simultaneously. The process manager must make decisions on the prioritization and sequence of these processes.

There are three primary types of process schedulers:

• Long-term job scheduler also known as the job scheduler, selects processes from the pool and loads them into memory for execution.
• Medium-term scheduler is responsible for swapping out processes from memory and bringing them back in later.
• CPU or short-term scheduler selects a process from the ready queue and allocates the CPU to it.

In addition to these schedulers, process queues play a crucial role in organizing programs and processes within the system:

• Job queue: Programs await execution in this queue.
• Ready queue: Programs ready for execution are temporarily housed here before being selected.
• Device queue: Processes that are currently blocked due to input/output (I/O) device constraints are placed in this queue.

The Importance of Process Scheduling in Operating Systems

• As previously mentioned, the operating system (OS) maintains a queue of numerous programs awaiting execution at any given moment. The OS orchestrates the initiation, suspension, and transition between these programs to ensure seamless operation. A process scheduler becomes imperative in guiding the OS on which program to execute, when to pause, and when to switch to another.
• Through scheduling, the OS efficiently allocates CPU time to each process based on a predefined strategy or algorithm. This approach ensures continuous CPU engagement, optimizing the utilization of resources and minimizing idle periods.
• The result is a reduction in time wastage, ensuring minimal waiting time for program execution. Process scheduling plays a vital role in minimizing the turnaround time for process completion, contributing to overall system efficiency. Additionally, it has a positive impact on reducing response times for programs, enhancing the overall responsiveness of the system.

CPU or Short-term Scheduling Algorithm

Having explored the foundational concepts, let’s delve into the definition of a scheduling algorithm. In an operating system, a scheduling algorithm is the mechanism that determines the allocation of CPU time to specific processes and dictates when such allocations should occur. These algorithms generally fall into two categories:

Non-preemptive scheduling is a scheduling strategy in operating systems where once a process starts its execution, it continues until it completes or enters a waiting state voluntarily. In non-preemptive scheduling, the operating system does not forcefully interrupt a running process to start or resume another process.

In preemptive scheduling, the operating system has the capability to forcefully pause a running process, save its state, and transfer control to another process according to a predefined scheduling algorithm.

CPU Scheduling Algorithms are used to:

• Maximize CPU utilization.
• Maximize throughput (i.e. number of processes to complete execution per unit time)
• Minimize wait, turnaround, and response time.

There are many types of CPU Scheduling Algorithms, I will discuss the most important and used ones in this tutorial:

First Come First Serve (FCFS) Scheduling Algorithm

FCFS (First Come First Serve) is a non-preemptive scheduling algorithm that schedules processes based on their arrival time. The algorithm states that the process that requests the CPU first is allocated the CPU first. It is implemented by using the First in First Out queue. When the CPU is free, it is allocated to the process at the head of the queue.

Here’s a step-by-step explanation of how FCFS works:

1. Arrival of Processes:
   As processes arrive, they are placed in a queue called the ready queue.
2. Execution Order:
   The process at the front of the ready queue (the one that arrived first) is selected for execution.
3. Execution Time:
   The selected process runs until it completes its execution or is blocked by an I/O operation.
4. Completion:
   Once a process finishes, the next process in the queue is selected for execution.
5. Waiting Time:
   The waiting time for each process is the time it spends in the ready queue before getting the CPU.

Advantages of FCFS:

• Simple and easy to understand.
• No starvation (all processes eventually get CPU time).
• It serves as a baseline for understanding more complex scheduling algorithms.

Disadvantages of FCFS:

• May result in poor turnaround time, especially if a long process arrives early, causing subsequent short processes to wait.
• Known as the “convoy effect,” where short processes get stuck behind a long process, leading to inefficient resource utilization.
• FCFS is typically used in scenarios where the order of arrival is considered fair, and no particular priority or criteria influence the execution sequence.

Example of FCFS scheduling algorithm in OS

The table in the video above demonstrates 5 processes that have arrived at the CPU Ready Queue at the same or different times. The process with the minimal arrival time goes first, if two processes arrive at the same time as of our case the process with the lower process ID is executed first. Since the first process (A) has a burst time of 2 units of time (The burst time is the amount of time a process requires to complete its execution), the CPU will remain busy for 2 units of time, which indicates that the second process (B) have to wait for 2 units of time since it arrived at the same time of the first process. Process B will be burst in 4 units of time, then process C that arrived at 3 unit of time enters and takes place at the 6th unit of time to be burst in 1 unit of time and the same goes for the rest of processes. So, the Completion time for Processes A is 2, B is 6, C is 7, D is 8, and E is 9.

In this way, the waiting and turnaround times for all processes can be calculated. Turnaround time = Completion Time — Arrival Time, so the Turnaround time for Processes A is 2, B is 6, C is 4, D is 5, and E is 6.

Waiting time = Turnaround time — Burst Time, so the Waiting time for Processes A is 0, B is 2, C is 3, D is 4, and E is 5.

The average turnaround time = 4.6 and the average waiting time=2.8 unit of time. We can contrast this with other algorithms for the same set of processes.

Shortest Job First (SJF) Scheduling Algorithm

Shortest Job First (SJF) also known Shortest Job Next (SJN) is a CPU scheduling algorithm that selects the process with the smallest burst time for execution. This algorithm can be preemptive or non-preemptive. In non-preemptive SJF, once the CPU cycle is allocated to a process, the process holds it till it reaches a waiting state or terminated. As you see in the example if we have three processes P1 arrives at 0 unit of time and its burst time is 8 and P2 arrives at 0 unit of time and its burst time is 3 and P3 arrives at 3 unit of time and its burst time is 4. P2 will be processed first, then P3 and finally P1.

In preemptive SJF, jobs are put into the ready queue as they come. A process with the shortest burst time begins execution.

As you see in the example if we have three processes P1 arrives at 0 unit of time and its burst time is 8 and P2 arrives at 0 unit of time and its burst time is 3 and P3 arrives at 5 unit of time and its burst time is 4. P2 will be processed first, then P1 starts bursting for one unit of time until P3 appears in the queue then it takes the priority, so P1 goes to ready state and p3 executes, then and finally P1 executes again the remaining 7 units of time.

SJF significantly reduces the average waiting time for other processes awaiting execution, the downside is that longer jobs has to wait more time to get executed.

Example of Non-Preemptive Shortest Job First Scheduling Algorithm:

In the table in the video above, 5 processes have arrived at the CPU Ready Queue at the same or different times. The process with the minimal arrival time goes first, if two processes arrive at the same time as of our case the process with the lower Burst Time is executed first. Since the first process (A) has a burst time of 2 units of time, the CPU will remain busy for 2 units of time, which indicates that the second process (B) will wait for 2 units of time since it arrived at the same time of the first process. Process B will be burst in 4 units of time, then process C that arrived at 3 unit of time enters and takes place at the 6th unit of time to be burst in 1 unit of time and the same goes for the rest of processes. So, the Completion time for Processes A is 2, B is 6, C is 7, D is 8, and E is 9. Because the last three processes arrived at the same time with the same Burst Time, the process with the lower process ID is executed first which in our case C then D then E.

In this way, the waiting and turnaround times for all processes can be calculated. Turnaround time = Completion Time — Arrival Time, so the Turnaround time for Processes A is 2, B is 6, C is 4, D is 5, and E is 6.

Waiting time = Turnaround time — Burst Time, so the Waiting time for Processes A is 0, B is 2, C is 3, D is 4, and E is 5.

The average turnaround time = 4.6 and the average waiting time=2.8 unit of time. Normally Short Job First non-preemptive outperforms First Come First Serve, in our example both performed the same due to the nature of the jobs in the queue, but is this going to be the same if we apply Short Job First preemptive algorithm? Let us discover.

Example of Preemptive Shortest Job First Scheduling Algorithm:

In the table in the video above, 5 processes have arrived at the CPU Ready Queue at the same or different times. The process with the minimal arrival time goes first, if two processes arrive at the same time as of our case the process with the lower Burst Time is executed first. Since the first process (A) has a burst time of 2 units of time, the CPU will remain busy for 2 units of time, which indicates that the second process (B) will wait for 2 units of time since it arrived at the same time of the first process. Process B enters running state for 1 unit of time, then process C, D and E arrives at the 3rd unit of time. Process B goes to ready state and process C enters running state based on burst time priority and as it has lower process id of processes D and E. Then process D enters the running state and once completed process E enters the running state all based on priority in shorter burst time and lower process id, then process B enters running state again consuming 3 units of time to finish the job. So, the Completion time for Processes A is 2, B is 9, C is 4, D is 5, and E is 6.

In this way, the waiting and turnaround times for all processes can be calculated. Turnaround time = Completion Time — Arrival Time, so the Turnaround time for Processes A is 2, B is 9, C is 1, D is 2, and E is 3.

Waiting time = Turnaround time — Burst Time, so the Waiting time for Processes A is 0, B is 5, C is 0, D is 1, and E is 2.

The average turnaround time = 3.4 and the average waiting time=1.6 unit of time. You may have noticed that the Shortest Job First preemptive outperformed Shortest Job First non-preemptive and the First Come First Serve as the priority was given to shorter jobs allowing the processor to interrupt long jobs and move them to ready state in order to give priority for shorter jobs to complete.

Round Robin Scheduling Algorithm

In the Round Robin scheduling concept, the algorithm employs a time-sharing approach. This algorithm is similar to First Come First Serve (FCFS), but with preemption. Each process is allocated CPU time known as a quantum time, which serves to constrain processing time, typically within the range of 1 to 100 milliseconds.

Upon the expiration of the allocated quantum time, the ongoing process is temporarily halted and placed back into the ready queue. If a process completes its tasks within a CPU burst smaller than the time quantum, it promptly releases the CPU, allowing the next process in line to utilize it immediately. Conversely, if a process’s CPU burst exceeds the time quantum, the process is temporarily suspended when the quantum time is reached. It is then re-queued at the tail of the ready queue and subsequently executed after the next process in line.

In a scenario where there are ’n’ processes in the ready queue and a time quantum ‘q’, each process is granted a maximum of 1/n of the CPU time during a single execution, with a limit of ‘q’ time units per CPU scheduling round. Importantly, no process experiences a wait time exceeding (n-1) times ‘q’ units, ensuring a fair and efficient distribution of CPU time among the processes.

How Round Robin Scheduling Algorithm works:

Let us consider 3 processes: P1 with Burst Time 6, P2 with Burst Time 3 and P3 with Burst Time 4 entered the ready queue at zero arrival time. The operating system has set Quantum time at 2 units of time. The process enters the run time or burst time based on the process id, the lowest process id goes first. Once P1 enters the run time, it runs for 2 units of time and then it is moved from the CPU to the ready queue with remaining burst time at 4 per the quantum time frame, then P2 enters for two units of time, and leaves to the ready queue with the remaining 1 unit of time, then P3 enters the burst time and leaves after 2 units of time to the ready queue with 2 units of time remaining. Now again P1 enters the burst time and consumes two units of time and leaves back to the ready queue with 2 units of time left. Then P2 enters the processor then burst in 1 units of time, as the burst time is less than the quantum time, the processor moved the next high priority process from the ready queue, which in this case P3 that is going to be burst in 2 units of time. Again, back to the ready queue to bring P1 which will be burst in two units of time and then the ready queue is empty, and all processes are completed.

Round Robin Scheduling Algorithm Example:

The table in the video above demonstrates 5 processes that have arrived at the CPU Ready Queue at the same or different times. The process with the minimal arrival time goes first, if two processes arrive at the same time as of our case the process with the lower process ID is executed first. Since the first process (A) has a burst time of 2 units of time, the CPU will remain busy for 2 units of time, which indicates that the second process (B) will wait for 2 units of time since it arrived at the same time of the first process. Process B enters running state for 2 units of time then move to the ready state per the Quantum Time limit, process C, D and E arrives at the 3rd unit of time to the ready time. Process C enters running state as it has lower process id of processes D and E. Then process D enters the running state and once completed process E enters the running state all based on lower process id, then process B enters running state again consuming 2 units of time to finish the job. So, the Completion time for Processes A is 2, B is 9, C is 5, D is 6, and E is 7.

In this way, the waiting and turnaround times for all processes can be calculated. Turnaround time = Completion Time — Arrival Time, so the Turnaround time for Processes A is 2, B is 9, C is 2, D is 3, and E is 4.

Waiting time = Turnaround time — Burst Time, so the Waiting time for Processes A is 0, B is 5, C is 1, D is 2, and E is 3.

The average turnaround time = 4 and the average waiting time=2.2 unit of time.

The Python code on this github link executes Round Robin Scheduling Algorithm with different arrival time.

Real Life Examples

The choice of scheduling algorithm depends on the specific needs of the system. First Come First Serve is a good choice for batch systems where turnaround time is not critical such as: (Payroll processing, Bank statement generation, Email filtering, etc.)

Shortest Job First is a good choice for interactive systems, where response time is important such as: (Web servers, Database systems, Graphical user interface, etc.).

Round Robin is a good choice for systems with a mix of batch and interactive workloads such as: (Network routers, Operating system kernels, Embedded systems, etc.)

Those algorithms can be combined in different ways in a wider scheduling algorithms, such as Multi-level Queue or Multi-level Feedback Queue algorithms.