Thread Pools and Deadlock

By the end of this lesson you will be able to

• Explain what a thread pool is, why servers use one, and what it costs, with the 10,000-tasks-on-20-workers arithmetic.
• Size a pool for CPU-bound and I/O-bound work, and spot when the real limit is a database rather than the CPU.
• Choose a bounded queue and a rejection policy, and predict the order in which a Java ThreadPoolExecutor grows.
• Recognise pool exhaustion from its symptoms, and limit the damage with timeouts and bulkheads.
• Explain how a pool can deadlock on itself with no lock anywhere, and fix it.
• State the four Coffman conditions, draw a cycle of any length, and tell a deadlock from a long wait chain.
• Prevent deadlocks with lock ordering and the other techniques, and say which are prevention and which are recovery.
• Detect deadlocks with a wait-for graph, thread dumps and pg_locks, and write correct retry logic for database deadlock victims.
• Tell deadlock, starvation, livelock and priority inversion apart from what you see on a dashboard.

#Where this lesson fits

Lesson 1.2 introduced the thread-per-connection server and named thread-pool exhaustion. Lesson 1.13 showed the same pattern in PHP-FPM, Gunicorn and Tomcat, and the 504s you get when workers run out. Lesson 2.5 showed how long-lived connections can pin a thread each.

In this chapter, lesson 3.1 explained what a thread is and what it costs to create, and lesson 3.2 explained scheduling and why too many threads waste CPU. This lesson answers the question they leave open: how do you run lots of work on a limited number of threads, and what goes wrong when threads wait for each other?

The event-loop alternative is in lesson 3.6. Locks in real code (mutexes, semaphores, races, CAS) are Chapter 14; here we look at waiting and deadlock as system behaviour.

#What a thread pool is

A thread pool is a set of worker threads created in advance that take tasks from a queue and run them. Producers put tasks in; workers pull them out, run them and come back for the next one.

          Incoming tasks
                 |
                 v
             Task queue
            /    |    \
           v     v     v
       Worker  Worker  Worker
       thread  thread  thread

Say an application receives 10,000 tasks. Instead of creating a new thread for each, you let 20 worker threads process them. If a task takes 50 ms:

• 20 workers finish 20 ÷ 0.05 s = 400 tasks per second.
• All 10,000 are done after 10,000 ÷ 400 = 25 seconds.
• There are never more than 20 threads, so creation cost and context switching stay under control.

The cost is that the last task waited about 25 seconds for 50 ms of work. A pool turns too much concurrency into queueing delay. That is usually the right trade, because a queue fails gradually and visibly, while 10,000 threads can bring the whole machine down.

#Benefits and problems

#Using one

Here is the simplest Java version:

ExecutorService executor = Executors.newFixedThreadPool(5);

executor.submit(() -> {
    System.out.println("Task running");
});

executor.shutdown();   // finish queued tasks, accept no new ones

It is fine for a demo, but its queue has no limit, which is a real hazard (see below). In production, spell the settings out:

ThreadPoolExecutor pool = new ThreadPoolExecutor(
    20, 20,                                  // core and maximum threads
    0L, TimeUnit.MILLISECONDS,               // keep-alive for extra threads
    new ArrayBlockingQueue<>(200),           // bounded queue
    new ThreadPoolExecutor.AbortPolicy());   // reject when full

A thread pool is the producer-consumer pattern with tasks as the data: request handlers produce, workers consume, and the queue separates their speeds. The difference is emphasis. Producer-consumer describes a data pipeline; a thread pool is about running tasks on a managed set of threads.

#Where you already meet pools

The last row matters. Everything in this lesson applies to any pool of scarce things: connections, processes, or memory buffers.

#How many threads?

There is no universal number, but there is a good way to reason. A thread that waits for I/O gives up its core, so the answer depends on how much of each task is waiting.

CPU-bound work (image resizing, compression, hashing) never waits, so one thread can fill one core:

threads ≈ cores

I/O-bound work (a web request that mostly waits on a database) leaves the core free while it waits, so more threads can share it:

threads ≈ cores × (1 + wait time ÷ compute time)

The version in Java Concurrency in Practice adds a target utilisation U between 0 and 1: cores × U × (1 + wait ÷ compute).

A worked example: 4 cores, and each request computes for 10 ms and waits 90 ms.

The formula is a starting point, and it looks only at the CPU. Check four more things:

