'Thread（二）线程同步容器'

线程同步容器

同步容器类

同步容器类包括Vector和Hashtable，二者是早期JDK的一部分，这些同步的封装器类是由Conllections.synchronizedXxx等工厂方法创建的。

这些类实现线程安全的模式是：将他们的状态封装起来，并对每个公有方法进行同步，使得每次只有一个线程能访问容器的状态。

同步容器类的问题

同步容器类都是线程安全的，但是在某些情况下可能需要额外的客户端加锁来保护复合操作。容器上常见的复合操作包括：迭代、跳转（根据指定顺序找到当前元素的下一个元素）以及条件运算。

例如 “若没有则添加”，当其他线程并发地修改容器时，他们可能会表现出意料之外的行为。

public static Object getLast(Vector list) {
    int lastIndex = list.size() - 1;
    return list.get(lastIndex);
}

public static void deleteLast(Vector list) {
    int lastIndex = list.size() -1;
    list.remove(liastIndex);
}

这些方法看似没有任何问题，从某种程度来说也确实如此——无论多少个线程同时调度他们，也不破坏Vector。但是从这些调用者角度来看，情况就不同了。

如果线程A 在包含10个元素的Vector上调用getLast，同时线程B 在同一个Vector上调用deleteLast，这些操作的交替执行如下图。

containers-1

交替调用getLast和deleteList时将抛出ArrayIndexOutOfBoundsException，同步容器类通过其自身的锁来保护它的每个方法，通过获得容器类的锁，我们可以使getLast和deleteLast成原子操作，并确保Vector的大小在调用size和get之间不会发生变化。

public static Object getLast(Vector list) {
    synchronized (list) {
        int lastIndex = list.size() - 1;
        return list.get(lastIndex);  
    }
}

public static void deleteLast(Vector list) {
    synchronized (list) {
        int lastIndex = list.size() -1;
        list.remove(liastIndex);
    }
}

在调用size和相应的get之间，Vector的长度可能会发生变化，这种风险在对Vector中的元素进行迭代时仍然会出现。

1
2
3

for(int i = 0; i < vector.size(); i++) {
    doSomething(vector.get(i));
}

在迭代的过程中，有其他线程并发地修改Vector时，可能抛出异常，但并不意味着Vector就不是线程安全的。Vector的状态仍然是有效的，但是迭代中抛异常显然不是人们所期望的。

我们可以通过加锁来解决不可靠迭代的问题，但是要牺牲一些伸缩性，通过在迭代期间持有Vector的锁，然而，这样同样会导致其他线程在迭代期间无法访问它，因此降低了并发性。

synchronized (vector) {
    for(int i = 0; i < vector.size(); i++) {
    doSomething(vector.get(i));
    }
}

ConcurrentModificationException

无论直接迭代还是for-each循环，对容器类进行迭代的标准方式都是使用Iterator，如果有其他线程并发地修改容器，即使是使用迭代器也无法避免在迭代期间对容器加锁。

在设计同步容器类的迭代器时并没有考虑并发修改的问题，并且它们表现出的行为是 “及时失败” 的。这意味着，当他们发现容器在迭代过程中被修改时，就会抛出一个ConcurrentModificationException异常。

这种 “及时失败” 的迭代器并不是一种完善的处理机制，而只是善意的捕获并发错误，因此只能作为并发问题的预警指示器。它们采用的实现方式是，将计数器的变化于容器关联起来：如果迭代期间计数器被修改，那么hasNext或next将抛出ConcurrentModificationException。

然而有些时候开发人员并不希望在迭代期间对容器加锁，如果容器的规模很大，或者执行时间很长，长时间对容器加锁会降低程序的可伸缩性，持有锁的时间越长，那么在锁上的竞争就可能越激烈，如果许多线程都在等待锁被释放，那么将极大地降低吞吐量和CPU的利用率。

如果不希望在迭代期间对容器加锁，那么一种替代方法就是 “克隆容器“，并在副本上进行迭代，由于副本被封闭在线程内，因此其他线程不会在迭代期间对其进行修改，这样就避免了抛出异常，但是在克隆过程中仍然需要对容器加锁。

隐藏迭代器

虽然加锁可以防止迭代器抛出ConcurrentModificationException，但在某些情况下，迭代器会隐藏起来，如以下程序

public class HiddenIterator {
    private final Set<Integer> set = new HashSet<Integer>();
    public synchronized void add(Integer i) {
        set.add(i);
    }
    public synchronized void remove(Integer i) {
        set.remove(i);
    }
    public void addTenThings() {
        Random r = new Random();
        for(int i = 0; i < 10; i++)
            add(r.nextInt());
        System.out.println("printSet:" + set);
    }
}

该方法可能会抛出ConcurrentModificationException，因为在打印的过程中，toString对容器进行迭代，当然真正的问题在于HiddenIterator不是线程安全的。在使用println中的set之前必须先获得锁，但是在代码中通常会忽略。

ConcurrentHashMap

与HashMap一样，ConcurrentHashMap也是基于散列的Map，但它使用了一种完全不同的加锁策略来提供更高的并发性和伸缩性，ConcurrentHashMap并不是将每个方法都在同一个锁上同步并使得每次只有一个线程访问容器，而是使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制称为分段锁。

在这种机制中，任意数量的读取线程可以并发地访问Map，执行读取操作的线程和执行写入的操作的线程可以并发地访问Map，并且一定数量的写入线程可以并发修改Map，ConcurrentHashMap带来的结果是，在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。

ConcurrentHashMap与其他并发容器一起增强了同步容器类：它提供的迭代器不会抛出ConcurrentModificationException因此不需要再迭代过程中对容器加锁，ConcurrentHashMap返回的迭代器具有弱一致性，弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以（但是不保证）在迭代器被构造后将修改操作反应给容器。

与Hashtable和synchronizedMap相比，ConcurrentHashMap有着更多的优势以及更少的劣势，因此在大多数情况下，用ConcurrentHashMap来替代同步Map能进一步提高代码的可申缩性。

额外的原子Map操作

一些常见的复合操作，例如：若没有则添加、若相等则移除和若相等则替换等，都已经实现为原子操作并且在ConcurrentMap的接口中声明。

public interface ConcurrentMap<K, V> extends Map<K, V> {
    //仅当K没有相应的映射值才插入
    V putIfAbsent(K key, V value);
    //仅当K被映射到V时才移除
    boolean remove(Object key, Object value);
    //仅当K被映射到oldValue时才替换为newValue
    V replace(K key, V value);
    //仅当K呗银蛇到某个值时才替换为newValue
    boolean replace(K key, V oldValue, V newValue);
    
}