5Operating Systems, Concurrency and Networks

Answer to Question 5.1.

It prints after fork 0 and after thread 1. The child has its own copy of count, so its increment stays in the child, while the thread changes the one count in the process.

Threads in a process share the address space, so they share global data and the heap. They also share open files, and signal handlers. Each thread has its own stack, its own registers and program counter, and its own thread-local storage. A thread can still reach another’s stack through a pointer, as the memory is all one space.

After fork, the child starts with a copy of the parent’s memory, which Linux makes lazily, and a copy of its file descriptor table. No memory stays shared unless it was mapped as shared. The open file descriptions are the exception: parent and child share file offsets through them.

Answer to Question 5.2.

It prints 4000 1000 0. shared is one atomic that all four threads increment. mine is one variable per thread, so each thread counts to 1000, and the mine of the main thread, which did no counting, is still 0.

shared has one address, in the program’s data segment. Each thread gets its own block of thread-local storage when it starts, and mine sits in it at a fixed offset. On x86-64 Linux, a register (fs) points at the current thread’s block, so reaching mine takes no lock and needs no atomic.

That suits a statistic updated often and read rarely. Each thread increments a thread_local counter of its own, which no other core writes, and a reader adds them up from time to time. That avoids a cache line bouncing between cores for each increment, at the price of a sum that is not a snapshot, and the counters must be registered so that a reader can find them.

Answer to Question 5.3.

It prints state Z, code 7 and gone True. A zombie is a child that has exited and not yet been waited for. It holds no memory or open files, only its entry in the process table, which keeps the exit status for the parent.

The way to clear one is for the parent to call wait or waitpid, as the listing does, and that gives the parent the code 7. You cannot kill a zombie, as it is already dead, so kill -9 does nothing.

If the parent dies first, its children are handed to init or the nearest subreaper, and that process waits on them, so the zombies go. The harm comes from a long-lived parent that never waits: each zombie holds a process ID, and the system has a limited number of these.

A parent that does not care about the status can set SIGCHLD to be ignored, and then no zombie is left.

Answer to Question 5.4.

It prints b'abc' b'de' and b'abcde'. The number of recv calls for TCP is not fixed: two or three here, counting the last one that returns nothing for the close, and that depends on timing and on the buffers. UDP keeps message boundaries, and TCP is a byte stream with none.

TCP guarantees that the bytes arrive complete, in order and without duplicates, or that the connection reports failure. It adds retransmission, flow control and congestion control, and it needs a connection first. UDP sends each datagram on its own, which may be lost, duplicated or reordered, and it tells the sender nothing. A datagram that does arrive arrives whole.

The trading angle is the cost of order. A lost TCP segment holds back every later byte until it is resent, and a market data consumer would rather have the newer prices now. So feeds usually send UDP with sequence numbers, and handle gaps themselves, while order entry usually runs over TCP, as each message must arrive and in order.

Answer to Question 5.5.

It prints little, 04030201 01020304 and 0x4030201. x86-64 stores the low byte of a number first, so 0x01020304 is laid out as 04 03 02 01. Network byte order is big-endian, the high byte first, which is what the format !I packs and what htonl converts to.

So htonl reverses the bytes on this machine. On a big-endian machine, it would do nothing.

A feed that sends its prices in little-endian order is read directly with the native format on x86-64, with no reversal. On a big-endian machine, the same price needs an explicit little-endian format. For portable code, write the order you mean: <I says little-endian on any machine, while =I means whatever the machine uses.

Answer to Question 5.6.

It prints True, False and b'a' b'b'. Both connections have the same local address and port, and different peer ports. A TCP connection is identified by four things: local address, local port, remote address and remote port. With the protocol, that makes the five-tuple.

So one server port can carry many connections. The kernel looks up each arriving segment by that tuple, and hands it to the right socket. accept returns a new socket for each connection, and the listening socket goes on listening.

The real limits are elsewhere. A client talking to a single server address and port has only its range of ephemeral source ports, some tens of thousands here (ip_local_port_range), and a server’s limit comes from memory and file descriptors.

Answer to Question 5.7.

It prints 1110 and 10. Three slots can be taken and the fourth try fails. After the other thread’s release, one slot is free again. A semaphore is a counter with no owner, so any thread may release it, whereas a mutex has an owner, and only that thread may unlock it.

So a semaphore suits counting: at most $N$ requests in flight, or items available in a queue, with one thread acquiring and another releasing. It also signals between threads, which a mutex cannot do. A mutex protects a critical section, and its owner rule lets a system offer priority inheritance, or a debug check.

Unlocking a std::mutex from a thread that does not own it is undefined behaviour. A binary semaphore looks like a mutex, and it gives no such protection, as nothing ties the release to the acquirer.

Answer to Question 5.8.

It prints caught [15], refused and -9. SIGTERM is a request, which a process may handle. SIGKILL cannot be caught, blocked or ignored, as the operator needs one way that always works. The status $-9$ shows the child was killed by that signal.

The kernel simply ends a process on SIGKILL. No handler runs, no destructor runs and no buffered data is flushed.

So a trading process should receive SIGTERM first, and its handler should set a flag and return. The main loop then stops sending new orders, cancels what is open, flushes its log, and exits. Only if it fails to finish in time does the operator send SIGKILL. And since the process can die anyway, in a crash for instance, an exchange-side cancel-on-disconnect, where a venue offers one, is the protection that does not depend on the process.

A handler should do very little. Most library calls are not safe inside one, because the signal may arrive while the same library is holding a lock.

Answer to Question 5.9.

The child takes about 0 faults on reading and about 2000 on writing. In the run here, the two counts were exactly 0 and 2000. The child prints 2 and the parent 1, at the same address, as each process has its own page tables that map one virtual address to different physical pages.

fork copies the page tables, and marks the writable pages read-only in both. So a read hits a page that is already mapped, and no fault occurs. The first write to each page faults. The kernel then copies that page, gives the writer its own copy, and makes it writable. That is copy-on-write. So fork itself is cheap in data, and the cost comes later, a page at a time.

For a large process that forks to save a snapshot, this is a good trick: the child sees a frozen view and writes it out, while the parent keeps running. But each page the parent changes during the save now costs a fault, and a copy of 4 KiB. If the parent rewrites most of its memory, that doubles memory use at worst, and it adds latency to the writes on the hot path, spread unpredictably in time. fork itself must also copy the page tables, which grows with the mapped size, and for that time the process is stopped.

The listing turns huge pages off for this range, so that the parent’s first touch does not depend on the system’s setting. On a current kernel the child’s counts do not change: a write to a shared huge page splits the mapping and copies only 4 KiB, and a run here with huge pages on again gave 0 and 2000. Older kernels tried to copy the whole huge page.

Answer to Question 5.10.

The indices are 254, 72, 418 and 359, with offset 2748 (0xabc): bits 47–39, 38–30, 29–21, 20–12, and 11–0. Mapping 1 GiB takes 262 144 entries, which is 512 tables of 4 KiB, or 2 MiB, plus 3 upper tables: 2 109 440 bytes in all. With 2 MiB pages, the last level goes, and it takes 3 tables, 12 KiB.

