Java并发编程学习——Java并发编程之美学习笔记五

发表于 | 分类于 | | 热度: ℃
字数统计: 1.5k | 阅读时长 ≈ 6

Java并发包中并发List介绍

并发包中的List只有 CopyOnWriteArrayList 。 CopyOnWriteArrayList是一个线程安全的List，对其的修改操作都是在底层的一个复制的数组上进行的，也就是使用了 写时复制 策略。

运行结果

在CopyOnWriteArrayList中，每个对象里有一个array数组对象用来存放具体元素，ReentrantLock独占锁对象用来保证同时只有一个线程能对array进行修改。

如果让我们自己做一个写时复制的线程安全的List我们会怎么做？我们需要考虑什么？

  • 何时初始化list，初始化list元素为多少个，list是有限大小吗？

  • 如何保证线程安全？

  • 如何保证使用迭代器遍历list时的数据一致性。

主要方法解析

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 默认初始化个数0
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

// 传入一个集合的时候，将集合复制到自身属性的array中
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}
// 传入为数组的时候直接复制
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

增加方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    // 获取独占锁并加锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 获取自身array并且复制一个快照
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在快照上进行操作
        newElements[len] = e;
        // 将新的快照赋值给array属性
        setArray(newElements);
        return true;
    } finally {
        // 最后解锁
        lock.unlock();
    }
}

获取指定位置的元素

1
2
3
4
5
6
7
8
9
10
11
12
final Object[] getArray() {
    return array;
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
    return get(getArray(), index);
}

获取操作并没有加锁，可能会产生 弱一致性问题 。比如当线程A执行get，线程B执行删除操作。线程A这里可以分为两个步骤 1. 获取当前array 2. 通过获取到的array根据索引获得指定元素。

假如这个时候当线程A执行完步骤1，然后线程B执行删除操作，我们假设线程A需要获得的是index为1的元素，此时线程B将原来array复制到新的array中然后对这个新array进行remove(1)的操作，之后把这个新的array重新赋值到对象中的array中，当这一系列操作完成后，线程A获取指定元素，而这个时候线程A是通过原来array获取的，所以它仍能获取到index为1的元素。

例如对于以下程序 运行结果可能会是2或者3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class CopyOnWriteArrayListTest {

  public static void main(String[] args) throws InterruptedException {
    CopyOnWriteArrayList<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    copyOnWriteArrayList.add(1);
    copyOnWriteArrayList.add(2);
    copyOnWriteArrayList.add(3);
    copyOnWriteArrayList.add(4);
    Thread threadOne = new Thread(new Runnable() {
      @Override
      public void run() {
        copyOnWriteArrayList.remove(1);
      }
    });
    Thread threadTwo = new Thread(new Runnable() {
      @Override
      public void run() {
        System.out.println(copyOnWriteArrayList.get(1));
      }
    });
    threadOne.start();
    threadTwo.start();
    threadTwo.join();
    threadOne.join();
    System.out.println("结束");
  }
}

修改指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁并加锁
    lock.lock();
    try {
        // 获取array
        Object[] elements = getArray();
        // 获取原来的指定元素
        E oldValue = get(elements, index);
        // 如果参数不和老值相同则进行更新
        if (oldValue != element) {
            int len = elements.length;
            // 复制array
            Object[] newElements = Arrays.copyOf(elements, len);
            // 在新的array中进行更新
            newElements[index] = element;
            // 重新设置array
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            // 确保volatile语义还是需要重新设置array
            // 因为对于volatile变量的写操作happens-before对volatile
            // 变量的读操作
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

删除指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁并加锁
    lock.lock();
    try {
        // 进行快照的准备工作
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        // 如果删除的是最后一个
        if (numMoved == 0)
            // 直接移除最后一个的空间
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 创建一个快照
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            // 将array设置为快照
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

弱一致性的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static final class COWIterator<E> implements ListIterator<E> {
    // 数组的快照
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    // 判断是否还有下一个元素
    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor > 0;
    }

    // 遍历的方法
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    。。。。。
}

在snapshot中保存着当前array的快照,也就是说迭代器所操作的是array的一个快照，所以当其他线程对array进行更改的时候，迭代器是感知不到的，这又会产生弱一致性问题。

我们来看一下实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class CopyOnWriteArrayListTest {

  public static void main(String[] args) throws InterruptedException {
    CopyOnWriteArrayList<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    copyOnWriteArrayList.add(1);
    copyOnWriteArrayList.add(2);
    copyOnWriteArrayList.add(3);
    copyOnWriteArrayList.add(4);
    copyOnWriteArrayList.add(5);

    Thread threadOne = new Thread(new Runnable() {
      @Override
      public void run() {
        copyOnWriteArrayList.set(1,123);
        copyOnWriteArrayList.remove(2);
        copyOnWriteArrayList.remove(3);
      }
    });
    // 保证iterator先获取
    Iterator<Integer> integerIterator = copyOnWriteArrayList.iterator();

    threadOne.start();

    threadOne.join();

    while (integerIterator.hasNext()) {
      System.out.println(integerIterator.next());
    }

  }

}

运行结果

我们可以看到运行结果是1 2 3 4 5

我们来看一下创建iterator的源码

1
2
3
4
5
6
7
public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
}

其实跟上面讲到的获取和删除的弱一致性一样，因为修改和删除操作时对一个快照进行修改和删除的，并且最终把新的快照地址重新赋值给array，虽然此时的array指向的地址已经变了，但是原来迭代器中获取array的地址并没有改变，所以迭代器操作的还是原来的array，这就是写时复制产生的弱一致性问题。

-------------本文结束感谢阅读-------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多