How does a read-write mutex/lock work?

Question

Let's say I'm programming in a threading framework that does not have multiple-reader/single-writer mutexes. Can I implement their functionality with the following:

Create two mutexes: a recursive (lock counting) one for readers and a binary one for the writer.

Write:

• acquire lock on binary mutex
• wait until recursive mutex has lock count zero
• actual write
• release lock on binary mutex

Read:

• acquire lock on binary mutex (so I know the writer is not active)
• increment count of recursive mutex
• release lock on binary mutex
• actual read
• decrement count of recursive mutex

This is not homework. I have no formal training in concurrent programming, and am trying to grasp the issues. If someone can point out a flaw, spell out the invariants or provide a better algorithm, I'd be very pleased. A good reference, either online or on dead trees, would also be appreciated.

Solution 1

The following is taken directly from The Art of Multiprocessor Programming which is a good book to learn about this stuff. There's actually 2 implementations presented: a simple version and a fair version. I'll go ahead and reproduce the fair version.

One of the requirements for this implementation is that you have a condition variable primitive. I'll try to figure out a way to remove it but that might take me a little while. Until then, this should still be better than nothing. Note that it's also possible to implement this primitive using only locks.

public class FifoReadWriteLock {
    int readAcquires = 0, readReleases = 0;
    boolean writer = false;
    ReentrantLock lock;
    Condition condition = lock.newCondition(); // This is the condition variable.

    void readLock () {
        lock.lock();
        try {
            while(writer)
                condition.await();
            readAcquires++;
        }
        finally {
            lock.unlock();
        }
    }

    void readUnlock () {
        lock.lock();
        try {
            readReleases++;
            if (readAcquires == readReleases)
                condition.signalAll();
        }
        finally {
            lock.unlock();
        }
    }

    void writeLock () {
        lock.lock();
        try {
            while (writer)
                condition.await();

            writer = true;

            while (readAcquires != readReleases)
                condition.await();
        }
        finally {
            lock.unlock();
        }
    }

    void writeUnlock() {
        writer = false;
        condition.signalAll();
    }
}

First off, I simplified the code a little but the algorithm remains the same. There also happens to be an error in the book for this algorithm which is corrected in the errata. If you plan on reading the book, keep the errata close by or you'll end up being very confused (like me a few minutes ago when I was trying to re-understand the algorithm). Note that on the bright side, this is a good thing since it keeps you on your toes and that's a requirement when you're dealing with concurrency.

Next, while this may be a Java implementation, only use it as pseudo code. When doing the actual implementation you'll have to be carefull about the memory model of the language or you'll definitely end up with a headache. As an example, I think that the readAcquires and readReleases and writer variable all have to be declared as volatile in Java or the compiler is free to optimize them out of the loops. This is because in a strictly sequential programs there's no point in continuously looping on a variable that is never changed inside the loop. Note that my Java is a little rusty so I might be wrong. There's also another issue with integer overflow of the readReleases and readAcquires variables which is ignored in the algorithm.

One last note before I explain the algorithm. The condition variable is initialized using the lock. That means that when a thread calls condition.await(), it gives up its ownership of the lock. Once it's woken up by a call to condition.signalAll() the thread will resume once it has reacquired the lock.

Finally, here's how and why it works. The readReleases and readAcquires variables keep track of the number threads that have acquired and released the read lock. When these are equal, no thread has the read lock. The writer variable indicates that a thread is trying to acquire the write lock or it already has it.

The read lock part of the algorithm is fairly simple. When trying to lock, it first checks to see if a writer is holding the lock or is trying to acquire it. If so, it waits until the writer is done and then claims the lock for the readers by incrementing the readAcquires variable. When unlocking, a thread increases the readReleases variable and if there's no more readers, it notifies any writers that may be waiting.

The write lock part of the algorithm isn't much more complicated. To lock, a thread must first check whether any other writer is active. If they are, it has to wait until the other writer is done. It then indicates that it wants the lock by setting writer to true (note that it doesn't hold it yet). It then waits until there's no more readers before continuing. To unlock, it simply sets the variable writer to false and notifies any other threads that might be waiting.

