Implement advanced pthread synchronization primitives

Open pbalduino opened this issue 4 months ago • 1 comments

Goal

Implement advanced POSIX threading synchronization primitives including barriers, spinlocks, and reader-writer locks to provide complete pthread synchronization support.

Context

With basic pthread API implemented (Issue #109), we need to add advanced synchronization primitives that many applications rely on. These provide efficient coordination mechanisms for complex multithreaded applications and are part of the full POSIX threading specification.

Definition of Done

pthread_barrier_t: Thread barriers for synchronizing groups of threads
pthread_spinlock_t: Spin locks for short critical sections
pthread_rwlock_t: Reader-writer locks for shared/exclusive access
pthread_once_t: One-time initialization mechanism
Robust mutexes: pthread_mutex with robustness attributes
Process-shared synchronization: Synchronization across process boundaries
Timeout variants: Timed versions of synchronization operations
Priority inheritance: Advanced mutex features for real-time systems

pthread_barrier_t Implementation

typedef struct {
    pthread_mutex_t mutex;      // Protects barrier state
    pthread_cond_t condition;   // Condition variable for waiting
    unsigned int count;         // Number of threads required
    unsigned int waiting;       // Number of threads currently waiting
    unsigned int generation;    // Generation counter for reuse
    int initialized;            // Initialization flag
} pthread_barrier_t;

typedef struct {
    int pshared;               // Process-shared attribute
} pthread_barrierattr_t;

// Barrier operations
int pthread_barrier_init(pthread_barrier_t *barrier,
                        const pthread_barrierattr_t *attr,
                        unsigned count);
int pthread_barrier_destroy(pthread_barrier_t *barrier);
int pthread_barrier_wait(pthread_barrier_t *barrier);

// Barrier attributes
int pthread_barrierattr_init(pthread_barrierattr_t *attr);
int pthread_barrierattr_destroy(pthread_barrierattr_t *attr);
int pthread_barrierattr_setpshared(pthread_barrierattr_t *attr, int pshared);
int pthread_barrierattr_getpshared(const pthread_barrierattr_t *attr, int *pshared);

pthread_spinlock_t Implementation

typedef struct {
    volatile int lock;         // Spin lock state (0=unlocked, 1=locked)
    int pshared;              // Process-shared flag
} pthread_spinlock_t;

// Spinlock operations
int pthread_spin_init(pthread_spinlock_t *lock, int pshared);
int pthread_spin_destroy(pthread_spinlock_t *lock);
int pthread_spin_lock(pthread_spinlock_t *lock);
int pthread_spin_trylock(pthread_spinlock_t *lock);
int pthread_spin_unlock(pthread_spinlock_t *lock);

pthread_rwlock_t Implementation

typedef struct {
    pthread_mutex_t mutex;     // Protects rwlock state
    pthread_cond_t read_cond;  // Condition for readers
    pthread_cond_t write_cond; // Condition for writers
    int readers;               // Number of active readers
    int writers;               // Number of active writers (0 or 1)
    int waiting_readers;       // Number of waiting readers
    int waiting_writers;       // Number of waiting writers
    int prefer_writers;        // Writer preference flag
} pthread_rwlock_t;

typedef struct {
    int pshared;              // Process-shared attribute
    int kind;                 // Reader/writer preference
} pthread_rwlockattr_t;

// Reader-writer lock operations
int pthread_rwlock_init(pthread_rwlock_t *rwlock,
                       const pthread_rwlockattr_t *attr);
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);
int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock,
                              const struct timespec *abstime);
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock,
                              const struct timespec *abstime);
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);

// Reader-writer lock attributes
int pthread_rwlockattr_init(pthread_rwlockattr_t *attr);
int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr);
int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared);
int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t *attr, int *pshared);
int pthread_rwlockattr_setkind_np(pthread_rwlockattr_t *attr, int pref);
int pthread_rwlockattr_getkind_np(const pthread_rwlockattr_t *attr, int *pref);

