Official PYQ · 2025Set 1 · Q28CPU SchedulingMCQ2 marks

GATE CS 2025 Set 1 Q28 — CPU Scheduling

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?

View worked solution

Answer: A

We are given two processors, $M_1$ and $M_2$ , and four processes $P_1, P_2, P_3, P_4$ arriving at $t = 0$ with CPU bursts of $20, 16, 25,$ and $10$ ms, respectively.

The priority orders on the processors are:

On $M_1$ : $P_1 > P_3 > P_2 > P_4$
On $M_2$ : $P_2 > P_3 > P_4 > P_1$

Let's trace the scheduling step-by-step:

At $t = 0$ : Both $M_1$ $M_{1}$ and $M_2$ $M_{2}$ are free.
- On $M_1$ , the highest priority waiting process is $P_1$ . Thus, $P_1$ is scheduled on $M_1$ (runs from $t = 0$ to $t = 20$ ).
- On $M_2$ , the highest priority waiting process is $P_2$ . Thus, $P_2$ is scheduled on $M_2$ (runs from $t = 0$ to $t = 16$ ).
At $t = 16$ : $M_2$ $M_{2}$ becomes free. The waiting processes are $P_3$ $P_{3}$ and $P_4$ $P_{4}$ .
- On $M_2$ , the priority order is $P_3 > P_4$ . Thus, $P_3$ is scheduled on $M_2$ (runs from $t = 16$ to $t = 41$ ).
At $t = 20$ : $M_1$ $M_{1}$ becomes free. Only $P_4$ $P_{4}$ is waiting.
- $P_4$ is scheduled on $M_1$ (runs from $t = 20$ to $t = 30$ ).

Now, we calculate the waiting times for each process:

Waiting time of $P_1 = 0$ ms
Waiting time of $P_2 = 0$ ms
Waiting time of $P_3 = 16 - 0 = 16$ ms
Waiting time of $P_4 = 20 - 0 = 20$ ms

The average waiting time is:

\text{Average Waiting Time} = \frac{0 + 0 + 16 + 20}{4} = \frac{36}{4} = 9.00 \text{ ms}

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More CPU Scheduling questions

GATE CS 2025 Set 1 Q28 — CPU Scheduling

Related questions