Computing time for CPU Scheduling Algorithms using Tabular Method

The usual method of computing average time, average wait time, turnaround time and average turnaround time for processes is to make a Gantt Chart and then compute these times.

In this post, we explore another way to compute the average turn around time and average wait time for processes based on the same logic given by the specific algorithms.

Popular CPU scheduling algorithms are as follows

  1. First Come, First Serve
  2. Shortest Job First
  3. Priority Scheduling
  4. Round Robin
Throughout the post, we will use the same example to compute the times using FCFS.Consider the following processes.
CPU Scheduling
CPU Scheduling

We will compute the average turnaround time and average wait time for the processes using the tabular method.

First Come, First Serve

At first, make a table as follows, with processes ordered in the way they arrive in the queue.

CPU Scheduling - FCFS
CPU Scheduling – FCFS

The first column is for processes in the ready queue and listed in the order as they arrive. The arrival of all three processes is 0.

  1. Fill the first row with burst time of process P1.
  2. Fill the second row with burst time of process P2 because it starts after P1.
  3. Similarly, fill the burst time of P3 in the third row last column because P3 start after P2 process.
  4. Each column is Turnaround time for each process in the queue.
Average Turnaround Time = (24 + 27 + 30)/3 = 81/3 = 27 ms
Note: waiting time of the first process is always 0.
To compute the average waiting time of each process add all the value in row Total, except the last column and divide by a number of processes.
Average Waiting Time = (0 + 24 + 27)/3 = 51/3 = 17 ms

First Come, First Serve with Change in Order

Suppose we change the order of execution. Does that change the average waiting time and turnaround time of the processes scheduled using the FCFS,  let’s find out the answer.
Average Turnaround Time = (3 + 6 + 30)/ 3 = 13 ms

Average Waiting Time = (0 + 3 + 6)/3 = 3 ms

In the above example, process P3 is the first, process P2 is second and process P4 is the third in that order. We already know the wait time of the process P3 = 0 because it is the first process to arrive in the queue.

For turnaround time take the total of row “Total” and divide by 3 will give you the answer and for the average waiting time, the sum of first two columns of the row “Total” divided by 3 will give you the answer.

First Come, First Serve with different Arrival Times

Consider another example, here process arrive at the ready queue with different times.
FCFS Different Arrival Time
FCFS Different Arrival Time

To compute the average turnaround time and average waiting time using the tabular method. Draw following table but this time we have different arrival times for each process.

FCFS Average Wait Time Using Tabular Method
FCFS Average Wait Time Using Tabular Method
 To calculate the individual Turnaround time for each process, we need to take the column total for minus the arrival time in the same column.
For Example,
In the  first column, we have a Total = 12 – 0 (Arrival Time) = 12 ( Turnaround time for P1)
In the second column, we have a Total = 18 – 1( Arrival Time) = 17 ( Turnaround time for P2).
Average Turnaround time = (12 + 17 + 23)/3 = 52/3 = 17.33 ms.
To compute the waiting time of each process, take each column total – next process arrival time and you get the results.
 For example,
waiting time for P1 = 0
waiting time for P2 = 12 – 1 = 11
waiting time for P3 = 18 – 4 = 14
Average Waiting Time = (0 + 11 + 14) =  25/3 = 8.33 ms

Conclusion

The tabular method employs the same method as performing calculations using Gantt Char but if the number of processes and other data becomes too complex then you may tend to make mistakes. Then using the Tabular method simplifies the calculations.
In the next post in this series, we will see more complex examples and how they can be tackled using this method of calculation.

Bibliography

Abraham Silberschatz, Peter B. Galvin, Greg Gagne, A Silberschatz. 2012. Operating System Concepts, 9th Edition. Wiley.

 

Advertisements