pthread_once_t Implementation

typedef struct {
    volatile int state;        // Initialization state
    pthread_mutex_t mutex;     // Protects initialization
} pthread_once_t;

#define PTHREAD_ONCE_INIT { 0, PTHREAD_MUTEX_INITIALIZER }

// One-time initialization
int pthread_once(pthread_once_t *once_control, void (*init_routine)(void));

Robust Mutexes

// Extended mutex attributes for robustness
int pthread_mutexattr_setrobust(pthread_mutexattr_t *attr, int robust);
int pthread_mutexattr_getrobust(const pthread_mutexattr_t *attr, int *robust);

// Robust mutex operations
int pthread_mutex_consistent(pthread_mutex_t *mutex);

// Robustness values
#define PTHREAD_MUTEX_STALLED    0
#define PTHREAD_MUTEX_ROBUST     1

Timed Synchronization Operations

// Timed mutex operations
int pthread_mutex_timedlock(pthread_mutex_t *mutex,
                           const struct timespec *abstime);

// Timed condition variable operations  
int pthread_cond_timedwait(pthread_cond_t *cond,
                          pthread_mutex_t *mutex,
                          const struct timespec *abstime);

// Timed barrier operations
int pthread_barrier_timedwait(pthread_barrier_t *barrier,
                             const struct timespec *abstime);

Implementation Details

Spinlock Implementation

Use atomic compare-and-swap for lock acquisition
CPU pause instructions for reduced power consumption
Backoff strategies for contention reduction
Process-shared spinlock support using shared memory

Barrier Implementation

Generation-based barrier for reuse without destruction
Efficient wakeup of all waiting threads
Support for different barrier counts
Process-shared barriers using shared memory

Reader-Writer Lock Implementation

Fair scheduling between readers and writers
Configurable reader/writer preference policies
Efficient reader-only fast path
Deadlock prevention mechanisms

Robust Mutex Support

Detection of owner thread termination
Automatic mutex state recovery
Consistent state management across failures
Integration with pthread cleanup handlers

Performance Optimizations

Spinlock Optimizations

Adaptive spinning based on system load
NUMA-aware spinlock placement
Cache-line aligned spinlock structures
Exponential backoff for reduced contention

RWLock Optimizations

Fast path for uncontended readers
Batched reader wakeup for efficiency
Writer starvation prevention
Cache-friendly data structure layout

Barrier Optimizations

Tree-based barrier algorithms for scalability
Sense-reversing barriers for reuse efficiency
NUMA-aware barrier implementation
Hardware synchronization primitive usage

Testing Strategy

Barrier synchronization correctness testing
Spinlock performance and correctness validation
Reader-writer lock fairness and correctness testing
Robust mutex recovery testing
Timed operation timeout validation
Process-shared synchronization testing
Stress testing under high contention

Dependencies

Basic pthread API: Issue #109 - Core threading and mutex support
Kernel threading: Issue #108 - Thread management infrastructure
Shared memory: Issue #104 - For process-shared synchronization
Timer system: Issue #101 - For timed synchronization operations
Atomic operations: Atomic primitive support in hardware/compiler

Integration Points

Integrate with pthread mutex/condition variables
Support process-shared synchronization via shared memory
Integration with real-time scheduling policies
GDB debugging support for advanced synchronization
Performance monitoring and profiling integration

Security Considerations

Prevention of priority inversion attacks
Secure process-shared synchronization
Resource exhaustion protection
Deadlock detection and prevention
Secure cleanup of synchronization objects

Files to Create/Modify

lib/pthread/pthread_barrier.c - Barrier implementation
lib/pthread/pthread_spinlock.c - Spinlock implementation
lib/pthread/pthread_rwlock.c - Reader-writer lock implementation
lib/pthread/pthread_once.c - One-time initialization
lib/pthread/pthread_robust.c - Robust mutex support
lib/pthread/pthread_timed.c - Timed synchronization operations
include/pthread.h - Extended pthread synchronization interface

Performance Goals