"""Splitting an x86-64 virtual address under 4-level paging with 4 KiB pages."""


def indices(addr):
    offset = addr & 0xFFF
    levels = [(addr >> shift) & 0x1FF for shift in (39, 30, 21, 12)]
    return levels, offset


def table_bytes(mapped, page=4096, levels=4):
    """Bytes of tables to map `mapped` aligned bytes: a 4 KiB table per 512 entries below."""
    entries = (mapped + page - 1) // page
    tables = 0
    for _ in range(levels):
        entries = (entries + 511) // 512     # a table at this level is an entry one level up
        tables += entries
    return tables * 4096

Each table has 512 entries, which is $2^9$, so each level takes 9 bits. A page of 4096 bytes takes 12 bits as the offset. $4 \times 9 + 12 = 48$. On Linux, user space uses the lower half, under 47 bits, which is about 128 TB.

The loop works up the levels. $2^{30} / 2^{12} = 262\,144$ pages need that many entries of the last level, which fill 512 tables; these need 512 entries one level up, in 1 table; and so on up to the top. So the overhead is about 0.2% of what is mapped. The test checks the split by rebuilding 1000 random addresses from their parts, and the table count against a slow walk over every page that collects the distinct tables. One page alone still needs one table at each level.

The page tables are not what makes huge pages attractive. A translation cache entry then covers 2 MiB and not 4 KiB, so far fewer misses occur, and each miss has one level less to walk.

Answer to Question 5.11.

It prints heap mmap, unmapped and heap. Small blocks come from the heap, carved up by malloc itself. A block above a threshold, initially 128 KiB, gets its own mapping from the kernel, which free gives back at once, so the second line finds it unmapped.

The last line surprises people. glibc’s threshold moves. When a block above the threshold and below its upper limit is freed, the threshold rises to that block’s size. So after freeing 1 MiB, the next 1 MiB request comes from the heap. The reasoning is that a program which frees and reallocates big blocks should not pay for a system call every time.

For latency, that matters in three ways. An mmap and a munmap are system calls. A fresh mapping is empty, so each new page faults on first touch. And because the threshold moves, the same request can cost differently depending on history, so a benchmark may not tell you what the first run does.

The cure on a hot path is not to allocate there. Allocate up front, touch the pages, and reuse the memory. To remove the moving threshold, set M_MMAP_THRESHOLD with mallopt, which turns off the dynamic behaviour.

Answer to Question 5.12.

It prints about 1024 0 and then 0 100. The call gives address space only, with no physical memory behind it. A page gets physical memory the first time it is touched, by a page fault. So the virtual size jumps by 1024 at once, and the resident size grows only for the 100 MiB touched.

The first line is a promise, and the second is reality. The kernel uses this for lazy allocation, for fork’s copy-on-write, and for programs that map far more than they use. In its default mode it refuses only obvious overcommits, so a 1 GiB request here succeeds, and a request for far more than the machine could provide would fail. The exact rule depends on a system setting.

If every process touches all it asked for and memory runs out, the failure does not come from mmap, which returned long ago. It comes at a later touch, where the kernel has no pages to give, and it picks a victim with the out-of-memory killer. So a process can die from an ordinary write, on a line with no allocation.

For a trading process, that suggests allocating and touching memory at start-up, and locking it with mlock if a page fault in the hot path cannot be accepted. A failure at start then shows up before the market opens.

Answer to Question 5.13.

1000 prints 1000, using about 1 MiB. 100 000 needs about 100 MiB under an 8 MiB limit, and the process dies with SIGSEGV. Under the 256 MiB limit, it prints 100000. You cannot catch this with try: stack overflow is a memory fault, not a C++ exception. A new thread’s stack is 8 MiB under this limit, which our test reads back.

The stack grows downward page by page, as it is touched. When it reaches the limit set by ulimit -s, the kernel refuses to extend it, and the access faults. A signal handler for this would itself need a stack, so it has to run on an alternate one (sigaltstack), and even then it can do little but report.

A new thread does not grow in this way. Its whole stack is mapped when the thread is created, with a size set by RLIMIT_STACK at program start. If that limit is unlimited, it is 2 MiB on x86-64 instead, so changing ulimit can change every thread’s stack size in surprising ways. Set it explicitly with pthread_attr_setstacksize when it matters.

That mapping is virtual memory, so 1000 idle threads of 8 MiB take 8 GB of address space, and little real memory. Guard pages lie below each stack, which turns most overflows into a fault, unless a large frame jumps right over the guard.

Answer to Question 5.14.

The smallest possible value is 1000: on one core, the child must run between the parent’s write and the parent’s read returning, so the parent must be taken off the core at least once in each round. It printed 1000 here. A context switch saves one thread’s registers, and loads another’s, along with its address space if it is in a different process.

The listing adds voluntary switches, when the parent blocks in read, and involuntary ones, when a woken child preempts it, as one can replace the other and only the total has a clean lower bound.

The direct cost is entering the kernel, running the scheduler, and changing registers. Between processes, it also changes the page-table root, which can discard translations. The larger cost usually comes afterwards. The other task has pushed the first one’s data out of the caches and its predictions out of the branch predictor, so it runs slowly for a while on return. That cost depends on the work, and does not show up in a plain ping-pong. Published figures vary greatly by machine, so measure yours, and we do not quote one here.

On two cores, with each side spinning on a shared variable and not blocking, neither process leaves its core, so no switch occurs at all. The message crosses by a cache line transfer. The price is two cores at full use, even when idle. That is the usual trade in the hot path of a trading system.

Answer to Question 5.15.

Round robin with quantum 2 finishes A at 13, B at 9 and C at 5, for an average of 9. First-come-first-served finishes at 8, 12 and 13, for 11. Shortest-job-first finishes C at 1, B at 5 and A at 13, for 6.33. As the quantum grows, round robin becomes first-come-first-served, which the test confirms.

"""Completion times under round robin, all tasks arriving at time 0 in the order given."""
from collections import deque


def round_robin(bursts, quantum):
    left = list(bursts)
    queue = deque(i for i, b in enumerate(bursts) if b > 0)
    done = [0] * len(bursts)
    now = 0
    while queue:
        i = queue.popleft()
        run = min(quantum, left[i])
        now += run
        left[i] -= run
        if left[i]:
            queue.append(i)
        else:
            done[i] = now
    return done

The trace for quantum 2 goes A to 2, B to 4, C to 5, A to 7, B to 9, and A to 11 and 13. The last completion is always 13, the sum of the work, under any order that never idles. The test checks that, and compares the function with a second tick-by-tick model on 300 random cases.

Shortest-job-first gives the lowest average of the three, and in fact the lowest of any order, since each task’s length is counted once for every task behind it. It has two problems. You do not know the lengths in advance, and a steady stream of short jobs starves a long one forever.

Round robin needs no knowledge of length, and it bounds how long anyone waits before running. A short job finishes early, as C does here. A very small quantum gets close to sharing the core equally, but in a real system each switch costs time, which the model ignores, and at some point the quantum is mostly overhead. A real scheduler such as Linux’s is more complicated, and tracks how much CPU each task has received.

