The Reader-Writer Problem and Paradigms for Condition Variables
               by Gene Cooperman (gene@ccs.neu.edu)
               Copyright (c) 2022 -- all rights reserved

In the reader-writer problem, some threads execute a start function
'reader()' and other threads execute a start function 'writer()'.
Each thread acquires a read or write permission, does an arbitrary task
using that permission, and then releases the permission.  The 'acquire'
and 'release' phases are part of a critical section.  As described in
howto-1-mutex.txt, a paradigm should spend as little time as possible
in a critical section -- primarily, solely for accessing or modifying
some global shared variable,

In a first (partial) solution to the reader-writer problem, we consider
maintaining some global variables, protected by a mutex.
  int num_active_readers = 0;
  int num_active_writers = 0;
  int num_waiting_writers = 0;
  pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
The paradigm now looks like this for the reader (and something similar
for the writer):

void *reader(void *dummy) {
  // Acquire permission    
  pthread_mutex_lock(&mut);
  num_active_readers++;
  pthread_mutex_unlock(&mut);
  // Do task
  ...
  // Release permission    
  pthread_mutex_lock(&mut);
  num_active_readers--;
  pthread_mutex_unlock(&mut);
}

This is fine, but it is not enforcing the fundamental invariant for
the reader-writer problem:
INVARIANT:  Either there is exactly one active writer (and no active readers),
            Or there are zero active writers and arbitrarily many
            active readers. 

To enforce this, we need to make a reader or writer wait before acquiring
permission if the "active" permission would then violate the invariant.
For the reader:

void *reader(void *) { // VERSION 2 of reader()
  // Acquire permission    
  pthread_mutex_lock(&mut);
  while (num_active_writers > 0 || num_waiting_writers > 0) {
    WAIT(&mut);
  }
  num_active_readers++;
  pthread_mutex_unlock(&mut);
  // Do task
  ...
  // Release permission    
  pthread_mutex_lock(&mut);
  num_active_readers--;
  // SIGNAL OR POST TO WAITING THREADS THAT num_active_readers CHANGED.
  pthread_mutex_unlock(&mut);
}

Note that we use 'while'.  If the reader is interrupted for waiting
for any reason, it must again check the invariant before gaining
an active read permission.  Note that the 'while' condition chosen
here gives priority to writers.  If there is even one waiting writer,
then the reader must wait for the writer to do its task.

One can write an analogous version for a writer:

void *writer(void *dummy) {
  ...
  while (num_active_readers > 0 || num_active_writers > 0) {
    num_waiting_writers++;
    WAIT(&mut);
    num_waiting_writers--;
  }
  num_active_writers++;
  // Do task
  ...
  // Release permission    
  num_active_writers--;
  // SIGNAL OR POST TO WAITING THREADS THAT num_active_writers CHANGED.
}

Until now, we have not used condition variables.  But it now becomes
clear why the reader-writer problem was one of the original problems
that motivated the creation of:
  int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *attr);
  int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
  int pthread_cond_signal(pthread_cond_t *cond);
  int pthread_cond_broadcast(pthread_cond_t *cond);

So, 'WAIT(&mut)' becomes 'pthread_cond_wait(&cond, &mut)'. 
And:
> // SIGNAL OR POST TO WAITING THREADS THAT num_active_writers CHANGED.
becomes:
  pthread_cond_broadcast(&cond);

NOTE:  As an optimization, we could signal to one waiting thread instead
of broadcasting to all of them:
  pthread_cond_signal(&cond);
If 'pthread_cond_signal' works correctly, then 'pthread_cond_broadcast'
is also guaranteed to work correctly.  But not necessarily the reverse.

So, you can now guess the semantics of the 'pthread_cond_XXX' functions
even before reading the main page.  We can think of 'pthread_cond_wait'
analogous to 'sem_wait' and sending the thread to "WAITING_ROOM(cond)",
a "waiting room" associated with the 'cond' condition variable.
The call `pthread_cond_wait(&cond, &mut)' unlocks the mutex 'mut'
and puts the thread in a sleep state.  Hence, the "WAITING_ROOM(cond)"
is not part of the critical section protected by 'mut'.

Later, 'pthread_cond_broadcast(&cond)' will wake all threads in
"WAITING_ROOM(cond)".  Alternatively, 'pthread_cond_signal(&cond)'
will wake a single threads in "WAITING_ROOM(cond)".  It is undefined
which thread will be woken, but most implementations approximate a FIFO
wakeup policy.

DIAGRAM OF THE LIFE CYCLE OF A THREAD:
    enter crit. section -> test condition in 'while' ->
    WAIT:leave crit. section -> sleep -> WAKE ->
    enter crit. section (acquire mutex lock) ->
    WAIT again, or ACQUIRE permission and leave crit. section
    ... DO task ...
    enter crit. section -> signal/broadcast to waiting threads ->
    leave crit. section

I WILL ADD AN ACCOMPANYING DIAGRAM LATER (IN PROGRESS).