CPU Scheduling Algorithm: Operating System

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.

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.

Must Check: History of Operating Systems

Explore Interprocess Communication in Operating System

Some of the more common algorithms include:

Outline

• What is the CPU Scheduling Algorithm?
• An important CPU Scheduling Algorithm
  • First come First Serve
  • Shortest Time Job fFrst
  • Round-robin
  • Shortest Remaining Time First Algorithm
  • Priority Scheduling algorithm
• Conclusion

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.

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.

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!!!