Implementing a Semaphore

README.md

Implementing a Semaphore

Use the following commands to compile and link the examples:

$ gcc -std=c17 -pedantic-errors -O0 -g -S sem.c
$ as --gstabs -o sem.o sem.s 
$ gcc -o sem sem.o -lpthread

This implementation makes use of the C11 Atomic Operations Library.

Semaphores

A semaphore is an integer variable s that, apart from initialization, is accessed only through two standard atomic operations:

• wait(s) -- blocks while s <= 0, then decrements s; and
• signal(s) -- increments s.

A semaphore is used to limit access to a resource to a specific number of threads / processes. The initial value of the semaphore denotes the limit. A popular analogy is that a semaphore is like a bouncer at a bar / club. As people enter the bar, the number of people allowed to enter descreases. Once that number decreases to zero, people must wait to enter until other people leave.

If the semaphores initial value is 1, then this is known as a binary semaphore, which effectively serves the same role as a mutex. While the code example demonstrates a binary semaphore with a redundant mutex, readers are encourages to introduce more threads and increase the initial semaphore value to see what happens -- in this scenario the semaphore's internal mutex is not redundant as it is needed to protect its critical section (see the next section).

Waiting

Consider the following line for waiting on the semaphore:

int wait(mysem_t * s) {
  acquire(&s->mut);                 
  while (atomic_load(&s->val) <= 0);
  atomic_fetch_sub(&s->val, 1);
  release(&s->mut);
  return 0;
} // wait

While the atomic_load and atomic_fetch_sub functions themselves are guaranteed to be atomic by <stdatomic.h>, we have not guarantee that both lines involving these functions will execute atomically as a block. Therefore, we treat this portion of code as its own critical section with respect to the semaphore and use a mutex in order to ensure mutual exclusion.

POSIX Semaphores

Linux usually comes with the POSIX semaphores implementation. You can drop it in to this example by omitting the mutex-based implementation, including <semaphore.h>, and using the following:

sem_t sem;
#define wait(s) sem_wait(s)
#define signal(s) sem_post(s)

See sem_wait(3) and sem_overview(7) for more details.

sem.c

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdatomic.h>
#include <assert.h>

#define PING "ping"
#define PONG "pong"

void critical(const char * str) {
  size_t len = strlen(str);
  for (size_t i = 0; i < len; ++i) {
    printf("%c", str[i]);
  } // for
  printf("\n");
} // str

typedef volatile struct {
  volatile atomic_int val;
  volatile atomic_flag mut;
} mysem_t;
mysem_t sem;

#define acquire(m) while (atomic_flag_test_and_set(m))
#define release(m) atomic_flag_clear(m)

int wait(mysem_t * s) {
  acquire(&s->mut);                 
  while (atomic_load(&s->val) <= 0);
  atomic_fetch_sub(&s->val, 1);
  release(&s->mut);
  return 0;
} // wait

int signal(mysem_t * s) {
  return atomic_fetch_add(&s->val, 1);
} // signal

void * pingpong(void * p) {
  char * msg = (char *) p;
  for (;;) {
    wait(&sem);
    critical(msg);
    signal(&sem);
  } // for 
} // pingpong

int main() {
  setvbuf(stdout, NULL, _IONBF, 0);
  assert(ATOMIC_INT_LOCK_FREE == 2);
  atomic_init(&sem.val, 1);
  pthread_t ping;
  pthread_t pong;
  pthread_create(&ping, NULL, pingpong, PING);
  pthread_create(&pong, NULL, pingpong, PONG);
  for(;;);
  return 0;
} // main

Thanks!