Concurrency

The big picture: words you will need

Let us start with a few words, because everything else is built on them. A program is a recipe written down. A process is the recipe being cooked right now. Inside a process there can be one or many threads. A thread is one cook following one line of the recipe.

The scheduler is the surprise in this story. You do not decide when a thread runs. The scheduler can pause a thread in the middle of a sentence and give the turn to another one, then come back later. Because of that, the order in which the steps of two threads mix is not under your control, and it can change from one run to the next.

Concurrency against parallelism, processes and threads

These two words are often mixed up. Imagine one teacher grading homework from two classes. She grades a page of class A, then a page of class B, then A again. Both piles are in progress together, but she works on only one page at each moment. That is concurrency: several tasks in progress, with their steps mixed in time. Now imagine two teachers, each with one pile, grading at the very same instant. That is parallelism: several tasks really advancing at the same physical moment, which needs more than one worker, that is, more than one processor core.

On a single core the computer fakes simultaneity: it gives each thread a short time slice, again and again, so fast that everything looks simultaneous. This is sometimes called pseudoparallelism. For work that only computes, this does not save time: four threads on one core do the same total work as one thread, plus the cost of switching. Rob Pike's talk is the famous explanation: concurrency is structure, parallelism is execution.

What a thread owns and what it shares

Sharing memory makes threads easy to cooperate, because nothing must be copied. It also makes them dangerous, which is the subject of the next sections. Threads can be in three states. Running means it has a core right now. Ready means it could run but all cores are busy, so it waits for the scheduler. Blocked means it waits for an event (a file, a lock, a message) and would not run even with a free core. When the event happens, it becomes ready, not running.

          scheduler picks it
   ready ------------------------> running
     ^  <---- time slice ends ----    |
     |                                | waits for
     |        event happens           v an event
     +------------------------- blocked

When the scheduler stops one thread and starts another on the same core, that is a context switch: the system saves the registers, the program counter and the stack pointer of the one leaving and loads those of the one arriving. This work belongs to no task, so it is pure cost. Switching between two threads of the same process is cheaper than between two processes, because processes also change the address space, and that throws away cached memory translations.

Who creates the threads

• Kernel threads: made and scheduled by the operating system. They can use several cores, and a blocked one does not stop the others. Switching costs more.
• User-space threads: made by a library, invisible to the kernel. Cheap to create and switch, but the kernel sees one thread only. If one of them makes a blocking call, the whole process stops, and they cannot use several cores.
• Green threads and goroutines: made and scheduled by the language runtime, many of them over a few kernel threads (an M:N model). In Go, 100,000 goroutines that only sleep are fine on 8 cores: when one blocks on something the runtime knows (sleep, channel, mutex), only that goroutine is parked and the kernel thread goes on working.

Thread t = new Thread(() -> System.out.println("A"));
t.start();   // asks the JVM for a NEW thread, which runs the task
// t.run();  // just a normal method call: still ONE thread!
t.join();    // wait here until t has finished
System.out.println("B");   // always after A

After start(), the order between the new thread and the thread that created it is up to the scheduler and cannot be predicted. join() makes a meeting point: everything after t.join() happens after everything t did.

Race conditions and critical sections

Two children share one piggy bank. It has 5 coins. Both look inside and see 5. Each decides to add one coin, so each thinks 'now it has 6' and writes 6 on the label. The piggy bank really holds 7 coins, but the label says 6. One addition was lost, and nobody did anything wrong. This is a race condition: the answer depends on the uncontrolled order in which threads do their steps on shared data.

The program line counter++ looks like one step, but it is three: read the value, add 1, write the result. Look at what can happen when two threads run those three steps.

thread A            thread B            counter
read 5                                  5
                    read 5              5
add 1 (6)
                    add 1 (6)
write 6                                 6
                    write 6             6   <- two increments,
                                           only one counted

This kind of bug is called a lost update. Nothing crashes and no error is shown: the data is simply wrong, and it is different on every run. In this repository's counter-race mini-project, 8 workers make 1,000,000 increments in total and the broken counter usually ends somewhere between 150,000 and 700,000 instead of 1,000,000. The problem is the same in every language, because the three steps are the same in the machine.

How many results are possible?

