Course contentsShow
← Computer Science
Lesson 2581 of 2,87257. Concurrency FundamentalsFree lesson

Concurrent Stack Implementations

Implementing thread-safe stacks using lock-based and lock-free approaches with Treiber's algorithm.

Concurrent Stack Implementations

You'll learn how to build thread-safe stacks using both lock-based synchronization and lock-free algorithms like Treiber's.

The Core Challenge

A stack is conceptually simple: push items onto the top, pop them off the top (LIFO). But when multiple threads try to push or pop simultaneously, you face race conditions. Two threads might read the same "top" pointer, both try to update it, and one update gets lost—corrupting your stack.

Lock-Based Approach

The straightforward solution wraps a regular stack with a mutex (lock). Every push or pop operation acquires the lock, modifies the stack, then releases it. This guarantees mutual exclusion—only one thread modifies the structure at a time.

Pros: Simple to reason about, guaranteed correctness.
Cons: Lock contention creates bottlenecks; threads wait even when operations wouldn't actually conflict.

Treiber's Lock-Free Stack

The elegant alternative is Treiber's algorithm, which uses atomic compare-and-swap (CAS) operations:

  1. Push: Read current top pointer, create a new node pointing to it, then CAS top to your new node (retry if someone else changed top first)
  2. Pop: Read top, read its next pointer, then CAS top to next (retry on conflict)

No locks needed! Threads make optimistic attempts and retry on collision. This eliminates lock overhead but introduces ABA problem risks (requiring hazard pointers or epoch-based reclamation for safe memory management).

Choosing Your Approach

Lock-based is simpler and sufficient for moderate contention. Lock-free shines under high contention where avoiding blocking matters—but adds complexity around memory reclamation.

Key Takeaway: Thread-safe stacks can be built with locks for simplicity or lock-free CAS operations (Treiber's algorithm) for better scalability, each trading off implementation complexity against contention performance.