SynchronizedArrayList implemented using reader writer synchronization 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:


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


I request reviewers to provide feedback on following:


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




import java.util.ArrayList;

public class SynchronizedArrayList {
    private ArrayList&lt;Object&gt; list = new ArrayList&lt;Object&gt;();
    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
    }
}
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.


There can be many readers.

Yes.
There can only be just one writer.

Yes.
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 &lt; 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 &lt; 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
    }
}