Answer to Question 5.16.

Listing 5.29 follows each thread to what it waits on, and then to the holder of that lock, until it repeats itself or stops. Mutual exclusion, hold and wait, no preemption and circular wait must all hold. In practice, you usually remove circular wait, by taking locks in one global order.

"""Finding a deadlock: who holds which lock, and who waits for which."""


def find_cycle(holder, waits):
    """holder: lock to thread; waits: thread to the lock it needs. Returns a cycle or None."""
    done = set()
    for start in waits:
        path, seen = [], {}
        t = start
        while t in waits and t not in done:
            if t in seen:
                return path[seen[t]:]
            seen[t] = len(path)
            path.append(t)
            t = holder.get(waits[t])
        done.update(path)
    return None

No general search is needed since each thread blocks on at most one lock, and each lock has one holder. So every thread has at most one edge out, and from any start there is just one path to follow. It either stops at a running thread or enters a cycle. done makes the total work linear, as no thread is walked twice.

The other conditions can be removed too. Hold and wait goes if you take all locks at once, as std::scoped_lock does. No preemption goes if you use a try-lock and back off when it fails, at the risk of livelock.

The test compares the function with a reachability search on 2000 random states, of which over 100 hold a deadlock, and it checks that each returned cycle really is one.

With reader-writer locks or a semaphore, one lock may have many holders. The graph then has several edges per node, and needs a real cycle search, and for a semaphore a cycle no longer proves a deadlock, as another holder may release.

Answer to Question 5.17.

It prints b'Saaa' b'Saaa' b'SPaa' and b'SaTa' b'SaTa' b'SPaa'. The manual promises that a shared mapping’s writes reach the file and other mappings, and that a private mapping’s writes stay private. Whether the private mapping sees later changes to the file is unspecified, and that is where the S comes from.

The private mapping got the S, since its page was still the file’s own page at that moment, in the page cache. Its first write copied the page. After that it was on its own, and so the later T does not appear. A read through pread sees the shared write at once, as both go through one page cache.

A mapping suits random access over a large file, such as a tick store, since the kernel pages data in on demand, and evicts it under pressure, and it avoids a copy into a user buffer. It also lets several processes share one read-only copy in memory. read is often better for sequential scans. It also reports an I/O error as a return value, whereas a mapped read fails with a signal. And in the hot path, a mapped read can block on a page fault with no system call in sight.

A shared write reaches the disk when the kernel writes back the page, some time later. To force it, call msync, or fsync on the file.

Answer to Question 5.18.

write succeeding means the bytes reached the page cache, so the disk may hold the old file, the new one, or any mix. Listing 5.30 writes a new file, flushes it, renames it over the old name, and flushes the directory.

"""Replacing a file so that a crash leaves either the old contents or the new, never a mix."""
import os


def atomic_save(path, data):
    tmp = path + ".tmp"
    with open(tmp, "wb") as f:
        f.write(data)
        f.flush()
        os.fsync(f.fileno())                 # the new bytes are on disk
    os.replace(tmp, path)                    # the name moves in one step
    fd = os.open(os.path.dirname(path) or ".", os.O_RDONLY)
    try:
        os.fsync(fd)                         # and the move itself is on disk
    finally:
        os.close(fd)

Each call has a job. f.flush passes Python’s buffer to the kernel. fsync on the file forces the data and its metadata to the device, and it must come before the rename: otherwise a crash might leave the new name on an empty file. replace, which is rename(2), moves the name in one step, so another process never finds it missing. fsync on the directory makes that rename durable, as fsync on a file does not necessarily save the directory entry.

The test records the order of the calls, and simulates a crash before the rename, which leaves the old contents whole. No test here cuts the power, so the durability itself rests on the manual pages, and on the device.

What remains unprotected: a drive that acknowledges a flush it has not done, which is the hardware’s fault. A crash after the rename and before the directory flush can give either version, each complete, and the caller must be able to accept that. Updates between two saves are lost, as this makes each save atomic, not each change. That is why a system that must lose nothing appends to a log, with an fsync per commit, and a save is only an optimisation on top. Each fsync is slow, which is why many systems flush in groups.

Answer to Question 5.19.

Here it prints 1e-09 and 0. Use CLOCK_MONOTONIC to time a request, as it does not jump, and CLOCK_REALTIME for the time of day, as only that one relates to a calendar and to other machines. A clock read needs no system call, since the vDSO maps the code and data for it into your process.

CLOCK_REALTIME can jump when the time is set, so a duration computed from it can come out wrong or even negative. CLOCK_MONOTONIC does not jump, but its rate is adjusted, slightly, by NTP-like services. CLOCK_MONOTONIC_RAW is free of those adjustments, and it is meant for comparison with the hardware. Monotonic time has an arbitrary start, so it says nothing to another machine.

The vDSO exists since such calls are frequent enough to dominate. Reading the clock then costs about a function call, with no kernel entry. We checked that the mapping is there, in /proc/self/maps, and not how each clock source behaves, so check what your machine does.

Resolution is the smallest step that the clock can report, 1 ns here. Accuracy is how close a reading is to true time, and a server may be off by far more than that, depending on how it is synchronised. Two timestamps from different machines can thus be out of order, however fine their resolution.

Answer to Question 5.20.

It prints connected and sent, then b'early'. The kernel, not your process, completes the handshake. accept just takes an already established connection off a queue, and data that arrived early waits in that connection’s receive buffer.

The handshake goes: the client sends SYN, the server replies with SYN and ACK, and the client sends ACK. connect returns after the second of these. listen tells the kernel to do this for the port. The backlog sets the size of the queue of completed connections waiting for accept, capped by a system setting (somaxconn).

If the queue is full, the manual allows two outcomes: the client gets an error, or its request is ignored so that a retransmission succeeds later. TCP on Linux takes the second by default, so a client may see connect take far longer. A tight server that accepts slowly during a burst of reconnections can stall clients in this way. The behaviour differs by system, and depends on the settings.

So a connection can be established and even hold data, in a server process that has never heard of it. If that process then exits, the client gets a reset. That matters for health checks: a successful TCP connect shows that the kernel is listening, and it does not show that your application is alive.

Answer to Question 5.21.

It prints (True, 'EADDRINUSE') twice and then (True, 'bound'). The side that closes first enters TIME_WAIT, here the server’s. The second line fails since Linux needs SO_REUSEADDR on both the old and the new socket: the socket left in TIME_WAIT was set up without it.

That is what this restart problem usually is. The old process is gone, its connection is in TIME_WAIT, and the port looks busy for a while. So set SO_REUSEADDR on the listening socket before bind, from the first version on. It does not allow two active listeners on one address.

TIME_WAIT has two jobs, and lasts for twice the maximum segment lifetime. The final ACK of the close may be lost, in which case the peer resends its FIN, and this side must still be there to answer. And old segments of this connection may still be in the network, so the same four-tuple must not be reused until they have died out.

