سوال ۹۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

Each of the four processes needs $20$ ms of CPU work, delivered in $5$ ms CPU bursts that alternate with $5$ ms IO waits:

$\text{CPU}_5 \to \text{IO}_5 \to \text{CPU}_5 \to \text{IO}_5 \to \text{CPU}_5 \to \text{IO}_5 \to \text{CPU}_5$

Total CPU demand. Four processes $\times\, 20$ ms $= 80$ ms of CPU work. With two cores the absolute lower bound on makespan is

$\frac{80\ \text{ms}}{2\ \text{cores}} = 40\ \text{ms}.$

This bound is achievable because the $5$ ms IO waits of one process exactly match the $5$ ms CPU bursts of a partner process, so each core can stay $100\%$ busy by interleaving two processes. Put $P_1,P_2$ on core 1 and $P_3,P_4$ on core 2; core 1 runs:

$P_1[0\text{-}5],\ P_2[5\text{-}10],\ P_1[10\text{-}15],\ P_2[15\text{-}20],\ P_1[20\text{-}25],\ P_2[25\text{-}30],\ P_1[30\text{-}35],\ P_2[35\text{-}40]$

While $P_1$ does IO, $P_2$ uses the core, and vice-versa, so the core never idles and finishes both processes at $t = 40$ ms. Core 2 mirrors this for $P_3,P_4$. Hence the batch completes in $\Theta = 40$ ms (option 3).

Option 1 ($80$ ms) corresponds to the no-overlap / single-stream reading where the IO waits and the second core give no benefit ($4\times 20 = 80$). The official key therefore accepts both options 1 and 3; the rigorous optimal-schedule answer is $40$ ms (option 3).

Exam trick: With a perfectly matched CPU-burst / IO-wait ratio, the makespan is just (total CPU work) / (number of cores) — IO time hides completely behind another process's computation.