java - 如何使我的数据结构线程安全？

Question

我定义了一个 Element 类:

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

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

还定义了一个基于Element的List类。就是一个典型的链表，就像任何数据结构的书一样，有addHead，delete等操作

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
}

如何使这个 List 类线程安全？

在所有方法上同步？似乎不起作用。两个线程可能同时处理不同的方法并导致冲突。

如果我使用一个数组来保存类中的所有元素，那么我可以在数组上使用一个 volatile 来确保只有一个线程在处理内部元素。但目前所有元素都通过每个元素的下一个指针上的对象引用链接。我没有办法使用volatile。

在头部、尾部和大小上使用 volatile？如果两个线程运行不同的方法并持有彼此等待的资源，这可能会导致死锁。

有什么建议吗？

Answer 1

如果你在每个方法上放置synchronized，数据结构将是线程安全的。因为根据定义，同一时间只有一个线程会在对象上执行任何方法，并且还确保了线程间的顺序和可见性。所以就好像一个线程在做所有的操作一样好。

如果 block 覆盖的区域是整个方法，那么放置一个synchronized(this) block 不会有任何不同。如果该区域小于该区域，您可能会获得更好的性能。

做类似的事情

private final Object LOCK = new Object();

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

被认为是好的做法，虽然不是为了更好的性能。这样做将确保没有其他人可以使用您的锁，并无意中创建容易发生死锁的实现等。

在您的情况下，我认为您可以使用 ReadWriteLock 来获得更好的读取性能。顾名思义，ReadWriteLock 允许多个线程在访问“读取方法”时通过，这些方法不会改变对象的状态(当然，您必须正确识别哪些方法是“读取方法”和“写入方法”，并相应地使用 ReadWriteLock!)。此外，它确保在执行“写入方法”时没有其他线程正在访问该对象。它负责读/写线程的调度。

使类线程安全的其他众所周知的方法是“CopyOnWrite”，您可以在其中复制整个数据结构。仅当对象主要是“读”而很少“写”时才推荐这样做。

这是该策略的示例实现。 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;
}

这里，read 方法是在不经过任何锁的情况下访问，而 write 方法必须是同步。通过对数组使用 volatile 来确保读取方法的线程间排序和可见性。

write 方法必须“复制”的原因是赋值 array = newArray 必须是“一次性”(在 java 中，对象引用的赋值是原子的)，你可能不会在操作过程中触摸原始数组。