Average wait time for pre-emptive priority scheduling

operating systemprocessscheduling

Given the following table for calculating and average waiting time for the processes for priority based preemptive scheduling.

Process     Burst Time       Priority          
P1             10               3  
P2             1                1  
P3             2                4
P4             1                5
P5             5                2

The gantt chart would be as follows:

| P2 | P5 | P1 | P3 | P4  |
0    1    6    16   18   19

I have following questions:

1) Is the turn around time = 19 units?

2) How do i calculate average waiting time? Is there a formula?

3) What if few processes have the same priority?

I am new to OS. I have viewed some other similar questions but I did not get exactly how to do it.

Best Answer

Given the data,before you have to implement priority based preemptive scheduling, you should know the following facts :-

  1. priorities are usually numeric over a range
  2. high numbers may indicate low priority (system dependent)
  3. associate a priority with each process, allocate the CPU to the process with the highest priority
  4. any 2 processes with the same priority are handled FCFS

Proceeding with this much of knowledge,the required Gantt chart would be the same as what you've drawn:-

| P2 | P5 | P1 | P3 | P4  |
0    1    6    16   18   19

1) Is the turn around time = 19 units?

No, the turnaround time will be 16 + 1 + 18 + 19 + 6 = 60. Average turnaround time = 60 / 5 = 12.

2) How do i calculate average waiting time? Is there a formula?

Average waiting time is defined as the sum of total time waited before starting of the processes divided by the total number of processes.

Here, average waiting time = (6 + 0 + 16 + 18 + 1) / 5 = 41 / 5 = 8.2.

3) What if few processes have the same priority?

If the few processes will have same priority then the scheduling would be handled using First-Come First-Serve (FCFS) as mentioned in the 4th point above. So, everywhere including Gantt chart, the process coming first will be scheduled first and the other similar-priority process would be scheduled late as it came arrived late.

I hope it is crystal clear from my steps and doesn't need any further explanation.

Related Topic