Project ForgeA 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?
- 9.00
- B8.75
- C6.50
- D7.50
Explanation
At t=0, both processors are free with all 4 processes waiting: M1 picks its own highest-priority available job (P1), M2 picks its own highest-priority available job (P2) — no conflict since they pick different processes. M1 runs P1 [0-20], M2 runs P2 [0-16]. At t=16, M2 frees up; among the still-waiting {P3,P4}, M2's priority ranks P3 above P4, so M2 runs P3 [16-41]. At t=20, M1 frees up; only P4 remains waiting, so M1 runs P4 [20-30]. Waiting times: P1=0, P2=0, P3=16 (waited from 0 to 16), P4=20 (waited from 0 to 20). Average = (0+0+16+20)/4 = 9.00 ms.
Source: GATE CS 2025 (Session 1 / CS1) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.