1
\$\begingroup\$

I am trying to understand the workings of reader writer locks. For the sake of learning, I implemented reader writer synchronization by my own. I implemented SynchronizedArrayList with reader writer synchronization.

I set out with following objective:

  1. There can be many readers.
  2. There can only be just one writer.
  3. Fairness among writers. In other words, writers should be served in FIFO manner.

I request reviewers to provide feedback on following:

  1. Correctness of code by considering the above set objectives.
  2. Efficiency of code.
  3. Any other improvements.

import java.util.ArrayList;

public class SynchronizedArrayList {
    private ArrayList<Object> list = new ArrayList<Object>();
    private int readerCount = 0;

    public void add(int index, Object obj)
    {
        synchronized(this) {
            while (readerCount != 0)
                waitForSignal();

            addInternal(index, obj);
        }
    }

    public Object get(int index) {
        synchronized(this) {
            readerCount++;
        }

        Object toReturn = getInternal(index);

        synchronized(this) {
            readerCount--;
            if (readerCount == 0) {
                this.notify();
            }
        }

        return toReturn;

    }

    private Object getInternal(int index) {
        return list.get(index);
    }

    private void addInternal(int index, Object obj) {
        list.add(index, obj);
    }

    private void waitForSignal() {
        //not yet implemented
    }
}
\$\endgroup\$
  • \$\begingroup\$ Objective #2 (one writer) appears to conflict with objective #3 (Fairness among writers.) Can you clarify this? \$\endgroup\$ – VoiceOfUnreason Jul 28 '14 at 14:59
  • \$\begingroup\$ @VoiceOfUnreason I suppose he simply means : writers acquire a fair lock in the order in which they requested it. \$\endgroup\$ – bowmore Jul 28 '14 at 15:29
4
\$\begingroup\$

My answer will try to cover some ground @JvR seems to have missed. (as he said concurrency is hard, 4 eyes see more than 2)

Question you didn't really ask, but actually probably the most important one :

Is this class thread safe?

No. If getInternal() throws an exception (say IndexOutOfBoundsException for instance) the readerCount is never decremented again. Result : Any writer will wait forever to be allowed to write.

Assume we fix it?

Thread safe? Yes, but now not effecient. Under high reader contention a writer may never get the chance to write, since a write lock request does not prevent new readers to acquire a lock. This can keep readerCount above zero indefinitely.

Another efficiency problem : you synchronize on this. If any 3rd party class locks on the list, it will no longer function correctly. Readers and writers will be blocked until that lock is released.

I concur with @JvR's answers to your three questions.

  1. There can be many readers.

    Yes.

  2. There can only be just one writer.

    Yes.

  3. Fairness among writers. In other words, writers should be served in FIFO manner.

    No. From Java Concurrency in Practice :

intrinsic locking offers no deterministic fairness guarantees, but the statistical fairness guarantees of most locking implementations are good enough for almost all situations. The language specification does not require the JVM to implement intrinsic locks fairly, and no production JVMs do.

@JvR covers the solution you'd need to implement for the fairness problem quite aptly already.

Other improvements?

  • @JvR mentioned generics, but I'd like to broaden that remark to : You're not implementing the List interface. Ok you're not actually making a useful class, but learing about locks, so probably not that important.
  • addInternal() and getInternal() : too thin to be a private method : inline them.
  • initialization of the internal list : use the diamond operator. (if you're on 7+)

Here is the code I used to play with your list :

private static final int TASKS = 20; // if you don't see the high contention problem : increase this value.

static SynchronizedArrayList list1 = new SynchronizedArrayList();

public static void main(String[] args) {
    list1 = new SynchronizedArrayList();
    CountDownLatch start = new CountDownLatch(1);
    CountDownLatch ready = new CountDownLatch(TASKS);
    final ReadWriteLock lock = new ReentrantReadWriteLock();

    ExecutorService executorService = Executors.newFixedThreadPool(TASKS);

    executorService.submit(new Runnable() {
        @Override
        public void run() {
            ready.countDown();
            try {
                start.await();
                for (int i = 0; i < 50; i++) {
                    Thread.sleep(10);
                    list1.add(i, i);
                    System.out.println("             Written " + i);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    });

    for (int i = 0; i < TASKS - 1; i++) {
        executorService.submit(new Runnable() {
            @Override
            public void run() {
                ready.countDown();
                try {
                    start.await();
                    boolean keepOnTrucking = true;
                    while (keepOnTrucking) {
                        keepOnTrucking = false;
                        try {
                            list1.get(49);
                        } catch (Exception e) {
                            keepOnTrucking = true;
                        }
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        });
    }

    try {
        ready.await();
        start.countDown();

        executorService.shutdown();
        executorService.awaitTermination(5, TimeUnit.MINUTES);

    } catch (InterruptedException e) {
        // just end
    }
}
\$\endgroup\$
  • \$\begingroup\$ Good catch on the exception; can't believe I missed that! \$\endgroup\$ – JvR Jul 28 '14 at 21:27
2
\$\begingroup\$

You Must Construct Additional Pylons Code

private void waitForSignal() {
    //not yet implemented
}

This will be a pretty significant part of your implementation. I'll take it at face value and assume it's just looping on wait(), but this is going to be the meat of your stuff.

Correctness of code

  1. (pass!) There can be many readers.
  2. (pass!) There can only be just one writer. (simultaneously, I assume)
  3. (fail!) Fairness among writers. In other words, writers should be served in FIFO manner.

synchronized does not give any ordering guarantees. This gives JVM implementations the greatest freedom and opportunity for optimisation and throughput, but makes access order unpredictible. If you don't want to use any of the prebuilt (and tuned and optimised and tested) solutions in java.util.concurrent, you'll have to manage a FIFO queue of your own. (1)

(1) Caution: Concurrency is hard, and not like long division hard; more like managing a fastfood restaurant with a troupe of gremlins hard. I mean, just peek at the source code of classes in j.u.c. I'm usually all for re-inventing the wheel as an exercise, but this is some serious chow to chew.

notify() vs notifyAll()

Object.notify() is a tricky thing to use and almost always leaves room for a potential deadlock. It's tempting to use it instead of the safer notifyAll() because, come on, only one thread is going to get access anyway, but it's not safe.

The trouble is that all waiting threads are not equal: there is only one that should be woken, and that's the one at the head of the queue. Every other thread needs to pass on the notification, but the woken thread is chosen at random, with no guarantee that eventually the head of the queue will be chosen. So thread A could be waiting forever while C, D, and E poke each other at random.

Note: notify() would be safe if you did not have a FIFO requirement!

Efficiency

This is really hard to judge, partly because different JVMs and versions have different synchronized implementations, partly because waitForSignal() is missing. The current code doesn't have any obvious or glaring inefficiencies, least of all that are likely to be consistent across implementations.

Miscellaneous

Your class doesn't use generics for its elements. It's not important for the concurrency, but just sayin'.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.