Threads and concurrency models

Why this matters

Processes being isolated from each other is an advantage until you need to compute something together. Passing data between processes costs copies and system calls, and creating a process requires a whole new address space.

Threads solve this: several lines of execution in one address space, cheap to create and instant at sharing data. That is also what makes them dangerous: everything that makes threads convenient also makes them a source of bugs that don’t reproduce.

Prerequisites. The address space and the process control block (module 6), the context switch and scheduling (module 7).

What threads share

The shared heap gives threads both their whole advantage and their whole danger. Sharing data is free, because nothing stops two threads from writing to the same variable.

What they have in common is the code, global and static data, the heap, the open file table, the current directory, credentials and signal handlers.

What stays their own is the stack, the registers including the program counter, the mask of blocked signals, thread-local storage (TLS) and the ID.

The practical consequences are immediate. A pointer obtained in one thread is valid in another, unlike with processes. A file opened by one thread is available to all. But one thread’s local variable is out of reach for the rest, because it lives on that thread’s own stack.

Most important: if one thread accesses an invalid address, SIGSEGV takes down the whole process. There is no isolation between threads at all.

Process or thread

	Process	Thread
Address space	its own	shared
Creation cost	high	low
Data exchange	IPC, copying	shared memory, free
Fault isolation	a crash doesn’t affect others	a crash kills everyone
Switching	reloading page tables, flushing the TLB	registers only

The rule for choosing is simple. If parts of a program have to work on the same data, use threads. If they are independent and a failure in one must not affect the rest, use processes. Browsers deliberately went back to a separate process per tab because of the fourth row of this table.

In Linux the difference is smaller than it looks

The Linux kernel has no separate “thread” entity. Both a process and a thread are created by the same clone() call, and the only difference is which resources the flags say to share. fork() is the same clone() without CLONE_VM, and creating a thread is clone() with it. So the kernel schedules tasks, not processes, and ps -eLf shows them.

Mapping models

Threads live on two levels at once: there are the ones managed by a library in user space, and there are the ones the kernel scheduler sees.

In the N:1 model, all of a program’s threads are mapped onto one kernel thread. Switches are very cheap, because they never enter the kernel at all, but a single blocking system call stops every thread at once, and there is no parallelism across multiple cores whatsoever.

In 1:1, each user thread has a matching kernel thread. One blocking doesn’t affect the others and the parallelism is real; the price is that creating a thread goes through the kernel, and the number of threads is limited by kernel resources. This is how Linux, Windows and macOS work.

M:N multiplexes M user threads onto N kernel threads by the library. In theory it is the best of both worlds; in practice, coordinating the library’s scheduler with the kernel’s turned out to be extremely hard: Solaris and FreeBSD tried and gave up.

Concurrency without threads

Courses usually end with the previous section, but the industry has moved on. The problem with the 1:1 model is that a kernel thread costs memory for its stack and takes part in scheduling. Ten thousand connections turn into ten thousand threads, gigabytes of stacks and a scheduler that switches more than it works.

The first workaround is the event loop: one thread, a set of non-blocking descriptors and epoll (module 13). Instead of “a thread waits” you have “a descriptor in the set”. This is how nginx, Node.js and Redis work. The limitation is obvious: one computation that runs long stalls the whole loop.

The second way is coroutines and async/await, that is, functions that can pause and resume later. The compiler turns such a function into a finite state machine whose state lives on the heap instead of a separate stack, so a switch costs as much as a function call, not a system call.

The third way is lightweight threads: goroutines in Go, virtual threads in Java, processes in Erlang. It is the library’s own scheduler multiplexing thousands of lightweight threads onto a few kernel threads, that is, the same M:N model. The difference is that it is now built inside a single runtime that controls both the code and all the blocking calls, so coordination has finally become possible.

Concurrency is not parallelism

Concurrency is a property of a program’s structure: several tasks in progress at once, interleaved. Parallelism is a property of execution: several computations physically at the same time on different cores. A single-threaded epoll server is concurrent but not parallel.

