CPU Scheduling Algorithms in OS || 7 Types CPU scheduling in OS

 

Scheduling Algorithms:

Following are the scheduling algorithms as listed below:

 

 

 

 

 

 

 

 

 

 

 

 First Come First Served Scheduling (FCFS)

Simplest scheduling algorithms, it assigns cpu to the process which arrives first. Easy to understand and can easily be implemented using queue data structure. Always non preemptive in nature.

Example1: consider the following set of process with their arrival time, execution time (in minutes per sec):

Process	Burst Time
P1	25
P2	04
P3	04

Calculate the average waiting time , Average turnaround time and average response time for FCFS.

Gantt chart 

P1

P2

P3

  

                             0                                         25                                      29                            33

Now we calculate the waiting time for each process  

                    Waiting time=Response time-Arrival Time

                          P1 = 0 – 0 = 0 

                         P2 = 25 – 0 = 25

                        P3 = 29 – 0 = 29

Total waiting time =   54 MS

The Average Waiting Time will be:

 

 

Now we calculate the Response Time for each process 

 

Response Time = first Response – Arrival Time

 

P1= 0 – 0 = 0

 

P2= 25 – 0 =25

 

P3= 29 -0 =  29

 

Total Response Time =   54 MS

The Average Response Time will be:

 

 

Now we calculate the Turnaround Time for each process 

Turnaround Time = Execution Time + Waiting Time

Turnaround Time = Finished Time  –  Arrival Time

P1= 25 – 0 = 25

P2= 29 – 0 =29

P3= 33 -0 =  33

Total Turnaround Time =   87 MS

The Average Turnaround Time will be:

 

Example 2: consider the following set of process with their arrival time, execution time (in minutes Sec): Calculate the average waiting time and Average turnaround time for FCFS.

Process	Burst Time	Arrival Time
P1 P2 P3 P4	7 4 8 6	0 2 4 6

    Gantt chart     

P1

P2

P3

P4

                     

 

  0                           7                             11                           19                         25

 

 

Waiting Time = Response Time – Arrival Time

 

Waiting Time = Turnaround Time – Burst Time (Execution Time)

 

P1= 7–7 = 0

 

P2= 9 – 4 = 5

 

P3 =15 – 8 = 7

 

P4 =19 – 6 = 13

 

Total Waiting Time = 25 MS

 

Average Waiting Time = 25/4 = 6.2 MS

Now we are going to calculate the turnaround time:

Turnaround Time = Finished Time – Arrival Time

 

P1= 7–0 = 7

P2= 11 – 2 = 9

P3 =19 – 4 = 15

P4 =25 – 6 = 19

 

Total Turnaround Time = 50 MS

Average Turnaround Time = 50/4  = 12.5 MS

 

Shortest Job First (SJF)

Simplest scheduling algorithms, out of all available process cpu is assigned to process having smallest burst time requirement. Easy to understand and can easily is implemented using queue data structure. Other name of this algorithm is shortest process next (SPN).can be used both non preemptive and preemptive in nature. SJF algorithm gives the minimum average time for a given set of processes.

 

Example1: consider the following set of process with execution time (in minutes per sec):

Process	Burst Time
P1	09
P2	04
P3	18
P4	80

Calculate the average waiting time, Average turnaround time and average response time for SJF with non-preemptive approach.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Now we calculate the waiting time for each process  

  Waiting time=Response time-Arrival Time

                               Or

WT= Turnaround Time – Burst Time

P1 = 13 – 9 = 4

P2 = 04 – 4 = 0

P3 = 31 – 18 = 13

P4 = 111 – 80 = 31

Total waiting time =   48 MS

The Average Waiting Time will be:

AWT= 48/4 = 12 MS.

Now we calculate the Response Time for each process 

Response Time = first Response – Arrival Time

In Non-preemptive approach waiting time and response time are same.

Now we calculate the Turnaround Time for each process 

Turnaround Time = Finished Time  –  Arrival Time

P1 = 13 – 0  = 13

P = 04 – 0  = 04

P3 = 31 – 0  = 31

P4 = 111– 0 =111

Total Turnaround Time =   159 MS

The Average Turnaround Time will be:

 

TAT= 159/4 =  39.7 MS.                           ANS.

 

 

Example 2: consider the following set of process with their arrival time, execution time (in Seconds). Calculate the average waiting time and Average turnaround time for SJF with non-preemptive approach.

 

Waiting Time = Turnaround Time – Burst Time (Execution Time)

 3+11+3+0+7

Total Waiting Time = 24 S

Average Waiting Time = 24/5 = 4.8 S

Now we are going to calculate the turnaround time:

Turnaround Time = Finished Time – Arrival Time

4+15+5+6+10

Total Turnaround Time = 40 S

 

Average Turnaround Time = 40/5  = 8 S                                        Ans.

 

Priority Scheduling

In the priority scheduling the process enter into the ready queue according to priority.

The process of highest priority enters into the ready queue. SJF is a general form of priority scheduling where the priority is the inverse of the next cpu burst. Can be used both non preemptive and preemptive scheduling.

Example1: consider the following set of process with execution time (in minutes):

Process	Burst Time	Priority
P1	9	5
P2	1	1
P3	2	3
P4	1	4
P5	4	2

Calculate the average waiting time, Average turnaround time and average response time for Priority Scheduling with non-preemptive approach.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Now we calculate the waiting time for each process  

WT= Turnaround Time – Burst Time

P1 = 17 – 9  = 8

P2= 1 – 1    = 0

P3= 7  – 2    = 5

