Computer Architecture · I/O, interrupts, and concurrency
A shared bus has three masters M_0,M_1,M_2 and a nonpreemptive round-robin arbiter
Problem
A shared bus has three masters $M_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 $M_0$. All three masters request at time $0$ with burst lengths $3,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 $0$ 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 $3$ cycles. Prove that a master that has already requested has next-grant wait at most $6$ 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 $6$, and explain why no finite wait bound survives. 4. Audit these claims: (i) the arbiter should preempt after one cycle, so the grants are $M_0[0,1)$, $M_1[1,2)$, $M_2[2,3)$; (ii) the average wait is $3+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 $EPC$ prefix.
Hint
Start at $M_0$ and do not preempt: the first grant occupies three cycles, so $M_1$ cannot start before time $3$.
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
- A processor uses 32-bit little-endian memory and 32-bit instructions that are always…Instruction-set architecture and assembly semantics
- Encode each of the decimal integers -73, -1, 0, 1, and 119 as an 8-bit two's-complement…Instruction-set architecture and assembly semantics
- IEEE-754 binary32 operations are performed with round-to-nearest, ties-to-even, and…Datapath and control implementation
- A J-type jump instruction has the 32-bit encoding `0x0810000F`Datapath and control implementation
- A 32-bit multi-cycle RISC processor executes the six-instruction sequence below…Pipelining, hazards, and speculation
- Register file contents before execution, all values 32-bit two's complement: x1 =…Pipelining, hazards, and speculation
- A 5-stage in-order pipeline (IF, ID, EX, MEM, WB) issues at most one instruction per…Caches, virtual memory, and memory hierarchy
- A MIPS-style delayed branch has a 1-instruction delay slot that is always executed…Caches, virtual memory, and memory hierarchy
- Roofline time is the max of a compute ceiling and a bandwidth ceilingParallel architecture and performance limits