CIS 307: Readers and Writers

The Readers and Writers problem is discussed in Tanenbaum on page 58 with code on page 60. In his solution readers and writers are scheduled alike. Here is a paraphrase of Tanenbaum's solution [this was originally proposed in [1]]:

	GLOBAL VARIABLES:
		mutex, db : semaphore := 1;
		readcount : integer   := 0;
	READER:
		p(mutex);
		readcount++;
		if (readcount is 1) then p(db);
		v(mutex);
		CRITICAL REGION where we read
		p(mutex);
		readcount--;
		if (readcount  is 0) then v(db);
		v(mutex);
	WRITER:
		p(db);
		CRITICAL REGION where we write
		v(db);

Notice that in this solution on the semaphore db we will have at most one reader (all other readers will wait on mutex). But once a reader gets in, all waiting readers can (but not necessarily do) get in ahead of waiting writers.

Here we see a solution where:

• If a writer is waiting no new reader can start reading
• When a writer finishes writing it lets all pending readers read, ahead of possibly waiting other writers.

	GLOBAL VARIABLES:
		mutex : semaphore := 1;
		readsleep, writesleep : semaphore := 0;
		readcount, readwait, writewait : integer := 0;
	READER:
		p(mutex);
		if (writewait > 0) {readwait++; v(mutex); p(readsleep);}
		else {readcount++; v(mutex);}
		CRITICAL REGION where we read
		p(mutex);
		readcount--;
		if (readcount is 0 and writewait>0) 
			{writewait--; v(writesleep);} 
		else
			v(mutex);
	WRITER:
		p(mutex);
		if (readcount>0)
			{writewait++; v(mutex); p(writesleep);}
		CRITICAL REGION where we write
		if (readwait>0)
			while (readwait>0) 
			    {readwait--; readcount++; v(readsleep);}
		else
			v(mutex);

Notice that for some mutex we do the p operation in a reader and the corresponding v operation in a writer, or viceversa.

And here is a paraphrase of the "classic" solution from [1]. In this solution Writers are given absolute priority over Readers.

	GLOBAL VARIABLES:
		mutex1 : semaphore := 1;
		mutex2 : semaphore := 1;
		mutex3 : semaphore := 1;
		db     : semaphore := 1;
		r      : semaphore := 1;
		readcount, writecount : integer := 0;
	READER:
		p(mutex3);
		  p(r);
		    p(mutex1);
		    readcount++;
		    if (readcount is 1) then p(db);
		    v(mutex1)
		  v(r);
		v(mutex3);
		CRITICAL REGION where we read
		p(mutex1);
		readcount--;
		if (readcount is 0) then v(db);
		v(mutex1);
	WRITER:
		p(mutex2);
		writecount++;
		if (writecount is 1) then p(r);
		v(mutex2);
		p(db);
		CRITICAL REGION where we write
		v(db);
		p(mutex2);
		writecount--;
		if (writecount is 0) then v(r);
		v(mutex2);

In this solution:

• mutex3 is only used by entering readers and it will force them to compete with each other without interfering with the writers or exiting readers.
• mutex1 is only used by exiting readers and at most one entering reader and it will force them to compete with each other without interfering with the writers.
• mutex2 is only used by writers.

The three solutions we have seen differ only in the way they schedule readers and writers. This kind of scheduling established by the use of synchronization commands (here p and v on semaphores) is called intermediate scheduling as distinct from the microscheduling taking place at the ready queue and in the semaphores themselves, and from the macroscheduling taking place at the level of jobs.

[1]P.J.Courtois,F.Heymans,D.L.Parnas: Concurrent Control with "Readers" and "Writers", CACM October 1971