Waiting on Two Things

For eight chapters you have been following the bytes, down through the headers on your machine, along the wire, and up through the headers on Mira’s. It has been a useful place to stand, and it has also left something out. In this chapter the camera turns around. Instead of watching the bytes, you watch the program, and in particular you watch what it does during the long stretches, which are most of the time, when no bytes are arriving at all.

Take the chat window on your machine, written as plainly as it can be written. It connects to Mira’s program at 5222 and gets a conversation handle. Then it loops:

forever:
    line = read from keyboard
    write line to socket
    reply = read from socket
    show reply

It reads what you typed and sends it, then reads what she sent and shows it, and goes around again. Run it. You type hi and press enter. The first line completes, and the second line sends your greeting. Now the program reaches the third line and calls read on the socket, and Mira has not replied yet. Something has to happen, and it is worth being clear about what.

Think about what you are asking for. To read from the socket means to be given the bytes that have arrived on this conversation. None have. The socket’s buffer, the one the operating system set up in Chapter 8, is empty. The operating system has two choices. It could return immediately and say that there is nothing yet, in which case your program would have to ask again, and again, spinning through the loop thousands of times a second and burning the processor on a question whose answer is not changing. Or it could hold the program: suspend it right there in the middle of the read call, and not let it continue until bytes arrive. Then, when Mira’s reply lands in the buffer, it wakes the program and hands it the bytes as if no time had passed.

Operating systems chose the second, and for good reason. A held program costs nothing. It is not running, it is not using the processor, it is parked. When you have one thing to wait for, parking until it happens is the right thing to do. A call that behaves this way is said to block, and every read you have ever done from a file or a keyboard or a socket has probably worked this way without your noticing, because there was always something to read soon enough.

So your program blocks on the socket. Two seconds later Mira replies. The program wakes, shows the reply, and loops back to the top, where it reads from the keyboard, and now it is blocked there, waiting for you to type.

The failure is so ordinary that you may already have spotted it. Your program is at the top of the loop, parked on the keyboard, waiting for your next line. Mira sends another message, and then another. She is typing quickly; she has something to say. Nothing appears on your screen. Her messages have arrived. They are sitting in the socket’s buffer on your machine, because the operating system did its job, matched the four-tuple, and put the bytes where they belong. But your program is not looking at the socket. It is parked on the keyboard, and it will not look at the socket until you type something, at which point it will send your line, and then read from the socket, and three of Mira’s messages will tumble out at once. You are deaf to Mira whenever you are waiting for yourself.

Very well, swap the order. Read the socket first and the keyboard second. Now you see Mira’s messages the instant they arrive, and you cannot type a word until she says something, because the program is parked on the socket and will not reach the keyboard read until bytes come in. Now you are deaf to yourself whenever you are waiting for Mira. Whichever order you choose, one of the two inputs is always the one you are blocked on, and while you are blocked on it the other one might as well not exist.

loading…

Your program is a single cursor moving through its loop. The keyboard and the socket are two lamps. Pick an order for the reads, then type while Mira sends, and watch the cursor park on one lamp while the other lights up unattended.

This is not a bug in the program. Every line of it is correct. It is a consequence of blocking itself, of the very sensible decision that a read should park you until there is something to read. That decision assumed one thing to wait for, and you have two. The moment you have two, whichever one you choose to wait on, you have chosen to ignore the other. And it took very little to get here. Not a thousand users, not a busy server, but one conversation with one person and a keyboard. The simplest chat client that could possibly exist is already broken by this.

The first fix is the one most people reach for, and it works. If the problem is that one program can only be parked in one place, have two. Ask the operating system to run two paths through your program at once, two threads, each with its own position in its own loop. One thread does nothing but wait on the keyboard and send what you type. The other does nothing but wait on the socket and show what arrives.

thread A, forever:               thread B, forever:
    line = read from keyboard        reply = read from socket
    write line to socket             show reply

Each thread blocks on its one thing. When you type, thread A wakes and sends. When Mira writes, thread B wakes and shows. Neither ever waits on the other’s input, because neither ever reads the other’s input, and the chat works.

