Synchronization¶

Overview¶

Synchronization mechanisms coordinate access to shared resources and prevent race conditions in concurrent systems.

Mutex (Mutual Exclusion)¶

A mutex ensures that only one thread/process can access a shared resource at a time.

Implementation¶

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&mutex);
// Critical section
pthread_mutex_unlock(&mutex);

// Or use trylock
if (pthread_mutex_trylock(&mutex) == 0) {
    // Got lock
    pthread_mutex_unlock(&mutex);
}

How Mutexes Work¶

Conceptual:

mutex = 0 (unlocked) or 1 (locked)

lock():
  while (mutex == 1)
    wait
  mutex = 1

unlock():
  mutex = 0
  wake_one_waiter()

Actual implementation uses:

Atomic instructions (CMPXCHG on x86)
Futex system call (fast user-space mutex)
Wait queues in kernel

Futex (Fast Userspace Mutex)¶

Linux mutexes use futex for efficiency:

Uncontended case: Atomic operation in user space (fast)
Contended case: System call to kernel (slow)

// Simplified futex usage
int futex_val = 0;

// Lock
while (__sync_val_compare_and_swap(&futex_val, 0, 1) != 0) {
    futex(&futex_val, FUTEX_WAIT, 1, NULL);
}

// Unlock
futex_val = 0;
futex(&futex_val, FUTEX_WAKE, 1);

Mutex Types¶

Normal: No deadlock detection Recursive: Same thread can lock multiple times Error-checking: Detects deadlocks, errors

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
pthread_mutex_init(&mutex, &attr);

Semaphores¶

A semaphore is a counter that coordinates access to resources.

Binary Semaphore¶

Acts like a mutex (value 0 or 1).

sem_t sem;
sem_init(&sem, 0, 1);  // pshared=0, value=1

sem_wait(&sem);   // Decrement (wait if 0)
// Critical section
sem_post(&sem);   // Increment

sem_destroy(&sem);

Counting Semaphore¶

Allows multiple accesses (value >= 0).

// Limit concurrent accesses to 3
sem_t sem;
sem_init(&sem, 0, 3);

sem_wait(&sem);   // One of 3 slots
// Use resource
sem_post(&sem);   // Release slot

Semaphore vs Mutex¶

Feature	Mutex	Semaphore
Ownership	Yes (lock/unlock by same thread)	No (any thread can post)
Use case	Mutual exclusion	Signaling, resource counting
Value	Binary (locked/unlocked)	Integer (0 to N)
Typical use	Protect data	Control access count

Deadlock¶

Deadlock occurs when processes wait indefinitely for each other.

Four Necessary Conditions¶

All four must be true for deadlock:

Mutual Exclusion: Resource can't be shared
Hold and Wait: Process holds resources while waiting for more
No Preemption: Resources can't be forcibly taken
Circular Wait: Circular chain of waiting

// Deadlock example
Thread 1:              Thread 2:
lock(mutex_A);         lock(mutex_B);
lock(mutex_B);         lock(mutex_A);  // DEADLOCK

Deadlock Prevention¶

Break one of the four conditions:

1. Eliminate Circular Wait - Resource Ordering

// Always acquire locks in same order
lock(mutex_A);
lock(mutex_B);
// Both threads follow same order

2. Hold and Wait - All or Nothing

// Acquire all locks at once
lock_all([mutex_A, mutex_B]);
// Or release all if can't acquire all

3. Allow Preemption - Timeouts

if (pthread_mutex_timedlock(&mutex, &timeout) != 0) {
    // Release held locks and retry
}

Deadlock Detection¶

# Detect deadlocks using tools
gdb --batch --ex "thread apply all bt" --pid <PID>
pstack <PID>

# Monitor lock contention
perf record -e syscalls:sys_enter_futex -p <PID>

Livelock¶

Processes are active but make no progress.

Example¶

// Both threads keep trying to be polite
Thread 1:              Thread 2:
while (true) {         while (true) {
  if (mutex2_locked)     if (mutex1_locked)
    unlock(mutex1);        unlock(mutex2);
  lock(mutex1);          lock(mutex2);
}                      }
// Both keep backing off for each other

Livelock vs Deadlock¶

Feature	Deadlock	Livelock
State	Blocked/waiting	Running/active
CPU usage	Low	High
Detection	Easier (processes blocked)	Harder (processes running)
Resolution	Break circular wait	Add randomness/backoff

Race Conditions¶

Race condition occurs when behavior depends on timing of events.

Example¶

// Race condition: lost update
int counter = 0;

Thread 1:              Thread 2:
int tmp = counter;     int tmp = counter;
tmp++;                 tmp++;
counter = tmp;         counter = tmp;
// Final counter = 1, not 2!

Solution: Atomic operations or locks

