GATE 2025 CS1 Q.38: solution and answer

GATE 2025 · CS1Q.38 · 2 marks · MCQ

A computer has two processors, $M_{1}$ and $M_{2}$ . Four processes $P_{1}, P_{2}, P_{3}, P_{4}$ 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:
- $M_{1}$ uses priority of execution for the processes as, $P_{1} > P_{3} > P_{2} > P_{4}$ , i.e., $P_{1}$ and $P_{4}$ have highest and lowest priorities, respectively.
- $M_{2}$ uses priority of execution for the processes as, $P_{2} > P_{3} > P_{4} > P_{1}$ , i.e., $P_{2}$ and $P_{1}$ have highest and lowest priorities, respectively.

A process $P_{i}$ is scheduled to a processor $M_{k}$ , if the processor is free and no other process $P_{j}$ 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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The average waiting time is 9.00 ms, option (A).

Official answer: ASource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

All four processes arrive at $t = 0$ and both processors are free. Each free processor takes the waiting process that ranks highest in its own priority order, and no process is preempted once started.
At $t = 0$ : $M_{1}$ ranks $P_{1}$ first, so $P_{1}$ runs on $M_{1}$ during $[0, 20]$ . $M_{2}$ ranks $P_{2}$ first, so $P_{2}$ runs on $M_{2}$ during $[0, 16]$ .
At $t = 16$ : $M_{2}$ becomes free. $P_{3}$ and $P_{4}$ are waiting, and $M_{2}$ ranks $P_{3} > P_{4}$ , so $P_{3}$ runs on $M_{2}$ during $[16, 41]$ . $M_{1}$ is still busy, so $M_{2}$ is the only free processor.
At $t = 20$ : $M_{1}$ becomes free. Only $P_{4}$ is waiting, so $P_{4}$ runs on $M_{1}$ during $[20, 30]$ .
Timeline: $M_{1}$ : $P_{1} [0, 20]$ , $P_{4} [20, 30]$ . $M_{2}$ : $P_{2} [0, 16]$ , $P_{3} [16, 41]$ .
All arrivals are at 0, so waiting time = start time: $Process P_{1} P_{2} P_{3} P_{4} Start 001620 Burst 20162510 Waiting 001620$
Average waiting time $= \frac{0 + 0 + 16 + 20}{4} = \frac{36}{4} = 9.00$ ms, which is option (A).

KEY IDEA

With non-preemptive scheduling on two processors, each processor that becomes free picks the waiting process that is highest in its own priority list. Simulate the events in time order.

WATCH OUT FOR

Using one global priority order, or letting $P_{4}$ run on $M_{2}$ at $t = 16$ before $P_{3}$ . $M_{2}$ ranks $P_{3}$ above $P_{4}$ , so $P_{3}$ goes first and $P_{4}$ waits until $M_{1}$ frees at $t = 20$ .

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 8 CPU scheduling questions, with notes

GATE 2025 CS1 Q.38: solution and answer

Answer and solution

More CPU scheduling questions