Computing Times for CPU Scheduling using Tabular Method – II

Previous Article
Next Article

In the previous post, we computed the average waiting time and average turnaround time for processes that are scheduled with First Come, First Serve (FCFS) algorithm using Tabular Method.


In this post, we will compute average waiting time and average turnaround time for scheduled processes with another algorithm called Shortest Job First (SJF). You may have already seen an example of SJF in the previous post when we changed the order of the process in FCFS. In shortest job first algorithm, the process with shortest burst time is scheduled first for CPU time.

There is two version of this algorithm.

1. Preemptive.
2. Non-Preemptive

The preemptive version is also known as Shortest-Job-Remaining-Time and Shortest-Job-First is the non-preemptive version. For example, consider following scheduled processes.

CPU Scheduling SJF
Figure1: CPU Scheduling SJF

We see that there are 4 processes scheduled according to Shortest-Job-First and the arrival time of the processes is same which is 0.

The burst time decides the order of the processes for CPU scheduling. The order is a job with lowest burst time has the highest priority.

P4 -> P1 -> P3 -> P2

We will use this order in Tabulation Method for computing average wait time and turnaround time as follows.
The table has process ordered according to shortest job first algorithm and the arrival time is same for each process. The order of the process is most important for this method to work and the order is decided by the burst time for each process.

Figure: CPU Scheduling SJF
Figure2: CPU Scheduling SJF

Let’s fill the table according to burst time of each process in such a way that only upper triangular part has the entries and lower triangular part of arrival time is not filled. Also, each row next to the process will have only burst time of that process and nothing else.

Figure3: CPU Scheduling SJF
Figure3: CPU Scheduling SJF

Each column total is nothing but Turnaround time for the process. Therefore,

Average Turnaround Time = (3 + 9 + 16 + 24)/4 = 52/4 = 13 ms

The first process in the order is P4 whose wait time is 0 and the first three column total gives wait time for the process – P1, P3, P2 respectively.

Average Waiting Time = (0 + 3 + 9 + 16)/4 = 28/4 = 7 ms

Shortest Job First (SJF) with Different Arrival Time

Shortest Job First Scheduling with a different arrival time for each process add more complexity, but you will find it easy with the Tabular Method. You can easily compute the average waiting time and average turnaround time.

However, you have to consider these very important points before drawing a table.

  1. First, consider the arrival time of the processes.
  2. Next, select the process with the smallest burst during that arrival time.
  3. Reiterate the first and the second step for next arrival time.
  4. Order the arrival times according to the order of processes.

Consider another schedule of processes,

SJF with different arrival time
Figure4: SJF with different arrival time

At this time, the processes are not ordered according to SJF and arrival time is not ordered. We order the process and the arrival time for Tabulation method.

SJF Algorithm using Tabular Method
Figure5: SJF Algorithm using Tabular Method

To compute individual turnaround time of each process we subtract the total of each column with arrival time. The processes are ordered as follows

Process Order          :          P1 ->  P3 ->  P2 -> P4
Arrival time Order  :           0          4          2        5
Average Turnaround Time = (7 + 4 + 10 + 11)/4 = 32/4 = 8 ms
To compute the waiting time of each process using the following formula.
Waiting time = (Column Total of current process – Burst time of  the process)
Figure6: CPU Scheduling SJF Wait Time
Figure6: CPU Scheduling SJF Wait Time
Waiting Time of each process
P1 = 7 – 7 = 0
P3 = 4 – 1 = 3

P2 = 10 – 4 = 6

P4 = 11 – 4 = 7

Average Waiting Time

(0 + 3 + 6 + 7)/4 = 16/4 = 4 ms


The computation with different arrival time is difficult but systematic with Tabular Method, instead of using a Gantt Chart. There will be no mistakes in computation.  In the next post, we will use Tabular Method to compute the CPU Scheduling times for Priority Scheduling.


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


Previous Article
Next Article