25Concurrency, Operating Systems and Networks

Solution of Interview question 25.1.

Each ++counter is a load, an add and a store; when the threads interleave between the load and the store, one increment overwrites the other and is lost. The standard says more: unsynchronised concurrent access with a write is a data race and the behaviour is undefined, so no output can be predicted, and ThreadSanitizer reports “data race” on this program (the chapter’s test asserts the diagnosis, never the number printed). Fix with an atomic, a mutex, or per-thread counters.

What the interviewer is looking for: the read-modify-write mechanism and the formal status of a data race.

Solution of Interview question 25.2.

When the critical section is a few instructions, the lock is rarely contended, and the waiting thread runs on its own core with nothing better to do, as on isolated cores of a trading engine: spinning avoids a sleep and a wake-up through the kernel. Never when the holder can be descheduled (a spinner then burns its whole time slice) or when many threads contend.

What the interviewer is looking for: the trade-off between spinning and sleeping, tied to core isolation.

Solution of Interview question 25.3.

The kernel saves one thread’s registers and loads another’s. Beyond that, the incoming thread finds caches, branch predictors and translation buffers holding the other thread’s state, so it runs slowly for a while. Trading systems pin hot threads to isolated cores, keep them busy polling rather than blocking, and move non-critical work to other cores (One Quant Book 13, chapter 13).

What the interviewer is looking for: direct and indirect costs, and pinning and isolation as the remedy.

Solution of Interview question 25.4.

Market data goes to many receivers at once, and a late update is worthless: multicast UDP sends once to all subscribers and never blocks on a lost packet; receivers detect gaps by sequence number and recover separately. Orders must arrive, once and in order, and a loss must be known: TCP gives a reliable ordered stream and a session whose failure is visible.

What the interviewer is looking for: fan-out and staleness against reliability and order.

Solution of Interview question 25.5.

Two (for a million increments each). Thread A loads 0 and stalls; thread B completes all but its last increment; A stores 1, overwriting B’s work; B loads 1 for its last increment and stalls; A completes its remaining increments; B stores 2. An exhaustive enumeration of all interleavings for small counts (Proposition 25.1) confirms that 2 is the minimum. In C++ the program is a data race, so even this analysis describes the machine model, not a guarantee of the language.

What the interviewer is looking for: the adversarial interleaving and the caveat about undefined behaviour.

Solution of Interview question 25.6.

Under sequential consistency no: some write comes first in the single order, so the other thread’s later read sees it; the chapter’s explorer finds only (0,1), (1,0) and (1,1). On x86, yes: each store can sit in its core’s store buffer while the load after it reads memory. With C++ relaxed (or even acquire and release) atomics, yes. To forbid it, make all four operations seq_cst or put a seq_cst fence between each store and the following load (on x86, an mfence or a locked instruction).

What the interviewer is looking for: store buffering, the difference between SC and TSO, and the full fence.

Solution of Interview question 25.7.

The flag store is a release and the flag load an acquire: every write before the release (the message) is then visible to a thread whose acquire reads the flag’s new value. It forbids “flag seen, stale message”, the outcome (1, 0) of the chapter’s message-passing test, which sequential consistency also forbids and relaxed ordering allows. This is the pattern of the SPSC queue’s indices.

What the interviewer is looking for: the release–acquire pairing and the outcome it excludes.

Solution of Interview question 25.8.

Eight 8-byte counters fill one 64-byte cache line, so each write invalidates the line in the other core’s cache and the line ping-pongs between cores (false sharing, One Quant Book 13, chapter 3). Give each counter its own line (alignas(64) or padding), or keep counters thread-local and combine them at the end.

What the interviewer is looking for: cache-line granularity of coherence and padding as the fix.

Solution of Interview question 25.9.

A page holds $4096/8 = 512$ entries, so each level resolves 9 bits; the offset takes 12 bits; $(48 - 12)/9 = 4$ levels. TLB reach: $1536 \times 4\,\text{KiB} = 6\,\text{MiB}$ with small pages, $1536 \times 2\,\text{MiB} = 3\,\text{GiB}$ with huge pages, so a working set of a few gigabytes stays translated with huge pages and misses constantly without them.

What the interviewer is looking for: the radix arithmetic and the reach argument for huge pages.

Solution of Interview question 25.10.

Listing 25.1. The producer reads its own tail relaxed (only it writes it), reads head with acquire (so the consumer’s reads of a slot happen before the producer overwrites it), writes the element, then stores tail with release (publishing the element). The consumer mirrors it: acquire on tail, read, release on head. The indices sit on separate cache lines to avoid false sharing. The chapter’s stress test passes two million sequence numbers in order and runs clean under ThreadSanitizer.

What the interviewer is looking for: each ordering justified by what it publishes, and the cache-line layout.

Solution of Interview question 25.11.

The card receives the frame, checks it and writes it by DMA into a ring of buffers in host memory; it raises an interrupt, the driver schedules polling (NAPI) and hands the buffer to the stack; IP and UDP headers are processed, the socket is looked up and the payload queued on its buffer; a thread blocked in recvmsg is woken, and the system call copies the payload to user memory (Figure 25.1). Kernel bypass maps the card’s ring into the process, which polls it: the interrupt, the stack traversal, the wake-up, the system call and the copy all disappear.

What the interviewer is looking for: the full path, and exactly which steps bypass removes.

Solution of Interview question 25.12.

def gaps(seqs):
    """Missing sequence-number ranges in a stream that should be consecutive; duplicates and late
    arrivals are ignored. Returns a list of (first_missing, last_missing)."""
    expected, out, seen_late = None, [], set()
    for s in seqs:
        if expected is None:
            expected = s + 1
            continue
        if s == expected:
            expected += 1
        elif s > expected:
            out.append((expected, s - 1))
            expected = s + 1
        else:
            seen_late.add(s)
    # late arrivals fill earlier gaps
    filled = []
    for a, b in out:
        cur = a
        for x in range(a, b + 1):
            if x in seen_late:
                if cur <= x - 1:
                    filled.append((cur, x - 1))
                cur = x + 1
        if cur <= b:
            filled.append((cur, b))
    return filled

Track the next expected number; a higher one opens a gap, a lower one is a duplicate or a late arrival that closes part of a gap. When a gap stays open past a timeout, take the packet from the redundant line (arbitration), request a retransmission, or, for a book feed, mark the book invalid and rebuild from a snapshot (One Quant Book 10, chapter 26). The chapter’s test compares the detector with a direct count of missing numbers on 300 random streams.

What the interviewer is looking for: gap bookkeeping with late packets, and the recovery hierarchy.

Solution of Interview question 25.13.

Deadlock: A holds the book and waits for the risk state while B holds the risk state and waits for the book. Prevent it by a global lock order (always the book first), or by acquiring both at once with a deadlock-avoiding primitive (std::scoped_lock on both mutexes); better still, design so that one thread owns each piece of state and others send it messages.

What the interviewer is looking for: the circular wait and the standard preventions.