Concurrent Data Structures

A Rust implementation of various lock-free and concurrent data structures, demonstrating different synchronization patterns and mutual exclusion algorithms.

Overview

This project implements a comprehensive collection of concurrent data structures and synchronization primitives used in multi-threaded programming. Each module demonstrates different approaches to handling concurrent access to shared data—from traditional locks to lock-free algorithms.

Project Structure

Synchronization Primitives

• clhlock.rs - Craig, Landin, and Hagersten (CLH) queue lock implementation
• mcslock.rs - MCS (Mellor-Crummey and Scott) queue lock implementation
• mcsparklock.rs - MCS parking lot lock variant
• ticketlock.rs - Ticket lock (fairness-based mutual exclusion)
• prosem.rs - Parking lot-based semaphore implementation

Concurrent Data Structures

• lockfreelist.rs - Lock-free linked list using atomic operations and epoch-based memory reclamation
• treiberstack.rs - Treiber's lock-free stack using compare-and-swap (CAS) operations
• msqueue.rs - Michael & Scott's lock-free queue

Utilities & Examples

• memord.rs - Memory ordering and synchronization primitives
• linearzibility.rs - Linearizability testing utilities
• crossbeam_example.rs - Examples using the crossbeam crate for epoch-based reclamation
• locklink.rs - Lock-link utilities

Key Concepts

Lock-Free Algorithms

These data structures use atomic operations and careful synchronization to avoid traditional locks:

• Compare-and-swap (CAS) operations
• Atomic references
• Epoch-based memory reclamation (via crossbeam_epoch)

Queue-Based Locks

Traditional mutual exclusion algorithms that queue waiting threads:

• CLH Lock: Efficient for NUMA systems
• MCS Lock: Cache-friendly queue-based lock
• Ticket Lock: Simple, fair mutual exclusion

Memory Ordering

Proper memory ordering semantics for lock-free programming using Rust's std::sync::atomic module.

Building

cargo build

Running

cargo run

The main execution runs the lock-free list example by default. Modify main.rs to test different data structures.

Dependencies

• crossbeam - Provides epoch-based memory reclamation for safe lock-free structures
• std::sync::atomic - Atomic primitives for lock-free programming

Testing

This project focuses on concurrent algorithm implementation. For testing concurrent correctness:

cargo test

Learning Resources

These implementations are useful for understanding:

• Multi-threaded synchronization techniques
• Lock-free algorithm design
• Memory safety in concurrent code
• Performance characteristics of different locking strategies

Notes

• All implementations are designed to be thread-safe (Send and Sync traits properly implemented)
• Memory reclamation is handled through epoch-based methods (crossbeam) to prevent use-after-free bugs
• Some structures use unsafe code for performance; safety is ensured through proper synchronization

License

Educational project for concurrent programming study