To know what a concurrent piece of code can produce, list the ways its steps can mix (the interleavings). For two threads that start with counter = 0 and each do one counter++, there are only two outcomes. If the read of one thread comes after the write of the other, the result is 2. If both reads happen before any write, the result is 1. It can never be 0, and it can never be more than 2.

The critical section

The stretch of code that touches the shared thing is the critical section (or critical region). The cure is mutual exclusion: while one thread is inside, the others wait outside. Keep the critical section small, so nobody waits long. A good solution to the critical-section problem must satisfy four conditions:

1. Never two threads inside at once (mutual exclusion).
2. It must not assume anything about the speed of the threads or the number of cores.
3. A thread that is outside the critical section must not block another thread.
4. No thread waits forever.

A simple idea that breaks the third condition is strict alternation: a variable turn says whose turn it is, and each thread enters only on its turn. A fast thread is stuck behind a slow one that is not even interested in the critical section, because the slow thread has not used its turn yet.

Two traps

• Check-then-act: you test a condition (if the key is missing) and then act (put the key), but another thread changes things between the test and the action. Even if each call to a thread-safe map is safe by itself, the whole sequence is not. The critical section is the whole sequence, so it needs one atomic operation or one lock around both calls.
• Data race against race condition: a data race is a low-level fault. A race condition is a bigger idea: the result depends on the order. You can have a race condition with no data race. Two threads that do setBalance(getBalance() - 100), with both methods synchronised, never touch memory together, yet they still lose an update because the read and the write are separate critical sections.

Mutexes and locks

Think of the key to a small bathroom at a cafe. Only one person can have the key, and whoever has it is the only one inside. The others wait. When the person comes out, the key goes back on the hook and the next person takes it. A mutex (short for mutual exclusion) is that key. It has two states, locked and unlocked. A thread calls lock before the critical section and unlock when it leaves. If the mutex is already locked, the thread waits.

mu.Lock()
defer mu.Unlock()   // runs when the function ends, however it ends
counter++

The most important rule: every lock must be released on every way out, including errors, or everybody else waits forever. Each language helps in its own way.

A lock is reentrant when the thread that already holds it can take it again without blocking itself. It remembers the owner and how many times it was taken, and it is free only when the releases equal the acquisitions. Java locks are reentrant. That is why a synchronized method can call another synchronized method of the same object without freezing.

Waiting by spinning or by sleeping

How should a thread wait for a lock? One way is busy waiting (spinning): it keeps asking 'is it free yet?' in a loop, like a child on a car trip asking 'are we there yet?' every ten seconds. It burns processor time. The other way is to block: the thread goes to sleep and the system wakes it when the lock is free. Sleeping and waking costs time too. So spinning is a good choice only when the wait is shorter than that cost: a very short critical section whose owner is running on another core. A lock that spins with a hardware instruction is a spinlock. Many real mutexes spin for a moment and then sleep.

How big should a lock be?

The granularity of a lock is how much data it protects. One big lock is simple but makes everyone wait for everyone. Many small locks let threads that touch different data work together. The limit is the invariant, a fact that must always be true. If an inventory keeps stock + reserved = total, then both numbers must change inside one critical section, or another thread will see the sum broken in the middle. Splitting into two locks and updating them one after the other breaks that. The fix is to hold both locks at once, always taking them in the same order (the next sections explain why).

Priority inversion

Suppose thread L (low priority) holds a mutex, thread H (high priority) asks for it and blocks, and thread M (medium) becomes ready and does not even use the mutex. M runs before L, so L cannot finish and release the lock, and H is stuck behind M. A high-priority thread now depends on a medium one. The cure is priority inheritance: while L holds a lock that H wants, L temporarily runs with H's priority.

Semaphores and monitors

Picture a library with 3 study rooms. At the door there is a jar with 3 tokens. To go in you take a token. When the jar is empty you wait. When someone leaves, they put the token back. That jar is a semaphore: a counter with two operations that cannot be interrupted. down (also called P) takes one unit, and if the counter is zero it puts the thread to sleep. up (also called V) gives one unit back and wakes a sleeping thread. Because the test and the change of the counter are one indivisible action, no wake-up is lost.

A semaphore is not the same as a mutex. A mutex has an owner: only the thread that locked it may unlock it. A semaphore remembers no owner, so one thread can do down and another can do up. That makes a semaphore good for sending a signal. In Java, thread A blocks on acquire() of a semaphore with 0 permits, and thread B later calls release() to let A continue. A ReentrantLock would refuse that, since B does not own it.

