Answer each question out loud before opening it. If you miss more than three in the checkpoint, revisit the lessons linked at the end.
Deadlock is frozen (no handshakes); livelock is busy (retries, NAKs) with no completions.
Mutual exclusion, hold and wait, no preemption, circular wait.
Yes; the master must not wait for the address to be accepted before offering data.
Requests can only finish by sending responses; shared buffers let requests block them: message-dependent deadlock.
Deadlock-freedom arguments assume responses are consumed; reserve space at request time.
Every buffer fills with packets waiting for the next; a dateline with two VCs breaks the cycle.
Waiting holds resources, pre-allocation doesn't scale, plain retry can livelock; the credit guarantees the retry is accepted.
Above the target's worst legitimate latency, below what the system tolerates; recover by freeing everything and discarding late responses.
Task. A 2×2 mesh connects two processors and two memory controllers. Processors send read requests; memories send read data back; memories also send snoops to processors, which answer with snoop responses. Make it deadlock-free and argue it.
Routing: XY on the mesh, so no routing cycles. Message classes and their dependencies: a read request may cause snoops; a snoop causes a snoop response; the memory can only send read data after the snoop responses arrive. So four classes, ordered request < snoop < snoop response < read data, each in its own virtual channel on every link and in every router and interface queue. Consumption: processors always accept read data and snoops' responses are always accepted by memories, with space reserved when the request or snoop is issued. Argument: number the resources (class, then XY order within a class) so every wait goes to a higher number; no cycle can exist. Assumptions checked with per-interface assertions; stress-test with all four agents saturating every class.
Under starvation the rest of the system progresses; under livelock no one completes.
Arrows from each agent or resource to what it waits for; a cycle is a deadlock.
Circular wait.
The offering side never waits for the accepting side's readiness.
Three.
They advertise infinite completion credits, reserving space before each read.
The cycle remains; a big enough burst still fills it.
Wasted attempts about 2N − 1 per completion in the model, and unbounded waits for unlucky requests.
It must not be reused until a late response can no longer be matched to it.
Its assumptions (consumption, dependency rules, no shared resources) with how each is checked, and liveness arguments for retries and arbiters.