CPU Scheduling Algorithm: Operating System

CPU Scheduling Algorithm: Operating System

7 mins read11.6K Views Comment
clickHere
Updated on Nov 16, 2023 12:52 IST

Scheduling of processes is very important thing in an operating system. We have covered important CPU scheduling algorithms in this article, with solved examples and proper explanations.

2022_06_8.jpg

There are different processes, and every process wants to get executed, but all cannot be executed simultaneously. So that is why we need Scheduling.CPU does this Scheduling. That’s why we call it CPU scheduling. CPU Scheduling Algorithm is an essential part of any operating system. Various algorithms can be used, each with advantages and disadvantages.

Some of the more common algorithms include:

Outline

What is the CPU Scheduling Algorithm?

CPU scheduling algorithm uses to schedule process execution by determining which process should be removed from execution and which process should be executed. And at the end, the main goal is to engage the CPU all the time, which means the CPU should not be idle.

Types of Scheduling Algorithms

  1. Preemptive process-These processes are based on the process priority. If a low priority process is executing and the higher priority process enters, then the low priority process is preempted(stop running) and executes the high priority process first.
  2. Non-preemptive process-In these algorithms, if any process is assigned CPU, it will execute entirely or be released in case of context switching or termination. There is no process priority in this.

Some important terms:

  1. Throughput-The number of processes completing execution per unit time. It must be maximum.
  2. Turnaround time- Time taken by the processes to finish their execution. It must be a minimum.
  3. Waiting time-The time for which the process stays in the ready queue. It must be a minimum.

Important CPU Scheduling Algorithm

1. First come, first serve

FCFS is a Non-Preemptive scheduling algorithm, where the process that arrives first is executed first completely, then the second process is picked up for execution, and so on. This means FCFS is non-preemptive scheduling. It is the easiest and simplest CPU scheduling algorithm while SJF is a bit more complex, it tries to execute the shortest jobs first to minimize the overall completion time. FCFS is managed on the FIFO queue(First in first out).

.

Waiting time=Turn around time-Burst time

Waiing time=0+(5-1)+(8-2)+(6-3)/4=13.25 sec.

At Time=0

  • Process 0 is a ready queue so it will execute completely as preemption is not there.

At Time=5

  • Then Process 1 comes after process 0, it will execute now for 3 sec.
  • All processes are in the ready queue by now.

At Time=8

  • Process 2  will execute for 8 sec.

At Time=16

  • Process 3 will execute for 9 sec.

Also read: What is Operating Systems (OS) – Types, Functions, and Examples.

Operating System Interview Questions
Operating System Interview Questions
In this article you will find important operating system questions which are likeable to be asked in interview.
Distributed Operating System
Distributed Operating System
Have you ever heard of distributed operating systems? Let's explore it in depth, starting from about, types, advantages, disadvantages and everything in detail! An operating system is a set of...read more
Interprocess Communication in Operating System
Interprocess Communication in Operating System
Processes in operating systems need to communicate with each other. Interprocess communication (IPC) is a process that allows different processes of a computer system to share information. If you want...read more

Explore: Operating System Online Courses & Certifications

2. Shortest Time Job First

A non-preemptive algorithm in which the process with the shortest burst time is selected for execution.

SJF is a no preemptive scheduling algorithm, which means process 1 will not be completely executed, and process 2 will start execution. Later on, process 1 will get a chance to get executed. This algorithm is used to break ties if two processes have the same burst time by checking the arrival time. The process which arrived early in the ready queue will be executed. Let’s understand with an example.

Waiting time=Turn around time-Burst time

Waiting time=(5-3)+(8-4)+(2-2)+(10-4)/4=3 sec.

Note: We are taking the time in seconds in all examples.

At Time=0

  • No process is there in the ready queue.
  • CPU will be in an idle state

At Time=1

  • Process 1 and 3 are in the ready queue.
  • Process 3 will execute as its burst time is less than Process 1.

At Time=3

  •  Process1 and  2 are in the ready queue, but the burst time of process 1more than process 1(4>3).
  • Process 1 will execute.

At Time=6

  • Processes 2 and 4 are in the ready queue.
  • Process 2 will execute. 

At Time=10

  • Process 4 will execute.
Types of Operating Systems
Types of Operating Systems
There are different types of operating system.This article includes imporant types of operating systems with diagrams. This article covered types of operating systems multiprogramming, multiprocessor, distributed, batch, time-sharing, and multitasking...read more
Process Scheduling: Operating System
Process Scheduling: Operating System
Have you ever wondered how your computer juggles multiple tasks simultaneously? To know that, you must read this blog on process scheduling in the operating system! This article includes...read more
Process Management in Operating System
Process Management in Operating System
Process management in operating systems involves the handling and coordinating multiple processes executed by the CPU. It includes tasks like process scheduling, creation, execution, and termination, ensuring efficient and fair...read more