The lost wake-up

Why do we need these tools instead of an if and a sleep? Imagine a consumer checks 'the box is empty' and, before it can go to sleep, the producer puts an item in the box and shouts 'wake up!'. Nobody is asleep yet, so the shout is lost. The consumer then sleeps and may never wake. The test and the going to sleep must be one atomic action. A semaphore solves it by keeping the signal inside its counter, and a monitor solves it by doing the test and the wait under the same lock.

Monitors

A monitor bundles the lock and the waiting together, so the programmer makes fewer mistakes. In Java every object is a monitor with a lock and a wait set (a waiting room). Inside synchronized code:

• wait() releases the lock and puts the thread to sleep in the waiting room. Only the lock holder may call it.
• notify() wakes one waiting thread, chosen arbitrarily. notifyAll() wakes all of them. A woken thread must win the lock again before it goes on.

synchronized String take() throws InterruptedException {
    while (items.isEmpty()) {   // WHILE, never IF
        wait();
    }
    return items.removeFirst();
}

Why while and not if? Java monitors follow Mesa semantics: being notified only makes a thread ready, it does not hand it the lock at once. By the time it gets the lock back, another thread may have taken the item. The rules also allow a spurious wake-up, a wake-up with no notification at all. So the thread must check the condition again after every wake-up. With if, two consumers woken by one put() would both try to remove the same item, and one of them would fail.

One more trap: an object monitor has a single waiting room, even if threads wait for different things (buffer not full, buffer not empty). With a one-slot buffer, two producers and two consumers, a notify() may wake a thread of the wrong kind. It sees that its condition is false and goes back to sleep, and the signal is lost, so everybody can end up asleep. The ways out are notifyAll(), or a Lock with one Condition object for each condition.

Atomic operations, visibility and memory models

A locker with a lock is slow if you must queue just to add one to a number. Can the machine do 'read, add, write' as one single move? Yes. An atomic operation is one that other threads see as either not started or already finished, never half done. The processor offers special instructions for this, such as TSL (test and set lock) and XCHG (exchange). They read a memory word and write to it with no other core able to act in between. They are the foundation of mutexes and semaphores.

Compare-and-swap

The most powerful atomic building block is compare-and-swap (CAS): 'if the value is still the one I expected, replace it with the new one, and tell me whether you did'. A lock-free increment is a loop: read 41, compute 42, try compareAndSet(41, 42). If it returns false, somebody else changed the value in between, so you start again from a fresh read. No update is lost, because a write based on an old value is always refused.

int old, next;
do {
    old = value.get();          // read
    next = old + 1;             // compute
} while (!value.compareAndSet(old, next)); // retry if it changed

CAS has a famous trap, the ABA problem. A lock-free stack pops by checking that the top is still A. Thread T1 reads top = A, A.next = B and is paused. Meanwhile T2 pops A, pops B and pushes A back. When T1 wakes up, the top is A again, so its CAS succeeds, but B was already removed, and the stack now points to a dead node. The value looked unchanged, yet the world changed. The usual defences are a version counter glued to the value, or never reusing a node while some thread still refers to it.

Visibility: seeing what others wrote

There is a second problem, quieter than lost updates. Each core has its own small fast memory (a cache), and the compiler and the processor may reorder or postpone writes. So a thread may not see a value that another thread already wrote. This is a visibility problem. Picture a worker thread that runs while (!stopped) { work(); } where stopped is a plain boolean. Another thread sets stopped = true. The worker is allowed to keep reading its old copy forever, and never stop.

A memory model is the set of rules that says when a write by one thread is guaranteed to be seen by another. In Java it is built on the happens-before relation. These things create it: releasing and later taking the same lock, writing and later reading a volatile field, starting a thread, and waiting for it with join(). Without such a link, the program has no guarantee. Go has its own memory model with the same spirit.

• volatile in Java gives visibility: every read sees the latest write. It does not make count++ atomic, because that is still read, add, write. Two threads doing count++ 1,000 times on a volatile int can end below 2,000.
• In Rust, the Ordering does not change whether the operation is atomic. It says what order guarantees the operation gives to other reads and writes, from Relaxed (nothing beyond the operation itself) to SeqCst (one single global order). A counter that is read only after joining all threads can use Relaxed, because join already gives visibility.