1. The narrowest downstream resource. With 40 threads and 10 database connections held for 90 ms, the ceiling is 10 ÷ 0.09 s ≈ 111 requests per second. The other threads queue for a connection, which adds memory use and hides the real limit.
2. Little's law as a cross-check. Threads in use = arrival rate × time per request. 500 requests per second at 0.1 s needs 50 threads. If each request takes 2 s, it needs 1,000. Lesson 1.2 used this, and Chapter 17 treats it in full.
3. What "cores" really means. In a container with a CPU limit, count the limit, not the host's cores (lesson 3.2 covers throttling). Hyper-threads are not full cores either. Several pools in one process share those same cores, so the pools' numbers must add up.
4. The measured result. Run a load test and raise the size until throughput stops rising or latency jumps. That is your number, whatever the formula said.

For database connection pools, the PostgreSQL community's starting point, quoted in the HikariCP documentation, is connections ≈ (cores × 2) + effective disk count, counted on the database server. It is often surprisingly small. A database with too many active connections spends its time on lock and scheduling contention, and gets slower for everyone.

#Separate pools for different work

Put slow and fast tasks, or CPU-bound and I/O-bound tasks, in separate pools. In a shared pool, a few long tasks take all the workers and short tasks wait behind them. A CPU pool sized at the core count and an I/O pool sized by the formula can then be tuned and monitored separately.

#Queues: bounded, and what to do when full

The queue is where a pool decides how it behaves under overload. An unbounded queue never says no, so overload shows up as memory growth and huge latency, and then as a crash that loses everything queued. A bounded queue turns overload into an explicit decision.

How long should it be? Decide how long a task may usefully wait:

queue length ≈ throughput × acceptable wait

At 400 tasks per second, with clients that give up after about a second and a half second you can afford to spend waiting, that is 400 × 0.5 = 200. Anything queued beyond that would be finished after nobody cares. It is better to refuse it now.

Java's ThreadPoolExecutor grows in an order that surprises most people:

1. Fewer than core threads running: start a new thread.
2. Otherwise: put the task in the queue.
3. Queue full: start extra threads, up to maximum.
4. At maximum too: reject the task.

So extra threads start only after the queue is full. With a large or unbounded queue, the maximum never takes effect. Executors.newFixedThreadPool uses an unbounded queue, and Executors.newCachedThreadPool does the opposite: no queue capacity and no practical thread limit, so a burst can create thousands of threads. Tomcat's request pool is an exception: it adds threads before queueing, using its own executor.

Three more rules from production:

• Drop tasks that are already too old. A worker that picks up a request whose client timed out 10 seconds ago should skip it. Carry a deadline with the task and check it first.
• An in-memory queue dies with the process. If tasks must survive a crash or deploy (emails, payments), the queue belongs in a durable system. Chapters 30 to 32 cover that.
• Rejecting is a feature. Fast failure for a few protects the rest. Chapter 29 and Chapter 28 build rate limiting and load shedding on the same idea.

#Pool exhaustion: the classic incident

Thread-pool exhaustion is one of the most common production failures. It looks strange because nothing appears broken: there is no crash, CPU is low, and yet everything is slow.

The sequence is always much the same. One dependency slows down. Threads calling it stop returning. The number of threads held grows at arrival rate × hold time, so a 30 s timeout at 50 requests per second can hold up to 1,500 threads, far more than a pool of 200. The pool fills in seconds, and now every endpoint queues, including ones that never touch the slow dependency. Then retries add load and health checks fail, so the load balancer removes instances and pushes their traffic onto the rest.

How to recognise it, and what each symptom rules out:

Monitor these for every pool: active threads, queue length, task wait time (separate from run time) and rejection count. Wait time is the early warning. It rises before users complain.

The fixes, in the order to apply them:

1. A timeout on every outbound call. It sets the hold time. Without it, one dependency can hold a thread forever. Chapter 28 covers how to choose values.
2. A bounded queue and fast rejection, as above.
3. Bulkheads. Give risky dependencies their own small pool or a concurrency limit, so a failure stays in its compartment. Chapter 28 covers bulkheads and circuit breakers.
4. Match pools along the path. 200 request threads over 20 database connections means 180 threads may queue on the connection pool. That can be fine for short bursts, but set a short connection-acquire timeout so it fails instead of hanging.
5. Consider a different concurrency model for work that mostly waits: an event loop or virtual threads (lesson 3.6).

#A pool that waits for itself

