Semaphores

The original proposed synchronisation primitive for all things synchronisation. Can function as a lock as well as as a condition variable, whatever that is

A semaphore is an object with an integer value that we can sem_wait() or sem_signal() for. It’s initial value is quite important so it must be initted well

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

int sem_signal(sem_t *s) {
  /*
   * increment the value of semaphore by 1
   * if there are one or more threads waiting, wake one
   */
}

Semaphore Invariant

The value of the semaphore, when negative, is equal to the number of waiting threads

Semaphores as Locks

Here the value of the semaphore is usually just between two states, locked and unlocked

sem_init(s, NULL, 1); // init unlocked sem
 
sem_wait(s);
/* critical section */
sem_signal(s);

And that would look like

sem value	thread 0	thread 1
1
1	call `sem_wait()`
0	`sem_wait()` returns
0		call `sem_wait()`
-1		`sem_wait()` waits
-1	(critical section)
-1	call `sem_signal()`
0	`sem_signal()` returns
0		(critical section)
0		call `sem_signal()`
1		`sem_signal()` returns

Note how we start in an unlocked state

Semaphores for Ordering

When we want something to occur AFTER another thing has happened, we start in a “locked” state.

sem_t *s;
 
void *thing1(void* arg) {
  (void*)arg;
  printf("child: heheheheheheh\n"):
  sem_signal(s);              // signal end of thing1
  return NULL;
}
 
int main(void) {
  sem_init(s, NULL, 0);       // init locked sem
  pthread_t t;
  printf("parent: begin\n");
  pthread_create(&c, NULL, thing1, NULL);
  sem_wait(s);                // wait for thing1 to finish
  printf("parent: end\n");    // do thing 2
  return 0;
}

Initial Semaphore Values

We mentioned the invariant above about how the negative value indicates the number of waiting processes. Similar the positive value indicates the number of immediately available resources after initialization.

A value of $0$ indicates there are no resources to give away yet. $1$ and higher say these many threads can start running simultaneously

Classical Problems

Produce/Consumer(Bounded Buffer Problem)

Consider async events. One thread may gather and add them to a queue, while another pops them and processes each event. The first thread is the producer and the second, the consumer.

Queue/Buffer operations are critical and must be mutually exclusive
If a consumer thread arrives while the buffer is empty, it blocks until the a producer adds a new item

we create three semaphores

full to keep track of when items are available
empty for when the buffer is empty
mutex for mutual exclusion

sem_t full, empty, mutex;
 
void *producer(void* arg) {
  for (;;) {
    sem_wait(&empty);
    sem_wait(&mutex);
    /* add item i to buffer */
    sem_signal(&mutex);
    sem_signal(&full);
  }
}
 
void *consumer(void* arg) {
  while(1) {
    sem_wait(&full);
    sem_wait(&mutex);
    /* consume item */
    sem_signal(&mutex);
    sem_signal(&empty);
  }
}
 
int main(void) {
  // ...
  sem_init(&empty, NULL, NO_ITEMS);  // NO_ITEMS available
  sem_init(&full, NULL, 0);          // 0 are full
  sem_init(&mutex, NULL, 1);         // mutex is unlocked
}

Mutual Exclusion and Deadlocks
A producer will not be running at the same time as a consumer, and vice versa, thanks to the empty and full semaphores. But in the event of multiple producers/consumers, so prevent race conditions when adding/consuming, we need the third mutex semaphore.

But adding it incorrectly can lead to deadlocks
void *consumer(void* arg) {
  while(1) {
    sem_wait(&mutex);
    sem_wait(&full);
    /* consume item */
    sem_signal(&empty);
    sem_signal(&mutex);
  }
}
Here

The consumer acquires the mutex

The consumer waits for an items to be available

If it is not, then it goes to sleep and NEVER RELEASES THE MUTEX

the mutex is acquired by a sleeping process and nothing else can acquire it giving us a DEADLOCK

We fix this by reducing the scope of the lock

Designated Producer-Consumer Problem (unbounded buffer)

Consider a similar scenario, but now each item was produced for a designated consumer and must be consumer only by that consumer. We now mantain an array of semaphores each individually telling its designated consumer if it can consume or not;