This algorithm is fair because the readers can't block a writer indefinitely. Once a writer indicates that it wants to acquire the lock, no more readers can acquire the lock. After that the writer simply waits for the last remaining readers to finish up before continuing. Note that there's still the possibility of a writer indefinitely blocking another writer. That's a fairly rare case but the algorithm could be improved to take that into account.

---

So I re-read your question and realised that I partly (badly) answered it with the algorithm presented below. So here's my second attempt.

The algorithm, you described is fairly similar to the simple version presented in the book I mentionned. The only problem is that A) it's not fair and B) I'm not sure how you would implement wait until recursive mutex has lock count zero. For A), see above and for B), the book uses a single int to keep track of the readers and a condition variable to do the signalling.

Solution 2

1. You may want to prevent write starvation, to accomplish this you can either give preference to writes or make mutex fair.
   ReadWriteLock Java's interface documentation says Writer preference is common,
   ReentrantReadWriteLock class documentation says This class does not impose a reader or writer preference ordering for lock access. However, it does support an optional fairness policy.

2. Note R..'s comment

   Rather than locking and unlocking the binary mutex for reading, you can just check the binary mutex state after incrementing the count on the recursive mutex, and wait (spin/yield/futex_wait/whatever) if it's locked until it becomes unlocked

3. Recommended reading:
   Programming with POSIX Threads
   Perl's RWLock
   Java's ReadWriteLock documentation.

Comments

[Fred Foo]

I'll read your full answer tomorrow, but anyway you're right about the flaws in my scheme. +1.

[user454322]

Nice answer. However, the code in the answer has serious flaws, e.g., variables are not synchronized, starvation risk....so follow @Ze Blob advice only use it as pseudo code.

[Admin]

I just want to mention that the algorithm "Ze Blob" suggested is not fair either. Suppose you have active readers. Now arrives a writer, increases the writers counter (well sets it to 1). Then arrives another writer (and gets blocked on the writer cond var). Now 1000 readers arrive (and also getting blocked on the cond var). And now active readers finish. What will happen now? You are releasing one writer (which may be the second writer and not the first one). In addition you releasing ll the readers. So the chances that now again readers will get inside and writers will wait again.

[Miguel Gamboa]

Is the writeUnlock() correct? Can we call condition.signalAll(); without the lock acquisition? If you try it you may get a java.lang.IllegalMonitorStateException.

[Ze Blob]

@MiguelGamboa As mentioned, the code should be treated as pseudo-code only. Some implementation of a condition variable doesn't require that the lock be held to signal while others do. Adjust the as necessary.

[Miguel Gamboa]

IMHO this is a typo from the book’s example. I would understand the pseudo-code argument if there was a consistent use of the signalAll() method. However, some examples use it with the lock held and others not.

[Ze Blob]

Note that readUnlock doesn't requires a lock because of the call to signalAll. It's there to synchronize the writes and reads of the readReleases and readAcquires which could otherwise be modified by another read thread and lead to inconsistent results. writeUnlock on the other hand already has exclusive ownership of the lock and therefore doesn't require a lock. Unfortunately, this text box is a bit too tiny to go into the full gory details.

[Miguel Gamboa]

@ZeBlob Nevertheless you are getting a Condition from a ReentrantLock through its method newCondition() which states: The returned Condition instance supports the same usages as do the Object monitor methods … If this lock is not held when any of the Condition waiting or signalling methods are called, then an IllegalMonitorStateException is thrown.. So, maybe your argument that “condition variable doesn't require that the lock be held to signal” is not acceptable.

[Calicoder]

I'm almost certain this implementation is broken. Here's why. readAcquires and readReleases can only be modified by a thread that has the lock. That's what the code of readLock and readUnlock says. So, if your thread is currently inside of writeLock(), it will encounter this loop: while (readAcquires != readReleases) { condition.await(); }. This loop will never exit because readQcquired and readReleases can never change because writeLock() holds the lock, so the lock will be forever held by the writeLock() method, stuck in that loop.