Section 8: Concurrency Problems

Locks (Section 7) fix some problems and cause others. This section covers the four classic traps of multithreaded programs. Each one has a simple street-life version:

Problem	Street-life version
Race condition	Two people grab the last seat at the same time and both think it is theirs
Deadlock	Two cars meet on a one-lane bridge. Neither will reverse. Both stay forever
Livelock	Two people in a corridor keep stepping aside in the same direction. They are busy, but go nowhere
Starvation	You wait in line, but VIPs keep cutting in front of you, forever

These bugs are nasty because they depend on timing. A program can run 1,000 times fine and fail on the 1,001st. They may only appear on a faster PC, a PC with more cores, or when the system is busy.

8.1 Race Condition (Unsynchronized Access)

What it is: A race condition is a bug where the result depends on which thread happens to get there first (who "wins the race"), because threads use shared data without proper synchronization.

You saw the counter in Section 7.1. Here it is again as a picture of two interleaved threads on two cores:

 count starts at 10. Each thread runs:  count = count + 1

 Core 0 (Thread A)       Core 1 (Thread B)       count in RAM
 ─────────────────       ─────────────────       ────────────
 load  → 10                                         10
                         load  → 10                 10
 add   → 11                                         10
                         add   → 11                 10
 store → 11                                         11
                         store → 11                 11     ✗ expected 12

Kinds you will hear about:

Kind	Meaning
Data race	Two threads access the same memory at the same time and at least one writes, with no lock
Check-then-act	"If the file does not exist, create it": another thread creates it between the check and the act
Torn read	One thread reads a big value while another is halfway through writing it, and sees half old and half new

Symptoms: wrong totals, corrupted data, crashes that "only happen sometimes", and bugs that vanish when you add print statements (because printing changes the timing). People call these heisenbugs.

Fixes:

Fix	How
Use a lock around the critical section	Mutex, critical section, SRW lock
Use atomic operations	`InterlockedIncrement` for the counter
Do not share	Give each thread its own copy and combine results at the end
Make data read-only after setup	No writes means no race

Detecting: The Visual Studio debugger and tools such as ThreadSanitizer (in Clang and recent compilers), the free Microsoft tool Application Verifier, and careful code review. Also, stress testing on many cores helps trigger rare timings.

8.2 Deadlock (Circular Waiting)

What it is: A deadlock happens when two or more threads each hold a lock and wait for a lock held by another, so none can ever continue. All involved threads sit in the Waiting state forever, using no CPU. The program simply hangs.

The classic picture: Two locks, X and Y; two threads, A and B.

 Thread A:  lock X ... then wants Y
 Thread B:  lock Y ... then wants X

      holds                     wants
 ┌──────────┐  ───────────►  ┌────────┐
 │ Thread A │                │ lock Y │
 └──────────┘                └────────┘
      ▲                           │
      │ wants                     │ held by
      │                           ▼
 ┌────────┐                  ┌──────────┐
 │ lock X │  ◄────────────── │ Thread B │
 └────────┘      holds       └──────────┘

 A waits for B.  B waits for A.   ► circle = DEADLOCK

Step by step:

 time ─►   Thread A                 Thread B
   1       lock X  ✔
   2                                lock Y  ✔
   3       lock Y  ... WAITS        
   4                                lock X  ... WAITS
   5       (both wait forever)

The four conditions. A deadlock needs all four at once (called the Coffman conditions). Break any one and deadlock is impossible:

Condition	Meaning
Mutual exclusion	A lock can be held by only one thread
Hold and wait	A thread holds one lock while asking for another
No preemption	A lock cannot be taken away by force
Circular wait	A ring of threads, each waiting for the next

Symptoms: the program or window freezes ("Not Responding") but CPU use is near 0%. This differs from an infinite loop, where one core runs at 100%.

Prevention:

Method	Idea
Lock ordering	Every thread takes locks in the same order (always X before Y). This breaks circular wait. The most common fix.
Try-lock with timeout	Use `TryEnterCriticalSection` or a wait with timeout. If you cannot get the second lock, release the first and retry later
Lock fewer things at once	Hold only one lock at a time when you can
Take all locks at once	Ask for everything together or none
Avoid calling unknown code while holding a lock	A callback might lock something else