Deadlock, livelock and starvation

Two cars arrive at a narrow bridge from opposite sides. Neither can go forward, and neither wants to go back. They wait forever. A deadlock is exactly that: a group of threads, each waiting for something that another thread in the group holds, so none of them can ever move. The program is alive, uses no processor and does nothing, and it raises no error.

The four conditions

A deadlock on resources needs four conditions at the same time (they are called the Coffman conditions). Remove any one and the deadlock is impossible.

Seeing a deadlock

A resource-allocation graph draws threads and resources as dots. An arrow from a resource to a thread means 'held by'. An arrow from a thread to a resource means 'wants'. When each resource has a single unit, a cycle in the graph means deadlock.

   wants          held by
P1 ------> R2 ---------> P2
 ^                        |
 |        held by         | wants
 +-------- R1 <-----------+

A Java thread dump shows the same thing in text. For every thread it lists the locks it holds (locked) and the one it waits for (waiting to lock). Follow the chain: philosopher-0 holds 0a and waits for 0b, philosopher-1 holds 0b and waits for 0c, philosopher-2 holds 0c and waits for 0a. The chain returns to the first thread, so there is a circular wait, and the three threads in the cycle will never move again.

Four strategies

• Ignore it (the ostrich algorithm): pretend deadlocks do not happen. It is a real engineering choice when they are rare and fixing them is expensive.
• Detect and recover: let requests be granted, check now and then for a cycle, and then recover by taking a resource away, rolling back, or killing a process. Databases do this with transactions.
• Avoid: know the maximum each process may ask for, and grant a request only if the resulting state is still safe. This is the banker's algorithm.
• Prevent: make one of the four conditions structurally impossible, as in the table above.

A state is safe when there is some order in which every process can finish, even if each asks for its maximum. Example with 12 units of one resource. P1 holds 4 and may need up to 10, P2 holds 3 and may need up to 5, P3 holds 2 and may need up to 8. Units held: 9, so 3 are free. The remaining needs are 6, 2 and 6. P2 can finish with its 2 units, giving back 3, and then 6 are free. P1 finishes, then P3. The state is safe. Now P1 asks for 2 more: 1 unit would remain, the needs would be 4, 2 and 6, and nobody could be sure to finish. The banker refuses the request for now.

Lock ordering

The prevention most used in real code attacks circular wait. Give every lock a position and always take them in that order. For a bank transfer, lock the account with the smaller id first, whatever the order of the arguments. Two transfers between the same two accounts then lock in the same order and cannot form a circle. The order must come from a fixed property (like an id), not from the position in a call. And it must be respected by all code: a single path that breaks it, often hidden in a callback called while holding a lock, can make a cycle possible again. That is one more reason not to call outside code while holding a lock.

Livelock and starvation

Two people meet in a corridor. Both step to the left, then both step to the right, then to the left again. Nobody is stuck, both are busy, and nobody passes. That is a livelock: threads keep running but make no progress, because each reacts to the other in a way that undoes its own step. It often comes from a deadlock cure: take the first lock, try the second with tryLock(), and if it fails, release the first and start over immediately. Two symmetric threads can repeat this in step forever. A random wait before retrying (random backoff) makes it unlikely, and a global lock order makes backing off unnecessary.

Starvation is when a thread never gets the resource or the processor it needs, even though the resource is released again and again, because the selection policy always prefers others. Unlike a deadlock, the system as a whole keeps working. The cure is a fair policy: first come, first served, or raising the priority of whoever has waited long.

Classic problems: producer-consumer, readers-writers, dining philosophers

Some puzzles appear so often that every computer scientist learns them. Once you know the three below, you will recognise them hidden inside real programs.

Producer-consumer

A pizza shop: the cook (producer) puts pizzas on a shelf with room for N pizzas, and the delivery person (consumer) takes them. If the shelf is full, the cook must wait. If it is empty, the delivery person must wait. The shelf of fixed size is a bounded buffer, and the bound makes the faster side wait for the slower one.

The classic solution uses three semaphores. empty counts free slots, full counts items, and mutex guards the shelf itself. For a buffer of 8 slots that starts empty:

