Ballhausen's solution to classical reader-writers fairness problem

ballhausen.c

/* Ballhausen's solution to classical reader-writers fairness problem */
/* Initial problem : a continual flow of readers blocks writers from updating */
/* Ballhausen's solution :
 *  * one readers takes up the same space as all readers reading together
 *  * a semaphore access_db is used by readers to enter the database with a
 *    an initial value equalling the number of readers
 *  * every time a reader is accessing the db, the semaphore value is
 *    decremented
 *  * every time a reader is leaving the db, the semaphore value is incremented
 *  * writers want exclusive access to the db. It occupies all spaces step by
 *    step of the access_db semaphore by waiting for old readers to leave and
 *    such, blocking entry to the new ones
 *  * writers use a semaphore mutex to prevent deadlock between two writers
 *    trying to occupy half available space each
*/

#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <time.h>


#define N_READERS (10)
#define N_WRITERS (5)

static sem_t mutex;
static sem_t access_db;

/* sleeping function */
static void wait_a_bit(int const tid, unsigned int const wait) {
  srand(time(NULL) ^ (tid << 16));
  usleep((unsigned int)rand() % wait);
}

/* sleep a bit and return thread id */
static pid_t preprocess(void) {
  pid_t const tid = syscall(SYS_gettid);
  wait_a_bit((int)tid, 1000);
  return tid;
}

/* reader job */
static void *reader(void *args) {
  /* sleep a bit and retrieve thread id */
  pid_t const tid = preprocess();
  /* read 10 times */
  for (unsigned int i = 0 ; i < 10 ; ++i) {
    /* try to access database */
    sem_wait(&access_db);
    /* we can perform the reading operations */
    printf("READ reader(%u)\n", tid);
    /* leave database */
    sem_post(&access_db);
    /* we'll wait a bit (delaying display) */
    printf("WAIT reader(%u)\n", tid);
    wait_a_bit((int)tid, 10000000);
  }
  pthread_exit(0);
}

/* writer job */
static void *writer(void *args) {
  /* sleep a bit and retrieve thread id */
  pid_t const tid = preprocess();
  /* write 10 times */
  for (unsigned int i = 0 ; i < 10 ; ++i) {
    /* engage mutual exclusion for access_db semaphore */
    sem_wait(&mutex);
    /* try to have exclusive access to database over all readers */
    for (unsigned int i = 0 ; i < N_READERS ; ++i)
      sem_wait(&access_db);
    /* we can perform writing operations */
    printf("WRITE writer(%u)\n", tid);
    /* allow some readers to have access to database back */
    for (unsigned int i = 0 ; i < N_READERS ; ++i)
      sem_post(&access_db);
    /* we'll wait a bit (delaying display) before another writer can try to
     * access database */
    printf("WAIT writer(%u)\n", tid);
    wait_a_bit((int)tid, 10000000);
    /* allow other writer to access the access_db semaphore */
    sem_post(&mutex);
  }
  pthread_exit(0);
}

int main() {
  pthread_t t_r[N_READERS];
  pthread_t t_w[N_WRITERS];

  sem_init(&mutex, 0, 1); /* writers mutex for access_db manipulations */
  sem_init(&access_db, 0, N_READERS); /* slots for db access */

  /* create readers and writers threads */
  for (unsigned int i = 0 ; i < N_READERS; ++i)
    pthread_create(&t_r[i], NULL, reader, NULL);
  for (unsigned int i = 0 ; i < N_WRITERS; ++i)
    pthread_create(&t_w[i], NULL, writer, NULL);

  /* waiting for readers and writers */
  for (unsigned int i = 0 ; i < N_READERS; ++i)
    pthread_join(t_r[i], NULL);
  for (unsigned int i = 0 ; i < N_WRITERS; ++i)
    pthread_join(t_w[i], NULL);

  /* destroy semaphores */
  sem_destroy(&mutex);
  sem_destroy(&access_db);
}