So this state is correct, and it costs little: a small kernel object per closed connection. It can become a real problem for a client that opens very many short connections to one server, which can run out of source ports. The right remedy is usually to reuse connections. Setting the state’s duration lower or killing it early removes a protection, so be sure you have understood it first.

Answer to Question 5.22.

The product is $10^{10} \times 10^{-3} / 8 = 1.25$ MB. With a 65 535-byte window, the rate is $65\,535 \times 8 / 10^{-3} = 524$ Mb/s, about 5% of the link. Window scaling multiplies the 16-bit field by a power of 2, agreed during the handshake, so the window can reach 1 GiB.

"""A window protocol: what one round trip can carry, and a round-by-round model of it."""


def bandwidth_delay_bytes(link_bps, rtt_s):
    return link_bps * rtt_s / 8


def steady_rate_bps(window_bytes, rtt_s, link_bps):
    return min(window_bytes * 8 / rtt_s, link_bps)


def simulate_bytes(window_bytes, rtt_s, link_bps, seconds):
    """Each round trip sends one window, capped by what the link carries in one round trip."""
    per_round = min(window_bytes, link_bps * rtt_s / 8)
    return per_round * int(seconds / rtt_s)

A sender may have at most a window of unacknowledged data in flight, and acknowledgements take a round trip. So one window goes per round trip, whatever the link’s speed. To fill the link, the window must reach the bandwidth-delay product. The test compares the formula with a round-by-round count on 200 random cases, and it checks the two ends: a small window limits the rate, and a large window leaves only the link.

Double the round-trip time with a fixed window, and the rate halves. The extreme is an intercontinental link, where a small default window gives little throughput on a very fast path. That’s why buffer settings matter more with distance.

The two controls answer different questions. Flow control protects the receiver: it advertises how much buffer it has, and that is the window in the header. Congestion control protects the network: the sender keeps its own congestion window, grows it, and cuts it on signs of loss or delay. The sender uses the smaller of the two.

The answer ignores loss. A lost segment makes a typical sender cut its rate, so on a long path even a small loss rate can reduce throughput far below this limit.

Answer to Question 5.23.

Listing 5.32 keeps a buffer, and takes out complete messages only. recv returns whatever has arrived, which may be part of a message, several messages, or a mixture. On loopback, a small write usually arrives whole, so the bad version passes; on a real network with segmentation and bursts, it does not.

"""Length-prefixed messages over a byte stream: a 2-byte big-endian length, then the body."""
import struct

MAX_BODY = 4096


class Deframer:
    def __init__(self):
        self.buf = bytearray()

    def feed(self, data):
        self.buf += data
        out = []
        while len(self.buf) >= 2:
            size = struct.unpack_from("!H", self.buf)[0]
            if size > MAX_BODY:
                raise ValueError("frame too long")
            if len(self.buf) < 2 + size:
                break
            out.append(bytes(self.buf[2:2 + size]))
            del self.buf[:2 + size]
        return out


def frame(body):
    return struct.pack("!H", len(body)) + body

TCP has no idea where your messages begin. The length field goes first, so the reader can always tell how many bytes it needs, and the loop handles several messages in one read. If only a part of a message is there, it stays in the buffer until the next call.

The length limit matters. Without one, a corrupted length makes the reader wait for up to 65 535 bytes that may never arrive, and then deliver garbage as a message, with every later frame misaligned. With a wider length field, the same fault could hold gigabytes. An empty body is a legal message, and the test covers it, as a careless if not body would lose one. The test also feeds 300 messages through random splits, and over a real TCP connection read in pieces of 97 bytes.

del self.buf[:n] is cheap in CPython, as a bytearray only moves its logical start, and the test sees the first byte’s address move by $n$. In a language where it shifts the bytes, keep a read position, and compact from time to time.

On the sending side, send may accept only part of the data, so use sendall on a blocking socket, or keep the remainder and retry on a nonblocking one. Two threads must not write to one socket without a lock, or their messages can interleave.

Answer to Question 5.24.

It prints b'abcd' b'ij', then 65507, then Message too long. The bytes efgh were discarded when the 4-byte read took the first datagram. Each recv consumes one whole datagram, whatever the buffer size. 65 507 is the 65 535 limit of the IP length field, minus 20 bytes of IP header and 8 of UDP.

Nothing tells you about the truncation by default. recvmsg sets a MSG_TRUNC flag in its results, and with that flag passed to recv, the call returns the real length. So a feed handler should use a buffer larger than the biggest datagram it can receive, or check that flag.

A real feed keeps its datagrams below the path’s MTU, typically under about 1500 bytes on Ethernet. Larger ones get split into IP fragments, and if one fragment is lost, the whole datagram is lost, so the loss rate multiplies. Fragments also add reassembly work. Venues specify their packet sizes, so read the specification and size the buffer to match.

On a loopback interface the MTU is large, which is why the maximum works here without any visible problem. That says nothing about a real network.

Answer to Question 5.25.

It prints 8192, sent 1000, no error, True and [True]. The kernel doubles the requested size to allow for its own bookkeeping, so 4096 reads back as 8192. The receiving socket’s buffer overflowed, the kernel dropped the rest there, and the last column of /proc/net/udp counts those drops.

The sender sees nothing, since UDP has no feedback. A successful sendto only means the packet was accepted for sending. Nothing tells the receiving program either, and that is why you must watch the counters. The count of datagrams received is below 1000 on any run where the buffer is this small and nobody reads while they are sent.

For a feed handler that drops during bursts, the order of action is as follows. First measure where: socket buffer drops, the NIC’s ring, or the network. The sequence numbers tell you that data was lost, and the counters tell you where. Then look at the reader. It should do nothing on its thread but read and hand on, with slow work moved elsewhere. Give it a core of its own, and keep interrupts and the reader on the right NUMA node. Then raise SO_RCVBUF, with the system limit rmem_max if needed. A bigger buffer only rides out a burst, and if the reader is slower on average it still loses data, only later. For the last step, consider kernel bypass.

Answer to Question 5.26.

A group is an address in 224.0.0.0/4 that any host can join. A sender, which need not join, sends one copy, and the network copies it to all members. A host joins with IP_ADD_MEMBERSHIP. With join the listing prints b'tick', and otherwise nothing. 239.1.2.3 maps to 01:00:5e:01:02:03, and 31 other groups share that address.

"""The Ethernet address of an IPv4 group: 01:00:5e and the low 23 bits of the group."""
import ipaddress


def group_mac(group):
    low = int(ipaddress.IPv4Address(group)) & 0x7FFFFF
    return "01:00:5e:" + ":".join(f"{(low >> s) & 0xFF:02x}" for s in (16, 8, 0))

The Ethernet address keeps only the low 23 bits, and a group has 28 significant bits, so 5 bits are lost and $2^5 = 32$ groups map to each. 224.1.2.3 and 239.129.2.3 are two of them. So the network card may pass up packets for a group you did not join, and the kernel filters them out. Busy feeds should choose group addresses that do not collide.

Joining also has a network side. The host sends an IGMP report, and switches with IGMP snooping use it to forward the group only to ports that asked. The membership is per interface, so naming the wrong one is a classic reason for receiving nothing on a machine with several networks.

