Arihant Gate Tutor Operating System Intro Excercise 1

Question

6. Consider a set of 5 processes whose arrival time, CPU time needed are given below.

Process        Arrival time                         CPU time
P1                   0                                10
P₂                0                                5
P3                  2                                3
P4                  5                                20
P5                  10                               2

If the CPU scheduling is SJF with pre-emption, the
average waiting time will be

(a) 8 ms                                                 (b) 14 ms
(c) 6.2 ms                                               (d) None of these

 

Answer 1

NOTE: SFJ WITH PRE – EMPTION is given

• At time t=0, both P1 and P2 are available. P2 has a shorter burst time, so execute P2.
• At time t=5, P3 arrives. Preempt P2 and execute P3.
• At time t=8, P1 arrives. Preempt P3 and execute P1.
• At time t=10, P5 arrives. Preempt P1 and execute P5.
• At time t=12, P1 will continue. Preempt P4 and execute P1.
• At time t=20, P4 arrives. Preempt P1 and execute P4.
•  
• Calculate waiting time for each process:
•  
• P1: (t=8-10,12-20) - (arrival time=0) = 10
• P2: (t=0) - (arrival time=0) = 0
• P3: (t=5) - (arrival time=2) = 3
• P4: (t=40) - (arrival time=5) = 15
• P5: (t=12) - (arrival time=10) = 0

• Average waiting time = (10 + 0 + 3 + 15 + 0) / 5 =  28/ 5 = 5.6 ms

Answer 2

To find the average waiting time for the SJF (Shortest Job First) scheduling algorithm with preemption, we can use the following steps:

1. Sort the processes based on their arrival times.
2. Initialize a priority queue (min-heap) to keep track of the processes based on their remaining burst times.
3. Iterate through the processes in the order of their arrival.
4. At each step, check if there is any process with a shorter remaining burst time in the priority queue. If so, preempt the current process and execute the one with the shorter burst time.
5. Calculate the waiting time for each process.
6. Find the average waiting time.

Let's calculate:

Process	Arrival Time	CPU Time
P1	0	10
P2	0	5
P3	2	3
P4	5	20
P5	10	2

Sorted processes based on arrival time:

1. P1 (Arrival Time: 0, CPU Time: 10)
2. P2 (Arrival Time: 0, CPU Time: 5)
3. P3 (Arrival Time: 2, CPU Time: 3)
4. P4 (Arrival Time: 5, CPU Time: 20)
5. P5 (Arrival Time: 10, CPU Time: 2)

Now, let's simulate the execution:

• At time t=0, both P1 and P2 are available. P2 has a shorter burst time, so execute P2.
• At time t=5, P3 arrives. Preempt P2 and execute P3.
• At time t=8, P1 arrives. Preempt P3 and execute P1.
• At time t=18, P4 arrives. Preempt P1 and execute P4.
• At time t=38, P5 arrives. Preempt P4 and execute P5.

Calculate waiting time for each process:

• P1: (t=8) - (arrival time=0) = 8
• P2: (t=0) - (arrival time=0) = 0
• P3: (t=5) - (arrival time=2) = 3
• P4: (t=18) - (arrival time=5) = 13
• P5: (t=38) - (arrival time=10) = 28

• Average waiting time = (8 + 0 + 3 + 13 + 28) / 5 = 52 / 5 = 10.4 ms

  Therefore, the correct answer is not provided among the options (a), (b), (c), and (d). The calculated average waiting time is 10.4 ms.