A pool can deadlock with no lock in sight. A task running in a pool submits a child task to the same pool and blocks until the child finishes. With light load there is a free worker for the child. Under load, every worker holds a parent that is waiting for a child, and the children sit in the queue waiting for a worker that will never be free.

This passes tests, because tests rarely fill the pool. In production it freezes the service with zero CPU. The fixes:

• Do not block inside a pool task on another task from that pool. Chain the next step instead (thenCompose on a CompletableFuture).
• Use a separate pool per level of dependency, so the dependency runs one way and cannot form a cycle.
• Use a work-stealing pool such as ForkJoinPool for recursive work, where a waiting worker can run other queued tasks.
• Always add a timeout to get() and similar calls, so a freeze becomes an error you can see.

The same bug exists with connection pools: each request holds one connection and asks for a second, for instance through a nested transaction in a separate connection. The HikariCP documentation gives the minimum safe size: pool size = threads × (connections per task − 1) + 1. With 10 threads that need 2 connections each, that is 11. A pool of 10 can freeze until its timeout fires.

#Other everyday pool traps

• Exceptions disappear. With submit, an exception is kept in the returned future. If nobody reads the future, nobody ever sees the error. Log inside the task or check the future.
• Thread-local data leaks between tasks. Threads are reused, so a user id or security context left in a thread-local variable by one task is visible to the next, which can become a security bug. Always clear it in finally.
• Shutdown needs care. Call shutdown(), wait with awaitTermination for a limited time, then shutdownNow() if you must. Do this when you get SIGTERM (lesson 3.1), or the tasks in the queue are lost on every deploy.
• Name your threads. A thread dump full of pool-3-thread-17 tells you little; payment-client-17 tells you where to look.
• Do not pool virtual threads. They are cheap by design, so limit concurrency with a semaphore instead (lesson 3.6).

#Deadlock

A deadlock is a state in which two or more threads or processes each wait for a resource that another of them holds, so none of them can ever continue. The note's short version mentions processes, but it applies to anything that can hold and wait: threads, processes, database transactions, or services calling each other.

Take two threads and two locks:

Thread A:                Thread B:
  acquire Lock 1           acquire Lock 2
  wait for Lock 2          wait for Lock 1

Now:

Thread A holds Lock 1, waits for Lock 2
Thread B holds Lock 2, waits for Lock 1

Neither will release, so both wait forever. This is what makes deadlock so awkward: it depends on timing. The same code usually runs fine, and it freezes only when both threads get their first lock before either asks for its second.

#The four Coffman conditions

In 1971 Coffman, Elphick and Shoshani described four conditions that must all hold at once for a deadlock to exist. They are necessary conditions: remove any one and deadlock is impossible.

Mutual exclusion is rarely removable, because if a thing could be shared you would not have locked it. In practice you attack the other three, and most of all circular wait.

The note's three-thread sketch mixes up holding and waiting, so here it is redrawn clearly:

Thread A holds R1, waits for R2 (held by B)
Thread B holds R2, waits for R3 (held by C)
Thread C holds R3, waits for R1 (held by A)

A → B → C → A    the cycle

Two details interviewers like:

• A long wait chain is not a deadlock. A → B → C, with C running, drains on its own when C finishes. Many threads blocked on one slow lock holder looks similar in a dashboard, but the fix is different.
• A cycle guarantees deadlock only when each resource has a single instance. With several interchangeable instances (a pool of 5 connections), a cycle in the resource graph may still resolve, because some other holder can release one. So with pools, the question becomes "can everyone be waiting at once?", which is what the formula in the previous section answers.

#Handling deadlock: four strategies

There are four broad approaches, and real systems combine them.

#Prevention in practice

Lock ordering is the most useful one:

Always:
Lock 1 → Lock 2

Nobody takes Lock 2 and then Lock 1. Every wait now points from a lower lock to a higher one, and arrows that only go up cannot form a loop.

When the order comes from data, sort it. transfer(from, to) that locks from and then to deadlocks when 7→9 and 9→7 run together, because the two calls take opposite orders. Lock the smaller account id first, whichever way the money moves. The same applies to database rows.

Ordering can be broken in places you do not read. If you hold a lock while calling a callback, listener or library, that code may take other locks in any order. Do not call code you do not control while holding a lock, and never hold a lock across a network call: it turns a slow dependency into a queue of blocked threads, and two services doing this to each other can form a cycle that crosses machines.

