How to make my data structure thread safe?

Question

I defined an Element class:

class Element<T> {
    T value;
    Element<T> next;

    Element(T value) {
        this.value = value;
    }
}

also defined a List class based on Element. It is a typical list, just like in any data structure books, has addHead, delete and etc operations

public class List<T> implements Iterable<T> {
    private Element<T> head;
    private Element<T> tail;
    private long size;

    public List() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void insertHead (T node) {
        Element<T> e = new Element<T>(node);
        if (size == 0) {
            head = e;
            tail = e;
        } else {
            e.next = head;
            head = e;
        }
        size++;     
    }

    //Other method code omitted
}

How do I make this List class thread safe?

put synchronized on all methods? Seems not working. Two threads may work on differnt methods at the same time and cause collision.

If I have used an array to keep all the elements in the class, then I may use a volatile on the array to make sure only one thread is working with the internal elements. But currently all the elements are linked through object refernece on each's next pointer. I have no way to use volatile.

Using volatile on head, tail and size? This may cause deadlocks if two thread running different methods holding on the resource each other waiting for.

Any suggestions?

Answer 1

I'd look at the source code for the java.util.LinkedList class for a real implementation.

Synchronized by default will lock on the instance of the class - which may not be what you want. (esp. if Element is externally accessible). If you synchronize all the methods on the same lock, then you'll have terrible concurrent performance, but it'll prevent them from executing at the same time - effectively single-threading access to the class.

Also - I see a tail reference, but don't see Element with a corresponding previous field, for a double linked-list - reason?

Answer 2

I'd suggest you to use a ReentrantLock which you can pass to every element of the list, but you will have to use a factory to instantiate every element.

Any time you need to take something out of the list, you will block the very same lock, so you can assure that no two threads will be accessing at the same time.

Answer 3

If you put synchronized on every method, the data structure WILL BE thread-safe. Because by definition, only one thread will be executing any method on the object at a time, and inter-thread ordering and visibility is also ensured. So it is as good as if one thread is doing all operations.

Putting a synchronized(this) block won't be any different if the area the block covers is the whole method. You might get better performance if the area is smaller than that.

Doing something like

private final Object LOCK = new Object();

public void method(){
    synchronized(LOCK){
        doStuff();
    } 
}

Is considered good practice, although not for better performance. Doing this will ensure that nobody else can use your lock, and unintentionally creating a deadlock-prone implementation etc.

In your case, I think you could use ReadWriteLock to get better read performance. As the name suggests, a ReadWriteLock lets multiple threads through if they are accessing "read method", methods that does not mutate the state of the object (Of course you have to correctly identify which of your methods are "read method" and "write method", and use ReadWriteLock accordingly!). Also, it ensures that no other thread is accessing the object while "write method" are executed. And it takes care of the scheduling of the read/write threads.

Other well known way of making a class thread-safe is "CopyOnWrite", where you copy the whole data structure upon mutation. This is only recommended when the object is mostly "read" and rarely "written".

Here is a sample implementation of that strategy. http://www.codase.com/search/smart?join=class+java.util.concurrent.CopyOnWriteArrayList

private volatile transient E[] array;

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of element to return.
 * @return the element at the specified position in this list.
 * @throws    IndexOutOfBoundsException if index is out of range <tt>(index
 *            < 0 || index >= size())</tt>.
 */
public E get(int index) {
    E[] elementData = array();
    rangeCheck(index, elementData.length);
    return elementData[index];
}
/**
 * Appends the specified element to the end of this list.
 *
 * @param element element to be appended to this list.
 * @return true (as per the general contract of Collection.add).
 */
public synchronized boolean add(E element) {
    int len = array.length;
    E[] newArray = (E[]) new Object[len+1];
    System.arraycopy(array, 0, newArray, 0, len);
    newArray[len] = element;
    array = newArray;
    return true;
}

Here, read method is accessing without going through any lock, while write method has to be synchronized. Inter-thread ordering and visibility for read methods are ensured by the use of volatile for the array.

The reason that write methods have to "copy" is because the assignment array = newArray has to be "one shot" (in java, assignment of object reference is atomic), and you may not touch the original array during the manipulation.