The appeal of this is real. Each thread’s code reads like a straight line: do this, then that, then wait. There is no cleverness in it. You have made two simple programs and let the operating system interleave them. But sit with it a moment longer and ask what the threads are doing. Almost all of the time, nothing. Thread A is parked and thread B is parked. Both are suspended inside a read, waiting. The operating system is watching the keyboard and the socket on their behalf, and when one of them has something, it wakes the matching thread. All the real work, which is noticing that bytes have arrived, is being done by the operating system. The threads are two places to be parked, and no more than that.

If the operating system already knows when either the keyboard or the socket has something, there is no reason to ask it in two separate places. Ask once. Hand it both handles and say: park me until any of these is ready, and tell me which. That gives you one thread and one loop, and it looks like this:

forever:
    ready = wait until any of [keyboard, socket] has something
    if keyboard in ready:
        line = read from keyboard      ← won't block; we know it's ready
        write line to socket
    if socket in ready:
        reply = read from socket       ← won't block; we know it's ready
        show reply

The program parks in one place only, the wait at the top. It is not waiting on the keyboard or on the socket. It is waiting on the operating system to tell it that something is ready. When something is, it wakes knowing which, reads from that one, and the read does not block, because the whole point is that there is something there. It acts on what it read and goes back to the top to wait again.

You type, and the wait returns with the keyboard flagged; you send, and go back to waiting. Mira writes, and the wait returns with the socket flagged; you show it, and go back to waiting. If both happen at once the wait returns with both flagged, you handle both, and you go back. Nothing is ever missed, because you are never parked on one input to the exclusion of the other. You are parked on all of them at once, which is something only the operating system can offer, and it does.

This shape, one thread, one wait, and act on what is ready, is called an event loop. The question at the top, which of these is ready, is called readiness notification, and every operating system provides it under one name or another. The loop is the shape of every server you will ever write, whether you write it by hand or a language writes it for you.

It is worth setting down what you have agreed with the operating system, because it is an agreement in the sense this book has been using all along, and both halves matter. The operating system’s half is that it will tell you when any of your handles is ready, so that you never have to guess and never have to block on one while another is waiting. Your half is that you will never park yourself on a single handle; when the operating system tells you something is ready, you deal with it and come straight back to ask again.

The operating system keeps its half through the readiness call. You keep yours by discipline, and your half is where this goes wrong, which is why it gets a chapter of its own. If you break your promise, if in the middle of handling one input you do something that parks the program for a while, then the loop is not at the top asking what is ready. It is stuck in the middle, and every other lamp can light up as much as it likes, because nobody is looking.

Coming up · I·15 — One Slow Thing

You have promised not to make the loop wait. In Chapter 15 you break that promise three different ways, and watch what happens to every conversation the program is holding.

→

The keyboard and one socket are two inputs. Two threads handle two inputs perfectly well, and if that were the end of the matter the loop would be a curiosity. It is not the end of the matter. Turn to Mira’s side. Her program is the one with the listening socket at 5222, and in Chapter 8 it acquired three connected sockets, yours, your second window, and Theo’s. Next month it will be thirty people, and in Part III it will be a great many more than that.

With threads, every conversation is a parked thread. Thirty conversations means thirty threads, which is fine. Ten thousand conversations means ten thousand threads, each holding memory for its own stack, each something the operating system has to keep track of and switch between, and almost all of them parked almost all of the time, because most people in a chat are reading rather than typing. You are paying for ten thousand waiters so that a handful can act.

With the loop, every conversation is a handle in a list. Ten thousand connections is ten thousand entries. There is one thread and one wait, and the operating system reports which handful are ready. The nine thousand nine hundred idle ones cost nothing but their place in the list. When one of them becomes ready it is handled and then forgotten again.

loading…

On the left, one parked thread per connection. On the right, one loop and one list. Add connections, and watch the memory and the switching cost on the left climb while the right stays flat until something actually happens.