# producer                 # consumer
down(empty)                 down(full)
down(mutex)                 down(mutex)
put item in buffer          take item from buffer
up(mutex)                   up(mutex)
up(full)                    up(empty)

In Java you do not need to build it: ArrayBlockingQueue is a ready bounded buffer. put() blocks while it is full and take() blocks while it is empty, and all the synchronisation is inside the class. It is the recommended way.

Readers-writers

A shared notice board: many students may read it together, but when the teacher writes on it, nobody else may read or write. Several readers at once are fine; a writer needs the board alone. With reader preference, a new reader may join whenever other readers are already reading, even if a writer is waiting. If readers keep arriving before the last one leaves, the writer waits forever: it is starved. Versions that make new readers queue behind a waiting writer fix this, at the price of less sharing among readers.

Dining philosophers

Five philosophers sit at a round table with five forks, one between each pair. To eat, each needs the two forks beside him. A fork is a lock.

            P0
       f0        f1
    P4              P1
       f4        f2
         P3  f3  P2

The naive rule is 'take the left fork, then the right'. If all five take the left fork at the same moment, each holds one fork and waits for the neighbour's: P0 waits for P1, P1 for P2, and so on until P4 waits for P0. A circle of waiting, so a deadlock. All four conditions are present. There are two famous fixes:

The waiter's semaphore does not protect a critical section. It limits how many threads are in a region at once. Its start value carries the whole guarantee: with 5 permits it restricts nothing and the deadlock returns, and with 1 permit the deadlock is gone but so is all the parallelism.

Message passing and channels

Instead of sharing a fridge and fighting over the eggs, give each cook their own station and let them pass plates to each other. Nobody touches the same thing, so nobody needs a lock. This is message passing. Go's motto says it well: 'do not communicate by sharing memory; share memory by communicating'. The tasks do not access the same variable. They send and receive values, and the synchronisation is part of the communication.

In Go the way to send is a channel: a pipe between goroutines. The convention is that whoever receives a value becomes the only one using it. Channels come in two flavours.

With an unbuffered channel, sender and receiver must meet: whoever arrives first waits for the other. This meeting is called a rendezvous and it also synchronises the two goroutines. With a buffered channel of capacity 3, three sends go through with no receiver, because the values wait in the internal queue. The fourth send blocks until a receive frees a slot.

chan of capacity 3, nobody receiving:

send 1  -> [1][ ][ ]   ok
send 2  -> [1][2][ ]   ok
send 3  -> [1][2][3]   ok
send 4  -> [1][2][3]   BLOCKS until a receive

ch := make(chan int)   // unbuffered
ch <- 1                // blocks: nobody is receiving yet
go func() { <-ch }()   // never reached!

That example shows a rule: on an unbuffered channel the receiver must exist before the send can finish. When every goroutine of the program is blocked, the Go runtime notices and ends the program with an error.

Closing a channel

close(ch) says 'no more values will come', and it is the sender's job. Values already in the channel are still delivered. A for v := range ch loop ends when the channel is closed and empty. Without close, the loop would wait forever for one more value.

One owner, no lock

Here is a way to fix the counter race with no lock. One goroutine owns the variable count. Eight workers send the value 1 on a channel 1,000 times each, and the owner adds what it receives. Updates are applied one at a time, in the order they arrive. The variable is never read and written at the same moment, so the answer is always exactly 8,000. The channel plays the role of a request queue.

Rust: sending moves ownership

In Rust, tx.send(data) moves the value to the receiver. The sending thread loses access to it, and if the next line tries data.push(1), the compiler refuses to build the program. So two threads never change the same sent data, and there is no data race, with no copy and no lock.

Actor model and the BEAM

Imagine a company where every employee has their own desk, their own notebook and a mailbox. Nobody reads another person's notebook. If you want something, you drop a letter in their mailbox, and they read their letters one at a time. That is the actor model. An actor keeps a state of its own, talks only by asynchronous messages, and handles the messages of its mailbox one at a time. Since no other actor can see its state, there is no shared memory to protect with locks.

The best known home of actors is the BEAM, the virtual machine of Erlang and Elixir. A BEAM process is not an operating-system process. It is created and scheduled by the BEAM itself, has its own stack, heap and garbage collector, starts with very little memory and shares no data with the others. A system can keep hundreds of thousands of them, for example one per open connection.