Let’s look at our shared memory

sem_t rw_mutex = 1;
sem_t r_mutex[N] = {0, 0, 0, 0, 0, ...};

void* consumer(int i) {
  sem_wait(&r_mutex[i]);
  for (;;) {
    sem_wait(&rw_mutex);
    /* consume item from buffer */
    sem_signal(&rw_mutex);
  }
}
 
void* producer() {
  for (;;) {
    int i = rand() % N;
    sem_wait(&rw_mutex);
    /* produce item for i */
    sem_signal(&r_mutex[i]);
    sem_signal(&rw_mutex);
  }
}

extending this for a bounded buffer shouldn’t be hard i don’t think

The Reader-Writer Problem

For the different requirements of different data structures. Consider a database

Any number of readers can be in a critical section simultaneously
Writers must have exclusive access to the critical section

This can be called categorical mutual exclusion

There are many versions of this problem, we are first going to look at the Reader-Priority version

Reader-Priority

We would need a few variables

a w_mutex: to ensure writers are mutually exclusive
a readers int to count the number of readers accessing the db
a r_mutex to protect the readers int

sem_t w_mutex;
sem_t r_mutex;
int readers = 0;
 
void* writer(void* arg) {
  sem_wait(&w_mutex);
  /* write to db */
  sem_signal(&w_mutex);
}
 
void* reader(void* arg) {
  sem_wait(&r_mutex);
  readers++;
  if (readers == 1) {
    /* first reader => wait for writers to free up */
   sem_wait(&w_mutex);
  }
  sem_signal(&r_mutex);
 
  /* read from db */
 
  sem_wait(&r_mutex);
  readers--;
  if (readers == 0) {
    /* last reader => wakeup writers now */
    sem_signal(&w_mutex);
  }
  sem_signal(&r_mutex);
}

Lightswitches

Patterns like can be called Lightswitches, where the first one in turns on the light, and the last one out turns it off

Writer Starvation

We noticed earlier that waiting on a semaphore, while already holding a semaphore could lead to potential deadlocks, but thankfully in this case we are safe, since the writer never touches r_mutex. However we have another, related problem. Our solution above favours readers, if a new reader were to come while a writer was waiting, it would be queued before the writer.

In such a scenario, writers could starve and potentially never run. To mitigate this we would need another semaphore to tell readers that a writer is waiting and stop letting new readers in.

If we operate under the assumption that semaphore queues are FIFO queues, we can do the following

sem_t r_mutex, w_mutex, q_mutex;
int readers = 0;
 
void* writer(void* arg) {
  sem_wait(&q_mutex);
  sem_wait(&w_mutex);
  sem_signal(&q_mutex);
 
  /* write to db */
 
  sem_signal(&w_mutex);
}

If a writer enters while a reader is reading, it will block on line 4 waiting for w_mutex, and in the process q_mutex will be locked as well. Preventing other readers from entering the queue

void* reader(void* arg) {
  sem_wait(&q_mutex);
  sem_wait(&r_mutex);
  readers++;
  if (readers == 1) {
    sem_wait(&w_mutex);
  }
  sem_signal(&q_mutex);
  sem_signal(&r_mutex);
 
  /* read from db */
 
  sem_wait(&r_mutex);
  readers--;
  if (readers == 0) {
    sem_signal(&w_mutex);
  }
  sem_signal(&r_mutex);
}

However, all this ensures is that one writer gets to proceed before the other readers. It still favours the readers to get ahead of writers in general. Secondly, here we assume that a semaphore waiting queue is FIFO, which may not be true and potentially varies from implementation to implementation.

Writer-Priority

We will now implement a lightswitch type design for writers as well

sem_t block_readers;
sem_t block_writers;
 
sem_t r_mutex;
sem_t w_mutex;
int readers;
int writers;

void *reader(void* arg) {
  sem_wait(&block_readers);   // NEW LINE // wait for read to be unblocked
  wait(&r_mutex);
  readers++;
  if (readers == 1) {
    sem_wait(&block_writers);       // first reader blocks writers
  }
  sem_signal(&r_mutex);
  sem_signal(&block_readers);  // NEW LINE //
 
  /* read from db */
 
  sem_wait(&r_mutex);
  readers--;
  if (readers == 0) {
    sem_signal(&block_writers);     // last reader unblocks writers
  }
  sem_signal(&r_mutex);
}
 
