Problem 20.7 Readers-Writers problem, alternative solution

#1

It seems to me it would be easier to just let the first entering reader lock the mutex and the last exiting reader to unlock it. The writer will just do regular lock/unlock. So we can implement like this:

public class RWLock {
	protected boolean locked;
	protected int readerCount;

	//These are regular mutex lock/unlock operations
	protected synchronized void lock() {
		while(locked) wait();
		locked = true;
	}
	protected synchronized void unlock() {
		locked = false;
		notifyAll();
	}

	//Writer just does lock/unlock
	public void writeLock() { lock(); }
	public void writeUnlock() { unlock(); }

	public synchronized void readLock() {
		if (readerCount == 0)
			lock();
		readerCount++;
	}
	
	public synchronized void readUnlock() {
		if (--readerCount == 0)
			unlock();
	}
}
0 Likes

#2

Oops, sorry, it seems there may be a problem if 2 readers are waiting for a writer then only one of them will be allowed to proceed. It seems that using notifyAll() instead of notify() can fix this problem, i ll need to think this through. Sorry for posting, I don’t see a way to delete my post here.

0 Likes

#3

That’s fine, and feels free to come and modify the solution.

0 Likes

#4

Actually looks like the above solution works as long as we use notifyAll() instead of notify() in unlock(). I wrote a test program that launches many threads as readers and writers trying to enter critical section and staying there for random amount of time, checks lock invariant and gathers some statistics. I can post the test program, although it is more involved.
The above solution of course favors readers over writers since once at least one reader is in critical section, other readers don’t have to wait, so this can lead to writer starvation. I ll think about how to modify this for problems 20.8 and 20.9.

0 Likes

#5

I think most of time, you shall always use notifyAll() instead of notify() because notify() might not invoke the thread you want. Again, thanks for this contribution!

0 Likes

#6

We might want to use notify() instead of notifyAll() for a regular lock (where only one thread can be in), wouldn’t we waste performance waking up all threads if we already know only one of them can acquire the lock?

Btw, i think for the 2nd problem (writer-preference RWLock) we can build up on the first solution by also keeping a count of writers waiting for critical section:

	public static class RWLock2 extends RWLock {
		private int writerWaitCount; //number of writers waiting
		
		public synchronized void writeLock() throws InterruptedException
		{
			writerWaitCount++;
			super.writeLock();
			writerWaitCount--;
		}

		public synchronized void readLock() throws InterruptedException
		{
			while(writerWaitCount != 0 || (readerCount == 0 && locked))
				wait();
			locked = true;
			readerCount++;
		}
	}

This way the reader will not be allowed to enter if there are any writers waiting.

Btw, 20.8 solution in the book suggest for each reader to lock and immediately release LW. I m not sure if this is 100% effective. For the writer that already acquired LW, yeah, the other readers will have to wait. But there might be other writers waiting also. So once LW is released, it seems that we don’t have any guarantee if the next one to acquire LW will be reader or writer.

The solution above offers stronger guarantee, not sure if the formulation of the problem requires it though.

0 Likes