How to understand the "non-fair" mode of ReentrantReadWriteLock?

Question

ReentrantReadWriteLock has a fair and non-fair(default) mode, but the document is so hard for me to understand it.

How can I understand it? It's great if there is some code example to demo it.

UPDATE

If I have a writing thread, and many many reading thread, which mode is better to use? If I use non-fair mode, is it possible the writing thread has little chance to get the lock?

Answer 1

Non-fair means that when the lock is ready to be obtained by a new thread, the lock gives no guarantees to the fairness of who obtains the lock (assuming there are multiple threads requesting the lock at the time). In other words, it is conceivable that one thread might be continuously starved because other threads always manage to arbitrarily get the lock instead of it.

Fair mode acts more like first-come-first-served, where threads are guaranteed some level of fairness that they will obtain the lock in a fair manner (e.g. before a thread that started waiting long after).

Edit

Here is an example program that demonstrates the fairness of locks (in that write lock requests for a fair lock are first come, first served). Compare the results when FAIR = true (the threads are always served in order) versus FAIR = false (the threads are sometimes served out of order).

import java.util.concurrent.locks.ReentrantReadWriteLock;

public class FairLocking {

    public static final boolean FAIR = true;
    private static final int NUM_THREADS = 3;

    private static volatile int expectedIndex = 0;

    public static void main(String[] args) throws InterruptedException {
        ReentrantReadWriteLock.WriteLock lock = new ReentrantReadWriteLock(FAIR).writeLock();

        // we grab the lock to start to make sure the threads don't start until we're ready
        lock.lock();

        for (int i = 0; i < NUM_THREADS; i++) {
            new Thread(new ExampleRunnable(i, lock)).start();

            // a cheap way to make sure that runnable 0 requests the first lock
            // before runnable 1
            Thread.sleep(10);
        }

        // let the threads go
        lock.unlock();
    }

    private static class ExampleRunnable implements Runnable {
        private final int index;
        private final ReentrantReadWriteLock.WriteLock writeLock;

        public ExampleRunnable(int index, ReentrantReadWriteLock.WriteLock writeLock) {
            this.index = index;
            this.writeLock = writeLock;
        }

        public void run() {
            while(true) {
                writeLock.lock();
                try {
                    // this sleep is a cheap way to make sure the previous thread loops
                    // around before another thread grabs the lock, does its work,
                    // loops around and requests the lock again ahead of it.
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    //ignored
                }
                if (index != expectedIndex) {
                    System.out.printf("Unexpected thread obtained lock! " +
                            "Expected: %d Actual: %d%n", expectedIndex, index);
                    System.exit(0);
                }

                expectedIndex = (expectedIndex+1) % NUM_THREADS;
                writeLock.unlock();
            }
        }
    }
}

Edit (again)

Regarding your update, with non-fair locking it's not that there's a possibility that a thread will have a low chance of getting a lock, but rather that there's a low chance that a thread will have to wait a bit.

Now, typically as the starvation period increases, the probability of that length of time actually occuring decreases...just as flipping a coin "heads" 10 consecutive times is less likely to occur than flipping a coin "heads" 9 consecutive times.

But if the selection algorithm for multiple waiting threads was something non-randomized, like "the thread with the alphabetically-first name always gets the lock" then you might have a real problem because the probability does not necessarily decrease as the thread gets more and more starved...if a coin is weighted to "heads" 10 consecutive heads is essentially as likely as 9 consecutive heads.

I believe that in implementations of non-fair locking a somewhat "fair" coin is used. So the question really becomes fairness (and thus, latency) vs throughput. Using non-fair locking typically results in better throughput but at the expense of the occasional spike in latency for a lock request. Which is better for you depends on your own requirements.