Deadlock

Two people each hold one chopstick and wait for the other's. Neither lets go, so neither eats. Threads do the same with locks. Thread 1 holds lock A and waits for lock B. Thread 2 holds lock B and waits for lock A. Both wait forever: this is a deadlock. The program does not crash; it just stops making progress.

Four conditions

A deadlock needs all four of these at once:

Mutual exclusion: only one thread can hold a lock.
Hold and wait: a thread keeps the locks it has while it waits for more.
No preemption: nobody can take a lock away from a thread.
Circular wait: there is a cycle, each thread waiting for the next one's lock.

Break any one of them and deadlock cannot happen.

Lock ordering

The most common fix breaks the cycle. Pick one order for all locks, say A before B, and make every thread follow it. A thread holding B never waits for A, so no cycle can form. One simple rule: always take the lock with the lower address first.

Detect and recover

Some systems let deadlock happen and clean up after. A detector runs now and then, draws who waits for whom, and looks for a cycle. If it finds one, it stops one thread and undoes its work, so the others go on. Databases often do this. A simpler way is a timeout: if a thread waits too long, it gives up its locks and tries again later.

Other concurrency bugs

Most real concurrency bugs are not deadlocks. An atomicity violation is a forgotten lock: one thread checks a value, another changes it, then the first uses the old answer. An order violation is two steps that must run in order but are not forced to, like using a value before another thread sets it.

Remember

Deadlock: each thread holds a lock the other needs.
It needs all four conditions; break one to stop it.
Same lock order everywhere means no cycle.
Detectors find cycles; timeouts give up and retry.
Most bugs are atomicity or order violations.