Concurrency & Synchronization

Concurrency & Synchronization

Concurrency is when a program has multiple things happening at the same time (or appearing to). Modern systems are inherently concurrent: web servers handle thousands of connections simultaneously, databases execute many transactions in parallel, and operating systems run multiple processes. Writing correct concurrent code is one of the hardest problems in software engineering.

Why Concurrency Is Hard

Sequential code has a clear order: line 1 executes, then line 2, then line 3. Concurrent code has operations interleaving in ways that are non-deterministic — different orderings can produce different results, and the wrong ordering produces a bug.

Race condition: two threads access shared state without synchronization. The classic example:

Thread A: counter = counter + 1

Thread B: counter = counter + 1

Both read the same value (say, 5). Both add 1. Both write 6. Expected result: 7. Actual result: 6. Lost update.

Race conditions are insidious because they only manifest in specific timing conditions — the test passes most of the time, fails occasionally, and fails in production under load when timing conditions differ.

Mutual Exclusion and Locks

A mutex (mutual exclusion lock) ensures only one thread executes a critical section at a time:

mutex.lock()
counter = counter + 1   // critical section
mutex.unlock()

The key property: if thread A holds the mutex, thread B calling mutex.lock() blocks until A releases it. This serializes access to the critical section, preventing the race.

Lock granularity: a single global lock is simple but serializes everything. Per-object locks allow more concurrency but are harder to reason about. Fine-grained locking is more scalable but more prone to deadlocks.

Read-Write Locks (RWLock): for read-heavy workloads, many threads can read simultaneously (sharing the read lock), but writes require exclusive access (write lock). PostgreSQL's buffer cache uses this pattern extensively.

Deadlock

Deadlock occurs when threads form a circular wait:

• Thread A holds lock L1 and waits for L2
• Thread B holds lock L2 and waits for L1

Neither can proceed.

Coffman conditions (all four must hold for deadlock):

1. Mutual exclusion: locks can only be held by one thread
2. Hold and wait: threads hold locks while waiting for others
3. No preemption: locks cannot be forcibly taken
4. Circular wait: a cycle of threads, each waiting for the next

Prevention strategies:

• Lock ordering: always acquire locks in a consistent order across all code paths. If all threads acquire L1 then L2 (never L2 then L1), circular wait is impossible.
• Lock timeout: if a lock cannot be acquired in X milliseconds, release all held locks and retry. Breaks deadlock but requires retry logic.
• Deadlock detection: detect cycles in the "waiting for" graph; force one thread to abort. Used by databases (deadlock → rollback one transaction).

Semaphores and Higher-Level Primitives

A semaphore has a count. Wait decrements; signal increments. If count reaches 0, wait blocks.

Binary semaphore (count 0 or 1): equivalent to a mutex. Counting semaphore: allows N concurrent accesses. Used to limit connection pool size, rate-limit requests, or coordinate producer-consumer.

Condition variables: allow threads to wait for a condition without spinning:

mutex.lock()
while (!condition_is_true) {
  cond.wait(mutex)  // atomically releases mutex and blocks
}
// condition is now true; mutex is re-acquired
mutex.unlock()

Used with mutexes for producer-consumer, bounded buffers, and event signaling.

Monitors (Java's synchronized, Go's sync.Mutex with defer): encapsulate state and the lock protecting it; provide a cleaner pattern than raw mutex + condition variable.

Lock-Free Data Structures

Lock-free algorithms use hardware atomic operations (Compare-And-Swap, CAS) to implement concurrent data structures without mutexes:

CAS: atomically checks if a memory location has an expected value and only updates if it does. If another thread changed it first, CAS fails and you retry.

Lock-free stacks, queues, and counters are possible but complex. Useful in hot paths where lock contention is a bottleneck. The ConcurrentLinkedQueue in Java, and Go's sync/atomic package implement these.

Async/Await and the Event Loop

Thread-per-connection concurrency doesn't scale: a server with 10,000 concurrent connections would need 10,000 threads, consuming gigabytes of stack space and spending most time blocked on I/O.

Event loop model (Node.js, Python asyncio, JavaScript in browsers): a single thread handles many connections by interleaving I/O:

1. Submit I/O operation, register callback
2. Immediately handle other work
3. When I/O completes, callback fires

async/await syntax makes this readable:

async function fetchUser(id) {
  const user = await db.query('SELECT * FROM users WHERE id = $1', [id])
  const orders = await db.query('SELECT * FROM orders WHERE user_id = $1', [id])
  return { user, orders }
}

Each await yields back to the event loop; when the operation completes, execution resumes.

Event loop limitations: if one operation is CPU-intensive (image processing, cryptography, complex computation), it blocks the event loop and all other connections stall. CPU-bound work must run in a worker thread pool (Node.js worker_threads, Python multiprocessing).

Go's Concurrency Model (CSP)

Go's goroutines are lightweight threads (2KB initial stack, millions can run simultaneously). Go's channels implement Communicating Sequential Processes (CSP):

don't communicate by sharing memory; share memory by communicating

Rather than locking shared data, goroutines pass data through channels:

ch := make(chan int)
go func() { ch <- expensiveComputation() }()
result := <-ch  // blocks until result is ready

The select statement waits on multiple channels, implementing fan-in, timeouts, and cancellation patterns.