Because an Agent runs read, computation and write inside a single process, an increment cannot be interleaved with another. Eight tasks that each call Agent.update(counter, &(&1 + 1)) 1,000 times always end with exactly 8,000.

call and cast

• GenServer.call: the caller waits for the reply. This naturally slows down whoever is asking.
• GenServer.cast: the message is only put in the mailbox, and the sender never learns when, or whether, it was handled.

An actor handles one message at a time, so its top speed is 1 divided by the handling time. If a GenServer needs 1 ms per message, it manages at most 1,000 messages per second. If a thousand producers send 5,000 per second with cast, the extra 4,000 each second pile up in the mailbox. Nobody slows the producers down (no backpressure), so memory grows and answers get later and later. The ways out: use call so producers wait, spread the work over several processes, or drop some load.

Fair scheduling and let it crash

What if a process runs an endless calculation with no receive? The BEAM does preemptive scheduling without clock interrupts: it counts the work of each process in reductions (small units of work). When a process spends its budget, it goes to the back of the queue and another takes the scheduler. A process that only computes cannot hog a core, and the others stay quick.

Since processes share nothing, a failing process dies alone. Links and monitors tell the interested processes, and a supervisor restarts the child by its strategy. With one_for_one, only the dead child is restarted. The philosophy is called let it crash: separate the code that does the work from the code that handles failures, and return to a trusted starting state instead of trying to repair a broken one.

The measurement holds 10,000 idle connections, each waiting 30 seconds. All three models pass easily, with a median latency below one millisecond, because none of them spends an operating-system thread on a waiting connection. The numbers say nothing about heavy computation inside a handler, and they depend on what a real handler keeps alive.

Async, promises and the event loop

A waiter in a restaurant does not stand next to your table waiting for the soup to cook. He takes your order, goes to serve other tables, and comes back when the kitchen rings the bell. One waiter can look after many tables because most of the time is spent waiting. A Node.js or Bun server works like this. It uses one thread and I/O calls that do not block. The event loop asks the operating system which operations are ready and runs the callback of each, one at a time. An idle connection holds no thread, so thousands of them cost little memory.

Promises and async/await

A promise stands for a result that will exist in the future, like a receipt for a cake that is still in the oven. It starts pending and settles only once: either fulfilled with a value or rejected with an error. After that its state never changes. Functions declared async always return a promise, and await pauses only that function until the promise settles, leaving the thread free for other events. The code looks sequential, but it is the same chain you would write with then.

async function sequential() {
	await sleep(300);
	await sleep(200);
	await sleep(100);          // total about 600 ms
}
async function together() {
	await Promise.all([sleep(300), sleep(200), sleep(100)]); // about 300 ms
}

With one await per line, each wait starts only after the previous ended, so the times add up. When you create all the promises first and wait with Promise.all, the waits overlap, and the total is the time of the slowest.

The two queues

The loop has two kinds of line. Macrotasks are timers and I/O callbacks. Microtasks are promise continuations (the then and the part after an await). After each piece of synchronous code the loop empties the whole microtask queue, and only then takes the next macrotask. So an already-resolved promise always goes ahead of a setTimeout(..., 0).

console.log("A");
setTimeout(() => console.log("B"), 0);        // macrotask
Promise.resolve().then(() => console.log("C")); // microtask
(async () => { console.log("D"); await null; console.log("E"); })();
console.log("F");
// prints: A D F C E B

The big limit: one slow callback blocks everyone

Each callback runs to the end before the next event is handled. Waiting for I/O does not hold the thread, but a synchronous computation does. If a handler computes for 2 seconds, and three requests arrive at the same instant, they are served one after the other: about 2, 4 and 6 seconds. In general, n handlers of t seconds of processor work take n times t. The event loop gives concurrency for I/O, not parallelism for computation. For work that keeps the processor busy, send it to another thread, such as a worker thread, which talks to the main thread by messages.

One thread can still have a race

Between two awaits the code runs without interruption, but at each `await` other tasks may run. Look: const current = balance; await audit(); balance = current - amount;. If withdraw(80) is called twice with a balance of 100, both read 100, both wait, both write 20. The final balance is 20, not -60. It is a check-then-act race with no parallel threads at all. The fix is to leave no await between the read and the write, or to put the operations in a queue so they run one at a time.

The same idea in a window: Swing

