Concurrent Data Structures and Algorithms

A *thread-safe* structure simply doesn't break when several threads use it — often by putting one big lock around everything.

Learning Objectives

Distinguish thread-safe from concurrent data structures; define linearizability and sequential consistency.

Build lock-based stacks and queues; understand concurrent queues, maps and hash tables, read/write lock trade-offs, atomic counters, concurrent caches, blocking and non-blocking structures.

Explain lock-free stacks and queues, CAS loops, ABA and the memory-reclamation challenge (hazard pointers, epochs, RCU); work-stealing deques; concurrent iteration and snapshots; false sharing, padding and alignment.

Test with stress tests and linearizability checking; prefer standard library structures.

Plain-Language Explanation

A *thread-safe* structure simply doesn't break when several threads use it — often by putting one big lock around everything. A *concurrent* structure is designed so that threads can make progress at the same time — different buckets of a hash map, both ends of a queue. The hardest part is not the algorithm but proving that every possible interleaving still behaves like the simple single-threaded version.

Precise Technical Explanation

Thread-safe versus concurrent data structure Thread-safe: correct under concurrent use (e.g. Collections.synchronizedMap, a list behind one mutex). Concurrent: designed for parallel access with fine-grained locking or lock-free techniques (ConcurrentHashMap, ConcurrentLinkedQueue). Both can still be misused with check-then-act sequences of separate calls.

Each operation appears to take effect atomically at a single point (its linearization point) between its invocation and response, and the resulting order is a legal sequential history. Composable: a system of linearizable objects is linearizable.

All operations appear in *some* single order consistent with each thread's program order — but not necessarily respecting real-time order across threads. Weaker than linearizability and not composable.

Lock-based stacks and queues One mutex around a std::stack/deque — simple and often fast enough; a two-lock queue (Michael & Scott 1996) lets enqueuers and dequeuers proceed in parallel.

MPMC queues (ConcurrentLinkedQueue, ConcurrentQueue<T>, crossbeam::queue), bounded ring buffers with atomic indices (LMAX Disruptor), SPSC queues (fastest; Module 8).

Concurrent maps and hash tables Lock striping (N locks for N bucket groups), per-bin CAS plus locks (ConcurrentHashMap), split-ordered lists, lock-free hash tables; resizing concurrently is the hard part.

Read/write lock trade-offs Module 4: benefit only for long, read-dominated critical sections; otherwise reader-count contention outweighs the gain.

Single atomic, striped counters (LongAdder), per-thread counters (Module 6).

Map + eviction policy (LRU/LFU/TinyLFU) + expiry + single-flight loading; eviction bookkeeping is the contention point (Caffeine uses buffered, batched policy updates).

Blocking data structures Operations wait for a condition (BlockingQueue.take), built on locks and condition variables.

Non-blocking data structures Operations never wait for other threads to release a lock (lock-free/wait-free, Module 6) — built on CAS.

Lock-free stack concept Treiber stack: push — new node's next = head, CAS head from old to new; pop — read head, CAS head to head.next. Retry on CAS failure (implemented below).

Lock-free queue concept Michael-Scott queue: linked list with head and tail pointers, a dummy node, and CAS on tail.next then on tail (helping lagging updates).

Read, compute, CAS, retry (Module 6).

Module 6: tags/versions or safe reclamation.

Memory reclamation challenge In a lock-free structure, a thread may still hold a pointer to a node another thread has just unlinked. Freeing it immediately risks use-after-free and ABA. GC languages solve this automatically; C/C++/Rust need explicit schemes.

Hazard pointers overview Each thread publishes the pointers it is about to dereference; a retired node is freed only when no hazard pointer refers to it (C++26 std::hazard_pointer).

Epoch-based reclamation overview Threads announce entry into epochs; retired nodes are freed two epochs later when no thread can still be in the old one (crossbeam-epoch).

Readers proceed without synchronization; writers publish new versions and wait for a grace period before freeing old ones (Module 18).

