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

This is a periodic / real-time scheduling problem. The rule “the process with the smaller ratio $\tfrac{\text{CPU time}}{\text{period}}$ gets higher priority” is exactly Rate-Monotonic Scheduling (RMS) in disguise: assigning higher priority to the task whose $C_i/T_i$ is smaller is equivalent to giving higher priority to the shorter relative load, and for a fixed CPU time the priority rises as the period grows — i.e. shorter periods are favored less, longer periods more. Regardless of the exact priority order, the question only asks for the CPU utilization.

For a set of periodic tasks, the CPU utilization is the sum of each task's fraction of CPU time over its period:

$U = \sum_{i=1}^{n} \frac{C_i}{T_i}.$

Plugging in the table values:

$U = \frac{5}{25} + \frac{20}{50} + \frac{10}{40} = 0.20 + 0.40 + 0.25 = 0.85.$

So the CPU utilization is $0.85$ — option 3.

Why the distractors are tempting:

• Option 2, $3\left(\sqrt[3]{2}-1\right) = 3\left(2^{1/3}-1\right) \approx 0.7798$, is the Liu–Layland schedulability bound for $n=3$ tasks under RMS — a sufficient condition for schedulability, not the utilization itself.
• Option 4 (“not schedulable”) plays on the fact that $0.85 > 0.78$, so RMS is not guaranteed schedulable by the Liu–Layland test. But the bound is only sufficient, not necessary, and the question asks for utilization, which is always well-defined as $\sum C_i/T_i$.

Exam trick: $\sum C_i/T_i$ is the actual CPU utilization; $n\left(2^{1/n}-1\right)$ is merely the RMS schedulability bound. The question asked for utilization, so compute the sum — don't be lured into reporting the bound.