P4= 8  – 1  = 7

P5= 5 – 4   = 1

Total waiting time =   21 Minutes

The Average Waiting Time will be:

AWT= 21/5 = 4.2 Minutes

Now we calculate the Response Time for each process 

Response Time = first Response – Arrival Time

In Non-preemptive approach waiting time and response time are same.

Now we calculate the Turnaround Time for each process 

Turnaround Time = Finished Time  –  Arrival Time

P1= 17 – 0  = 17

P2= 1 – 0   = 1

P3= 7 – 0   = 7

P4= 8 – 0  = 8

P5= 5 – 0  = 5

Total Turnaround Time =   38 Minutes

The Average Turnaround Time will be:

 

TAT= 38/5 =  7.6 Minutes                            ANS.

 

 

Example 2: consider the following set of process with their arrival time, burst time (in Seconds). Calculate the average waiting time and Average turnaround time for Priority Scheduling with non-preemptive approach.

 

 

 

 

 

 

Waiting Time = Turnaround Time – Burst Time (Execution Time)

0 + 3 + 5 + 5 + 9

Total Waiting Time = 22 Sec

Average Waiting Time = 22/5 = 4.4 Sec

Now we are going to calculate the turnaround time:

Turnaround Time = Finished Time – Arrival Time

4 + 6 + 6 + 10 + 11

Total Turnaround Time = 37 Sec

 

Average Turnaround Time = 37/5  = 7.5 Sec                                   Ans.

 

Round Robin Scheduling:

The round robin scheduling algorithm is designed especially for time sharing system. It is similar to FCFS scheduling, but preemption is added to switch b/w process.

 

A small unit of time, called time quantum (time slice) is defined. The ready queue is used as circular queue.  Round robin scheduling response time is better than other.

Round robin scheduling is always preemption in nature.

 

A time quantum is generally from 01 to 100 milliseconds.

Example1: Let following table:

Process	Burst Time
P1	27
P2	5
P3	3

Time Quantum is 5.

Calculate the average waiting time for Round robin scheduling.

Gantt chart                

                  P1,p2,p3,p1,p1,p1,p1,p1

P1

P2

P3

P1

P1

P1

P1

P1

          0          5                      10            13                      18                            23                        27               32                35

Now we calculate the waiting time for each process  

WT= TAT  – Burst Time

P1 = 35 – 27  = 8

P2= 10 – 5    = 5

P3= 13  – 3    = 10

Total waiting time =   23 Minutes

The Average Waiting Time will be:

 

AWT= 23/3 = 7.6 Minutes                           Ans.

 

 

Example 2: consider the following set of process with their arrival time, burst time (in Seconds). Calculate the average waiting time and Average turnaround time for round robin scheduling. Time Quantum is 2.

 

 

Waiting Time = Turnaround Time – Burst Time (Execution Time)

7 + 6 + 2 + 4

Total Waiting Time = 19 Sec

Average Waiting Time = 19/4 = 4.75 Sec

Now we are going to calculate the turnaround time:

Turnaround Time = Finished Time – Arrival Time

 12  + 10  +4  + 5

Total Turnaround Time = 31 Sec

 

Average Turnaround Time = 31/4  = 7.75 Sec                                   Ans.

 

Shortest Remaining Time Next (SRTN):

·        It is the preemptive version of SJF.

·        Shortest Remaining Time, also known as shortest remaining time first.

·        In this algorithm, the process with the smallest amount of time remaining until completion is selected to execute.

·        Process will always run until they complete or a new process is added that requires a smaller amount of time.

·        Shortest remaining time is advantage because short process are Handled very quickly.  

Example: consider the following set of process with their arrival time, burst time (in Seconds). Calculate the average waiting time and Average turnaround time for shortest remaining time next.

 

Now we calculate the waiting time for each process  

WT= Turnaround Time – Burst Time

4 + 0 + 7 + 0

Total waiting time =   11 Seconds

The Average Waiting Time will be:

AWT= 11/4 = 2.7 Seconds

Now we calculate the Turnaround Time for each process 

Turnaround Time = Finished Time – Arrival Time

9 + 3  + 11 + 1

Total Turnaround Time =    24 Seconds

The Average Turnaround Time will be:

TAT= 24/4 =  6 Seconds

                         

Now we calculate the Response Time for each process 

Response Time = first Response – Arrival Time

0 + 0 + 7 + 0

Total Response Time =    7 Seconds

The Average Response Time will be:

 

TAT= 7/4 =  1.7 Seconds                                             Ans.

 

Multi-Level Queue Scheduling

Multi-Level Queue (MLQ) scheme solves the mix job problem by maintaining separate “ready” queues for each type of job class and apply different scheduling algorithms to each.

 

The foreground queue might be scheduled by RR algorithm while background queue is scheduled by FCFS algorithm.

Multi-Level Queue

 

 

 

 

 

 

 

 

 

  Multi-Level Feedback Queue Scheduling

A multilevel feedback queues is a scheduling algorithm designed by .

Multilevel feedback queues scheduling, however, allows a process to move between queues. The idea is to separate process with different CPU burst time.Leonard Kleinrock in 1970

Multi-Level Feedback Queue

 

 

How did you like this article CPU Scheduling Algorithms in OS | 7 Types CPU scheduling in OS? We hope that this article is about CPU Scheduling Algorithms? You must have liked it and you have got to know a lot of new things in it.

If you have any question or any suggestion regarding this post in your mind, then you can message in the comment box below.

If you liked this article, please share this article on social media sites like Facebook and Whatsapp etc. Thank you for your time.