The knock of a new connection from Chapter 8 folds in without any extra machinery. A listening socket is just another handle, and it becomes ready when someone is waiting to be accepted. So the loop watches it alongside every connected socket, and when it lights up the program accepts, adds the new handle to the list, and goes back to waiting. New conversations and old ones are handled in the same place:

handles = [listening socket]
forever:
    ready = wait until any of handles has something
    for each h in ready:
        if h is the listening socket:
            new = accept from h
            add new to handles
        else:
            bytes = read from h
            handle bytes

That is a server, and that is the whole shape of one. It will get more elaborate, since you will add writing, and timeouts, and the handling will grow complicated, but the skeleton you have just written is what is inside every web server, every chat server, and every database’s network layer.

Before we move on, reading is not the only thing that can park you. Somewhere in the loop above, you write to the socket. It has given you no trouble yet, and it will not, until Mira’s machine gets busy or the wire gets slow, and one day a write, which has always returned at once, does not return. The program sits there in the middle of the write, the loop is not at the top, and the lamps light up unattended. Why a write would ever wait is a question about what is happening at the other end of the conversation, and you do not have the tower to answer it yet. Five chapters from now you will. For the moment the fact to keep is that write can block too. It is the other half of the promise.

Coming up · I·14 — Slow Down

Write has always come back at once. In Chapter 14 it does not, and the reason turns out to be one of the most important ideas in the book.

→

Threads or the loop?

You built both, and both are real, so it is worth being honest about the trade.

Threads let each conversation be written as a straight line: read, think, write, read. Nothing is inside out. The cost is that every conversation is a parked thread, which is fine at dozens and painful at tens of thousands, and that threads sharing memory need a kind of care you have not had to think about yet.

The loop handles any number of conversations in one thread and costs nothing for the idle ones. The cost is that the code is inside out. Instead of read, then think, then write, you have “when readable, read” and “when writable, write”, with the “then” scattered across handlers. It is harder to read, and it depends entirely on your keeping the promise.

Modern languages mostly resolve this by hiding the loop. You write what looks like a straight line, await the read, then think, then await the write, and underneath, a loop is parking your straight line at each await and running someone else’s until you are ready. It is the best of both, and it has one cost of its own, which is that people use it for years without ever knowing there is a loop under there or that they have made it a promise. Then one day they do a slow thing without an await in front of it, the loop stops, and every user of their program freezes at once, and they have no idea why, because nobody ever showed them Chapter 9. You have now seen it. Chapter 15 is about keeping the promise.

The camera has turned back around now. The bytes get the next few chapters, because there is something badly wrong with them: Mira is about to send you a photo, and it is not going to fit. But carry this chapter’s picture with you. Your program is a cursor in a loop, parked at the top, waiting for the operating system to say what is ready. Everything that happens to your program from here on happens between two of those waits. When you read about a server handling a million connections in Part III, this is how. When you write a server that mysteriously stops responding to everyone at once, this is why.

Coming up · I·10 — Too Big for One Frame

Mira sends a photograph. It is three megabytes. The frame holds fifteen hundred.

→

In the real world

The readiness call was first offered by BSD Unix in 1983 as select. You handed it a set of handles and it returned when any of them was ready. It was joined by poll, and then by faster variants built for large sets: epoll on Linux in 2002, kqueue on BSD and macOS, and I/O completion ports on Windows. They differ in how they scale and in what precisely they report, but every one of them is the question at the top of your loop.

The moment the loop became unavoidable is well documented. In 1999 a paper titled “The C10K problem” asked how one machine could serve ten thousand simultaneous connections, and answered that it could not be done with a thread each. Servers built around a single loop displaced the thread-per-connection designs that preceded them for the reason your second visual shows; nginx, released in 2004, is the canonical example. Node.js, in 2009, made the loop the only model: every program is a loop, whether the programmer knows it or not.

That last clause is the point. async and await, in JavaScript since 2017, in Python since 2015, and in most languages since, are the loop with the bookkeeping hidden. Each await is your program keeping its promise, saying that it is going to wait for this and something else may run. Each blocking call without one is the promise broken. Every mysterious “my server stopped responding to everyone” report in every help forum is someone discovering Chapter 15 the hard way.