Chase-Lev deque: the owner pushes/pops at the bottom without CAS in the common case; thieves CAS at the top; used by every work-stealing scheduler.

Concurrent iteration semantics Options: *fail-fast* (throw ConcurrentModificationException — ArrayList iterators), *weakly consistent* (may or may not see concurrent changes, never throws — ConcurrentHashMap), *snapshot* (iterates a copy — CopyOnWriteArrayList), or undefined behavior (most unsynchronised containers in C++).

Iterate an immutable snapshot (copy-on-write arrays, persistent structures): consistent, but writes are expensive.

False sharing and padding Pad hot fields of different threads to separate cache lines (Module 6; Memory course Module 13).

alignas(64) / @Contended (Java, internal) / CachePadded<T> (crossbeam).

Testing with stress tests Many threads, many iterations, randomised operations, invariant checks (counts conserved, no duplicates), runs under TSan.

Linearizability testing concept Record a concurrent history of invocations/responses, then search for a sequential order consistent with real-time order and the specification (Knossos, Porcupine, Lincheck). A small brute-force checker is implemented below.

Choosing standard library structures over custom algorithms Library concurrent containers are tested on many platforms, reclaim memory correctly, and handle edge cases (resizing, ABA). Write your own only for measured needs — and then test with model checkers.

Why It Matters in Real Systems

Allocators, schedulers, caches, message queues and databases depend on concurrent data structures; their correctness bugs are rare, catastrophic and hard to reproduce.

Key Terms

Operations appear atomic within their duration The instant an operation takes effect Lock-free stack using CAS on the head

Lock-free linked queue with head and tail Hazard pointer / epoch Safe memory-reclamation schemes Weakly consistent iterator

May reflect some concurrent changes, never throws Several locks guarding partitions

Syntax and API Overview