8.3 Livelock

What it is: In a livelock, threads are not blocked. They keep running and reacting to each other, but make no progress. It is like deadlock with the lights on: the CPU is busy, yet nothing useful gets done.

Corridor example:

 Two people meet in a corridor.
   Both step LEFT to let the other pass  → still blocked
   Both step RIGHT                        → still blocked
   Both step LEFT again ...               → forever

In code: A thread that uses "try-lock, and if it fails, release everything and try again immediately" can livelock with another thread doing the same.

 Thread A:  lock X, try Y fails → unlock X, retry...   ┐ both keep
 Thread B:  lock Y, try X fails → unlock Y, retry...   ┘ repeating

	Deadlock	Livelock
Threads' state	Waiting (asleep)	Running or Ready (busy)
CPU use	Near zero	Can be high
Progress	None	None

Fixes: add a random delay (back-off) before retrying so the threads fall out of step; make one thread win by a fixed rule (for example, the lower-numbered thread goes first); and use lock ordering.

8.4 Starvation

What it is: Starvation is when a thread is ready to run, or waiting for a lock, but never gets its turn because others keep going first. The system as a whole works; one thread suffers.

Common causes:

Cause	Example
Strict priorities	High-priority threads always busy, so a low-priority thread never runs (Section 5)
Unfair locks	A lock that always lets new arrivals jump ahead of long waiters
Reader/writer locks	A steady flow of readers keeps a writer waiting forever
Greedy thread	One thread holds a lock for very long stretches

Windows protections: The balance-set manager (Section 5.2) boosts threads that have waited around four seconds in the Ready state, so plain CPU starvation of ordinary threads is rare. Lock starvation, however, is up to the programmer.

Fixes: use fair queues (first come, first served); keep high-priority work short; do not hold locks long; and give writers some priority over new readers.

8.5 How to Detect and Avoid Each

Summary of symptoms:

Problem	What you see	CPU use
Race condition	Wrong or random results, crashes "sometimes"	Normal
Deadlock	Program freezes totally	Near 0% for that program
Livelock	Program seems busy but no progress	Often high
Starvation	One part of the program is very slow or never finishes	Normal

Windows tools to find a hang:

Tool	How
Resource Monitor → CPU tab → right-click a hung process → Analyze Wait Chain	Shows which thread waits for which. If it finds a cycle, it reports the process is deadlocked
Task Manager → Details	Shows "Not Responding" and 0% CPU
Process Explorer (Sysinternals) → Threads tab	Look at each thread's stack to see where it waits
Debugger (Visual Studio, WinDbg)	Break in and inspect the thread stacks; threads stuck on `EnterCriticalSection` or `WaitForSingleObject` show who waits on whom
Application Verifier / Driver Verifier	Checks lock use and can spot some deadlock and lock errors
Performance Monitor	Context switches and processor queue length help identify livelock and overload

Prevention checklist:

Habit	Prevents
Share as little data as possible	Everything
Keep locks short	Starvation, deadlock
Always lock in the same order	Deadlock
Use try-lock with timeout and random back-off	Deadlock, livelock
Use atomic operations for simple counters and flags	Race condition
Use thread pools and queues so threads pass messages instead of sharing	Race, deadlock
Test under heavy load on a many-core PC	All of them

Final lesson: A message queue (one thread sends work, another receives it) is often safer than many threads sharing memory. Pass data, not access.

Summary

Problem	Plain meaning	Main fix
Race condition	Result depends on timing; unsynchronized shared data	Locks, atomics, no sharing
Deadlock	Threads wait for each other in a circle, forever	Same lock order; try-lock with timeout
Livelock	Threads keep reacting, make no progress	Random back-off; fixed winner rule
Starvation	A thread never gets its turn	Fair locks; short high-priority work
Priority inversion	High waits for low while medium runs (Section 5.4)	Inheritance or boosts; avoid shared locks
Wait chain	A map of who waits for whom	Resource Monitor → Analyze Wait Chain

The Big Picture: When Sharing Goes Wrong