lamports.c

/* Lamport's bakery algorithm */
/* Improve safety in the usage of shared resources among multiple threads by */
/* means of mutual exclusion */

/* Communications of the ACM, August 1974, Volume 17, Number 8, P.453 */

#include <pthread.h>
#include <stdbool.h>
#include <stdio.h>

#define NUM_THREADS (20)
#define NAN (0) /* invalid number */

/* The counter threads will increment */
static unsigned int c;

/* This indicates if a thread is choosing a number */
static bool choosing[NUM_THREADS] = { false };
/* This is the priority system, the smallest enters the critical section */
static unsigned int numbers[NUM_THREADS] = { NAN }; /* must have been unbound */

static unsigned int max_in_numbers(void) {
  /* Retrieve the greatest number in numbers[] */
  unsigned int max = 0;
  for (unsigned int i = 0 ; i < NUM_THREADS ; ++i) {
    if (numbers[i] > max)
      max = numbers[i];
  }
  return max;
}

#define LESS(i, j) \
  (numbers[j] < numbers[i]) || ((numbers[j] == numbers[i]) && (j < i))

/* i represent a single thread */
/* j is sequentially representing all the threads */
static void lock(unsigned int const i) {
  /* We are choosing our number */
  choosing[i] = true;
  /* We have a maximum value number */
  numbers[i] = 1 + max_in_numbers(); /* unsafe ? */
  /* We chose our number */
  choosing[i] = false;

  /* We will observe other threads */
  for (unsigned int j = 0 ; j < NUM_THREADS ; ++j) {
    /* We are waiting for every other thread j to choose a number */
    while (choosing[j] == true) {
      /* We are busy for an other thread j to choose its number */
    }
    /* We are waiting other threads to have a chose number which is strictly */
    /* less than ours */
    while (numbers[j] != NAN && LESS(i, j)) {
      /* Waiting for an other thread j to have a smaller number than our */
    }
  }
  /* At this point we have the smallest number of all the threads so we have */
  /* priority to enter the critical section */
}

static void unlock(unsigned int const i) {
  /* We reset our smallest number so an other thread can enter the critical */
  /* section */
  numbers[i] = NAN;
}

static void inc(void) {
  for (unsigned int i = 0 ; i < 5000 ; ++i) {
    c++;
  }
}

static void *inc_safe(void *args) {
  unsigned int tid = *(unsigned int *)args;
  lock(tid);
  inc();
  unlock(tid);
  pthread_exit(0);
}

static void *inc_unsafe(void *args) {
  (void)args;
  inc();
  pthread_exit(0);
}

int main() {
  unsigned int tid[NUM_THREADS];
  pthread_t t[NUM_THREADS];

  for (unsigned int i = 0 ; i < NUM_THREADS; ++i)
    tid[i] = i;

  c = 0;

  for (unsigned int i = 0 ; i < NUM_THREADS; ++i)
    pthread_create(&t[i], NULL, inc_unsafe, &tid[i]);

  for (unsigned int i = 0 ; i < NUM_THREADS; ++i)
    pthread_join(t[i], NULL);

  printf("counter (unsafe) = %d\n", c);

  c = 0;

  for (unsigned int i = 0 ; i < NUM_THREADS; ++i)
    pthread_create(&t[i], NULL, inc_safe, &tid[i]);

  for (unsigned int i = 0 ; i < NUM_THREADS; ++i)
    pthread_join(t[i], NULL);

  printf("counter (safe) = %d\n", c);
}