Confusing the two is costly, because concurrency doesn’t speed up computation, and parallelism doesn’t help with waiting.

How many threads

There are two answers to this question, and they depend on what the threads are busy with.

For compute-bound work the optimum is roughly the number of cores. More threads won’t add computing power, but they will add switches.

For work that waits on I/O the optimum is well above the number of cores, because most threads are blocked and don’t use the CPU. That said, threads aren’t the best tool for such work anyway: waiting is cheaper with a descriptor than with a thread that has a megabyte of stack.

How it actually works in Linux

ps -eLf | awk '$6 > 1' | head

Tasks with several threads. The LWP and NLWP columns hold the thread ID and the number of threads in the process.

ls /proc/$$/task

Each thread of the process is represented here by a directory. A single-threaded shell has one, and its name matches the PID.

cat /proc/self/status | grep -E 'Threads|SigBlk|Cpus_allowed_list'

The number of threads, the mask of blocked signals and the allowed cores: all of these are attributes of the thread, not of the process.

top -H -p $(pgrep -n -f . )

-H shows individual threads instead of a single summary line for the process. You can see exactly which thread is using the CPU.

grep -c ^processor /proc/cpuinfo; ulimit -s

The number of logical cores and the default thread stack size. The second number explains why ten thousand threads is a bad idea: multiply one by the other.

Common misconceptions

“Threads will make the program faster.” They will speed up only what can really be done in parallel, and only up to the number of cores. When the bottleneck is the disk or the network, extra threads give you nothing but contention.

“Each thread has its own copy of the variables.” Only its local variables are its own, because they live on the stack. Globals, statics and everything on the heap are shared. That is how two functions, each correct on its own, together produce a wrong result (module 9).

“A thread crashed, but the program keeps running.” It doesn’t: SIGSEGV in any thread terminates the whole process, so when you need fault isolation, you need processes.

“async/await makes code parallel.” It doesn’t: in most runtimes async code runs on a single thread and simply doesn’t block while waiting. That doesn’t make the computation parallel.

“Goroutines aren’t threads.” They are threads, just not kernel threads. The M:N model with its own scheduler is the same idea that was abandoned in the nineties and brought back where the runtime controls all the blocking calls.

Check yourself

1. One thread accesses an invalid address and gets SIGSEGV. What happens to the other threads of the process?

They keep running, the fault is isolatedThey terminate along with the whole processThey move to the "blocked" stateThey restart automatically

2. Which of these does each thread have its own copy of?

The heapThe open file tableThe stack and registersGlobal variables

3. Why does the N:1 model give no parallelism on a multi-core CPU?

The thread library is slowThe kernel sees only one thread and can put it on only one coreN:1 does not support more than one core in hardwareThreads in N:1 have no stacks of their own

4. A server handles 10,000 simultaneous connections. Why is a thread per connection a bad architecture?

The kernel does not support more than 1024 threadsThread stacks take gigabytes of memory, and the scheduler spends its time switching between threads that are mostly asleepThreads cannot work with socketsConnections cannot be distributed among threads

5. A single-threaded epoll server handles thousands of connections. Is it concurrent or parallel?

Both concurrent and parallelConcurrent, but not parallelParallel, but not concurrentNeither

6. How many threads make sense for a purely compute-bound task?

As many as possibleRoughly as many as there are coresTwice as many as there are connectionsOne, the rest just get in the way

Lab

A3: producer–consumer. First with a mutex and a condition variable, then lock-free on a ring buffer. The first part builds on module 9, the second shows what it costs to give up locks.

Sources

• OSTEP, Concurrency: An Introduction
• Silberschatz, Operating System Concepts, chapter 4
• man 7 pthreads, man 2 clone, man 3 pthread_create
• Why Threads Are A Bad Idea: Ousterhout, the classic argument for the event loop
• Concurrency is not parallelism: Rob Pike