Code-level details for all of this (synchronized, ReentrantLock.tryLock, Go and Python) are in Chapter 14.

#Detecting deadlocks

The wait-for graph is the core idea. Draw one node per thread and an edge from each waiter to the holder of what it wants. A cycle means a deadlock. Databases and the JVM build this graph from their lock tables.

In a running process, take a thread dump:

Take two or three dumps some seconds apart. Threads stuck at the same place in all of them are truly stuck. Many threads in one frame, and one that moves, is a slow holder, not a deadlock.

In a database, the engine usually finds it for you:

-- PostgreSQL: who is blocked, and by whom, right now
SELECT pid, pg_blocking_pids(pid) AS blocked_by, wait_event_type, state, query
FROM pg_stat_activity
WHERE cardinality(pg_blocking_pids(pid)) > 0;

-- The locks themselves
SELECT locktype, relation::regclass, mode, granted, pid
FROM pg_locks
WHERE NOT granted;

In MySQL, SHOW ENGINE INNODB STATUS has a LATEST DETECTED DEADLOCK section that shows both transactions.

A deadlock error is not a bug in the database. It is normal behaviour that your code must handle: catch the error, wait a small random time and retry the whole transaction. Then reduce how often it happens: consistent row order, shorter transactions, no user interaction or remote calls inside a transaction, and indexes so that updates lock only the rows they need. Log deadlocks (log_lock_waits in PostgreSQL) and treat a rising rate as a bug report. Chapter 22 covers transactions further.

Across machines, no one sees the whole graph. If transaction 1 holds a row on shard A and waits on shard B, while transaction 2 does the opposite, each database sees only an ordinary lock wait. The same goes for service A calling B while B calls A, each using up the other's pool. The practical answer is timeouts everywhere, plus a consistent order of access.

#Deadlock vs starvation vs livelock

Livelock: threads keep reacting to each other to avoid a conflict, and the actual work never advances. It is often caused by a well-meant fix for deadlock, namely tryLock and retry with no delay. The cure is a random delay, so one thread gets ahead.

Starvation: a thread keeps losing, usually a low-priority one that misses out on CPU or a resource. Priority is not the only cause. A stream of readers can starve a writer on a read-write lock, and an unfair lock can favour whichever thread is already running. Fair locks and queues fix it, at some cost in throughput. Aging raises a waiting task's priority with time.

#Priority inversion

Priority inversion means a high-priority task is held up by a lower-priority one because of a lock. The note's definition stops at "Low holds a lock that High wants". A short wait like that is normal. The dangerous version needs a third task: Medium, which does not need the lock, preempts Low. Now Low cannot finish, so High cannot run, for as long as Medium runs. Medium has effectively outranked High.

The famous case is Mars Pathfinder in 1997. Soon after landing, the lander's computer kept resetting. A low-priority weather task held a mutex on a shared bus, a high-priority bus task waited for it, and a medium-priority communications task kept Low from running. A watchdog saw that the high-priority task had missed its deadline, and reset the system. Engineers reproduced it on a ground copy, then uploaded a small change turning on priority inheritance for that mutex in VxWorks, and the resets stopped.

Priority inheritance means that while Low holds a lock that High wants, Low runs at High's priority. Linux offers this for real-time work with PTHREAD_PRIO_INHERIT.

You may never write real-time code, but the shape appears everywhere. A nightly batch job holds a row lock on a busy table at low CPU priority, and customer checkouts wait behind it. A low-priority task inside a shared lock gets throttled by its container's CPU limit, and everything needing that lock stalls. The rule is the same: never let low-priority work hold something that high-priority work needs for long.

#What this means for system design

• Every pool is a concurrency limit and a queue. Name them on your diagram: request threads, database connections, outbound clients. Overload shows up at the smallest one.
• Size from numbers. Arrival rate × time per request gives the threads you need; cores × (1 + wait ÷ compute) gives the threads the CPU can use. If the first is far larger than the second, you need more machines or a different model, not a bigger pool.
• Bound everything. Bounded queues, timeouts and rejection make overload a controlled, visible event.
• Isolate. One slow dependency must not be able to take all the threads.
• Assume database deadlocks will happen. Order your row access and always write the retry.
• Do not hold locks across slow work, and above all not across a network call.
• Distributed locks can deadlock too. A lease or expiry is their way of adding preemption. Chapter 38 covers them.

#Interview angles

#Try it yourself

1. Watch the thread count change throughput. Save and run this. 200 tasks each wait 50 ms, as a database call would:

import time
from concurrent.futures import ThreadPoolExecutor

def io_task(_):
    time.sleep(0.05)   # 50 ms of waiting

for workers in (1, 4, 20, 100):
    start = time.perf_counter()
    with ThreadPoolExecutor(max_workers=workers) as pool:
        list(pool.map(io_task, range(200)))
    print(f"{workers:>3} workers: {time.perf_counter() - start:5.2f} s")

You should see about 10 s, 2.5 s, 0.5 s and 0.1 s. These tasks only wait, so more workers help. Change time.sleep to a busy CPU loop and the benefit disappears.

2. Make a real deadlock and read the stacks. The threads are daemons, so the program can still exit:

import faulthandler
import threading
import time

lock1 = threading.Lock()
lock2 = threading.Lock()

def worker_a():
    with lock1:
        time.sleep(0.1)      # give B time to take lock2
        with lock2:
            print("A finished")

def worker_b():
    with lock2:              # swap these two lines to apply lock ordering
        time.sleep(0.1)
        with lock1:
            print("B finished")

a = threading.Thread(target=worker_a, name="A", daemon=True)
b = threading.Thread(target=worker_b, name="B", daemon=True)
a.start()
b.start()

time.sleep(1)
print("alive after 1 s:", a.is_alive(), b.is_alive())
faulthandler.dump_traceback(all_threads=True)

The dump shows each thread stuck on the line of its second lock. Now make worker_b take lock1 first, run it again and watch both finish.

3. Deadlock a pool with no locks:

import os
from concurrent.futures import ThreadPoolExecutor
from concurrent.futures import TimeoutError as FutureTimeout

pool = ThreadPoolExecutor(max_workers=2)

def child():
    return "child done"

def parent():
    return pool.submit(child).result()   # blocks a worker until child runs

parents = [pool.submit(parent) for _ in range(2)]
try:
    print([p.result(timeout=2) for p in parents], flush=True)
except FutureTimeout:
    print("stuck: both workers wait for children that are still queued", flush=True)
os._exit(0)                              # a stuck pool would block a normal exit

Change range(2) to range(1) and it works, which is exactly how this bug gets through testing.

4. Make PostgreSQL pick a victim. Open two psql sessions:

CREATE TABLE accounts (id int PRIMARY KEY, balance int);
INSERT INTO accounts VALUES (1, 100), (2, 100);

-- Session 1:
BEGIN;
UPDATE accounts SET balance = balance - 10 WHERE id = 1;

-- Session 2:
BEGIN;
UPDATE accounts SET balance = balance - 10 WHERE id = 2;

-- Session 1 (this one waits):
UPDATE accounts SET balance = balance + 10 WHERE id = 2;

-- Session 2 (after about a second, one session gets the error):
UPDATE accounts SET balance = balance + 10 WHERE id = 1;
-- ERROR:  deadlock detected

While session 1 waits, run the pg_blocking_pids query above in a third session.

5. Take a thread dump of any Java service you run: jcmd <pid> Thread.print. Count how many threads are in each state and where most of them are waiting.

#Summary

Key takeaways

• A thread pool is a queue plus a fixed set of reused workers. It limits concurrency and turns overload into queueing delay.
• CPU-bound: threads ≈ cores. I/O-bound: threads ≈ cores × (1 + wait ÷ compute). Then check the narrowest downstream resource and load test.
• More threads help only while something is idle. Beyond that they add latency.
• Use bounded queues and a deliberate rejection policy. Java's ThreadPoolExecutor fills the queue before starting extra threads.
• Pool exhaustion looks like high latency with low CPU. Timeouts cap the hold time, bulkheads contain the damage.
• A pool whose tasks block on tasks in the same pool can deadlock with no locks.
• Deadlock needs all four Coffman conditions: mutual exclusion, hold and wait, no preemption, circular wait. Break any one.
• Lock ordering is the main prevention; sort by id when the order comes from data. Timeouts are recovery, not prevention.
• A wait chain is not a deadlock; only a cycle is. Find cycles with a wait-for graph, thread dumps and pg_locks.
• Databases abort a victim, so your code must retry the whole transaction. Across machines nothing detects the cycle, so use timeouts.
• Deadlock: frozen, low CPU. Livelock: busy, no progress. Starvation: one loser while the rest progress. Priority inversion: Medium delays High through a lock held by Low.

Self-check: thread pools and deadlock30 questions