Spinlock acquisition < 50ns uncontended
RWlock reader acquisition < 100ns uncontended
Barrier synchronization < 10μs for 8 threads
Robust mutex overhead < 10% vs normal mutex
Timed operations accurate to 1ms resolution

Error Handling

ETIMEDOUT for timed operations
EOWNERDEAD for robust mutex owner death
ENOTRECOVERABLE for unrecoverable robust mutex
EINVAL for invalid parameters
EBUSY for resource conflicts

Standards Compliance

Full POSIX.1-2017 advanced threading compliance
IEEE Std 1003.1 synchronization primitive specifications
Real-time extensions support (IEEE Std 1003.1b)
Linux pthread extensions compatibility
Single UNIX Specification compliance

Usage Examples

#include <pthread.h>
#include <time.h>

// Barrier example - synchronize threads at checkpoint
pthread_barrier_t checkpoint;

void* worker_with_barrier(void* arg) {
    int id = *(int*)arg;
    
    // Do work phase 1
    printf("Thread %d: Phase 1 complete\n", id);
    
    // Wait for all threads to reach checkpoint
    int result = pthread_barrier_wait(&checkpoint);
    if (result == PTHREAD_BARRIER_SERIAL_THREAD) {
        printf("Last thread reached barrier\n");
    }
    
    // Do work phase 2
    printf("Thread %d: Phase 2 complete\n", id);
    return NULL;
}

// Reader-writer lock example
pthread_rwlock_t data_lock = PTHREAD_RWLOCK_INITIALIZER;
int shared_data = 0;

void* reader_thread(void* arg) {
    pthread_rwlock_rdlock(&data_lock);
    printf("Read data: %d\n", shared_data);
    pthread_rwlock_unlock(&data_lock);
    return NULL;
}

void* writer_thread(void* arg) {
    pthread_rwlock_wrlock(&data_lock);
    shared_data++;
    printf("Updated data to: %d\n", shared_data);
    pthread_rwlock_unlock(&data_lock);
    return NULL;
}

// Spinlock example for short critical sections
pthread_spinlock_t cache_lock;

void update_cache(int key, int value) {
    pthread_spin_lock(&cache_lock);
    // Very short critical section
    cache[key] = value;
    pthread_spin_unlock(&cache_lock);
}

// One-time initialization example
pthread_once_t init_once = PTHREAD_ONCE_INIT;

void initialize_library(void) {
    // Expensive initialization code
    printf("Library initialized once\n");
}

void* thread_using_library(void* arg) {
    pthread_once(&init_once, initialize_library);
    // Use library functions...
    return NULL;
}

int main() {
    // Initialize barrier for 4 threads
    pthread_barrier_init(&checkpoint, NULL, 4);
    
    // Initialize spinlock
    pthread_spin_init(&cache_lock, PTHREAD_PROCESS_PRIVATE);
    
    pthread_t threads[8];
    int thread_ids[8];
    
    // Create worker threads with barrier
    for (int i = 0; i < 4; i++) {
        thread_ids[i] = i;
        pthread_create(&threads[i], NULL, worker_with_barrier, &thread_ids[i]);
    }
    
    // Create reader/writer threads
    for (int i = 4; i < 8; i++) {
        if (i % 2 == 0) {
            pthread_create(&threads[i], NULL, reader_thread, NULL);
        } else {
            pthread_create(&threads[i], NULL, writer_thread, NULL);
        }
    }
    
    // Wait for all threads
    for (int i = 0; i < 8; i++) {
        pthread_join(threads[i], NULL);
    }
    
    // Cleanup
    pthread_barrier_destroy(&checkpoint);
    pthread_spin_destroy(&cache_lock);
    pthread_rwlock_destroy(&data_lock);
    
    return 0;
}

Related Issues

Completes full POSIX threading support
Enables high-performance multithreaded applications
Required for database and server applications
Foundation for real-time application support
Enables advanced parallel programming patterns

Sep 28 '25 15:09 pbalduino