IP_MULTICAST_TTL defaults to 1, so the packet does not cross a router, and IP_MULTICAST_LOOP defaults to on, so a sender’s own host receives it. We read both from a fresh socket. Therefore a test on one machine can work while two machines on different subnets get nothing, unless the TTL is raised and the routers are set up for multicast.

The run here is on loopback, with no switch and no IGMP on a wire, so what the network does rests on the sources in the ledger.

Answer to Question 5.27.

It prints ('EINPROGRESS', 0) and ('EINPROGRESS', 'ECONNREFUSED'). A nonblocking connect starts the handshake and returns at once, so its result is only “in progress”, even when the attempt will fail. The real result is delivered later, in SO_ERROR.

So writable does not mean connected. select marks the socket writable when the attempt has finished, in either way. If you take that for success and start sending, you see a confusing error on the first write, far from the cause. Read SO_ERROR when it wakes: 0 means connected, and anything else is the reason for failure. Reading the option also clears it.

The listing’s first case is a server that exists and the second is a closed port. Both return EINPROGRESS here, even on loopback, and that is what makes the check necessary. The manual allows other results, so handle a return of 0, which means it connected immediately, as well.

A blocking connect can wait a long time on an unreachable host, with several retransmissions of the SYN, so a process that must stay responsive connects without blocking, and sets its own time limit using select or epoll.

Answer to Question 5.28.

With no arguments, the C++ program is killed by SIGPIPE and prints nothing. With one, send uses MSG_NOSIGNAL, so it returns $-1$ and the program prints -1 Broken pipe. In the Python listing, the first send returns 3, and the second raises BrokenPipeError, which is Python’s name for EPIPE.

A process that writes to a connection with no reader gets a signal, and by default that signal ends the process. So a server can die because one client went away, unless it takes care. Set SIGPIPE to be ignored at start-up, or pass MSG_NOSIGNAL on each send, and then handle the error return. Python sets it to ignored for you, which is why you see an exception there.

The first send succeeds, since at that point this side only knows that the peer has sent a FIN. A FIN means the peer has no more to send, and it could still be reading, so TCP accepts the data and sends it. The peer’s kernel, finding that the socket has been closed and nobody can read this data, replies with RST. Once that has arrived, the next write fails. The listing waits for that reply with a poll that asks for no event, as only an error or a hang-up then wakes it. A select for reading would not wait, as the FIN has already made the socket readable. Across a network, with no wait, the second send could go first and also succeed.

So a successful send never meant that the peer read it. Bytes in the local buffer may be lost, and if you need to know, the application needs its own acknowledgement. For order entry, that is why a session has sequence numbers and replies.

Answer to Question 5.29.

The high-priority task finishes at 26. This is priority inversion: the task in the middle, which needs no lock, delays a higher one by all of its 20 ticks. With priority inheritance, the holder of the lock runs at its waiter’s priority, and the high-priority task finishes at 6.

"""One CPU, strict priorities, by ticks. A task is (priority, arrival, program), a program
("cpu", n) and ("lock", n) steps, the second holding the lock n ticks. Larger is higher."""


def simulate(tasks, inherit=False):
    left = [[list(step) for step in prog] for _, _, prog in tasks]
    done, owner, now = [None] * len(tasks), None, 0
    while any(d is None for d in done):
        ready, waiters = [], []
        for i, (prio, arrival, _) in enumerate(tasks):
            if done[i] is not None or arrival > now:
                continue
            if left[i][0][0] == "lock" and owner not in (None, i):
                waiters.append(prio)
            else:
                ready.append(i)
        effective = {i: tasks[i][0] for i in ready}
        if inherit and owner in effective and waiters:
            effective[owner] = max(effective[owner], *waiters)   # at its waiter's priority
        now += 1
        if not ready:
            continue
        i = max(ready, key=lambda k: effective[k])
        step = left[i][0]
        if step[0] == "lock":
            owner = i
        step[1] -= 1
        if step[1] == 0:
            if step[0] == "lock":
                owner = None
            left[i].pop(0)
            if not left[i]:
                done[i] = now
    return done

The trace without inheritance: the low task runs 0–1 and holds the lock. The high task arrives and blocks at once on the lock, so the low task carries on to 2, when the middle one arrives and takes the core until 22. Only then can the low task finish, at 24. The high task then takes 2 ticks. With inheritance, the low task runs through to 4 at high priority, and the high task finishes at 6, as if the middle task were not there.

The test shows the shape. Without inheritance, the high task finishes at $6 + m$ for a middle task of $m$ ticks, so the delay grows without limit. With it, the time is always 6, bounded by what is left of the critical section. This is checked on 200 random cases. The last completion time does not change with inheritance, as the total work is the same: it only changes who waits.

The other fixes: keep critical sections short, avoid sharing locks across priorities, or run all lock holders at a raised ceiling priority. Linux has PTHREAD_PRIO_INHERIT for mutexes. A trading system that uses real-time priorities on pinned cores has this same risk: a low-priority thread that holds a lock and has lost its core can stop the hot path. A SCHED_FIFO thread that spins on a lock held by a lower real-time priority on its own core waits forever, as nothing lets the holder run. If the holder is a normal task, it runs only in the slice that the kernel keeps back from real-time tasks, 5% by default.

Answer to Question 5.30.

Listing 5.35 is one answer. may_read is false once a writer is waiting. Without that preference, a steady flow of overlapping readers could hold off a writer forever. The risk simply moves: a steady flow of writers can now starve the readers.

class RwLock {
    std::mutex m_;
    std::condition_variable readers_, writers_;
    int active_readers_ = 0, waiting_writers_ = 0;
    bool writing_ = false;

    bool may_read() const { return !writing_ && waiting_writers_ == 0; }

public:
    void lock_shared() {
        std::unique_lock l(m_);
        readers_.wait(l, [&] { return may_read(); });
        ++active_readers_;
    }
    bool try_lock_shared() {
        std::lock_guard l(m_);
        if (!may_read()) return false;
        ++active_readers_;
        return true;
    }
    void unlock_shared() {
        std::lock_guard l(m_);
        if (--active_readers_ == 0 && waiting_writers_ > 0) writers_.notify_one();
    }
    void lock() {
        std::unique_lock l(m_);
        ++waiting_writers_;
        writers_.wait(l, [&] { return !writing_ && active_readers_ == 0; });
        --waiting_writers_;
        writing_ = true;
    }
    void unlock() {
        std::lock_guard l(m_);
        writing_ = false;
        if (waiting_writers_ > 0) writers_.notify_one();
        else readers_.notify_all();
    }
};

The last reader wakes a writer, as the writer’s predicate cannot be true before that. A writer leaving wakes the next writer if there is one, and otherwise all readers, since many may enter at once. All state changes happen under the mutex, so no wake-up can be lost.

The test for preference needs no timing assumption in its assertion. One reader holds the lock. A writer thread calls lock and blocks, and the driver sleeps only to give it time to get there. Then try_lock_shared must return false. If the writer had not arrived yet, the call would return true and the test would fail, never pass wrongly. A twin with the writer check removed prints 1 on that line, so the test can fail the model. Under ThreadSanitizer, the writers and readers run with an invariant ($a = b$ on plain variables), and there is no race report.

