Mutex and semaphore

Gold that disappears under load

A game server keeps every online player's inventory in memory and handles events on a pool of worker threads: loot from a raid, a sale at the shop, a quest reward. One weekend the economy dashboard shows that players were credited 3,000,000 gold while their balances rose by 2,999,700. There is no exception and no error in the logs, and the test suite, which sends events one at a time, passes on every run.

The culprit is one line, player.gold = player.gold + amount. It reads like one step, and it is three: read the gold, add the amount, write the result back. Two events for the same player, handled by two threads at the same moment, can interleave like this:

1. Thread A, handling a 100-gold loot drop, reads player 17's gold: 500.
2. Thread B, handling a 50-gold quest reward, reads the same gold: 500.
3. Thread A adds 100 and writes 600.
4. Thread B adds 50 to the 500 it read and writes 550.

Player 17 should have 650 and has 550; thread A's 100 is gone. This is a race condition: the result depends on how the threads' steps happen to interleave. This one is the read-modify-write kind, where a value is read, changed and written back while another thread does the same. It is intermittent because the window is tiny: two events for the same player have to land within the moment between one thread's read and its write, or the scheduler has to pause thread A inside that window. A test that sends one event and waits for it before sending the next never opens the window; thousands of events a second open it occasionally. Writing player.gold += amount changes nothing, because the shorter line still reads, adds and writes. Neither does a global interpreter lock like CPython's: it keeps the interpreter's own data consistent, but a thread can still be switched out between the read and the write.

A stretch of code only one thread may enter

The three steps have to run as one, with no other thread touching player 17's gold in between. A stretch of code that reads and writes shared state and must not overlap with another thread doing the same is a critical section. For a single counter there is a shortcut: an atomic increment (Java's AtomicLong, C++'s std::atomic, Go's sync/atomic) performs the read, the add and the write as one indivisible operation. But a loot drop rarely touches one number. It adds gold, puts an item in a bag that may be full, and bumps a loot counter, and those three have to change together.

A mutex, short for mutual exclusion, is the general tool. Each player gets one, and every piece of code that touches that player's inventory follows the same protocol: acquire (lock) the mutex, do the work, release (unlock) it. A thread that tries to acquire a mutex another thread holds waits until it is released. Replay the trace with it:

1. Thread A acquires player 17's mutex.
2. Thread B tries to acquire the same mutex and waits.
3. Thread A reads 500, writes 600 and releases the mutex.
4. Thread B acquires it, reads 600, writes 650 and releases it.

Diagram components: Client, Client, Mutex / Lock, Data Store.

Both threads go through the same mutex. B's read-modify-write starts only after A has released it.

