Semaphores

Binary Semaphores (Locks)

You can use semaphores to make a lock.

sem_t m;
sem_init(&m, 0, 1); // initialize to X; what should X be?

sem_wait(&m);
// critical section here
sem_post(&m);

Here we’ve initialized the semaphore to a value of 1.

Does this work? Assume Thread 0 first gets to call wait. It will decrement the value to 1 and is free to continue and is in the critical section. If now another thread calls wait, the value gets set to -1 and that other thread will have to wait. When Thread 0 is done, the post will increment the value to 0, and wake up the sleeping thread. This thread will run as the value is not negative.

What if we have more than two threads? I think it still works. If I understand correctly, once a thread is woken up, it does not need the value to be non-negative - it will continue. This works assuming only one thread is woken up. I think this is what post does.

Ordering

Say you want one thread to wait for another thread to complete before continuing.

sem_t s;

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

int main(int argc, char *argv[]) {
    sem_init(&s, 0, 0); // what should X be?
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

Set your semaphore to 0. Create your child thread, and then wait. If the child thread runs before wait, we’re good. Otherwise the parent thread will run wait and sleep until the child thread runs. Pretty simple.

Allowing \(N\) Threads to Run

Sometimes we are OK letting \(N\) threads access a resource, but need to limit it so no more can. We solve this problem using a semaphore whose initial value is \(N\).

Producer/Consumer Using Semaphores

Below is the full solution to this problem using semaphores.

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value;
    fill = (fill + 1) % MAX; // Line F2
}

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

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++)
    {
        sem_wait(&empty); // Line P1
        sem_wait(&mutex); // Line P1.5 (MUTEX HERE)
        put(i);           // Line P2
        sem_post(&mutex); // Line P2.5 (AND HERE)
        sem_post(&full);  // Line P3
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full); // Line C1
        sem_wait(&mutex); // Line C1.5 (MUTEX HERE)
        int tmp = get(); // Line C2
        sem_post(&mutex); // Line C2.5 (AND HERE)
        sem_post(&empty); // Line C3
        printf("%d\n", tmp);
    }
}

Some things to point out about this code:

You need the mutex where it is (after the empty/full semaphore). Putting it before will result in a deadlock. Also, if you don’t have the mutex at all, you’ll get a race condition where your counter for how full the buffer is gets incremented/decremented.

Reader-Writer Locks

The reader-writer lock is one where you allow multiple threads to read simultaneously, as long as there are no ongoing modifications.

The code is fairly simple:

typedef struct _rwlock_t {
    sem_t lock; // binary semaphore (basic lock)
    sem_t writelock; // allow ONE writer/MANY readers
    int readers; // #readers in critical section
} rwlock_t;

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

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1) // first reader gets writelock
        sem_wait(&rw->writelock);
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0) // last reader lets it go
        sem_post(&rw->writelock);
    sem_post(&rw->lock);
}

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

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

In this solution, once any reader has acquired a lock, any other reader is also allowed to acquire the lock. But acquiring the write lock requires all readers to have released the read lock.

This solution has a problem: You can starve the writer.

Often, such locks add more overhead than is worth it. Benchmark!

The Dining Philosophers

The dining philosophers problem is this: You have five philosophers sitting on a round table. Between each pair of philosophers is a fork - so each philosopher has a fork on the left and on the right.

Now any given philosopher will do one of two things:

1. Think
2. Eat

To eat, (s)he needs to get the fork on both sides. Once done eating, (s)he puts down the forks. Clearly, if one philosopher has both forks, that philosopher is preventing the person on both sides from eating.

Which algorithm will allow all philosophers to eat at some point?

The basic one fails:

void get_forks(int p) {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
}

void put_forks(int p) {
    sem_post(&forks[left(p)]);
    sem_post(&forks[right(p)]);
}

This will lead to a deadlock if all philosophers decide to eat at the same time.

The solution is:

void get_forks(int p) {
    if (p == 4) {
        sem_wait(&forks[right(p)]);
        sem_wait(&forks[left(p)]);
    } else {
        sem_wait(&forks[left(p)]);
        sem_wait(&forks[right(p)]);
    }
}

void put_forks(int p) {
    sem_post(&forks[left(p)]);
    sem_post(&forks[right(p)]);
}

Basically we require one philosopher to pick the forks in a different order from the others.

Also note that put_forks doesn’t change!