Ostep-Semaphores

Semaphores

A semaphore is a powerful synchronization primitive, first developed by Dijkstra & colleagues, with a wide variety of uses. It can be used as both a lock and a condition variable.

The interface is very simple:

sem_t s;

int sem_init(sem_t *s, int _mode, int val) {
    // initialize the semaphore with the given val
}

int sem_wait(sem_t *s) {
    // decrement semaphore val by 1
    // wait if value is negative
}

int sem_post(sem_t *s) {
    // increment semaphore val by 1
    // if there are any threads waiting, wake one
}

The semantics are essentially that the semaphore's value determines how many threads can do things at once.

Locks

Aka binary semaphore: use sem_init(&s, 0, 1). Then exactly one thread will be allowed to enter a critical section guarded by sem_wait(&s). Releasing the lock is accomplished via sem_post(&s).

Ordering

Semaphores can also be used to order execution of events, just like we accomplished with condition variables. For example, to have a parent thread wait until a child is finished:

sem_t s;

void * child(void *arg) {
    printf("child");
    sem_post(&s); // signal child done here
    return NULL;
}

int main(int argc, char *argv[]) {
    // 0 means the first waiter will wait until the first poster posts
    sem_init(&s, 0, 0); 
    printf("before child");``
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here
    printf("after child");
    return 0;
}

Producer/consumer

A multi-producer and multi-consumer bounded buffer requires both mutual exclusion (ensure producers don't overwrite each other's entries) and conditions (don't consume an empty buffer and dont produce exceeding the buffer). So let's use the two forms of the semaphores above:

sem_t removed; // signals an entry has been removed
sem_t added; // signals an entry has been added
sem_t mutex; // binary semaphore lock

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&removed); // wait for room in the buffer
        sem_wait(&mutex); // obtain lock; enter critical section
        put(i);
        sem_post(&mutex); // release lock
        sem_post(&added); // signal entry added
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&added); // wait until buffer is non-empty
        sem_wait(&mutex); // obtain lock; enter critical section
        get(i);
        sem_post(&mutex); // release lock
        sem_post(&removed); // signal entry removed
    }
}

int main(int argc, char argv[]) {
    sem_init(&removed, 0, MAX) // allow MAX items in the buffer
    sem_init(&added, 0, 0) // the buffer is empty to start
    sem_init(&mutex, 0, 1) // binary semaphore makes a mutex
}

// the buffer stuff
int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value;
    fill = (fill + 1) % MAX;
}
void get() {
    int tmp = buffer[use];
    use = (use + 1) % MAX;
    return tmp;
}

Reader-Writer Locks

It can be more efficient for concurrent data structures to allow unlimited concurrent reads, but exclusive writes. We can make such a reader-writer lock pretty easily using semaphore locks.

typedef struct _rwlock_t {
    // lock for write access
    sem_t writelock;
    // lock for critical sections managing reader count
    sem_t lock;
    int readers;
} rwlock_t;

void rwlock_init(rwlock_t *lock) {
    lock->readers = 0; // no readers to start
    sem_init(&lock->lock, 1); // lock
    sem_init(&lock->writelock, 1); // lock 
}

void rwlock_acquire_readlock(rwlock_t *lock) {
    // enter crit section
    sem_wait(&lock->lock);
    lock->readers++;
    // if this is the first (current) reader,
    // then make sure we wait for any writers to finish!
    if (lock->readers == 1)
        Sem_wait(&lock->writelock);
    // exit crit section
    sem_post(&lock->lock);
}

void rwlock_release_readlock(rwlock_t *lock) {
    // enter crit section
    sem_wait(&lock->lock);
    lock->readers--;
    // if this is the last (current) reader,
    // wake any potentially waiting writers
    if (lock->readers == 0)
        sem_post(&lock->writelock);
    // exit crit section
    sem_post(&lock->lock);
}

void rwlock_acquire_writelock(rwlock_t *lock) {
    sem_wait(&lock->writelock);
}

void rwlock_release_writelock(rwlock_t *lock) {
    sem_post(&lock->writelock);
}

This is a naive implementation; it's quite easy for readers to starve writers with it. Realistic RwLocks use more sophisticated techniques.

Cautionary Tip: RwLocks add significant overhead, and often a simple and fast locking primitive will end up being more performant.

The dining philosophers

Imagine five philosphers and five forks around a table, with a fork between each philospher. The philosophers are either thinking (no forks) or eating (both forks - the left and right). Let's say we use a semaphore for each fork.

The first naive solution is broken:

sem_t forks[5];

// eat
void getforks() {
    sem_wait(forks[p]);         // L
    sem_wait(forks[(p+1) % 5]); // R
}

// think
void putforks() {
    sem_post(forks[p]);
    sem_post(forks[(p+1) % 5]);
}

because of a possible deadlock. Suppose all the philosphers try to eat at once, and each one gets to run line L to obtain the left fork forks[p] before execution proceeds to line R. Then all the philosophers get stuck waiting for their right fork.

A simple solution (proposed by Dijkstra) is to simply have one of the philosophers obtain the locks in a different order:

// eat
void getforks() {
    if (p == 4) {
        sem_wait(forks[(p+1) % 5]); // R
        sem_wait(forks[p]);         // L
    } else {
        sem_wait(forks[p]);         // L
        sem_wait(forks[(p+1) % 5]); // R
    }
}

Implementing semaphores

This implementation is a bit different from Dijkstra's original, in that the negative value of the semaphore is not reflective of the number of waiting threads. It's easier to implement and matches the current Linux version.

typedef struct __zem_t {
    // value must be positive to allow a thread to pass sem_wait.
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} zem_t;

void zem_init(zem_t *s, int value) {
    s->value = value;
    cond_init(&s->cond);
    mutex_init(&s->lock);
}

void zem_wait(zem_t *s) {
    mutex_lock(&s->lock);
    // if non-positive, wait until positive
    while (s->value <= 0) {
        cond_wait(&s->cond, &s->lock);
    }
    s->value--;
    mutex_unlock(&s->lock);
}

void zem_post(zem_t *s) {
    mutex_lock(&s->lock);
    s->value++;
    cond_signal(&s->cond);
    mutex_unlock(&s->lock);
}