CAS-Based Locks: From Spinlocks to Queue Locks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Basic Test-and-Set Spinlock
 
#include <stdatomic.h>
#include <stdbool.h>
 
typedef struct {
    atomic_bool locked;
} TASSpinlock;
 
void tas_spinlock_init(TASSpinlock* lock) {
    atomic_store(&lock->locked, false);
}
 
void tas_spinlock_acquire(TASSpinlock* lock) {
    // Spin until we successfully change locked from false to true
    while (atomic_exchange(&lock->locked, true)) {
        // atomic_exchange is essentially TAS: atomically swap in 'true'
        // Returns: previous value
        // If previous was 'true', lock was held - spin and retry
        // If previous was 'false', we just acquired it - exit loop
    }
    // We now hold the lock
}
 
void tas_spinlock_release(TASSpinlock* lock) {
    atomic_store(&lock->locked, false);
    // Lock is now available for others
}
 
/*
 * Analysis:
 * 
 * Correctness:
 * ✓ Mutual exclusion: Only thread that sees 'false' from TAS enters CS
 * ✓ Atomicity: TAS is hardware atomic, no race in acquire
 * 
 * Performance Problems:
 * ✗ Cache line bouncing: Every TAS attempt writes to the cache line
 * ✗ Bus saturation: Continuous TAS generates heavy memory traffic
 * ✗ Unfairness: No ordering guarantees; starvation possible
 * ✗ No backoff: Threads hammer the lock at max CPU speed
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// Test-and-Test-and-Set Spinlock
 
#include <stdatomic.h>
#include <stdbool.h>
 
typedef struct {
    atomic_bool locked;
} TTASSpinlock;
 
void ttas_spinlock_init(TTASSpinlock* lock) {
    atomic_store(&lock->locked, false);
}
 
void ttas_spinlock_acquire(TTASSpinlock* lock) {
    while (true) {
        // FIRST TEST: Spin on local cache reading
        // This loop generates no bus traffic after first cache miss
        while (atomic_load(&lock->locked)) {
            // Lock is held - spin locally on cached value
            // This read can be satisfied from our L1 cache
            // Other processors' caches also hold shared copy
            
            // Optional: Yield or pause to reduce power consumption
            // __builtin_ia32_pause();  // x86 PAUSE instruction
        }
        
        // Lock appears free - try to acquire
        // SECOND TEST: Attempt atomic TAS
        if (!atomic_exchange(&lock->locked, true)) {
            // TAS returned false - we successfully acquired
            return;
        }
        
        // TAS returned true - someone else grabbed it first
        // Loop back to spinning on reads
    }
}
 
void ttas_spinlock_release(TTASSpinlock* lock) {
    atomic_store(&lock->locked, false);
    // This write invalidates all cached copies
    // Spinning threads will see lock == false on next iteration
}
 
/*
 * Performance Analysis:
 * 
 * While lock held:
 * - All waiters spin on local cached reads
 * - NO memory bus traffic (after initial cache miss)
 * - Much better than TAS which writes on every iteration
 * 
 * When lock released:
 * - Release write invalidates all cached copies
 * - All waiters see lock==false and exit their read loop
 * - All waiters simultaneously attempt TAS (brief traffic burst)
 * - One wins, others see true from TAS and return to reading
 * 
 * Still unfair, but much less bus traffic during spinning
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

// TTAS Spinlock with Exponential Backoff
 
#include <stdatomic.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
 
#define MIN_BACKOFF 16
#define MAX_BACKOFF 8192
 
typedef struct {
    atomic_bool locked;
} BackoffSpinlock;
 
void backoff_spinlock_init(BackoffSpinlock* lock) {
    atomic_store(&lock->locked, false);
}
 
// Spin for approximately 'iterations' cycles
static inline void spin_wait(int iterations) {
    for (int i = 0; i < iterations; i++) {
        __builtin_ia32_pause();  // x86 PAUSE instruction
    }
}
 
void backoff_spinlock_acquire(BackoffSpinlock* lock) {
    int backoff = MIN_BACKOFF;
    
    while (true) {
        // TTAS: spin on local reads first
        while (atomic_load_explicit(&lock->locked, memory_order_relaxed)) {
            __builtin_ia32_pause();
        }
        
        // Try to acquire
        if (!atomic_exchange_explicit(&lock->locked, true, memory_order_acquire)) {
            return;  // Got the lock!
        }
        
        // Failed to acquire - back off before retrying
        // Random delay within [0, backoff) to prevent synchronization
        int delay = rand() % backoff;
        spin_wait(delay);
        
        // Exponential increase (with cap)
        if (backoff < MAX_BACKOFF) {
            backoff *= 2;
        }
    }
}
 
void backoff_spinlock_release(BackoffSpinlock* lock) {
    atomic_store_explicit(&lock->locked, false, memory_order_release);
}
 
/*
 * How backoff helps:
 * 
 * Without backoff (TTAS release):
 *   T1→ TAS ────────────────────────────
 *   T2→ TAS ────────────────────────────
 *   T3→ TAS ────────────────────────────
 *   (All simultaneously, cache line thrash)
 * 
 * With exponential backoff:
 *   T1→ TAS ─ wait(16) ─ TAS ─ wait(32) ─ TAS ──→ acquire
 *   T2→ TAS ─ wait(28) ─────── TAS ─ wait(56) ──→
 *   T3→ TAS ─ wait(10) ─ TAS ─ wait(45) ────────→
 *   (Spread out over time, less traffic)
 * 
 * Key insight: Randomness prevents threads from synchronizing
 * their retry attempts, which would defeat the purpose.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// Ticket Lock: FIFO-fair spinlock
 
#include <stdatomic.h>
#include <stdint.h>
 
typedef struct {
    atomic_uint ticket;     // Next ticket to hand out
    atomic_uint serving;    // Currently serving ticket number
} TicketLock;
 
void ticket_lock_init(TicketLock* lock) {
    atomic_store(&lock->ticket, 0);
    atomic_store(&lock->serving, 0);
}
 
void ticket_lock_acquire(TicketLock* lock) {
    // Take a ticket (atomic increment)
    // fetch_add returns the OLD value (our ticket number)
    unsigned int my_ticket = atomic_fetch_add(&lock->ticket, 1);
    
    // Wait until it's our turn
    while (atomic_load(&lock->serving) != my_ticket) {
        __builtin_ia32_pause();  // Spin-wait
    }
    
    // Our turn - acquire the lock
    // Memory barrier implicit in the acquire semantics
}
 
void ticket_lock_release(TicketLock* lock) {
    // Call the next number
    // No atomic needed if single writer (only holder writes serving)
    unsigned int current = atomic_load_explicit(&lock->serving, memory_order_relaxed);
    atomic_store(&lock->serving, current + 1);
}
 
/*
 * Properties:
 * 
 * ✓ Fair (FIFO): Threads acquire in order of arrival
 * ✓ Bounded waiting: With N waiters, at most N-1 will go before you
 * ✓ Simple: Just two counters
 * 
 * Performance:
 * - Acquire: O(1) for taking ticket + O(waiters) for spinning
 * - Release: O(1) increment
 * - All waiters spin on same 'serving' variable (cache contention)
 * 
 * When lock released:
 * - New 'serving' value invalidates all caches
 * - ALL waiters read new value
 * - Only ONE waiter's condition matches
 * - Still generates cache traffic, but only for reads
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

// MCS Queue Lock: Scalable spinlock with local spinning
 
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
 
typedef struct MCSNode {
    atomic_bool locked;              // Am I waiting?
    struct MCSNode* volatile next;   // Next waiter in queue
} MCSNode;
 
typedef struct {
    atomic_ptr(MCSNode*) tail;       // Tail of waiter queue
} MCSLock;
 
void mcs_lock_init(MCSLock* lock) {
    atomic_store(&lock->tail, NULL);
}
 
void mcs_lock_acquire(MCSLock* lock, MCSNode* my_node) {
    // Initialize my node
    my_node->next = NULL;
    my_node->locked = true;  // I'm waiting
    
    // Atomically append to queue, get predecessor
    MCSNode* predecessor = atomic_exchange(&lock->tail, my_node);
    
    if (predecessor != NULL) {
        // Queue wasn't empty - link myself and wait
        predecessor->next = my_node;
        
        // ════════════════════════════════════════════════════════
        // LOCAL SPINNING: I only spin on MY OWN node's flag
        // No cache coherence traffic from other waiters or releases
        // ════════════════════════════════════════════════════════
        while (atomic_load(&my_node->locked)) {
            __builtin_ia32_pause();
        }
    }
    // If predecessor was NULL, queue was empty - we have the lock
}
 
void mcs_lock_release(MCSLock* lock, MCSNode* my_node) {
    MCSNode* successor = my_node->next;
    
    if (successor == NULL) {
        // No known successor - try to atomically set tail to NULL
        MCSNode* expected = my_node;
        if (atomic_compare_exchange_strong(&lock->tail, &expected, NULL)) {
            // Successfully cleared tail - no one was waiting
            return;
        }
        
        // CAS failed: someone is in process of linking themselves
        // Wait for them to finish setting my_node->next
        while ((successor = my_node->next) == NULL) {
            __builtin_ia32_pause();
        }
    }
    
    // ════════════════════════════════════════════════════════
    // NOTIFY ONLY NEXT WAITER: O(1) cache invalidations
    // Compare to ticket lock: O(N) invalidations
    // ════════════════════════════════════════════════════════
    atomic_store(&successor->locked, false);
}
 
/*
 * Queue visualization:
 * 
 * Initially: tail→NULL
 * After T1 acquires:
 *   tail→[T1: locked=false, next=NULL]
 * After T2, T3 enqueue:
 *   tail─────────────────────────────→[T3]
 *   [T1: locked=false, next→] [T2: locked=true, next→] [T3: locked=true, next=NULL]
 * 
 * When T1 releases:
 *   - T1 sets T2->locked = false
 *   - ONLY T2's cache is invalidated
 *   - T3 never sees any traffic (still spinning on T3->locked)
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// Simplified CAS-Based Mutex with Blocking
 
#include <stdatomic.h>
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
 
// Lock states
#define UNLOCKED    0
#define LOCKED      1
#define CONTENDED   2   // Locked with waiters
 
typedef struct {
    atomic_int state;
} Mutex;
 
void mutex_init(Mutex* m) {
    atomic_store(&m->state, UNLOCKED);
}
 
void mutex_lock(Mutex* m) {
    int expected = UNLOCKED;
    
    // Fast path: Try to acquire uncontended lock
    if (atomic_compare_exchange_strong(&m->state, &expected, LOCKED)) {
        return;  // Got it immediately!
    }
    
    // Slow path: Lock is held
    // Try to spin briefly first
    for (int i = 0; i < SPIN_COUNT; i++) {
        expected = UNLOCKED;
        if (atomic_compare_exchange_weak(&m->state, &expected, LOCKED)) {
            return;  // Got it after spinning
        }
        __builtin_ia32_pause();
    }
    
    // Still can't get it - time to sleep
    while (true) {
        // Mark as contended (so holder knows to wake us)
        if (atomic_exchange(&m->state, CONTENDED) == UNLOCKED) {
            // Oops, it just became unlocked! We have it now.
            return;
        }
        
        // Sleep until state changes (using Linux futex)
        // FUTEX_WAIT: If state still equals CONTENDED, sleep
        syscall(SYS_futex, &m->state, FUTEX_WAIT, CONTENDED, NULL, NULL, 0);
        
        // Woken up - try to acquire again
        expected = UNLOCKED;
        if (atomic_compare_exchange_strong(&m->state, &expected, CONTENDED)) {
            return;  // Got it!
        }
        // Someone else got it first, go back to sleep
    }
}
 
void mutex_unlock(Mutex* m) {
    // Atomically check state and unlock
    int old_state = atomic_exchange(&m->state, UNLOCKED);
    
    if (old_state == CONTENDED) {
        // There are waiters - wake one up
        syscall(SYS_futex, &m->state, FUTEX_WAKE, 1, NULL, NULL, 0);
    }
    // If old_state was LOCKED (not CONTENDED), no waiters - just return
}
 
/*
 * State transitions:
 * 
 * UNLOCKED ──CAS──→ LOCKED      (uncontended acquisition)
 * LOCKED ──XCHG──→ CONTENDED    (waiter arriving)
 * CONTENDED ──CAS──→ CONTENDED  (waiter acquiring)
 * CONTENDED ──XCHG──→ UNLOCKED  (release, wake waiter)
 * LOCKED ──XCHG──→ UNLOCKED     (release, no waiters)
 * 
 * Key insight: CONTENDED state tells unlock() to wake waiters
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// Simple CAS-Based Reader-Writer Lock
 
#include <stdatomic.h>
#include <stdint.h>
 
// State encoding:
// Bits 0-30: Reader count
// Bit 31: Writer active flag
#define WRITER_BIT   0x80000000
#define READER_MASK  0x7FFFFFFF
 
typedef struct {
    atomic_uint state;
} RWLock;
 
void rwlock_init(RWLock* rw) {
    atomic_store(&rw->state, 0);
}
 
void rwlock_read_lock(RWLock* rw) {
    while (true) {
        unsigned int old_state = atomic_load(&rw->state);
        
        // Can't acquire read lock if writer is active or waiting
        if (old_state & WRITER_BIT) {
            __builtin_ia32_pause();
            continue;
        }
        
        // Try to increment reader count
        unsigned int new_state = old_state + 1;
        if (atomic_compare_exchange_weak(&rw->state, &old_state, new_state)) {
            return;  // Got read lock
        }
        // CAS failed, retry
    }
}
 
void rwlock_read_unlock(RWLock* rw) {
    // Decrement reader count
    atomic_fetch_sub(&rw->state, 1);
}
 
void rwlock_write_lock(RWLock* rw) {
    while (true) {
        unsigned int old_state = atomic_load(&rw->state);
        
        // Can only acquire if no readers and no writer
        if (old_state != 0) {
            __builtin_ia32_pause();
            continue;
        }
        
        // Try to set writer bit
        if (atomic_compare_exchange_weak(&rw->state, &old_state, WRITER_BIT)) {
            return;  // Got write lock
        }
        // CAS failed, retry
    }
}
 
void rwlock_write_unlock(RWLock* rw) {
    // Clear writer bit
    atomic_store(&rw->state, 0);
}
 
/*
 * Issues with this simple implementation:
 * 
 * 1. Writer starvation: Continuous readers prevent writers forever
 * 2. No fairness: New readers can keep jumping ahead of waiting writers
 * 3. Scalability: All readers CAS on same location (contention)
 * 
 * Production RWLocks are significantly more complex to address these
 */