Concurrency — Without Ordering, the Result Is Undefined

In a nutshell

The moment several execution flows touch the same data, the result comes to depend on the execution order. The mechanism that enforces that order is the lock, and using locks wrongly can land you in a state where nobody can make progress.

Why this was needed

The single line counter = counter + 1 is at least three steps in machine code: read, add, and write. When two threads run this code at the same time, both can read the same value and write the same value, so one increment disappears. This is a race condition.

The nasty thing about this bug is its reproducibility. In most runs nothing happens, and it appears when the load rises or the number of cores grows. So it passes tests and blows up in production.

How it works

A section of code that touches a shared resource is called a critical section, and a correct solution must satisfy three conditions.

1. Mutual exclusion — only one thread at a time enters the critical section.
2. Progress — if nobody is inside, one of those trying to enter must get in.
3. Bounded waiting — a thread trying to enter is not pushed back indefinitely.

It can be built with software alone (Peterson's algorithm), but modern CPUs provide atomic instructions. The typical one is CAS (compare-and-swap), which compares and swaps the value if it is the same, and almost all locks and lock-free data structures stand on top of it.

Synchronization tools differ in nature.

• Mutex — has an owner. Only the thread that locked it can release it.
• Semaphore — a counter. It has no notion of an owner, so A may acquire it and B may release it. It fits when you need to limit the number of resources.
• Condition variable — expresses "wait until some condition becomes true". It must always be paired with a mutex, and after waking up you must check the condition again (spurious wakeups exist).

How threads wait also differs. A spinlock waits by spinning on the CPU until the lock is released. It pays off only when the critical section is very short and there are spare cores; otherwise it just burns CPU. A blocking lock puts the thread to sleep and lets it do other things, but it costs a context switch.

A deadlock occurs only when four conditions hold at the same time: mutual exclusion, hold and wait, no preemption, and circular wait. The fact that all four are needed also means that breaking just one can prevent it. The method most often used in practice is to break circular wait, that is, the rule that all code acquires locks in the same order. If deadlocks are frequent in a database, first check whether transactions touch rows in inconsistent orders.

Priority inversion is also worth knowing. If a low-priority thread holds a lock and cannot run because a medium-priority thread pushes it aside, the high-priority thread waiting for that lock is blocked along with it. The famous reboot incident on the Mars Pathfinder probe was this problem, and the solution is priority inheritance, which temporarily raises the priority of the thread holding the lock.

What it looks like in the field

A pattern in which an application reads, decides, and then writes, such as "check the stock and deduct it if there is any", always breaks without a lock. There is a common misconception here, though: the belief that raising the database's isolation level solves it. If two transactions read the same set and update different rows, there is no write conflict, so snapshot isolation does not catch it. This phenomenon is called write skew, and it can be prevented only with the serializable level, explicit locking, or constraints.

Toward using fewer locks

Locks are correct but expensive, and using them wrongly creates deadlocks. So the practical direction is not to use locks well but to make them unnecessary. There are roughly three ways.

Do not share. If each thread touches only its own share of the data and merges at the end, no lock is needed at all. If you are counting, each thread counts separately and the totals are added at the end. You only need to synchronize once, in the merge step, so the contention disappears.

Do not modify. If, instead of changing a value, you create a new value and just swap the reference, readers are safe without locks. It suits configuration or lookup tables that are read overwhelmingly often. In exchange, it makes a copy on every update, so it does not suit frequently changing data.

Pass messages. Instead of sharing data, keep ownership in one place, and have other flows send requests for that place to handle. The value of this approach is not performance but that the places where the data changes are gathered into one. The place to look for a bug becomes one function rather than the whole codebase.

If you keep just a few rules when you do need locks, most incidents disappear. Keep the scope narrow, so that you do not call I/O or other locks inside the critical section; fix an order, so that you always take multiple locks in the same order; and do not call callbacks while holding a lock. The last one is especially easy to forget: the moment you call someone else's code, you cannot know which locks it will take, and the order rule breaks.

Finally, race conditions are hard to catch with tests, because most runs pass. So it is far more effective to put static analyzers or tools that detect races at run time into CI, and it also helps to have a separate test that raises the load and runs for a long time.

What you will do in the next lab

You will make four threads increment the same value and create the lost updates yourself. After running the same program five times and confirming that the value differs each time, you will prevent the problem with a lock and also by not sharing at all. Finally, you will take the locks in opposite orders to create a deadlock, and remove it just by unifying the order.