Concurrent linked list reader/writer not working properly

Question

I implemented my own concurrent linked list using Java's ReadWriteLock. I wrote the following ConcurrentLinkedList class using the readwritelock. Then I created a reader class: ListReader, and a writer class: ListWriter. Finally I created one writer class and two reader classes for testing.

ConcurrentLinkedList class

public class ConcurrentLinkedList<T> {
    public static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node<T> head = null;

    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public void add(T a) {
        writeLock.lock();
        try {
            Node<T> node = new Node<T>(a);
            Node<T> current = head;

            if (current == null) {
                current = node;
                head = current;
            } else {
                while (current.next != null) {
                    current = current.next;
                }
                current.next = node;
            }
        } finally {
            writeLock.unlock();
        }
    }

    public T get(int index) {
        readLock.lock();
        try {
            int i = 0;
            Node<T> current = head;

            while (current != null && i < index) {
                current = current.next;
                i++;
            }
            if (current == null)
                throw new IndexOutOfBoundsException();
            return current.data;
        } finally {
            readLock.unlock();
        }
    }

    int size() {
        readLock.lock();
        try {
            int size = 0;
            Node<T> current = head;
            while (current != null) {
                current = current.next;
                size++;
            }
            return size;
        } finally {
            readLock.unlock();
        }
    }
}

ListWriter class

public class ListWriter extends Thread {

    private ConcurrentLinkedList<Integer> list;
    private int[] arr;

    public ListWriter(ConcurrentLinkedList<Integer> list, int[] arr, String name) {
        this.list = list;
        this.arr = arr;
        setName(name);
    }

    @Override
    public void run() {
        for(int elem : arr) {
            list.add(elem);
            System.out.println("Thread " + getName() + " writing " + elem + " to the list");
            try {
                Thread.sleep(50);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

ListReader class

public class ListReader extends Thread {
    private ConcurrentLinkedList<Integer> list;

    public ListReader(ConcurrentLinkedList<Integer> list, String name) {
        setName(name);
        this.list = list;
    }

    @Override
    public void run() {
        for(int i=0; i<list.size(); i++) {
            int elem = list.get(i);
            System.out.println("Thread " + getName() + " reading " + elem + " from the list");
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

MainRun class

public class MainRun {
    public static void main(String[] args) {
        int[] numbers = new int[] { 1, 2, 3, 4, 5 };
        ConcurrentLinkedList<Integer> myList = new ConcurrentLinkedList<Integer>();

        Thread thread1 = new ListWriter(myList, numbers, "thread1");
        Thread thread2 = new ListReader(myList, "thread2");
        Thread thread3 = new ListReader(myList, "thread3");

        thread1.start();
        thread2.start();
        thread3.start();
    }
}

However, after running the program, sometimes I got incorrect output like this:

Thread thread1 writing 1 to the list
Thread thread3 reading 1 from the list
Thread thread1 writing 2 to the list
Thread thread3 reading 2 from the list
Thread thread1 writing 3 to the list
Thread thread1 writing 4 to the list
Thread thread3 reading 3 from the list
Thread thread1 writing 5 to the list
Thread thread3 reading 4 from the list
Thread thread3 reading 5 from the list

which means that the Reader thread2 never gets a chance to run. But sometimes it runs fine where both thread2 and thread3 are reading from the list. I even tried changing the Reader thread to sleep for longer time (e.g. Thread.sleep(500) in ListReader), but it still occasionally gets wrong where thread2 never runs. What causes this thread starvation problem for the reader thread? Why sometimes it works but sometimes it doesn't?

Answer 1

The problem is in your iteration in the reader:

for (int i = 0; i < list.size(); i++)
    list.get(i);

You do synchronize size() and get(), all right. But consider this scenario:

reader              writer
--------            --------
size: 0
                    write
exit "for" loop
<get() not called>

You start the writer before the reader, sure; but nothing guarantees that the writer will be scheduled before the reader.

You should probably .sleep() a little longer but do so before you check for the list size; also, consider implementing Iterable and use that instead, that will avoid the .size() problem although you may still get "short reads".

Answer 2

You seem to think of a queue rather than a list. Otherwise your loop is broken and can’t be fixed by inserting delays. You are invoking size() and get(int) multiple times without protecting against changes that may occur in-between. Once you add a remove(…)method to your list you will get into real trouble with such an attempt.

If you want a queue like behavior you could change the ListReader’s run method to:

@Override
public void run() {
    try {
       while(list.size()==0) Thread.sleep(100);
    } catch (InterruptedException e) {
       e.printStackTrace();
    }
    for(int i=0; i<list.size(); i++) {
       int elem = list.get(i);
       System.out.println("Thread "+getName()+" reading "+elem+" from the list");
       try {
           while(i==list.size()) Thread.sleep(100);
       } catch (InterruptedException e) {
           e.printStackTrace();
       }
    }
}

But of course it would be recommended to tell the readers the expected maximum number of items to avoid an infinite loop…

Answer 3

This has been a common problem with the ReadWriteLock implementation. In Java 5 there was write-thread starvation then in Java 6 an updated version saw read-thread starvation. Spend time and read Kabutz's explnation.

Java 8 has a solution for this! If you can, try installing Java 8 and slightly re-write your test to use a StampedLock. It leverages optimistic reads to prevent read/write starvation.