42Implementation

Remove FIFO entries in arrival order

Problem

ByteQueue.deq must return the oldest buffered byte and remove that same entry in one atomic action. The starter performs noAction and returns zero, so the queue never shrinks and the public run prints first = 00 and second = 00 instead of 12 and 34.

Complete only the body of deq, using the operations of the existing FIFO. Keep the interface, enq, the queue depth of two, and mkTop unchanged. Do not add a register that shadows the queue contents.

Read and predict

Read the ByteQueue interface. deq is an ActionValue method: it changes state and returns a value in the same call.
Read the internal FIFO#(Bit#(8)). Its interface separates looking at the head from removing it.
Trace mkTop by step: two enqueues on separate cycles, then two dequeues.

Before pressing Run, fill in this table for the repaired design: after each step, which entry is at the head, and what does each dequeue print?

`step`	action	head after the clock edge
0	enqueue `12`	`12`
1	enqueue `34`	?
2	dequeue	?
3	dequeue	?

Make the repair

Inside one atomic method, every read sees the state from the start of the action, and every removal takes effect only after the action commits. Use that rule to make the returned value and the removed entry be the same element. Run again and explain why the first dequeue does not return 34, even though it removes 12 in the same action.

Completion contract

Each call returns the oldest entry still in the queue and removes exactly that entry.
Values leave in the order they arrived, for more than two values and across repeated calls.
deq cannot fire on an empty queue; it inherits the queue's own readiness.
Printing 12 and 34 from constants does not satisfy other inputs.

Progressive hints

Hint 1: one call, two effects

An ActionValue method can perform an action and return a value in a single atomic operation. Both effects are needed here.

Hint 2: two FIFO methods

One FIFO method observes the current head without changing anything; another schedules the head's removal. Both see the same pre-commit state inside one method.

Hint 3: order inside the body

Call the removal as an action statement, then return the observed head. Even though the removal is written first, the return reads the head from before the clock edge.

Transfer experiment

In a scratch copy, enqueue three distinct values with a queue depth of three, then dequeue all of them. Predict every printed value before running, and explain why reading the head again in the next cycle would show a different entry.