Lock-Free Programming Patterns and Insights¶

Executive Summary¶

Through extensive testing and debugging of Queue, Stack, and Array implementations across C, C++, and Python, we've identified critical patterns for correct lock-free programming in shared memory contexts.

Core Insights¶

1. The Fundamental Race Condition¶

Problem: In our initial implementation, we updated the index (tail/head) BEFORE writing/reading data:

// WRONG - Race condition!
CAS(&tail, current, next);  // Other threads now see new tail
data[current] = value;       // But data isn't written yet!

Solution: We need atomic reservation followed by data operation:

// CORRECT - Reserve slot atomically
CAS(&tail, current, next);  // Reserve slot
data[current] = value;       // Write to reserved slot
fence(release);              // Ensure visibility

2. Memory Ordering Requirements¶

For lock-free MPMC (Multiple Producer Multiple Consumer) queues/stacks:

Push/Enqueue Pattern:¶

1. Reserve slot: Use relaxed or acquire-release CAS
2. Write data: Standard memory write
3. Release fence: Ensure data is visible before next operation

Pop/Dequeue Pattern:¶

1. Reserve slot: Use acquire-release CAS
2. Acquire fence: Ensure we see complete data
3. Read data: Standard memory read

3. The ABA Problem¶

Issue: A value changes from A→B→A between observations, causing CAS to succeed incorrectly.

Solutions: - Bounded arrays: Our implementation uses indices into fixed arrays, avoiding pointer reuse - Tagged pointers: Could add version numbers (not needed for our design) - Hazard pointers: For dynamic allocation (not applicable here)

4. Circular Buffer Subtlety¶

Circular buffers require one empty slot to distinguish full from empty: - Empty: head == tail - Full: (tail + 1) % capacity == head

This means a capacity-N buffer holds N-1 items maximum.

5. Language-Specific Considerations¶

C/C++¶

• True lock-free with atomic operations
• Memory fences critical for correctness
• Compiler optimizations can reorder without proper barriers

Python¶

• GIL prevents true parallelism in threads
• Use threading.Lock() for correctness
• Multiprocessing achieves true parallelism but with IPC overhead

Validated Patterns¶

Pattern 1: Lock-Free Ring Buffer Queue¶

typedef struct {
    _Atomic uint32_t head;
    _Atomic uint32_t tail;
    uint32_t capacity;
    // data follows
} queue_header_t;

// Push (MPMC)
int push(queue_t* q, value_t value) {
    uint32_t current_tail, next_tail;
    do {
        current_tail = atomic_load(&q->tail);
        next_tail = (current_tail + 1) % q->capacity;
        if (next_tail == atomic_load(&q->head))
            return FULL;
    } while (!CAS(&q->tail, current_tail, next_tail));

    q->data[current_tail] = value;
    atomic_thread_fence(memory_order_release);
    return OK;
}

Pattern 2: Lock-Free Stack¶

typedef struct {
    _Atomic int32_t top;  // -1 when empty
    uint32_t capacity;
    // data follows
} stack_header_t;

// Push
int push(stack_t* s, value_t value) {
    int32_t current_top, new_top;
    do {
        current_top = atomic_load(&s->top);
        if (current_top >= capacity - 1)
            return FULL;
        new_top = current_top + 1;
    } while (!CAS(&s->top, current_top, new_top));

    s->data[new_top] = value;
    atomic_thread_fence(memory_order_release);
    return OK;
}

Pattern 3: Shared Memory Layout¶

[Table Header][Table Entries][Structure 1][Structure 2]...[Structure N]
     Fixed         Fixed         Dynamic      Dynamic         Dynamic

Testing Insights¶

Stress Test Requirements¶

1. Concurrent operations: 16+ threads minimum
2. High contention: Small queue (10 slots) with many threads
3. Checksum validation: Sum all produced/consumed values
4. Long duration: 10,000+ operations per thread
5. Memory barriers: Test with TSan or Helgrind

Critical Test Cases¶

• Basic correctness (empty, single item, full)
• FIFO/LIFO ordering
• Producer-consumer balance
• High contention on small structures
• Rapid create/destroy cycles
• Cross-process access
• Memory boundary conditions

Recommendations for Future Data Structures¶

1. HashMap/HashSet¶

• Use open addressing with linear probing
• CAS for claiming slots
• Tombstones for deletion
• Consider Robin Hood hashing for better distribution

2. Priority Queue (Heap)¶

• Challenge: Maintaining heap property atomically
• Consider skip list as alternative
• Or use sharded heaps with per-shard locks

3. B-Tree¶

• Node-level locking more practical than lock-free
• Consider B-link trees for concurrent access
• Read-copy-update (RCU) for read-heavy workloads

4. Graph Structures¶

• Edge list representation most amenable to lock-free
• Adjacency lists challenging without garbage collection
• Consider epoch-based reclamation

Performance Characteristics¶

From our benchmarks:

Common Pitfalls to Avoid¶

1. Writing data after index update: Creates visibility race
2. Missing memory fences: Compiler/CPU reordering
3. Incorrect empty/full checks: Off-by-one errors
4. ABA vulnerability: When reusing memory
5. Assuming atomicity: Multi-word updates aren't atomic
6. Overflow handling: Index wraparound must be correct

Conclusion¶

Lock-free programming requires careful attention to: - Atomic operations and their memory ordering - Data visibility across threads - Race condition prevention - Thorough testing under high concurrency

The patterns validated here provide a solid foundation for implementing additional lock-free data structures in shared memory contexts.