Computer Sciences > GATE 2025 SET-1 > CPU Scheduling
A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
• M1 uses priority of execution for the processes as, P1>P3>P2>P4 i.e., P1 and P4 have highest and lowest priorities, respectively.
• M2 uses priority of execution for the processes as, P2>P3>P4>P1, i.e., P2 and P1 have highest and lowest priorities, respectively.
A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?
A
9.00
B
8.75
C
6.50
D
7.50

Correct : a

Explanation:
Let us re-verify the step-by-step scheduling execution to ensure absolute alignment with the non-preemptive priority rules for both processors.
1. At Time t = 0 ms:
• Both processors M1 and M2 are free, and all processes {P1, P2, P3, P4} are in the ready pool.
• Processor M1 selects its highest priority available process, which is P1 (Burst = 20 ms). P1 runs on M1 from t = 0 to t = 20.
• Processor M2 selects its highest priority available process among the remaining pool {P2, P3, P4}, which is P2 (Burst = 16 ms). P2 runs on M2 from t = 0 to t = 16.

2. At Time t = 16 ms:
• Processor M2 finishes P2 and becomes free. The remaining unallocated processes are {P3, P4}.
• According to M2's priority rules (P3 > P4), it schedules P3 (Burst = 25 ms). P3 runs on M2 from t = 16 to t = 41.

3. At Time t = 20 ms:
• Processor M1 finishes P1 and becomes free.
• The only remaining unallocated process in the system is P4 (Burst = 10 ms). M1 schedules P4, running from t = 20 to t = 30.

---
4. Calculate individual process waiting times:
• Waiting time for P1 = 0 - 0 = 0 ms
• Waiting time for P2 = 0 - 0 = 0 ms
• Waiting time for P3 = 16 - 0 = 16 ms
• Waiting time for P4 = 20 - 0 = 20 ms

5. Calculate the Average Waiting Time:
• Average Waiting Time = (0 + 0 + 16 + 20) / 4 = 36 / 4 = 9.00 ms

The mathematically verified average waiting time is exactly 9.00 ms, which makes option (a) the correct choice.

Similar Questions

Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II....
#288 MCQ
Which of the following CPU scheduling algorithm can potential cause starvation?
#802 MSQ
Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, a...
#925 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: