Solution: Cost of the Simulation

What does the task-index solution from the previous section cost?

Every queue operation is $O(1)$, and each turn of the loop does a fixed number of them, so the cost is proportional to the number of turns the loop takes.

Let’s count the turns in the trace first. With burstTimes = [9, 2, 7] and quantum = 4, the task with burst time 9 runs for 4, then 4, then 1. That is 3 turns. The task with burst time 2 finishes in 1 turn. The task with burst time 7 runs for 4, then 3. That is 2 turns. The loop runs $3+1+2=6$ times in total.

Each turn of a task uses up a full quantum, except possibly the task’s last turn, which uses up whatever is left. So the number of turns a task takes is its burst time divided by the quantum, rounded up. For the first task that is $9/4=2.25$, rounded up to 3. That matches the trace.

Now let’s do the same count in general. Let $q$ be the quantum and $n$ the number of tasks. A task with burst time $b$ takes $\lceil b/q\rceil$ turns, where $\lceil x\rceil$ means “round $x$ up to the nearest whole number”. Rounding up adds less than 1, so

$$\lceil \frac{b}{q}\rceil \le \frac{b}{q}+1.$$

Add this up over all the tasks. Write $b_1,b_2,\dots ,b_n$ for the burst times and $t=b_1+b_2+\cdots +b_n$ for their total. The number of turns is

$$\begin{array}{rl}\lceil \frac{b_1}{q}\rceil +\lceil \frac{b_2}{q}\rceil +\cdots +\lceil \frac{b_n}{q}\rceil & \le \left(\frac{b_1}{q}+1\right)+\left(\frac{b_2}{q}+1\right)+\cdots +\left(\frac{b_n}{q}+1\right)\\ & =\frac{b_1+b_2+\cdots +b_n}{q}+n\\ & =\frac{t}{q}+n.\end{array}$$

The first line replaces each rounded-up term with the bound we just found. The second line collects the $b_i/q$ terms, which share the denominator $q$, and collects the $n$ extra ones. The third line substitutes $t$ for the sum of the burst times.

Let’s check this against the trace. There $t=9+2+7=18$ and $q=4$, so $t/q+n=4.5+3=7.5$. The loop actually ran 6 times, which is under the bound, as it should be.

The setup loop that fills the queue runs $n$ times on its own. Adding that in gives at most $t/q+2n$ turns across both loops. The constant 2 does not matter in big-O, so the simulation as a whole runs in $O(n+t/q)$ time.

Can you drop the $t/q$ term and write $O(n)$ instead? I think we should keep both terms because each one measures something different about the running time. The input has three parts: the number of tasks $n$, their total burst time $t$, and the quantum $q$.

The while loop runs once per turn. Here are two inputs that both make it run 1000 times, for two different reasons.

• One task with burst time 1000, and a quantum of 1. There is one task, so $n=1$. But that task runs for 1 unit per turn, so it needs 1000 turns. The loop runs 1000 times. Here $t/q=1000/1=1000$ is what explains the count, and $n=1$ tells you nothing about it.
• 1000 tasks with burst time 1 each, and a quantum of 1000. Every task finishes on its first turn, so each task takes exactly one turn. That is 1000 turns, one per task. The loop runs 1000 times. Here $n=1000$ is what explains the count, and $t/q=1000/1000=1$ tells you nothing about it.

The loop runs 1000 times in both cases, but the count comes from a different term in each case. If we dropped $t/q$ and wrote $O(n)$, the first input would break the bound. If we dropped $n$ and wrote $O(t/q)$, the second input would break it. So we keep both.

I would still call the running time linear, but linear in $n+t/q$ rather than just $n$. The method runs in time proportional to the length of the schedule it simulates.