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

Question

我定义了一个Element类：

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

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

同时还定义了一个基于Element的List类。它是一个典型的列表，就像在任何数据结构书籍中一样，具有添加头部、删除等操作。

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类线程安全？

在所有方法上放置synchronized？似乎不起作用。两个线程可能同时在不同的方法上工作，导致冲突。

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

在head、tail和size上使用volatile？如果两个线程运行不同的方法并相互持有资源等待，则可能会导致死锁。

有什么建议吗？

- Ryan

Answer 1

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

如果synchronized(this)块覆盖的区域是整个方法，那么与之没有区别。如果该区域小于整个方法，则可能会获得更好的性能。

像这样做：

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;
}

在这里，读取方法在不经过任何锁的情况下进行访问，而写入方法必须进行同步。通过为数组使用volatile保证了读取方法的线程间排序和可见性。

写入方法必须进行“复制”的原因是因为赋值语句array = newArray必须是“一次性”的（在Java中，对象引用的赋值是原子操作），并且在操作期间不能触及原始数组。

- Enno Shioji

Answer 2

我会查看java.util.LinkedList类的源代码以获取真实的实现。

默认情况下，同步将锁定类的实例 - 这可能不是您想要的（特别是如果Element是外部可访问的）。如果您在同一个锁上同步所有方法，则并发性能将非常差，但它将防止它们同时执行 - 有效地将访问类的单线程化。

此外 - 我看到了一个尾部引用，但没有看到具有相应前一个字段的Element，这是双向链表的原因吗？

- jayshao

---

谢谢Jay。这只是一个示例代码。你的意思是在每个方法上添加synchronized可以确保类的线程安全，但并发性能很差吗？如果我在每个方法内部使用synchronized(this)，会更好还是没有区别？ - Ryan

内部锁定（即synchronized）稍微好些，但真正需要考虑的是你在锁定什么。例如，synchronized(this)将对当前实例进行同步，synchronized(this.class)实际上是全局同步等等。性能是相对的，但synchronized是一个大锤子——它会全局锁定你的类，在java.util.concurrent中的读/写锁定可以给你更多的细粒度控制，具体取决于你要做什么。 - jayshao

java.util.concurrent提供了条件线程安全，但并不是绝对的，对它们要进行良好的处理以避免并发问题。 - Ryan

"...但并发性能很差"。任何同步机制的性能主要取决于争用程度。如果争用很少，synchronized表现良好。更细粒度的锁定是减少争用的一种方式。 - Stephen C

Answer 3

我建议您使用ReentrantLock，可以将其传递给列表中的每个元素，但是您需要使用工厂来实例化每个元素。

每当您需要从列表中取出某些内容时，您将阻止相同的锁，以确保没有两个线程同时访问。

- Oso