dekkers.c

/* Implementation of Dekker's algorithm */
/* It allows two threads to share a single-use resource without conflict */
/* It uses only a shared memory for communication. */

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

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

/* Indicate the intention to enter the critical section */
static bool wants_to_enter[2] = { false, false };
/* Indicate who has proprity between the processors */
static unsigned int turn = 0; /* or random initialized between [0 ; 1] */

/* Indicate other thread id */
static unsigned int other_tid(unsigned int tid) {
  return tid == 1 ? 0 : 1;
}

/* Will safely execute task for a thread (represented by tid) */
static void dekkers_choice(unsigned int tid, void task(void)) {
  /* I wan't to enter critical section */
  wants_to_enter[tid] = true;
  /* But if other thread(s) also want to do so, I will have to ensure it's my */
  /* turn to enter the critical section. If it's my turn, the other thread(s) */
  /* will not want to enter the critical section */
  while (wants_to_enter[other_tid(tid)] == true) {
    if (turn != tid) {
      /* I will hide my itend to enter the critical section so I can focus on */
      /* waiting for my turn */
      wants_to_enter[tid] = false;
      while (turn != tid) {
        /* I'm busy waiting for my turn */
      }
      /* It's now my turn, I'll signal that I want to enter the critical */
      /* section again */
      wants_to_enter[tid] = true;
    }
    /* Now it's my turn and I signalled it, I can enter the critical section */
  }

  /* BEGIN critical section */
  task();
  /* END critical section */

  /* I will signal the other thread(s) turn */
  turn = other_tid(tid);
  /* And signal other thread(s) that I don't want to enter the critical */
  /* section anymore */
  wants_to_enter[tid] = false;
}

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

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

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

int main() {
  unsigned int tid[2] = { 0, 1 };
  pthread_t t0, t1;

  c = 0;

  pthread_create(&t0, NULL, inc_unsafe, &tid[0]);
  pthread_create(&t1, NULL, inc_unsafe, &tid[1]);

  pthread_join(t0, NULL);
  pthread_join(t1, NULL);

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

  c = 0;

  pthread_create(&t0, NULL, inc_safe, &tid[0]);
  pthread_create(&t1, NULL, inc_safe, &tid[1]);

  pthread_join(t0, NULL);
  pthread_join(t1, NULL);

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