GATE CS 2025 Set 1 Q.38: 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?

$9.00$

$8.75$

$6.50$

$7.50$

Official answer and solution

Official answer: A
From: Official GATE 2025 answer key

Solution

Simulate the two-processor non-preemptive schedule starting from $t = 0$ when all four processes arrive.

All four processes arrive at $t = 0$ with bursts $B(P_1) = 20$ , $B(P_2) = 16$ , $B(P_3) = 25$ , $B(P_4) = 10$ :

At $t = 0$ :
- On $M_1$ , $P_1$ has the highest priority, so $P_1$ is scheduled on $M_1$ for $[0, 20]$ . Waiting time $W(P_1) = 0\text{ ms}$ .
- On $M_2$ , $P_2$ has the highest priority, so $P_2$ is scheduled on $M_2$ for $[0, 16]$ . Waiting time $W(P_2) = 0\text{ ms}$ .
At $t = 16$ :
- $M_2$ finishes $P_2$ and becomes free. The waiting processes are $\{P_3, P_4\}$ .
- On $M_2$ , $P_3 > P_4$ , so $P_3$ is scheduled on $M_2$ for $[16, 41]$ . Waiting time $W(P_3) = 16\text{ ms}$ .
At $t = 20$ :
- $M_1$ finishes $P_1$ and becomes free. The only waiting process is $P_4$ .
- $P_4$ is scheduled on $M_1$ for $[20, 30]$ . Waiting time $W(P_4) = 20\text{ ms}$ .

Therefore, the average waiting time is:

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

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 38 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source