Using Threads for Computational Speedup

A common rule of thumb says that a program should never run more threads than the computer has processors. For many programs this is a sensible starting point. But consider a server that runs on a machine with a small number of processors, where each of its threads spends most of its time waiting for network input and output to finish, blocked around 90 percent of the time. Would such a server want more threads than processors, fewer, or the same number?

The word blocking describes what the thread is doing, not what the network is doing. While the operation is pending, the thread cannot continue past that point in its own code. Because the length of the wait is unpredictable, a network program cannot assume that a read will finish quickly. The source makes this point directly: programs that use the network must be prepared to deal with this blocking. Waiting is not an unusual event in network code. It is part of how that code normally behaves.

Blocking input and output also appears outside networks. Reading input that a user types at a command line program is another form of blocking input and output. The difference that matters for network programs is not whether they wait, but what else the program could be doing during the wait.

To see what blocking does to a thread, follow one thread through a single network read. The thread starts out running, executing its own code. When it reaches a network read whose data has not arrived yet, it becomes blocked. While it is blocked it is waiting, and it does not compete for the processor. When the data arrives, the thread becomes runnable again, meaning it is ready to continue. The operating system then gives it processor time, and it returns to running.

The timeline shows one thread. The key observation is the gap between issuing the read and the data arriving. During that gap the thread is blocked, and the length of the gap is not something the program can predict in advance. The source describes this as blocking for indefinite periods of time, so the length of the blocked stretch varies from read to read.

The state diagram names the same movement as a set of transitions. A thread enters the blocked state when it makes a blocking network call. The event that moves it out of blocked is the arrival of the data it was waiting for. A blocked thread does not compete for processing time, which is the property the rest of this article relies on.

Blocking is not always a problem. In some programs it is acceptable to stop all other processing and wait for input. A program with nothing else to do can afford to wait. A program with other work available benefits from letting some parts keep running while other parts are blocked. Threads make that possible: they let a program keep doing useful work in some parts while other parts are blocked.

The source contrasts two network programs. A client that sends requests to a server might be fine with a single thread, if it has nothing else to do while it waits for responses. A server is different. A server can usually be connected to several clients at the same time, and while it waits for data from one client, it can communicate with the others. When the server gives each client connection its own thread, a block on one connection does not stop the server from talking to the rest.

The processor rule breaks down once you separate two goals for threads. The first goal is computational speedup: using threads to make calculations finish sooner. The second goal is handling blocking input and output. The two goals ask the same question, how many threads can actually be doing work at the same time, but they get different answers, because a blocked thread does not count as doing work.

For computational speedup, the natural choice is one thread per available processor. If only one processor exists, adding more threads gives no speedup at all, and it slows the program because of the overhead of creating and managing the threads. Speedup is limited by how many threads can make real progress at the same time, and computing threads all want the processor at once.

For blocking input and output the situation is different. Many threads are waiting at any given moment, and a waiting thread does not compete for the processor. Only the active, unblocked threads compete for processing time. A program can therefore have many more threads than processors without overloading them, because most of those threads are not running at a given moment. The useful thread count for a blocking program is tied to how much of the time the threads spend waiting, not only to the number of processors.

The source gives a rough target for blocking I/O: about one active thread per processor. If the threads are mostly blocked, that target can mean many more threads in total. The rule of thumb is a starting point for estimation, not an exact formula. The calculation depends on how much blocking actually happens, which means you need to measure the blocked fraction for the program in question.