Search code examples
processoperating-systemscheduling

Average wait time for pre-emptive priority scheduling

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.

Solution

  • 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.