|
Read later
Save important notes and articles from internet using arusaquotes app.
Today we will practice problems on different types of CPU Scheduling Algorithms. We will see here that how CPU scheduler uses scheduling algorithms during execution of process. Let's see.
FCFS Example
Consider the above set of processes that arrive at time zero. The length of the CPU burst time given in millisecond.
Now we calculate the average waiting time, average turnaround time and throughput.
Average Waiting Time
First of all, we have to calculate the waiting time of each process.
Waiting Time = Starting Time - Arrival Time
Waiting time of
P1 = 0
P2 = 5 - 0 = 5 ms
P3 = 29 - 0 = 29 ms
P4 = 45 - 0 = 45 ms
P5 = 55 - 0 = 55 ms
Average Waiting Time = Waiting Time of all Processes / Total Number of Process
Therefore, average waiting time = (0 + 5 + 29 + 45 + 55) / 5 = 25 ms
Average Turnaround Time
First of all, we have to calculate the turnaround time of each process.
Turnaround Time = Waiting time in the ready queue + executing time + waiting time in waiting-queue for I/O
Turnaround time of
P1 = 0 + 5 + 0 = 5ms
P2 = 5 + 24 + 0 = 29ms
P3 = 29 + 16 + 0 = 45ms
P4 = 45 + 10 + 0 = 55ms
P5 = 55 + 3 + 0 = 58ms
Average Turnaround Time = (Total Turnaround Time / Total Number of Process)
Total Turnaround Time = (5 + 29 + 45 + 55 + 58)ms = 192ms
Therefore, Average Turnaround Time = (192 / 5)ms = 38.4ms
Throughput
Here, we have a total of five processes. Process P1, P2, P3, P4, and P5 takes 5ms, 24ms, 16ms, 10ms, and 3ms to execute respectively.
Throughput = (5 + 24 +16 + 10 +3) / 5 = 11.6ms
It means one process executes in every 11.6 ms.
SJF (Shortest Job First) Scheduling
|
| SJF Scheduling |
Average Waiting Time
We will apply the same formula to find average waiting time in this problem. Here arrival time is common to all processes(i.e., zero).
Waiting Time for
P1 = 3 - 0 = 3ms
P2 = 34 - 0 = 34ms
P3 = 18 - 0 = 18ms
P4 = 8 - 0 = 8ms
P5 = 0ms
Therefore, Average Waiting Time = (3 + 34 + 18 + 8 + 0) / 5 = 12.6ms
Average Turnaround Time
According to the SJF Gantt chart and the turnaround time formulae,
Turnaround Time of
P1 = 3 + 5 = 8ms
P2 = 34 + 24 = 58ms
P3 = 18 + 16 = 34ms
P4 = 8 + 10 = 18ms
P5 = 0 + 3 = 3ms
Therefore, Average Turnaround Time = (8 + 58 + 34 + 18 + 3) / 5 = 24.2ms
Throughput
Here, we have a total of five processes. Process P1, P2, P3, P4, and P5 takes 5ms, 24ms, 16ms, 10ms, and 3ms to execute respectively. Therefore, Throughput will be same as above problem i.e., 11.6ms for each process.
Round Robin Scheduling Example
Here is the Round Robin scheduling example with gantt chart. Time Quantum is 5ms.
|
| Round Robin Scheduling |
Average Waiting Time
For finding Average Waiting Time, we have to find out the waiting time of each process.
Waiting Time of
P1 = 0 + (15 - 5) + (24 - 20) = 14ms
P2 = 5 + (20 - 10) = 15ms
P3 = 10 + (21 - 15) = 16ms
Therefore, Average Waiting Time = (14 + 15 + 16) / 3 = 15ms
Average Turnaround Time
Same concept for finding the Turnaround Time.
Turnaround Time of
P1 = 14 + 30 = 44ms
P2 = 15 + 6 = 21ms
P3 = 16 + 8 = 24ms
Therefore, Average Turnaround Time = (44 + 21 + 24) / 3 = 29.66ms
Throughput
Throughput = (30 + 6 + 8) / 3 = 14.66ms
In 14.66ms, one process executes.
Shortest Remaining Time First(SRTF)
|
| SRTF Scheduling |
Average Waiting Time
First of all, we have to find the waiting time for each process.
Waiting Time of process
P1 = 0ms
P2 = (3 - 2) + (10 - 4) = 7ms
P3 = (4 - 4) = 0ms
P4 = (15 - 6) = 9ms
P5 = (8 - 8) = 0ms
Therefore, Average Waiting Time = (0 + 7 + 0 + 9 + 0) / 5 = 3.2ms
Average Turnaround Time
First of all, we have to find the turnaround time of each process.
Turnaround Time of process
P1 = (0 + 3) = 3ms
P2 = (7 + 6) = 13ms
P3 = (0 + 4) = 4ms
P4 = (9 + 5) = 14ms
P5 = (0 + 2) = 2ms
Therefore, Average Turnaround Time = (3 + 13 + 4 + 14 + 2) / 5 = 7.2ms
Throughput
Troughput = (3 + 6 + 4 + 5 + 2) / 5 = 4ms
Therefore, each process takes 4ms to execute.
Priority Scheduling Example
|
| Priority Scheduling Example with Gantt Chart |
Average Waiting Time
First of all, we have to find out the waiting time of each process.
Waiting Time of process
P1 = 3ms
P2 = 13ms
P3 = 25ms
P4 = 0ms
P5 = 9ms
Therefore, Average Waiting Time = (3 + 13 + 25 + 0 + 9) / 5 = 10ms
Average Turnaround Time
First finding Turnaround Time of each process.
Turnaround Time of process
P1 = (3 + 6) = 9ms
P2 = (13 + 12) = 25ms
P3 = (25 + 1) = 26ms
P4 = (0 + 3) = 3ms
P5 = (9 + 4) = 13ms
Therefore, Average Turnaround Time = (9 + 25 + 26 + 3 + 13) / 5 = 15.2ms
Throughput
Throughput = (6 + 12 + 1 + 3 + 4) / 5 = 5.2ms
Therefore, each process takes 5.2ms to execute.
Recommended Articles
Starvation and Aging in Operating Systems
Scheduling Algorithms in Operating System
Memory Management in Operating System
Spooling in Operating System
What is Deadlock in OS | Detection and Recovery from Deadlock
Threads in Operating System
Understanding Semaphores in Operating System
Implementing Arrays and Linked Lists in Your Programs
Introduction to Stacks and Their Applications in Programming
Learn Android App Development using Kotlin.
Start Learning