Posix

POSIX (Portable Operating System Interface) provides a standardized set of synchronization primitives for multi-threaded programming in C/C++ through the pthread library. These primitives include mutexes, condition variables, semaphores, barriers, read-write locks, and spinlocks. On Linux, many of these primitives are implemented using the futex (Fast Userspace Mutex) system call to optimize performance by avoiding unnecessary kernel transitions.

Mutexes (pthread_mutex_t)

How Mutexes Work

A mutex (Mutual Exclusion) is a binary lock used to synchronize access to shared resources. When a thread acquires a mutex, other threads attempting to lock it are blocked until the mutex is released.

Types of POSIX Mutexes

• Normal Mutex: Deadlocks if the same thread locks it twice.
• Recursive Mutex: Allows the same thread to lock it multiple times, requiring equivalent unlocks.
• Error-Checking Mutex: Returns an error code if the same thread tries to relock.

Implementation with Futexes

When a thread calls pthread_mutex_lock():

• The mutex’s internal futex word is checked and updated using an atomic compare-and-swap operation.
• On success, the lock is acquired without a syscall.
• On contention, the thread calls futex(FUTEX_WAIT, 1) to block until the lock is released.
• When unlocked, pthread_mutex_unlock() uses futex(FUTEX_WAKE, 1) to wake one waiting thread.

// Attempt to acquire the lock
if (__sync_bool_compare_and_swap(&futex_word, 0, 1)) {
    // Lock acquired successfully
} else {
    // Contention: enter a blocking state using futex
    while (futex_word == 1) {
        futex(&futex_word, FUTEX_WAIT, 1, NULL, NULL, 0);
    }
}

Condition Variables (pthread_cond_t)

Purpose and Use

Condition variables allow threads to wait for specific conditions to become true, typically in conjunction with mutexes. Threads can wait (pthread_cond_wait) or signal (pthread_cond_signal, pthread_cond_broadcast) to wake up waiting threads.

How They Use Futexes

• pthread_cond_wait() typically releases the associated mutex and calls futex(FUTEX_WAIT) to block the thread.
• pthread_cond_signal() uses futex(FUTEX_WAKE, 1) to wake a single thread, while pthread_cond_broadcast() wakes all waiting threads.

Semaphores (sem_t)

Types of Semaphores

• Binary Semaphore: Similar to a mutex, but without ownership semantics.
• Counting Semaphore: Allows N resources to be acquired concurrently.

Implementation with Futexes

• Semaphore’s internal counter is modified atomically.
• When resources are unavailable, threads block using futex(FUTEX_WAIT).
• Posting (releasing) to the semaphore uses futex(FUTEX_WAKE) with the number of threads to wake.

// Wait on semaphore
while (atomic_decrement_if_greater_than_zero(&sem_count) < 0) {
    futex(&sem_count, FUTEX_WAIT, 0, NULL, NULL, 0);
}

Barriers (pthread_barrier_t)

What Barriers Do

Barriers synchronize multiple threads at specific points, ensuring that all threads reach the barrier before any proceed.

How Futexes Are Used

• Internal counter tracks the number of threads that have arrived.
• When the count matches the thread target, all threads are released using futex(FUTEX_WAKE, INT_MAX).

Read-Write Locks (pthread_rwlock_t)

How They Work

• Read locks allow multiple threads to simultaneously access a resource.
• Write locks provide exclusive access, blocking both readers and writers.

Implementation Strategy

• Readers increment a counter without syscalls unless contention occurs.
• Writers use futexes to wait until all readers exit and block new readers.

Spinlocks (pthread_spinlock_t)

What Spinlocks Do

• Spinlocks continuously poll the lock variable until it becomes available, avoiding kernel intervention.
• They are fast under low contention but waste CPU cycles if contention is high.

Use Cases

• Ideal for short critical sections or when the lock is expected to be released quickly.

while (__sync_lock_test_and_set(&lock, 1)) {
    // Spin until the lock is available
}

Performance Considerations

When to Use Which Primitive

• Mutexes: General-purpose mutual exclusion.
• Condition Variables: When threads need to wait for conditions.
• Semaphores: For resource counting and producer-consumer scenarios.
• Barriers: To synchronize thread phases.
• Read-Write Locks: When read-heavy workloads need concurrent access.
• Spinlocks: For short critical sections with low contention.

Futex Optimization

• Avoids syscalls in uncontended cases, reducing context switch overhead.
• Efficiently manages sleeping threads when contention occurs using FUTEX_WAIT and FUTEX_WAKE.