This is a concurrency concept, not a language construct; standard structures: ConcurrentHashMap, ConcurrentLinkedQueue, CopyOnWriteArrayList (Java); ConcurrentDictionary, ConcurrentQueue, ImmutableList (C#); queue.Queue (Python); sync.Map (Go); crossbeam (Rust); TBB/folly/Boost.Lockfree (C++).

Complete Code Example

A Treiber lock-free stack versus a mutex-protected stack under stress, with conservation checks (G++ 11.2; nodes are never freed during the run, which sidesteps reclamation and ABA for this demonstration — production code needs hazard pointers or epochs):

A brute-force linearizability checker for a concurrent counter's history (CPython 3.13.1, deterministic):

Concurrent iteration semantics in Java — fail-fast, snapshot and weakly consistent (Temurin JDK 21):

#include <atomic>
#include <chrono>
#include <iostream>
#include <mutex>
#include <stack>
#include <thread>
#include <vector>

struct Node { long value; Node* next; };

class TreiberStack {
    std::atomic<Node*> head{nullptr};
public:
    void push(Node* n) {
        n->next = head.load(std::memory_order_relaxed);
        while (!head.compare_exchange_weak(n->next, n, std::memory_order_release, std::memory_order_relaxed)) {}
    }
    Node* pop() {
        Node* h = head.load(std::memory_order_acquire);
        while (h && !head.compare_exchange_weak(h, h->next, std::memory_order_acquire, std::memory_order_acquire)) {}
        return h;                                   // caller owns the node; never freed here (no reclamation scheme)
    }
};

int main() {
    constexpr int threads = 4, per = 200'000;
    std::vector<Node> pool(threads * per);         // all nodes pre-allocated, never freed during the run

    TreiberStack lf;
    auto t0 = std::chrono::steady_clock::now();
    std::atomic<long> popped_sum{0}, popped_count{0};
    {
        std::vector<std::jthread> ts;
        for (int t = 0; t < threads; ++t)
            ts.emplace_back([&, t] {
                for (int i = 0; 
…

lock-free Treiber stack: popped 800000 of 800000, sum conserved: true, 113 ms
mutex-protected stack:   popped 800000 of 800000, sum conserved: true, 59 ms

from itertools import permutations

# an operation: (name, start time, end time, kind, argument/result)
# a shared counter with inc() (returns nothing) and get() (returns the value)

def linearizable(history):
    """Is there a sequential order that respects real time (a ends before b starts => a first)
    and in which every get() returns the counter value at its position?"""
    ops = list(history)
    for order in permutations(ops):
        pos = {op[0]: i for i, op in enumerate(order)}
        if any(a[2] < b[1] and pos[a[0]] > pos[b[0]] for a in ops for b in ops):
            continue                                   # violates real-time order
        value, ok = 0, True
        for name, start, end, kind, arg in order:
            if kind == "inc":
                value += 1
            elif value != arg:
                ok = False
                break
        if ok:
            return " -> ".join(op[0] for op in order)
    return None

ok_history = [("A:inc", 0, 4, "inc", None), ("B:get", 1, 3, "get", 1), ("C:get", 5, 6, "get", 1)]
bad_history = [("A:inc", 0, 2, "inc", None), ("B:get", 3, 4, "get", 0)]   # get starts after inc finished, yet sees 0
stale_ok = [("A:inc", 0, 
…

overlapping inc/get seeing 1  : linearizable via A:inc -> B:get -> C:get
get after inc seeing 0        : NOT linearizable
overlapping inc/get seeing 0  : linearizable via B:get -> A:inc

import java.util.*;
import java.util.concurrent.*;

public class Iteration {
    public static void main(String[] args) {
        List<Integer> plain = new ArrayList<>(List.of(1, 2, 3));
        try {
            for (Integer x : plain) if (x == 1) plain.add(99);           // modify while iterating
        } catch (ConcurrentModificationException e) {
            System.out.println("ArrayList iterator: fail-fast ConcurrentModificationException");
        }

        List<Integer> cow = new CopyOnWriteArrayList<>(List.of(1, 2, 3));
        int seen = 0;
        for (Integer x : cow) { if (x == 1) cow.add(99); seen++; }          // iterates the snapshot taken at the start
        System.out.println("CopyOnWriteArrayList: iterator saw " + seen + " elements (snapshot); list now has " + cow.size());

        Map<String, Integer> chm = new ConcurrentHashMap<>(Map.of("a", 1, "b", 2));
        int visited = 0;
        for (String k : chm.keySet()) { chm.put("new-" + k, 0); visited++; }  // weakly consistent: no exception
        System.out.println("ConcurrentHashMap: weakly consistent iteration visited " + (visited >= 2 ? "at least the original 2" : visited) + " keys, no exception");
    }

…

ArrayList iterator: fail-fast ConcurrentModificationException
CopyOnWriteArrayList: iterator saw 3 elements (snapshot); list now has 4
ConcurrentHashMap: weakly consistent iteration visited at least the original 2 keys, no exception

Line-by-Line Explanation

Treiber push: set next to the observed head, CAS head from that value to the new node; on failure compare_exchange_weak refreshes n->next with the current head and retries.

Treiber pop: CAS head from h to h->next; a failed CAS refreshes h. Because nodes are never freed during the run, reading h->next of a node popped by another thread is safe here — exactly the guarantee real implementations must provide with hazard pointers or epochs.

The conservation check (count and sum of popped values) verifies no node was lost or duplicated.

Linearizability: the checker tries every order consistent with real time; the second history is rejected because a get that starts after inc completed must see 1. The third is accepted: overlapping operations may be ordered either way.

Java iteration: ArrayList detects the modification and throws; CopyOnWriteArrayList iterates the old snapshot; ConcurrentHashMap iterators are weakly consistent.

Interleaving or State Trace

Treiber push contention: T1 reads head = X, sets n1→next = X; T2 pushes n2 (head = n2); T1's CAS(X → n1) fails, refreshes n1→next = n2, retries CAS(n2 → n1) and succeeds — no update lost.

Correctness and Safety Analysis

Correctness arguments for concurrent structures are linearizability proofs: identify each operation's linearization point (the successful CAS for Treiber push and pop) and show the abstract state changes exactly there. Then add reclamation safety and memory-order correctness.

Common Mistakes and Misconceptions

"Lock-free = faster" (the measurement may show otherwise under contention).

Freeing nodes immediately in lock-free code.

Composing two thread-safe calls and assuming atomicity.

Assuming concurrent iterators see a consistent snapshot.

Testing only on x86.

Failure Modes and Debugging Steps

Lost/duplicated elements: run conservation stress tests; crashes: use-after-free in reclamation — ASan, epoch/hazard libraries; hangs: livelock in CAS loops under heavy contention — back-off.

Performance and Scalability Implications

Both stacks serialise on one hot location (the head or the mutex); lock-free avoids blocking but not contention. Scalable structures distribute contention (striping, elimination arrays, per-thread buffers).

Security Considerations

Use-after-free in concurrent structures is exploitable; prefer memory-safe languages or audited libraries for anything handling untrusted input.

Platform and Runtime Caveats

Java/C#/Go structures rely on GC for reclamation; C++ code needs hazard pointers (C++26), epochs or RCU libraries; Rust has crossbeam-epoch. Iterator semantics differ by container — read the documentation.

Real-World Applications

ConcurrentHashMap in every Java service, Caffeine caches, the LMAX Disruptor, Go's runtime scheduler deques, the Linux kernel's RCU-protected lists, allocator free lists.

Best Practices

Use standard concurrent containers; avoid custom lock-free code.

Specify iteration semantics and composite-operation atomicity in APIs.

Stress test with conservation invariants; check linearizability for custom structures.

Pad hot fields; measure contention.

Exercises

E1 · Beginner. Why is if (!map.containsKey(k)) map.put(k, v) wrong even on a ConcurrentHashMap?

Answer: The two calls are individually atomic but not together; another thread can insert between them. Use putIfAbsent/computeIfAbsent.

E2 · Intermediate. Identify the linearization points of Treiber push and pop.

Answer: The successful compare_exchange on head in each operation (for pop on an empty stack, the load that observed nullptr).

E3 · Advanced challenge. Explain how hazard pointers make Treiber pop safe to free nodes.

Answer: Before dereferencing h->next, a thread publishes h in its hazard slot and re-checks that head still equals h; after popping, the node is retired, and a reclaimer frees retired nodes only if no thread's hazard slot contains them — so no thread can be reading a freed node, and an address cannot be reused while protected (preventing ABA on it).

Quiz

? What is the key difference between linearizability and sequential consistency?
+ Linearizability also respects real-time order between non-overlapping operations. :: Sequential consistency only respects per-thread order.
- Sequential consistency is stronger. :: It is weaker.
- They are identical. :: Real-time order distinguishes them.
- Linearizability applies only to locks. :: It applies to any concurrent object.

? Why are nodes never freed in the Treiber demo?
+ Without a reclamation scheme, freeing could cause use-after-free and ABA. :: Hazard pointers or epochs are needed.
- Atomics cannot point to freed memory. :: They can — that is the danger.
- The stack is too small. :: Unrelated.
- C++ forbids freeing atomics. :: It does not.

? Which iterator behaviors exist in Java? (select all that apply)
+ Fail-fast (ArrayList) :: Throws ConcurrentModificationException.
+ Snapshot (CopyOnWriteArrayList) :: Iterates the array at iterator creation.
+ Weakly consistent (ConcurrentHashMap) :: No exception; may see some changes.
- Fully serialisable with automatic locking of the whole map :: Not provided by these iterators.

Summary

Thread-safe structures guard every operation; concurrent structures allow parallel progress through striping or lock-free algorithms. Linearizability is the correctness target; CAS loops, ABA defences and safe reclamation are the lock-free toolkit; iteration semantics must be specified; stress tests and linearizability checkers verify. Prefer the standard library's structures.