A Java Swing program uses the same model. A single thread, the event dispatch thread (EDT), takes events from a queue and runs the handlers one after another. Every read or change of a window component must happen on it, so the components need no locks. If a button's handler downloads a file for 10 seconds, the window freezes for 10 seconds: it does not repaint or answer clicks. Long work goes to a background thread. SwingWorker does it: doInBackground runs off the EDT and done runs back on it, where updating components is safe.

Thread pools and backpressure

A restaurant does not hire a new cook for each plate and fire him after the plate. It keeps a fixed team in the kitchen and a line of orders. A thread pool does the same: a limited number of threads take tasks from a queue and are reused. Creating a thread costs time and memory, and too many threads fight for the processor and use up resources. In a pool the creation cost is paid once, and the concurrency has a known ceiling.

In Java, Executors.newFixedThreadPool(4) makes a pool with exactly 4 threads and a task queue with no size limit. Submit ten long tasks: 4 run, 6 wait in the queue in arrival order. submit does not block, it queues the task and returns a Future (a ticket for the result).

How long will it take?

A thread blocked on I/O does nothing, but it is still occupied. With n tasks that each wait t seconds, on a pool of k threads, the total time is about ceil(n / k) times t. Twelve tasks that each sleep 1 second on 4 threads need 3 seconds.

Shutting a pool down

An ExecutorService keeps its threads alive, so you must stop it. shutdown is the polite way: nothing new is accepted, and what was already submitted is completed. shutdownNow is the immediate way: it sends interrupt to the active threads and returns the tasks that never started. Interruption is cooperative, so a task that ignores it keeps running.

Backpressure

Now the big danger. A pool of 10 threads can finish 100 tasks per second. For a long time, producers send 150 per second. With an unbounded queue, nothing stops them. The 50 extra tasks each second pile up in the queue and eat memory, and the wait of every new task grows without limit. Eventually the program runs out of memory. An unbounded queue hides the overload.

Backpressure means making the signal 'I am full' reach the producer. A water pipe is a good picture: if the sink is full, the tap must slow down. There are two ways. A bounded queue that blocks the producer when it is full (like the blocking buffer of the producer-consumer puzzle). Or load shedding: reject the extra work on purpose, so that you keep answering well for what you accept.

producers (150/s)    queue            workers (100/s)
   ===========>  [bounded: 100] ===========>  10 threads
                      |
               full? -> block the producer
                        or reject the task

A pool can deadlock itself

Two outer tasks are submitted to a pool of 2 threads. Each outer task submits an inner task to the same pool and calls get() on its Future to wait for it. Both outer tasks hold a thread and wait. The inner tasks sit in the queue and no thread is free to run them. A circular wait between the threads and the queue: a pool-exhaustion deadlock. The cures: do not block inside tasks (compose the results asynchronously), or use separate pools for outer and inner tasks.

Putting it all together

You have met many tools. How do they fit? Start from the problem. Concurrent tasks share something, or they wait for something. If they share data, you either protect it or stop sharing it.

Common mistakes

• Believing that counter++ is one step. It is read, add, write.
• Believing that volatile makes count++ safe. It gives visibility only.
• Believing that a thread-safe collection makes a sequence of calls safe (check-then-act).
• Calling run() instead of start().
• Using if instead of while around wait().
• Taking mutex before the counting semaphore in producer-consumer.
• Locking in different orders in different places.
• Calling unknown code (a callback) while holding a lock.
• Unbounded queues, which hide overload until memory runs out.
• Running heavy computation on the event loop.
• Trusting a test that passed many times, or a race detector that printed nothing.

A short recipe

1. Can you avoid sharing? Give the data one owner and send messages.
2. If you must share, find the whole critical section: all the steps that must happen as one.
3. Protect it with the simplest tool: a lock, or one atomic if it is one variable.
4. If you take several locks, define one global order.
5. Limit the queues and the number of threads, so overload shows up early.
6. Use a race detector and think about timing, because tests alone cannot prove a concurrent program correct.

The mini-projects of this repository let you see all of this running: the counter race (the lost update and its four fixes), the dining philosophers (deadlock and two cures) and the ten thousand connections (event loop, goroutines and BEAM processes). For more, the free book The Little Book of Semaphores and the game The Deadlock Empire are great ways to practise.