3. Round-Robin Scheduling

A fair algorithm that distributes CPU time equally among all of the processes.

The round-robin CPU scheduling algorithm is a CPU scheduling algorithm that evenly distributes CPU time among all of the processes in the queue. This algorithm is simple to implement and can be used in various situations.

When a process is added to the queue, the CPU scheduler will assign it a time slot. The CPU scheduler will swap it out for another process if the process is currently running. The process will then run for the time specified by its time slot. Once the process has finished its time slot, it will be added back to the end of the queue.

 

Waiting time=Turn around time-Burst time

Waiting time=(32-21)+(8-3)+(21-6)+(15-2)/4=11 s.

At Time=0

  • All processes are in the ready queue.
  • Process 1 will execute 5 sec as time quantum =5.

At Time=5

  • Process 2 will execute for 3 sec(burst time) and its execution is complete.

At Time=8

  •  Process 3 will execute.

At Time=13

  • Process 4 will execute for 2 sec and its execution is complete. 

At Time=15

  • Process 1 is left with a burst time of (21-5=17). So now process 1 will execute for 5 sec.

At Time=20

  • Process 1 will preempt
  • Process 3 will execute(burst time left=1).

At Time=21

  • All processes are executed only Process 1 is left.
  • Process 1 will execute for 5 sec.

At Time=26

  • Again Process 1 will execute for 5 sec.

At Time=31

  • Again Process 1 will execute for 1 sec.
 

4. Shortest Remaining Time First Algorithm

A preemptive version of shortest job first algorithm

 

The shortest remaining time algorithm is a heuristics algorithm used to find the best solution to a problem within a limited amount of time. The algorithm works by searching through all the possible solutions and selecting the one that will result in the shortest amount of time being spent on the problem. Resources are allocated to processes according to the shortest remaining time.

Waiting time=Turn around time-Burst time

Waiting time=(9-5)+(3-3)+(11-4)+(1-1)/4=1 sec.

At Time=0

  • Process 1 is in the ready queue.
  • Process 1 will execute for 1 sec and will preempt after that.

At Time=1

  • Process 2 will execute for 3 sec(burst time) and its execution is complete.
  • Meanwhile, Process 2 was executing process 3 comes in the ready queue but process 2 does not preempt as process 3 burst time is more than process 2. 

At Time=4

  •  Process 4 burst time is less than process 2(which is executing). So process 2 will be prompted and process 4 will start executing.
  • Process 4 execution is complete.

At Time=5

  • Now two processes 1 and 3 are left to be executed. The burst time of process1 and 3 are equal (i.e. 4). So process 4 arrival time is less than process 3 so process 1 will be executed.

At Time=9

  • Process 3 will execute.

5. Priority Scheduling Algorithm

A non-preemptive algorithm in which processes are executed according to the priority assigned.

The priority scheduling algorithm is a heuristics algorithm that is used to find the best solution to a problem with a limited amount of resources. In this, priority is assigned to each process. And the highest priority process will be executed first and then the second-lowest, and so on. The priority is decided o the basis of time and memory requirements. If two processes have the same priority, then check the arrival time. The process with a lower arrival time will be picked for execution in that case.

Waiting time=Turn around time-Burst time

Waiting time=(4-4)+(14-3)+(10-1)+(6-5)+(7-2)/5= 5.2 s.

NOTE: Priority order is 1(high) -5 (low).

At Time=0

  • Only Process 1 is in the ready queue so it will execute without preemption.
  • So no need to check the priority.

At Time=4

  • Process 4 will execute for 5 sec(burst time)as its priority is highest i.e. 1.
  • Process 5 is also having the same priority but process 4 arrival time is less than process 5 

At Time=9

  • Process 5 will execute.

At Time=11

  • Process 3 will execute according to its priority.

At Time=12

  • Process 2 will execute.

Conclusion

In this article, we have covered the most important scheduling CPU algorithm with properly solved examples. If you liked the article, please share it with your friends too.

Happy Learning!!!

FAQs

What is multilevel queue scheduling?

Multilevel queue scheduling divides the ready queue into multiple queues, each with a different priority level. Processes are assigned to a specific queue based on their characteristics. Each queue may have its own scheduling algorithm.

What is the priority scheduling algorithm?

Priority scheduling assigns a priority value to each process based on factors like the priority level assigned by the user or the nature of the task. The CPU is allocated to the process with the highest priority, and preemption may occur if a higher-priority process arrives.

What is the Round Robin scheduling algorithm?

Round Robin (RR) is a preemptive CPU scheduling algorithm that assigns a fixed time quantum to each process in the ready queue. Each process is allowed to execute for a specific time slice (quantum), after which it is moved to the end of the queue, and the next process gets a chance to run.

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio