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.