Question

You are given the following processes with CPU-burst time, arrival time and priority (lower # means higher priority)

Process	CPU-burst	Arrival time	Priority
P1	12	0	5
P2	6	6	2
P3	9	1	2
P4	14	3	1
P5	7	5	4

For each of the following scheduling algorithm, show (using the diagram as in the slides), how the process are being executed. Also calculate the average wait time.

1. Shortest job first (non-preemptive)
2. Shortest remaining job first (preemptive)
3. Priority-based (preemptive, with round robin on process with same priority, quantum = 3).
4. Priority-based (preemptive, with round robin on process with same priority, quantum = 5).

A couple of other details:

• If you need to preempt a job, only preempt when the new job has a strictly better criteria (priority, wait time etc.) Do not preempt if the criteria is the same.
• For round robin, if a process is to be swap back to the end of the queue, and another process arrived at the same time, the newly arrived process should enter the queue first. Also, if multiple process that have the same priority can start, pick the one that arrive earlier first

You should present your output in the table below (the first two step of case (b) is done for you):

Time	Current Process Being Run	Order of the processes in the wait queue
0	P1	--
1	P3	{P1}

You should add an entry whenever a process is swapped out (or finished execution) and another process is swapped in.

Answer 1

Given Data:

Process	Burst-Time	Arrival Time	Priority
P1	12	0	5
P2	6	6	2
P3	9	1	2
P4	14	3	1
P5	7	5	4

1. Shortest job first (non-preemptive)

We will solve using Gantt Chart

In the SJF algorithm, the process which has the smallest execution time (burst time) will be chosen for the next execution which is P2 and it will use the resource for 6 ms(12+6=18) completion time. The same process will be repeated.

P1

P2

P5

P3

P4

0 12 18 25 34 48

In the first step, we will select the process whose Arrival time is “0” which is P1 it will use the resource for till 12 and after P1 the process with the shortest burst time will be provided with the resource.

Waiting Time(Allocation Time - Arrival Time)

P1: 0 - 0 = 0 ms

P2: 12 - 6 = 6 ms

P3: 34 - 1 = 33 ms

P4: 48 - 3 = 45 ms

P5: 18 - 5 = 13 ms

Total Waiting Time = 97

Average Waiting Time: Total Waiting Time/ Number of processes

                                   : 97/5

                                   :19.4ms

OUTPUT: It is based on the burst time as well as arrival time the arrival time of P3 is 1 but it’s bust time is 9 and no other process has an arrival time 1 so only P1 will be there and the same will be followed by other processes.

Time	Current Process	Being Run Out	In Queue
0	P1	------	--------
1	P3	{P1}	{P1}
3	P4	{P1}	{P1,P3}
5	P5	{P1}	{P1}
6	P2	{P1}	{P1}

2. Shortest remaining job first (preemptive)

In this state the process switches from running state to ready state or waiting according to its arrival time and burst time.

P1

P3

P2

P5

P1

P4

0 1 10 16 23 34 48

Steps How the process allocation takes places:

P1 arrives at 0 when there was no process so it will take resource for 1 ms Burst TIme= 12-1

At 1 ms process, 3 will come 9-1=8 Still no process is there so it will take the resource 8-1=7 at 3 the P4 process will come but its time burst time is 14 so P3 will use the resource Till 10 because it will have lower burst time at 10 each process will arrive and this will become primitive scheduling.  

Waiting Time(Allocation Time - Arrival Time)

P1: 0 - 0 = 0 ms(It doesn’t matter if the process was removed.)

P2: 10 - 6 = 4 ms

P3: 1 - 1 = 0 ms

P4: 34 - 3 = 31 ms

P5: 16 - 5 = 11 ms

Total Waiting Time = 46

Average Waiting Time: Total Waiting Time/ Number of processes

                                   : 46/5

                                   :9.2ms

Priority-based (preemptive, with round-robin on the process with the same priority, quantum = 3).

The processes will run according to the priority.

According to the Arrival, Time P1 will arrive First and it will take 3 Quantum

Burst time Left 12-3=9

At Time 3 P3 will Arrive with burst time 9 and priority 2 and P4 also with burst time 14 and priority 1 so it will allocated to P4.P4=14-14=0 highest priority

At time 6 each process arrives.

P1

P4

P3

P2

P5

P1

0 3 17 26 32 39 48

Waiting Time(Allocation Time - Arrival Time)

P1: 0 - 0 = 0 ms(It doesn’t matter if the process was removed.)

P2: 26 - 6 = 20 ms

P3: 17 - 1 = 16 ms

P4: 3- 3 = 0 ms

P5: 32- 5 = 27 ms

Total Waiting Time = 36

Average Waiting Time: Total Waiting Time/ Number of processes

                                   : 63/5

                                   :12.6ms

Priority-based (preemptive, with round-robin on the process with the same priority, quantum = 5).

The processes will run according to the priority.

According to the Arrival, Time P1 will arrive First and it will take 3 Quantum

Burst time Left 12-5=9

At Time 5 P3, P4,P5 will Arrive .P4 priority is 1 so it will be allocated to P4.P4=14-14=0 highest priority

P1

P4

P3

P2

P5

P1

0 5 19 28 34 41 48

Waiting Time(Allocation Time - Arrival Time)

P1: 0 - 0 = 0 ms(It doesn’t matter if the process was removed.)

P2: 28 - 6 = 22 ms

P3: 19 - 1 = 18 ms

P4: 5- 3 = 2 ms

P5: 34- 5 = 31 ms

Total Waiting Time = 73

Average Waiting Time: Total Waiting Time/ Number of processes

                                   : 73/5

                                   :14.6ms