Skip to main content

Computer Architecture · I/O, interrupts, and concurrency

A shared bus has three masters M₀,M₁,M₂ and a nonpreemptive round-robin arbiter

Problem

Computer Architecture practice problem

A shared bus has three masters M0,M1,M2M_0,M_1,M_2 and a nonpreemptive round-robin arbiter. A grant, once given, is held for the entire requested burst. The arbiter's pointer starts at M0M_0. All three masters request at time 00 with burst lengths 3,2,13,2,1 cycles respectively. Time is discrete and grants occupy half-open intervals of cycles.

1. Give the grant intervals. For each master report the wait from time 00 until its grant begins. Compute the average wait.

2. Now consider the same three masters, still nonpreemptive and still round-robin, but every burst length is at most 33 cycles. Prove that a master that has already requested has next-grant wait at most 66 cycles, measured from the moment it is not the current grantee until its next grant begins.

3. Drop the burst bound, keeping nonpreemptive round-robin. Exhibit a finite request pattern in which some already-requesting master's next-grant wait exceeds 66, and explain why no finite wait bound survives.

4. Audit these claims: (i) the arbiter should preempt after one cycle, so the grants are M0[0,1)M_0[0,1), M1[1,2)M_1[1,2), M2[2,3)M_2[2,3); (ii) the average wait is 3+2+1=63+2+1=6; (iii) the point of the exercise is a precise interrupt retirement or a five-stage squash. Do not replace the bus schedule by an EPCEPC prefix.

Hint

Hint

Start at M0M_0 and do not preempt: the first grant occupies three cycles, so M1M_1 cannot start before time 33.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Computer Architecture sample problem: Try the free sample problem.

More Computer Architecture practice problems