CPU Scheduling Algorithms Questions and Answers

Answer: A

The algorithm is Shortest remaining time first.

Shortest-job-first is provably optimal for minimizing average waiting time: running shorter jobs first means fewer processes wait behind each long one. All processes here arrive together, so shortest remaining time first behaves exactly like SJF and achieves that optimum.

Round-robin with a small quantum interleaves everything, so every process waits through slices of all the others. A uniform random order is optimal only by chance. Priority proportional to burst length runs the longest jobs first, the worst possible order for average waiting time.

Answer: A

The average waiting time is 9.00 ms.

All four processes arrive at time 0 and both processors are free.

• t = 0: M1 picks its highest-priority process, P1 (runs 0 to 20). M2 picks its highest-priority process, P2 (runs 0 to 16).
• t = 16: M2 is free. P3 and P4 are waiting, and M2 ranks P3 above P4, so P3 runs 16 to 41.
• t = 20: M1 is free and only P4 is waiting, so P4 runs 20 to 30.

Waiting times are P1 = 0, P2 = 0, P3 = 16 and P4 = 20, so

\[ \text{average} = \frac{0 + 0 + 16 + 20}{4} = 9.00\ \text{ms} \]

The other averages do not come from a schedule that obeys both processors' priority rules; for instance, starting P3 at time 0 on either processor breaks the rule, since each processor has a higher-priority process waiting then.

Answer: B

The average waiting times are SRTF = 6, NP-SJF = 7.5.

SRTF. A runs 0-2. B arrives with 6 against A's remaining 8 and runs 2-4. C arrives with 3 against B's remaining 4 and runs 4-7 (D, arriving at 6 with 7, does not preempt C's remaining 1). Then B runs 7-11, D 11-18 and A 18-26. Waiting time is finish minus arrival minus burst: A 16, B 3, C 0, D 5, total 24, average 6.

NP-SJF. A runs 0-10 without interruption. At 10, C (3) is shortest and runs 10-13, then B (6) 13-19, then D (7) 19-26. Waiting times: A 0, C 6, B 11, D 13, total 30, average 7.5.

The other options get one of the two schedules wrong: 7 for SRTF, or 7 and 8.5 for NP-SJF, do not match these timelines.

Answer: D

The average turnaround time is 19 ms.

Under SRTF the process with the least remaining time runs, and an arrival can preempt it:

• 0-2: P1 runs (P2 arrives at 1 with 13, more than P1's 9 left). At 2, P3 arrives with 6, less than P1's 8 left, and preempts.
• 2-8: P3 runs to completion at 8. P4 arrives at 8 with 9.
• 8-16: P1 (8 left) runs to completion at 16.
• 16-25: P4 (9) runs; 25-38: P2 (13) runs.

\[ \begin{aligned} \text{TAT} &= (16-0) + (38-1) + (8-2) + (25-8) \\ &= 16 + 37 + 6 + 17 = 76 \\ \text{average} &= 76/4 = 19\ \text{ms} \end{aligned} \]

37 is P2's turnaround alone. 22 is close to the first-come first-served average, (10 + 22 + 27 + 30)/4 = 22.25, which ignores the shortest-remaining-time rule, and 15 matches no schedule of these processes.

Answer: B

The algorithm that cannot be preemptive is First Come First Serve (FCFS).

FCFS runs processes in arrival order, and each process keeps the CPU until it finishes or blocks. Taking the CPU away from a running process would break the first-come order, so FCFS is non-preemptive by definition.

SRTF is the preemptive version of shortest job first: a newly arrived process with a shorter remaining time takes over the CPU. Round robin preempts each process when its time quantum expires. Priority scheduling can be implemented either way; in its preemptive form a higher-priority arrival takes over the CPU.

Answer: D

The burst times that are NOT possible are P = 3, Q = 7, R = 7, S = 3.

With a quantum of 4 and the order P, Q, R, S, these bursts run as P (3, done), Q (4, 3 left), R (4, 3 left), S (3, done), Q (3, done), R (3, done). The switches are P to Q, Q to R, R to S, S to Q and Q to R, so there is no switch from R to Q at all, against the 'exactly one' required.

Each of the other sets meets every condition. For P = 4, Q = 10, R = 6, S = 2 the run is P, Q, R, S, Q, R, Q, giving one S to Q, one R to Q, two Q to R and no S to P. P = 2, Q = 9, R = 5, S = 1 runs in the same order (P, Q, R, S, Q, R, Q), and so does P = 4, Q = 12, R = 5, S = 4, where R finishes its last unit before Q's final quantum. In each, Q still needs CPU time after R's second turn, which is what produces the single R to Q switch.

Answer: C

The waiting time of R is 10 milliseconds.

Shortest job first runs the process with the shortest burst first. All three arrive together, so the order is Q (10), then R (15), then P (20):

\[ \begin{aligned} Q &: 0 \text{ to } 10 \\ R &: 10 \text{ to } 25 \\ P &: 25 \text{ to } 45 \end{aligned} \]

R waits while Q runs, so its waiting time (printed 'wailing time') is 10 ms. 25 is R's completion time, 15 its own burst, and 20 the burst of P.