It may be no faster than a mutex, since a reader must still write the lock’s state, here taking an inner mutex. So on many cores, all readers contend for one cache line, and for a very short critical section that traffic is the main cost. A read lock pays off when readers hold it long enough for real overlap. We measured nothing here. Other options, for very short reads and rare writes, are a sequence lock, or replacing a pointer to an immutable copy.

Answer to Question 5.31.

Listing 5.36 keeps 0 for free, 1 for locked, and 2 for locked with possible waiters. Locking and unlocking with no contention are atomic operations only, and the driver’s million rounds make no futex call. Three states are needed so that unlock can skip the system call when nobody is asleep.

class FutexMutex {
    std::atomic<int> state_{0};             // 0 free, 1 locked, 2 locked and maybe waiters

    long futex(int op, int value) {
        auto* word = reinterpret_cast<int*>(&state_);
        return syscall(SYS_futex, word, op, value, nullptr, nullptr, 0);
    }

public:
    static inline std::atomic<long> waits{0}, wakes{0};

    void lock() {
        int c = 0;
        if (state_.compare_exchange_strong(c, 1, std::memory_order_acquire)) return;
        if (c != 2) c = state_.exchange(2, std::memory_order_acquire);
        while (c != 0) {
            ++waits;
            futex(FUTEX_WAIT_PRIVATE, 2);        // sleeps only if the state is still 2
            c = state_.exchange(2, std::memory_order_acquire);
        }
    }
    void unlock() {
        if (state_.exchange(0, std::memory_order_release) == 2) {
            ++wakes;
            futex(FUTEX_WAKE_PRIVATE, 1);
        }
    }
};

With two states, unlock cannot know if anyone is sleeping, so it either makes a system call each time, or loses sleepers. State 2 records that someone may be asleep. A thread that fails to get the lock swaps in 2, and sleeps. If the old value was 0, its swap has in fact taken the lock.

A woken thread does not know whether others are still asleep, so it must set 2 and not 1. With 1, it would release later with no wake-up, and any other sleeper would sleep forever. Our test builds this twin, and the driver, with two waiters behind one holder, hangs and hits its time limit. The state 2 sometimes causes one unneeded wake-up, which is harmless.

FUTEX_WAIT takes the expected value because of a race. Between a thread’s decision to sleep and its entering the kernel, the holder may unlock and call wake, and with nobody yet asleep, that wake is lost. So the kernel checks the word and blocks atomically, and only if it still holds 2. If not, the call returns at once. That check closes the gap.

The memory orders are acquire on taking the lock, and release on giving it up, so the critical section’s accesses cannot leak out. The counter’s 400 000 is exact, and ThreadSanitizer reports no race. A real mutex adds spinning before sleep, and a lot of careful handling, so use std::mutex in production.

Answer to Question 5.32.

About 40.2 ms, or 400 times the round trip. The header goes at once, but Nagle holds back the body until the header is acknowledged, and the server delays that acknowledgement, as it has no reply to send until it has the body. Each waits for the other until the 40 ms timer ends it.

"""Small writes, then a wait for the reply, as events. Times in ms; each trip takes rtt / 2.
The peer replies once it has every piece; until then it holds its ACK for delack ms."""
import heapq


def request_reply_ms(pieces, nagle, rtt=0.1, delack=40.0, quickack=False):
    trip = rtt / 2
    events, tie = [], 0

    def at(when, what, n=0):
        nonlocal tie
        tie += 1
        heapq.heappush(events, (when, tie, what, n))

    if nagle:                                # one piece flies; the rest wait for its ACK
        at(trip, "data", 1)
        held = pieces - 1
    else:
        for _ in range(pieces):
            at(trip, "data", 1)
        held = 0
    got = 0
    while events:
        now, _, what, n = heapq.heappop(events)
        if what == "data":
            got += n
            if got == pieces:
                at(now + trip, "reply")      # the reply carries the ACK
            elif quickack:
                at(now + trip, "ack")
            else:
                at(now + delack + trip, "ack")
        elif what == "ack" and held:
            at(now + trip, "data", held)
            held = 0
        elif what == "reply":
            return now
    raise RuntimeError("no reply")

Each rule is reasonable alone. Nagle’s rule sends small data only when nothing is unacknowledged, which saved networks from floods of tiny packets. Delayed acknowledgement waits a little in the hope of carrying the ACK on a reply. The standard allows that delay up to 0.5 s, and the stem takes 40 ms. Together, in the pattern write, write, read, they deadlock until a timer fires. The timeline is: header arrives at 0.05, timer ends at 40.05, ACK arrives at 40.1, body arrives at 40.15, reply arrives at 40.2.

Three fixes. Best is to make one write: put the header and body in one buffer or use writev, which also saves a packet and a system call. Second is TCP_NODELAY, which sends everything at once, for 0.1 ms in the model, and is the usual setting for trading connections, where the application decides what a message is. Third is TCP_QUICKACK on the receiver, which gives 0.2 ms in the model, though it is not permanent, and must be set again.

One write alone never stalls, as the test shows, since nothing is outstanding when it goes. As the timer approaches 0, the stall shrinks to one extra round trip. TCP_NODELAY defaults to 0 on a new socket, which we read back. This is a model, and no packet capture was run, so the real timer value is the machine’s to determine.

Answer to Question 5.33.

The card takes the frame off the wire and writes it by DMA into a ring of receive buffers in memory. It raises an interrupt, or the driver is already polling. NAPI polls in software-interrupt context, hands the packet up through IP and UDP, finds the socket, and adds the packet to its receive queue. The scheduler wakes your thread, and recv copies the bytes to your buffer.

Stage by stage, here is where it waits, drops or copies.

The card: it hashes the header to choose one of its queues (receive side scaling), so a flow goes to a fixed queue and interrupt. If the ring is full, as when the kernel falls behind, the card drops the packet. ethtool -S shows those counters. Interrupt moderation may hold the interrupt for a short time, to batch packets.

The softirq: packets are processed on a core, possibly one chosen by the software steering of RPS. If that per-core queue passes its limit (netdev_max_backlog), the packet is dropped, and the second column of /proc/net/softnet_stat on this kernel holds the count. If the core is busy with other work, the packet waits here.

The socket: UDP finds the socket by address and port, and multicast membership is checked. If the socket’s receive buffer is full, the packet is dropped, and /proc/net/udp and nstat show that.

The wake-up: your thread must be scheduled, on a core that may be asleep or busy. A thread that spins in a nonblocking recv removes this wait. Then there’s the copy to user space, one more copy, and the system call’s cost.

Kernel bypass maps the card’s rings directly into the process, and your thread polls them, so the interrupt, softirq, protocol stack, socket queue, wake-up and copy all go. What remains is the DMA, your poll, and a full ring if you are slow. You give up kernel tools, and have to run your own protocol handling.

This answer is a description, and no packet was traced for it, so the stages rest on the kernel documents in the ledger.

