CS343

Concurrency Problems

A map of what breaks in concurrent programs, and which tools prevent each failure. Most of these come from CS343 Ch 5-11.

Failure modes

The core enemies, organized by what kind of progress they block:

failure	state of the thread	root cause	typical fix
Deadlock	blocked forever	circular wait on resources	ordering, detection, avoidance
Livelock	running, state keeps changing, no work done	symmetric retreats	randomization, arbiter
Starvation	ready, scheduler skips it	rule 5 broken	FIFO queues, bounded overtaking, aging
Busy-wait starvation	spinning in CAS retry	unlucky thread keeps losing	bounded retry or wait-free ops
Race Condition	fine per-thread	unsynchronized access, depends on order	mutual exclusion
Data Race	undefined behaviour	concurrent access, one write, no sync	atomics, locks
ABA Problem	logic bug in CAS	A→B→A invisible to CAS	tagged pointers, SC, SMR
Use-after-free (lock-free)	segfault	freed node still reachable via stale pointer	SMR: hazard pointers, epochs, RCU
Priority Inversion	high-prio blocked on low-prio’s lock	preemption mid-critical-section	priority inheritance / ceiling

Deadlock vs livelock vs starvation?

All three are “no progress” failures, but:

• Deadlock threads are blocked, CPU idle
• Livelock threads are running, burning CPU, but looping
• Starvation threads are ready, the scheduler just never picks them

Coordination primitives

From lowest level to highest, each one solves the layer below:

• Hardware atomics: test-and-set, swap, fetch-and-add, CAS, SC
• Software mutex algorithms: Dekker, Peterson, Bakery, Arbiter, Tournament
• Locks: spinlock, mutex, reader-writer, sync lock
• Higher-level: semaphore, barrier, monitor, task
• Message passing: no shared state at all, see Go channels

Programming models

How you structure concurrent code, each model trades safety for complexity differently:

model	write it	perf	gotchas
Lock-based	easy	meh under contention	deadlock, priority inversion, starvation
Lock-free	hard (raw CAS)	great	ABA, memory reclamation, unbounded retry
Wait-free	very hard	often worse than lock-free	mostly academic outside single-atomic ops
STM	easy (just atomic{})	bookkeeping overhead	I/O unsafe, needs language support
Message passing	medium	good, no shared state	just moves the problem to the channel

Lock-based (C++)

std::mutex m;
std::vector<int> v;
void add(int x) {
    std::lock_guard<std::mutex> lock(m);  // RAII, releases on scope exit
    v.push_back(x);
}

Lock-free (C++ stack push via CAS)

void push(Node* n) {
    Node* old;
    do {
        old = head.load();
        n->next = old;
    } while (!head.compare_exchange_weak(old, n));  // retry until nobody stomped us
}

Wait-free (atomic counter)

std::atomic<int> counter{0};
void inc() { counter.fetch_add(1); }  // single instruction, bounded steps

STM (Rust, rust-stm)

atomically(|tx| {
    let v = var.read(tx)?;
    var.write(tx, v + 1)  // runtime retries the whole block on conflict
});

Message passing (Go)

ch := make(chan int, 10)
go func() { ch <- 42 }()   // producer sends
fmt.Println(<-ch)          // consumer receives, no shared memory

Memory ordering issues

Compiler and hardware reorder reads and writes unless you tell them not to:

• Cache coherence makes each address look sequentially consistent, but across addresses ordering is weaker
• Memory model specifies what reorderings are legal, C++ gives you relaxed, acquire, release, seq_cst
• Memory barriers force ordering at specific points
• Disjoint reordering and eliding are the compiler’s optimizations that assume single-threaded semantics

Quick “which one do I reach for”

• Shared counter: fetch_add (wait-free)
• Shared queue: lock-free queue with SMR, or just a mutex if uncontended
• Multi-word atomic update: STM or a coarse lock, don’t try to hand-roll lock-free
• Producer/consumer: bounded buffer with semaphores or a channel
• Read-heavy shared state: RW lock, or RCU if you really need it

Related

• CS343
• Mutual Exclusion
• Concurrency
• Peter Buhr