Two details of that diagram matter more than they look. The mutex does not lock the memory: the gold is still an ordinary field, and a code path that writes it without acquiring the mutex races exactly as before. The protection is a convention every path has to follow, which is why the field usually sits behind methods that take the lock. And the mutex does more than keep B out. In the mainstream memory models (Java's, Go's, C++'s), a release followed by an acquire of the same mutex makes every write the previous holder made before releasing visible to the next one. That is why reads need the lock too, not only writes.

The release that never ran

The bag is full, so the code that adds the item throws an exception between the acquire and the release. The release line is never reached, player 17's mutex stays held, and every later event for that player waits on it forever. Each of those events occupies a worker thread while it waits, so with enough of them one exception ties up the whole pool.

So a mutex is released on every path out of the critical section, error paths included. Languages give you a form that does it for you: a try/finally block, Java's synchronized block, Go's defer mu.Unlock(), C++'s std::lock_guard, Python's with lock:. Use it instead of a bare unlock at the end of the function. Releasing undoes nothing, though: if the gold was added before the bag turned out to be full, the next holder sees the gold without the item. Check that every step can succeed (the bag has room) before the first write, or put back what was changed before the lock is released.

Most mutexes also have an owner: the thread that acquired it is the one expected to release it. Some implementations check this and refuse an unlock from any other thread; others leave it to the code, and Go's sync.Mutex has no owner at all, so its documentation allows one goroutine to lock it and another to unlock it. Where nothing checks, releasing a lock you do not hold can let a second thread into a critical section the first is still inside.

Ten connections for two hundred threads

Every few seconds the server saves changed inventories to its database. Saves run on the same 200 worker threads, but the database accepts only 10 connections from this server. A mutex around the database would let one save through at a time and leave nine connections idle. What the saves need is not one at a time but at most ten at a time.

A semaphore is a counter of permits, set at creation to the number of units available, here 10. Acquiring takes a permit and decrements the counter; when the counter is at zero, the acquiring thread waits. Releasing gives a permit back and lets one waiting thread proceed. Ten saves run at once, and the eleventh waits until one of them finishes.

Diagram components: Client, Client, Semaphore, Data Store.

The semaphore counts permits, not owners. The eleventh save waits until one of the ten releases its permit.

A connection pool library usually does this counting for you. You reach for a semaphore directly when the limited thing has no pool of its own: an external API that accepts five concurrent requests per key, or the number of large images decoded at once, so memory stays bounded. Two consequences follow from what a semaphore counts. It bounds how many threads are inside, not what they do there: ten savers running at once can still race on any state they share, and that state still needs a mutex. And a typical semaphore does not record which thread holds a permit, so any thread may release one. A path that forgets to release loses a permit for good, and after ten such leaks every save waits forever. A path that releases twice creates an eleventh permit, so eleven saves can try to connect at once, one more than the database accepts. Some libraries reject the extra release, such as Python's BoundedSemaphore.

A semaphore whose count only moves between 0 and 1, a binary semaphore, admits one thread at a time when it starts with its one permit, but it has no owner, so any thread may release it. That suits signalling (it starts at zero, and thread B waits on it until thread A releases it to say the data is ready) and makes it a risky lock, because a stray release lets a second thread in. For a critical section, use a mutex; for counted access to a limited resource, a semaphore.

Two players trade with each other

With one mutex per player, events for different players run in parallel, which is why the server has a mutex per player rather than one for everybody. A trade touches two players, a sword going one way and gold the other, so it acquires both mutexes: the player who opened the trade first, then the partner. Then player 17 offers player 42 a trade at the same moment player 42 offers one to player 17:

1. Thread A, running 17's trade, acquires player 17's mutex.
2. Thread B, running 42's trade, acquires player 42's mutex.
3. Thread A tries to acquire player 42's mutex and waits for thread B.
4. Thread B tries to acquire player 17's mutex and waits for thread A.

Neither thread will ever release, because each is waiting for the other. This is a deadlock. Nothing crashes, and with blocking mutexes like these no CPU is burned; two threads simply stop, and every later event for players 17 and 42 queues behind them. A thread dump shows it plainly: each thread blocked on a mutex the other holds. Of the conditions a deadlock needs, the cycle of threads each waiting for the next is usually the most practical one to break.

Lock ordering removes the cycle: every code path that takes more than one of these mutexes takes them in the same global order, for example lower player id first. Replay the trade with it. Both threads go for player 17's mutex first; B waits there while holding nothing, A takes both, finishes and releases, and B proceeds. The rule has to hold on every path, because one function that takes the two mutexes the other way round brings the cycle back. When a global order is impossible, because the second lock is only known after the first is held, the usual mitigation is a try-lock with a timeout: if the second mutex is not acquired within, say, 50 ms, release the first, wait a random moment and retry. That turns a hang into a retry, at the cost of wasted work. Without the random wait, two threads can keep backing off and retrying in step, a livelock.

What a lock costs

Threads waiting for a held lock do no work. That waiting is contention, and it grows with how long the lock is held and how many threads want it. A single lock that every event passes through runs the code inside it one thread at a time, however many cores the machine has.

The easiest way to make contention worse is to hold a lock across slow I/O. If the save takes player 17's mutex and then writes to the database, every loot drop for player 17 waits a database round trip, milliseconds instead of microseconds; and if the save also waits for one of the ten database permits, that wait sits inside the critical section too. Copy what you need under the lock, release it, and do the I/O outside. Here the saved copy may be a few milliseconds old by the time it reaches the database, which a periodic save tolerates because the next save catches up, as long as an older copy can never land after a newer one: either two saves of the same player never run at once, or the row carries a version number and the database refuses a copy older than the one it holds.

Then there is granularity: one mutex for the whole server is simple but makes every event for every player queue on it, while one mutex per field means a loot drop takes three locks, more ordering rules, and leaves a rule spanning the gold and the bag protected by no single lock. One mutex per player matches the unit that has to change together, so start coarse, measure where threads wait, and split only there.

All of this lives in one process's memory. Once the game runs on several servers, a mutex in one of them means nothing to the others, and the replacement is the subject of Distributed locks & leader election. Once the gold moves into a database row, the same lost update reappears between transactions, as Transactions & isolation levels shows.

Exclusive versus counted, on a Grid

The Mutex & Semaphore challenge asks for one drawing that makes exclusive and counted access look different. Use two Client nodes as competing threads, a Mutex / Lock node in front of the Data Store that holds the shared gold, and a Semaphore node with its permit count in the title, in front of a second Data Store for the database with ten connections. Label the edges with acquire and release, so the protected work visibly sits between them. The challenge allows up to six nodes, which is exactly that drawing. It does not ask about deadlock; the trade above, two threads taking two mutexes in opposite orders, is worth sketching on a blank Grid if you want to see the cycle.