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

 

Scheduling Algorithms:

Following are the scheduling algorithms as listed below:
CPU scheduling algorithms in OS
 

 

 

 

 

 

 

 

 

 

 

 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:

Come First Served Scheduling
 

 

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:

Come First Served Scheduling
 
 
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:
Come First Served Scheduling
 
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
 
Come First Served Scheduling

 

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.
 
Shortest Job First (SJF)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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.
Shortest Job First (SJF)
 
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.

 

Priority Scheduling

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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.
Priority Scheduling
 
 
 
 
 
 

















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.
 
Round Robin Scheduling








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.
Round Robin Scheduling
 
 

















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.
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 Scheduling

                                                                   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 Scheduling

                                               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.

Leave a Reply

Your email address will not be published. Required fields are marked *