Hardware interview practice

Two-core MESI reference model

MediumComputer ArchitectureC++

A checker models one cache line in two cores with only read, write, and evict operations. Write a C++ state-transition function for the model.

Starting point

Question code

enum State { I, S, E, M };
enum Op { READ, WRITE, EVICT };
bool step(State s[2], unsigned core, Op op);

Reviewed example

Input

Start in {I, I} and apply READ from core 0.

Expected output

The state pair becomes {E, I}.

With no other cached copy, the reading core receives the line exclusively rather than sharing it.

What to cover

Assume the input pair is one legal MESI state: II, EI, IE, SI, IS, SS, MI, or IM; behavior for an illegal initial pair is outside this model. Reject core>1, preserve state, and return false; return true for an accepted operation.
READ from I becomes E if the other core is I, otherwise both valid copies become S; READ from S/E/M changes nothing.
WRITE makes the selected core M and the other core I, regardless of the selected core's prior state.
EVICT makes only the selected core I; after every accepted operation, reject no legal state and preserve the MESI single-writer invariant.

Continue practicing