The Reader-Writer problem is a classic synchronisation problem in Operating Systems. There are several writers and readers accessing a shared resource such as a data array. The writers fill/update the data in the shared array while the readers use the data but do not modify the shared array. The problem is to ensure that writers do not overwrite data written either by other writers or before it is used by the readers. There exist many versions of the problem depending on the number of writers and readers as well as the size of the shared array.
In this lesson, we talk about the first and the simplest version of the problem, viz. the single-reader-single-writer problem. There is only a single writer writing into the array and a single reader using the data written into the array. The shared resource is a linear buffer/array and the process terminates when all the cells in the buffer are written by the writer and used by the reader.
What are the synchronisation issues here?
The solution requires the use of a condition variable from the
The writer thread needs to send a signal as and when needed whenever it writes into the cell. Similarly, the reader thread needs to check the condition if there are any newly-written items before continuing its execution.
The code to handle the reader-writer problem is split into four sections for easy understanding.
Two versions of the code are given. The first, does not have any synchronisation and it illustrates the kind of errors we can get. The second is the correct version that synchronises the reader and writer threads when they modify the shared resources.
The key in writing multi-threaded programs is to clearly distinguish between shared variables that require that require synchronisation from those that don't. It is also a great idea to identify which variables are shared between writers and which between readers.
One way of achieving this is by defining structures that bring together such variables. In the header section below, it can be seen that there are two variables which are shared between the reader and the writer.
There are also two variables which are used only by the writer thread.
Finally, the two thread functions are
//%cflags: -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define MAXTHREADS 20
#define NMAX 2000000
int nitems; /* No. of items to write */
struct {
int buff[NMAX]; /* Shared buffer */
int nready; /* No. of items to be verified by reader */
} shared;
/* All variables shared by the writer threads are put in a
variable called wshared so that we know easily that access
to these variables may need synchronisation */
struct {
int nput;
int nval;
} wshared;
void *writer(void *); /* Writer thread function */
void *reader(void *); /* Reader thread function */
int count; /* No. items written by each
writer */
The
After creating the two threads,
/* Process creates two threads: one writer and one reader and
runs them concurrently. */
int main(int argc, char *argv[])
{
int i, nthreads;
pthread_t tid[2];
nthreads = atoi(argv[1]); /* No. of threads to create */
nitems = atoi(argv[2]); /* No. of items to write */
count = 0;
if (pthread_create(&tid[0], NULL, writer,
(void *)&count) != 0) {
fprintf(stderr, "Error creating writer thread\n");
exit(1);
} /* Created writer thread */
if (pthread_create(&tid[1], NULL, reader,
(void *)NULL) != 0) {
fprintf(stderr, "Error creating reader thread\n");
exit(1);
} /* Created reader thread */
pthread_join(tid[0], NULL); /* Wait for writer to exit */
printf("Writer thread completed after writing %d items\n", count);
pthread_join(tid[1], NULL); /* Wait for reader to exit */
exit(0);
}
In the single-writer version, the writer thread is quite simple. Initially, both the shared variables
/* Writer thread simply writes items into the shared buffer until
nitems are written */
void *writer(void *count)
{
for ( ; ; ) {
if (wshared.nput >= nitems) {
return(NULL);
}
/* These three statements simply write the value
nval into location nput such that buff[i] = i
for all i */
shared.buff[wshared.nput] = wshared.nval;
wshared.nput++;
wshared.nval++;
*((int *) count) += 1; /* Return no. of items written */
}
}
The
/* Reader thread checks every cell in the buff array to ensure that
buff[i] = i. Otherwise, it prints an error giving information
about the location(s) and value(s) written incorrectly */
void *reader(void *count)
{
int i;
for (i=0; i<nitems; i++) {
if (shared.buff[i] != i)
printf("Error found: buff[%d] = %d\n", i, shared.buff[i]);
}
return(NULL);
}
Let us compile and run this program; but, wait a minute, where are the synchronisation primitives? Well, there aren't any yet! Let us see what happens when this program runs without any synchronisation between the writer and reader threads. Run the program 10 times (as below) and carefully check the output.
Repeat the above experiment but with
Finally, look carefully at the errors, they will be of two kinds:
This is the version where we put in the synchronisation primitives and make the program run correctly: the reader never prints anything! Let us now look at the modifications needed.
As both these are required really for the reader to synchronise with the writer, we create a new structure called
The new header section is given below. Note the initialisation of the two synchronisation variables. These ensure that the mutex variable is initially unlocked and the condition variable is not ready and in wait state.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define MAXTHREADS 20
#define NMAX 2000000
int nitems; /* No. of items to write */
struct {
int buff[NMAX]; /* Shared buffer */
int nready; /* No. of items to be verified by reader */
} shared;
/* All variables shared by the writer threads are put in a
variable called wshared so that we know easily that access
to these variables may need synchronisation */
struct {
int nput;
int nval;
} wshared;
struct {
pthread_mutex_t cvmutex;
pthread_cond_t cvar;
} rshared = {
PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER
};
void *writer(void *); /* Writer thread function */
void *reader(void *); /* Reader thread function */
int count; /* No. items written by each
writer */
The writer now needs to check if all the previously written items are already checked by the reader. If that is the case,
The new code is given below.
void *writer(void *count)
{
for ( ; ; ) {
if (wshared.nput >= nitems) {
return(NULL);
}
/* These three statements simply write the value
nval into location nput such that buff[i] = i
for all i */
shared.buff[wshared.nput] = wshared.nval;
wshared.nput++;
wshared.nval++;
pthread_mutex_lock(&rshared.cvmutex);
if (shared.nready == 0)
pthread_cond_signal(&rshared.cvar);
shared.nready++;
pthread_mutex_unlock(&rshared.cvmutex);
*((int *) count) += 1; /* Return no. of items written */
}
}
Reader also needs a bit of extra code. First the reader locks the mutex to get exclusive access and checks if there are any newly written items to read. This is done by checking the variable
Here is the new version.
void *reader(void *count)
{
int i;
for (i=0; i<nitems; i++) {
pthread_mutex_lock(&rshared.cvmutex);
while (shared.nready == 0)
pthread_cond_wait(&rshared.cvar, &rshared.cvmutex);
shared.nready--;
pthread_mutex_unlock(&rshared.cvmutex);
if (shared.buff[i] != i)
printf("Error found: buff[%d] = %d\n", i, shared.buff[i]);
}
return(NULL);
}
Compile and run the code again and see if you get any errors. Understand the code thoroughly before you go to the next version which is naturally more complex!