Answer to Question 5.34.

It prints [1, 1, 1] and [1, 0, 1]. Level-triggered mode reports the socket as long as data is unread, so the six leftover bytes give an event on the second poll. Edge-triggered mode reports changes only: nothing new arrived, so the second poll is empty, and the third fires since new data came.

So under edge-triggered mode, if you read only part of the data and wait, you can wait forever with bytes in the buffer, if no more arrive. The rule is to read until EAGAIN. That needs a nonblocking socket, as a blocking read on an empty socket would stall the whole loop. The same goes for writes.

Edge-triggered mode avoids repeat wake-ups for a socket you know you cannot serve yet, and it lets several threads share a set of sockets without all waking up on one event. It is easier to get wrong: level-triggered is the safer default.

select and poll take the whole set of descriptors on each call, and the kernel scans it, so each call costs in proportion to the number watched, whatever the number active. epoll registers once and keeps a ready list, so each call costs in proportion to the number ready. For ten thousand idle connections, that is a large saving.

It is no real gain when nearly all descriptors are active on each call, or when there are only a handful of them. A hot path that watches a few sockets may not wait at all, but spin with nonblocking reads, and avoid the system call that epoll_wait would be.

Answer to Question 5.35.

It prints parent threads 2, child threads 1, try_lock 0 and parent try_lock 1. Only the calling thread exists in the child. Memory is copied as it was, including the mutex in its locked state, and the thread that would unlock it does not exist there. So the child’s lock is stuck forever.

try_lock returns 0 here. A plain lock in the child would never return, and the program would hang with no error to show for it. That is the failure in the stem: a child calling into a logging library whose internal lock was held at the moment of the fork deadlocks at random, depending on what the other threads happened to be doing at the time. It may run for months and then hang.

The same goes for data under the lock. The other thread might have been halfway through an update, so the structure in the child is inconsistent, and no thread is there to finish it. Some libraries guard their state with pthread_atfork handlers, but you cannot count on every library.

So until it calls exec, a child of a multi-threaded process may safely call only async-signal-safe functions. In practice, you do almost nothing and call exec at once, or use posix_spawn. If you fork for a snapshot, do it before starting any threads, or copy data out by another route.

Answer to Question 5.36.

With no arguments it prints EOWNERDEAD and 0: the lock is granted, along with the news that its owner died. With one argument, a plain mutex stays locked, and the timed lock gives ETIMEDOUT. Without a time limit, the survivor would hang forever, with nothing in the logs.

The kernel can do this since a robust mutex’s owner keeps a list of the robust locks it holds. When a thread dies, the kernel walks that list, marks each lock with a flag, and wakes a waiter. A plain mutex is only a word in memory, and nobody knows who holds it. So a process crash leaves that word locked, and the whole shared segment is stuck.

On EOWNERDEAD, the new owner holds the lock, and the data it guards may be half updated, as the owner died at an arbitrary instruction. Only the application knows what a correct state looks like. So the new owner must check or repair the data, and then call pthread_mutex_consistent. If it unlocks without that call, the mutex becomes permanently unusable, and all later lock calls return ENOTRECOVERABLE. The library cannot repair the data for you, since it does not know what the lock protects.

So robustness has a price: every update must leave the data repairable, for instance by writing a log first, or by marking a record dirty during the update. In practice, the data’s design is the hard part.

The other course is to avoid a lock across processes at all. A lock-free ring lets a producer die with no lock held, and a separate process can watch for the death with waitpid or a heartbeat.

Answer to Question 5.37.

Listing 5.38 keeps the next number expected and a set of later ones. A duplicate or an old number is dropped, and whatever becomes contiguous comes out. When more than hold are waiting, the missing range is reported and skipped. Waiting forever would freeze the book: if both lines lost a packet, it will never come.

"""Merging the A and B lines of a feed: first copy wins; a gap comes after `hold` packets."""


class Arbiter:
    def __init__(self, first=1, hold=8):
        self.next = first
        self.hold = hold
        self.pending = set()
        self.gaps = []

    def on_packet(self, seq):
        """Takes a sequence number from either line; returns those now deliverable."""
        if seq < self.next or seq in self.pending:
            return []                        # the other line got here first
        self.pending.add(seq)
        out = []
        while True:
            while self.next in self.pending:
                self.pending.remove(self.next)
                out.append(self.next)
                self.next += 1
            if len(self.pending) <= self.hold:
                return out
            lowest = min(self.pending)       # waited long enough: give up on what is missing
            self.gaps.append((self.next, lowest - 1))
            self.next = lowest

The first copy wins, so the merged stream is at least as fast as the faster line, packet by packet, which is the point of having two. Each line is usually in order, so a missing number mostly means that line lost it, and the other line’s copy arrives shortly after.

hold sets the trade-off. Too small, and a copy that was merely behind on the slower line gets declared lost, which triggers a recovery for nothing. Too large, and every real loss stalls all later data until it is recognised. Choose it from the measured difference between the two lines: how many packets can arrive on the faster line during the normal lag of the slower one, at peak rates. A real handler adds a timer, as during a quiet market no later packet comes to trigger the gap check. This version has no timer, so a gap at the end of a burst stays pending.

The declared gap must go somewhere: a retransmission request, or a snapshot from a recovery service. Late copies that arrive after the skip are then dropped, as they are older than next.

The test merges two independently lossy lines at random on 300 cases. The output must be increasing, with no duplicates, and all numbers lost on both lines and passed by the output must be reported as gaps. With a large hold, a loss on one line never becomes a gap.

Answer to Question 5.38.

Each connection has a read buffer, through its Deframer, and a write buffer, out. Pending replies go in out. Listings 5.39 and 5.40 ask for EPOLLOUT only while out holds data, as an idle socket is almost always writable, and the loop would wake without pause. The server never blocks on one client.

class Conn:
    def __init__(self, sock):
        self.sock = sock
        self.reader = Deframer()
        self.out = bytearray()
        self.eof = False                     # the peer has finished sending


def serve(listener, stop_after_clients):
    listener.setblocking(False)
    ep = select.epoll()
    ep.register(listener.fileno(), select.EPOLLIN)
    conns, closed = {}, 0
    while closed < stop_after_clients:
        for fd, event in ep.poll():
            if fd == listener.fileno():
                sock, _ = listener.accept()
                sock.setblocking(False)
                conns[sock.fileno()] = Conn(sock)
                ep.register(sock.fileno(), select.EPOLLIN)
                continue
            c = conns[fd]
            alive = True
            if event & (select.EPOLLIN | select.EPOLLHUP | select.EPOLLERR):
                alive = read(c)
            if alive and flush(ep, fd, c):
                continue
            ep.unregister(fd)                # this client goes, and nobody else
            c.sock.close()
            del conns[fd]
            closed += 1
    ep.close()

def read(c):
    """Takes what has arrived. False if this connection must go."""
    try:
        data = c.sock.recv(65536)
        if not data:                         # it may still be reading our replies
            c.eof = True
        for body in c.reader.feed(data):
            c.out += frame(body)
    except BlockingIOError:
        pass
    except (OSError, ValueError):            # a reset, or a length above the limit
        return False
    return True