void *writer(void* arg) {
  sem_wait(&w_mutex);
  writers++;
  if (writers == 1) {
    sem_wait(&block_readers);        // first writer blocks readers
  }
  sem_signal(&w_mutex);
 
  sem_wait(&block_writers);          // block other writers to enter CS
  /* write to db */
  sem_signal(&block_writers);        // unblock writers
 
  sem_wait(&w_mutex);
  writers--;
  if (writers == 0) {
    sem_signal(&block_readers);      // last writer unblocks readers
  }
  sem_signal(&w_mutex);
}

Now a writer can always block readers. This ofcourse leads to the issue that readers may starve now :(

Dining Philosophers Problem

nerds

Each philosopher p is in the below loop

for(;;) {
  think();
  get_forks(p);
  eat();
  put_forks(p);
}

and we must provide get_forks(p) and put_forks(p) such that

There is no deadlock
No philosopher starves
Concurrency is high (as many philosophers get to eat at the same time as possible)

Let’s use the helpers left and right when talking about forks

int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

and we also need exclusive access to the forks, so it makes sense to have a semaphore for each fork.

sem_t forks[5];

Let’s look at a broken solution to see why this problem is interesting

Broken Solution: 1

Everyone just picks up their forks and starts eating

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

Can you spot the deadlock???

Since the table is circular, if every nerd picked up the left fork at the same time, none of them have a right fork they can use and are forever waiting. This will lead to them starving and eventually dying.

Resolving Deadlocks

One way to avoid deadlock is to think about the conditions that make the deadlock possible, then change one of the conditions. The Dining Philosophers’ deadlock is fairly fragile

Broken Solution: 2

All of pick their left forks, and check to see if the right is available. Since the issue with not having a right fork available, lets check if it is available before continuing.

void get_forks(p) {
  sem_wait(&forks[left(p)]);
  /* you can't actually check the value of a semaphore like below
   * but i don't want to make this pseudocode too complex */
  if (forks[right(p)] > 0) {
    sem_wait(&forks[right[p]]);
  } else {
    sem_signal(&forks[left(p)]);
  }
}

However this also has an issue(s)

Livelocks

Suppose all of the nerds pick up their left forks. They all simultaneously see that the right fork is not available, and all together put down the left fork. This repeats.

This is not a deadlock because they’re aren’t stuck waiting for a resource, rather for the condition that will enable them to use the resource.

The livelock could potentially be resolved by adding a random()/exponential() backoff function after every failed attempt to get a right fork, but that’s not very practical for us.

Broken Solution: 3

just use a mutex for each fork lmaoo

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

And this is somewhat decent ig, but

it still doesn’t resolve starvation
its a poor use of resources, we want the most concurrent solution remember

// TODO: come back to check correctness of this
// as far as ive seen the signal() is put in putfork instead

Working Solution: 1 (Footman)

If only $N - 1$ nerds eat at the same time, deadlock is impossible because one of them will always get the right fork. We can reframe this similar to the bounded buffer problem now, and treat the table of the buffer

sem_t footman = N-1; // 4 in our case
 
void get_forks(p) {
  sem_wait(&footman);
 
  sem_wait(&forks[left(p)]);
  sem_wait(&forks[right(p)]);
}
 
void put_forks(p) {
  sem_signal(&forks[left(p)]);
  sem_signal(&forks[right(p)]);
 
  sem_signal(&footman);
}

This also prevents starvation because the moment a nerd beside the 5th one finishes eating, the waiting 5th nerd must be allowed to eat

Working Solution: 2 (Djikstra’s)

Notice how our problems all occur because all 5 nerds are lefties. What if one of them was a rightie??? 4 would pick up their left fork, the rightie would fail to pick up their right fork, leaving the 4th one to be able to pick up their right fork too. No deadlock :D

This is simple to implement

void get_forks(p) {
  if (p == N-1) {
    sem_wait(&forks[right(p)]);
    sem_wait(&forks[left(p)]);
  } else {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
  }
}

And it also prevents starvation for the same reasons as above

Broken Solution: 3 (Tannebaum’s)

This guy created a state based system. Which means we maintain a state array for each philosopher

#define THINKING 0
#define HUNGRY 1
#define EATING 2
 
sem_t mutex;
sem_t sems[5] = {0, 0, 0, 0, 0}; // 5 locked semaphores
int state[5];

void get_forks(p) {
  sem_wait(&mutex);
  state[p] = HUNGRY;
  test(p);
  sem_signal(&mutex);
  sem_wait(&sem[p]);
}
 
void put_forks(p) {
  sem_wait(&mutex);
  state[i] = THINKING;
  test(right(p));
  test(left(p));
  sem_signal(&mutex);
}
 
void test(p) {
  if (state[p] == HUNGRY &&
      state[left(p)] != EATING &&
      state[right(p)] != EATING) {
    state[p] = EATING;
    sem_signal(sem[p]);
  }
}

There are two ways a nerd gets to eat

both of the neighbours aren’t eating, which means he gets the forks and eats
one of the neighbouts is eating, which means he waits for them to finish so he gets the forks

Starving Tannebaums

It is possible to starve in this solution due a repeating pattern of exclusion. Suppose $P_{2}$ and $P_{4}$ are currently eating, when $P_{2}$ finishes, $P_{1}$ starts, and when $P_{4}$ finishes, $P_{3}$ starts.

Once $P_{3}$ is done, $P_{4}$ starts, and once $P_{1}$ is done, $P_{2}$ starts. If this repeats, $P_{0}$ will starve

Cigarette Smoker’s Problem

4 threads are involved, one agent and 3 smokers
smoking a cigarrete consists of three ingredients
- tobcacco
- paper
- matches
the agent has an infinite supply of all 3 ingredients
each smoker has an infinite supply of one of the 3 ingredients. one has paper, the other tobcacco, the other matches.
the agent repeatedly chooses two of the ingredients at random and presents them to the smokers. The smoker with the complementary ingredient can pick them both up and smoke his cigarrete

There are three versions of this problem

Trivial Version:
- the agent just signals the smoker than can now run based on the ingredients
Interesting Version:
- you are not allowed to modify the agent code
Impossible Version:
- you are not alloewed to modify the agent code
- you can’t use conditional statements or an array of semaphores

We must avoid deadlock where the other two smokers take one ingredient each and wait for a third one that never comes

Let’s look at the trivial version :( [MS’25]

sem_t agent_sem = 0;
sem_t tobacco_sem = 0;
sem_t paper_sem = 0;
sem_t match_sem = 0;
 
sem_t mutex = 1;

void *agent(void* arg) {
  for (;;) {
    sem_wait(&mutex);
    ingredient_t choice;
    if (choice == (tobacco & paper)) {
      sem_signal(&match_sem);
    } else if (choice == (tobacco & match)) {
      sem_signal(&paper_sem);
    } else if (choice == (match & paper)) {
      sem_signal(&tobacco_sem);
    }
    sem_signal(&mutex);
    sem_wait(&agent_sem);
  }
}
 
void tobacco_smoker() {
  for (;;) {
    sem_wait(&tobacco_sem);
    sem_wait(&mutex);
    
    /* take paper and matches */
 
    sem_signal(&agent);
    sem_signal(&mutex);
 
    smoke();
  }
}

// TODO: other applications of semaphores

Here’s the interesting version’s solution too:

The agent simply signals the available ingredients

void *agent(void* arg) {
  for (;;) {
    sem_wait(&mutex); 
    ingredient_t choice;
    if (choice == (tobacco & paper)) {
      sem_signal(&tobacco_sem);
      sem_signal(&paper_sem);
    } else if (choice == (tobacco & match)) {
      sem_signal(&tobacco_sem);
      sem_signal(&match_sem);
    } else if (choice == (match & paper)) {
      sem_signal(&match_sem);
      sem_signal(&paper_sem);
    }
    sem_signal(&mutex);
    sem_wait(&agent_sem);
  }
}

The issue with the “intuitive” solution

simply having the below code is wrong

void tobacco_smoker() {
  for (;;) {
    sem_wait(&match_sem);
    sem_wait(&paper_sem);
 
    sem_wait(&mutex);
 
    /* smoke */
 
    sem_signal(&agent);
    sem_signal(&mutex);
  }
}

and so on for the three smokers may lead to Deadlock, because it is possible the tobacco smoker manages to acquire the match, and the match smoker acquires the paper. They are both now waiting for a resource that’s never going to come and no one can make a cigarrete

To mitigate this and only signal the correct smoker, we create helper threads. We run 3 helper threads with the following addition variables/semaphores

bool isTobacco = false, isPaper = false, isMatch = false;
sem_t t_smoker = 0;  // signal tobacco smoker to wake up
sem_t m_smoker = 0;  // signal match smoker to wake up
sem_t p_smoker = 0;  // signal paper smoker to wake up

void helper_a() {
  sem_wait(&tobacco_sem);
  sem_wait(&mutex);
 
  if (isPaper) {
    isPaper = false;
    sem_signal(&m_smoker);
  } else if (isMatch) {
    isMatch = false;
    sem_signal(&p_smoker);
  } else {
    isTobacco = true;
  }
 
  sem_signal(&mutex);
}

and each smoker can now wait on their semaphore

void tobacco_smoker() {
  for (;;) {
    sem_wait(&t_smoker);
    sem_wait(&mutex);
 
    /* smoke */
 
    sem_signal(&agent);
    sem_signal(&mutex);
  }
}

We can also generalise this problem and say that the agent does not wait for smokers, instead it keeps pushing ingredients on the table as it wants. Then you will need to keep count of the ingredients present instead of just boolean values.

Thread Throttling

To limit the max number of threads working on something together, you can use a counting semaphore.

sem_t throttle_sem = MAX_ALLOWED_THREADS;
 
void thread_routine() {
  sem_wait(&throttle_sem);
 
  /* do whatever */
 
  sem_signal(&throttle_sem);
}

This is a method of admission control, and can be used to limit the amount of threads performing a memory operation at the same time (for example)

Implementing Semaphores

Here’s a simple implementation using mutexes and condition variables (see more about condition variables in the thread api page)

typedef struct __zem_t {
  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);
  while (s->value <= 0) {
    cond_wait(&s->cond, &s->lock);
  }
  s->value--;
  mutex_unlock(&s->lock);
}
 
void zem_signal(zem_t *s) {
  mutex_lock(&s->lock);
  s->value++;
  cond_signal(&s->cond);
  mutex_unlock(&s->lock);
}

Trying to do the opposite and build condition variables with semaphores is far trickier¹, as we saw in [lab assignment 6]

http://birrell.org/andrew/papers/ImplementingCVs.pdf ↩

notes

Explorer

Semaphores

Semaphores

Semaphores as Locks

Semaphores for Ordering

Classical Problems

Produce/Consumer(Bounded Buffer Problem)

Designated Producer-Consumer Problem (unbounded buffer)

The Reader-Writer Problem

Reader-Priority

Writer Starvation

Writer-Priority

Dining Philosophers Problem

Broken Solution: 1

Broken Solution: 2

Broken Solution: 3

Working Solution: 1 (Footman)

Working Solution: 2 (Djikstra’s)

Broken Solution: 3 (Tannebaum’s)

Cigarette Smoker’s Problem

Thread Throttling

Implementing Semaphores

Graph View

Table of Contents

notes

Explorer

Semaphores

Semaphores

Semaphores as Locks

Semaphores for Ordering

Classical Problems

Produce/Consumer(Bounded Buffer Problem)

Designated Producer-Consumer Problem (unbounded buffer)

The Reader-Writer Problem

Reader-Priority

Writer Starvation

Writer-Priority

Dining Philosophers Problem

Broken Solution: 1

Broken Solution: 2

Broken Solution: 3

Working Solution: 1 (Footman)

Working Solution: 2 (Djikstra’s)

Broken Solution: 3 (Tannebaum’s)

Cigarette Smoker’s Problem

Thread Throttling

Implementing Semaphores

Footnotes

Graph View

Table of Contents