Synchronization

Critical section: sezione in cui si accede in lettura e scrittura a oggetti condivisi tra thread/processi

Problemi classici

Producer-consumer

Buffer circolare (struttura FIFO) con diversi produttori e consumatori.

• Semafori full e empty: blocco il producer se non ho spazi liberi
• Mutual exclusion tra produttori MEp e tra consumatori MEc

init(full, 0);
init(empty, SIZE);
init(MEp, 1);
init(MEc, 1);

Produttore:

produce(&val);
wait(empty);
wait(MEp);
enqueue(val);
signal(MEp);
signal(full);

Consumatore:

wait(full);
wait(MEc);
dequeue(&val);
signal(MEc);
signal(empty);

Reader-writer

Diversi reader che possono accedere ai dati in modo concorrente e diversi writer che lavorano in mutual exclusion.

Precedence to readers

Init:

num_readers = 0;
init(meR, 1);
init(meW, 1);
init(w, 1);

Reader:

wait(meR);
    num_readers++;
    // Se c'erano 0 reader mettiti in mutual exclusion con i writer
    if (num_readers == 1)
        wait(w);
signal(meR);
// Reading...
wait(meR);
    num_readers++;
    if (num_readers == 0)
        signal(w);
signal(meR);

Writer:

wait(meW);
wait(w);
// Writing
signal(w);
signal(meW);

Alternate direction tunnel

Se c'è traffico in una direzione, bloccalo nell'altra.

È il readers-writers problem con due set di reader.

Dining philosophers problem

N filosofi che possono pensare o mangiare, ed N bacchette; servono 2 bacchette per mangiare.

Semafori

Contatore e waiting queue protetti da un lock. Posso fare wait/down per accedere alla critical section e signal/up/post per uscire dalla critical section.

Se il contatore è inizializzato a N, allora N thread possono stare nella critical section contemporaneamente.

Semafori POSIX

int sem_init(sem_t *sem, 0, uint value);
int sem_destroy(sem_t *sem);

int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem); // Non-blocking wait
int sem_post(sem_t *sem);

Mutex

I mutex sono semafori binari.

Mutex POSIX

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int pthread_mutex_destroy(pthread_mutex_t *mutex);

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

Reader-writer locks [POSIX]

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);

int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_wrlock(pthread_rwlock_t *wrlock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_trywrlock(pthread_rwlock_t *wrlock);
int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_unlock(pthread_rwlock_t *unlock);

Condition variables [POSIX]

Wait su condizioni arbitrarie. Struttura generale:

mutex_lock(&mutex);
while !(f(x, y, z)) {
    cond_wait(cv, &mutex); // Aspetta che la cv cambi: unlocka il mutex, sleepa, ri-locka il mutex
}
// Operate on x, y, z...
mutex_unlock(cv);

Uso cond_signal/broadcast per segnalare che la cv è cambiata e wakeare i thread.

pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
int pthread_cond_destroy(pthread_cond_t *cv);

int pthread_cond_wait(pthread_cond_t *cv, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cv);
int pthread_cond_broadcast(pthread_cond_t *cv);

Spinlock [POSIX]

È come un mutex, ma anzichè mettere in pausa il processo fa busy wait.

pthread_spin_init(pthread_spin_t *lock, 0);
pthread_spin_destroy(pthread_spin_t *lock);

pthread_spin_lock(pthread_spin_t *lock);
pthread_spin_trylock(pthread_spin_t *lock);
pthread_spin_unlock(pthread_spin_t *lock);

Barrier [POSIX]

Ogni thread aspetta fino a che tutti hanno raggiunto lo stesso punto.

int pthread_barrier_init(pthread_barrier_t *barrier, NULL, uint count);
int pthread_barrier_destroy(pthread_barrier_t *barrier);

int pthread_barrier_wait(pthread_barrier_t *barrier);