Question

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

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

In the above table, a smaller priority number implies a higher priority. Suppose that these processes are scheduled by the priority policy with preemption.

1. Draw the Gantt chart (i.e., time chart) illustrating the execution of these processes.
2. What is the waiting time of each individual process?
3. What is the average waiting time for these processes?

Answer 1

In Priority Scheduling, we run the process first which has higher priority.

In Preemption, CPU scheduling algo is invoked under 3 conditions,

1. When a process wishes to perform I/O . Therefore, CPU scheduling algo is invoked to select a next new process.

2. When a process terminates and therefore CPU scheduling algo is invoked

3. When a process is forcefully removed from the CPU.(Process voluntarily leaves)

here, Process will interrupt only when it is interrupted or when a process of higher priority is waiting in ready queue.

a) Gantt chart is the chart which shows the sequence in which process was completed.

• At 0 time, we have four processes P1, P3, P4, P5
• P5 is the highest priority so it'll occur from 0-5 (5 is the burst time)
• Now, P1 is the higher priority so it'll occur for 5-12 as at 12 P2 occurs which is of highest priority.
• Then P2 completes at 13 and P1 executes which gets complete at 16.
• Now, P3 occurs from 16-18 then P4 from 18-19

THE GANTT CHART IS:

P5

P1

P2

P1

P3

P4

0 5 12 13 16 18 19 ------- TIME

On the basis of the gantt chart we can find completion time, Turn Around Time and Waiting Time

• Completion Time is time of completion of process.
• Turn Around Time is time taken to complete from when it arrived.
• Waiting Time is the time taken to start executing from when it arrived.
• Turn Around Time = Completion Time - Arrival Time
• Waiting Time = Turn Around Time - Burst Time

PROCESS	PRIORITY	ARRIVAL TIME	BURST TIME	COMPLETION TIME	TURN AROUND TIME	WAITING TIME
P1	3	0	10	16	16	6
P2	1	12	1	13	1	0
P3	4	0	2	18	18	16
P4	5	0	1	19	19	18
P5	2	0	5	5	5	0

b) Waiting Time of P1, P2, P3, P4, P5 are 6, 0, 16, 18, 0

c) Average Waiting Time = ( 6 + 0 + 16 + 18 + 0 ) / 5

= 40 / 5

= 8 milliseconds