def flush(ep, fd, c):
    """Sends what the socket will take. False if this connection must go."""
    if c.out:
        try:
            del c.out[:c.sock.send(c.out)]   # may take only part
        except BlockingIOError:
            pass
        except OSError:                      # a reset: the replies have nowhere to go
            return False
    if c.eof and not c.out:
        return False
    ep.modify(fd, (0 if c.eof else select.EPOLLIN) | (select.EPOLLOUT if c.out else 0))
    return True

The loop uses the default level-triggered mode, so one recv per event is enough, and leftover data gives another event. Every socket is nonblocking, and that matters most for send: on a blocking socket, a client that stopped reading would stop the server for everyone, once its buffer filled.

send may take only part of the data, so flush removes what was accepted and keeps the rest. When recv returns empty, the peer has finished sending, and it may still be reading, as with a half-close. So the server stops reading, sends what is in out, and then closes. If the peer has really gone, a recv or a send raises an error, and the connection is dropped with its pending replies, which have nowhere to go. A bad length from one client closes that client alone.

In the test, 8 clients each send 300 messages of up to 4000 bytes, chopped at random, then half-close, and they read in pieces of 1000 bytes on a separate thread. The sockets have small buffers, so the server must queue replies, and the test checks that it did. Every client gets its messages back exactly, in order, and the server stops once all have closed. A second test has one client close without reading and another send a length above the limit, and a third client is still served.

One slow client costs the others little CPU, but this listing has a real flaw: out has no limit, so a client that writes and never reads makes the server’s memory grow without bound. A real server limits it, by no longer reading from that client once out is large, which pushes back through TCP to the sender, or by closing the connection. Also, a single huge message delays the rest, as the loop runs one thread. Handlers must not block or run long.

Answer to Question 5.39.

Listing 5.41 is one such model. The sender repeats every unacknowledged packet in its window, and the receiver holds early packets, and delivers contiguous ones. It must acknowledge a duplicate, as a duplicate means its earlier ACK may have been lost. Otherwise the sender would resend forever.

class Receiver:
    def __init__(self):
        self.next = 0
        self.held = {}
        self.delivered = []

    def on_packet(self, seq, body):
        if seq >= self.next:
            self.held[seq] = body
        while self.next in self.held:
            self.delivered.append(self.held.pop(self.next))
            self.next += 1
        return seq                           # acknowledge every packet, even a duplicate


def send_all(bodies, window=8, loss=0.0, seed=0, max_rounds=100000):
    """Returns (delivered, transmissions, largest window used), or raises TimeoutError."""
    rng = random.Random(seed)
    rx = Receiver()
    base, acked = 0, set()
    sent = widest = 0
    for _ in range(max_rounds):
        while base in acked:
            base += 1
        if base == len(bodies):
            return rx.delivered, sent, widest
        flight = [s for s in range(base, min(base + window, len(bodies))) if s not in acked]
        widest = max(widest, max(flight) - base + 1)
        rng.shuffle(flight)
        for seq in flight:
            sent += 1
            copies = 2 if rng.random() < 0.05 else 1
            for _ in range(copies):
                if rng.random() >= loss:
                    ack = rx.on_packet(seq, bodies[seq])
                    if rng.random() >= loss:
                        acked.add(ack)
    raise TimeoutError("link too lossy")

The window limits how much is in flight, so it limits how much the receiver may have to hold and how much a loss wastes. With $w = 1$, this is stop-and-wait, and the rate is one packet per round trip, which the test checks through the widest window used.

Why in order and exactly once? delivered grows only in the while loop, which appends next and increments it, so the numbers delivered are $0, 1, 2, \dots$ with none skipped or repeated. A packet with a number below next is never stored, so a duplicate cannot come out again. Why does it finish? While the loss rate is below 1, each packet eventually gets through with its ACK, with probability 1, so the base keeps moving. The sender’s acked set only ever holds packets that the receiver really received. So nothing is dropped by a false acknowledgement.

The test delivers all of 200 packets at loss rates of 0, 0.1, 0.5 and 0.8, on several seeds. It checks the window, that no loss means exactly 200 transmissions, that more loss costs more, and that a loss rate of 1 raises TimeoutError rather than hanging. Duplicates and reordering are in the link model.

TCP has the same core, a window with cumulative acknowledgements, and selective ones as an option. What the model leaves out is real time: retransmission timers, round-trip estimation, and a congestion window that shrinks on loss. Flow control is also absent: this receiver has unlimited buffer. In a real network, sending a full window on each round when the link is the cause of the loss makes it worse.

Answer to Question 5.40.

Listing 5.42 is the ring. Indices must be lock-free, as a lock inside std::atomic would be private to one process, or be stuck if its holder died. The static_assert on is_always_lock_free checks that at compile time. If the producer dies, the consumer sees everything that was published, each slot whole, and never a slot half written.

template <std::size_t N>
struct ShmRing {                                // lives in shared memory; N is a power of two
    static_assert(std::atomic<std::uint64_t>::is_always_lock_free);
    alignas(64) std::atomic<std::uint64_t> head{0};   // the next slot to write, producer only
    alignas(64) std::atomic<std::uint64_t> tail{0};   // the next slot to read, consumer only
    alignas(64) std::uint64_t slots[N];

    bool push(std::uint64_t v) {
        std::uint64_t h = head.load(std::memory_order_relaxed);
        if (h - tail.load(std::memory_order_acquire) == N) return false;
        slots[h & (N - 1)] = v;
        head.store(h + 1, std::memory_order_release);   // publish only a complete slot
        return true;
    }
    bool pop(std::uint64_t& v) {
        std::uint64_t t = tail.load(std::memory_order_relaxed);
        if (t == head.load(std::memory_order_acquire)) return false;
        v = slots[t & (N - 1)];
        tail.store(t + 1, std::memory_order_release);
        return true;
    }
};

The slot is written first, and head moves only afterwards, with a release store. So a kill at any instruction leaves one of two states: head unchanged, and the slot’s contents simply unseen, or head moved with the slot complete. One store to head is one atomic step, with no state between. The consumer cannot tell from the ring alone that the producer has died, as a dead one and an idle one look the same, so it needs waitpid, a heartbeat or similar.

The driver has a child push the sequence 0, 1, 2 and so on until the parent kills it with SIGKILL, at a moment it did not choose. The parent has checked 200 000 values by then, drains what remains, and finds the sequence unbroken. It prints 0 9 1: no errors, signal 9, and enough read.

A mutex in that memory would behave differently. A process killed while holding one leaves it locked, unless it is robust, and then the data can be half updated, so you need a recovery plan. For this reason, a shared-memory path between processes is often built lock-free.

ThreadSanitizer sees one process, so the test runs the same header between two threads under it, and finds no race. With the store and load relaxed, it reports a data race, which shows that the test can catch a wrong order. The orders are the same, whether threads or processes run them. x86-64 hides this kind of fault on real runs, and we had no weakly ordered machine here. The cache-line alignment keeps the two indices from sharing a line.