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?