// Solution 1: Mutex
pthread_mutex_lock(&mutex);
counter++;
pthread_mutex_unlock(&mutex);

// Solution 2: Atomic operation
__sync_fetch_and_add(&counter, 1);

Common Race Condition Patterns¶

Check-Then-Act

// UNSAFE
if (file_exists("config.txt")) {
    open("config.txt");  // File might be deleted here!
}

// SAFE
int fd = open("config.txt", O_RDONLY);
if (fd >= 0) {
    // Use fd
}

Read-Modify-Write

// UNSAFE
balance = get_balance();
balance += 100;
set_balance(balance);

// SAFE
lock();
balance = get_balance();
balance += 100;
set_balance(balance);
unlock();

Spinlocks vs Mutexes¶

Spinlock¶

Busy-waits (loops) while trying to acquire lock.

while (__sync_lock_test_and_set(&lock, 1)) {
    while (lock) {
        // Spin (waste CPU)
    }
}
// Critical section
__sync_lock_release(&lock);

Characteristics:

No system call (fast if wait is short)
Wastes CPU while spinning
Good for very short critical sections
Used in kernel extensively

Mutex¶

Sleeps (blocks) while waiting for lock.

Characteristics:

System call when contended (slower)
Doesn't waste CPU
Good for longer critical sections
Used in user space

Comparison¶

Feature	Spinlock	Mutex
Wait method	Busy-wait	Sleep
CPU usage	High	Low
Context switch	No	Yes
Best for	<100μs	>100μs
Use case	Kernel, very short sections	User space, longer sections

Condition Variables¶

Allows threads to wait for specific conditions.

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;

// Waiter
pthread_mutex_lock(&mutex);
while (!ready) {
    pthread_cond_wait(&cond, &mutex);  // Atomically unlocks mutex and waits
}
// Condition is true, mutex is locked
pthread_mutex_unlock(&mutex);

// Signaler
pthread_mutex_lock(&mutex);
ready = 1;
pthread_cond_signal(&cond);  // or pthread_cond_broadcast(&cond)
pthread_mutex_unlock(&mutex);

Why use while loop?

Spurious wakeups
Condition might change before reacquiring mutex
Multiple waiters

Reader-Writer Locks¶

Multiple readers or one writer, but not both.

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;

// Reader
pthread_rwlock_rdlock(&rwlock);
// Read data
pthread_rwlock_unlock(&rwlock);

// Writer
pthread_rwlock_wrlock(&rwlock);
// Write data
pthread_rwlock_unlock(&rwlock);

Characteristics:

Multiple concurrent readers
Exclusive writer access
Good for read-heavy workloads

Atomic Operations¶

CPU-level atomic instructions for lock-free programming.

GCC Built-ins¶

// Atomic increment
int val = 0;
__sync_fetch_and_add(&val, 1);

// Compare and swap
int expected = 0;
bool success = __sync_bool_compare_and_swap(&val, expected, 1);

// Memory barriers
__sync_synchronize();

C11 Atomics¶

#include <stdatomic.h>

atomic_int counter = 0;
atomic_fetch_add(&counter, 1);

int expected = 0;
atomic_compare_exchange_strong(&counter, &expected, 1);

Memory Ordering¶

Memory Barriers¶

Prevent reordering of memory operations.

Types:

Compiler barriers: Prevent compiler reordering
CPU barriers: Prevent CPU reordering

// Compiler barrier
asm volatile("" ::: "memory");

// Full memory barrier
__sync_synchronize();

Ordering Models¶

Sequential consistency: Strictest, slowest
Acquire-release: Medium
Relaxed: Weakest, fastest

Practice Questions¶

What is the difference between a mutex and a semaphore?
Explain the four conditions necessary for deadlock.
How do you prevent deadlock?
What is a race condition and how do you prevent it?
When would you use a spinlock vs a mutex?
Why must pthread_cond_wait be in a while loop?
What is a futex and why is it fast?
Explain the difference between deadlock and livelock.

Synchronization¶

Overview¶

Mutex (Mutual Exclusion)¶

Implementation¶

How Mutexes Work¶

Futex (Fast Userspace Mutex)¶

Mutex Types¶

Semaphores¶

Binary Semaphore¶

Counting Semaphore¶

Semaphore vs Mutex¶

Deadlock¶

Four Necessary Conditions¶

Deadlock Prevention¶

Deadlock Detection¶

Livelock¶

Example¶

Livelock vs Deadlock¶

Race Conditions¶

Example¶

Common Race Condition Patterns¶

Spinlocks vs Mutexes¶

Spinlock¶

Mutex¶

Comparison¶

Condition Variables¶

Reader-Writer Locks¶

Atomic Operations¶

GCC Built-ins¶

C11 Atomics¶

Memory Ordering¶

Memory Barriers¶

Ordering Models¶

Practice Questions¶

Further Reading¶