并发和Readcopy-updateRCU

4次阅读

共计 3916 个字符，预计需要花费 10 分钟才能阅读完成。

在上一篇文章中的并发和 ABA 问题的介绍中，我们提到了要解决 ABA 中的 memory reclamation 问题，有一个办法就是使用 RCU。

详见 ABA 问题的本质及其解决办法, 今天本文将会深入的探讨一下 RCU 是什么，RCU 和 COW(Copy-On-Write) 之间的关系。

RCU(Read-copy update) 是一种同步机制，并在 2002 年被加入了 Linux 内核中。它的优点就是可以在更新的过程中，运行多个 reader 进行读操作。

熟悉锁的朋友应该知道，对于排它锁，同一时间只允许一个操作进行，不管这个操作是读还是写。

对于读写锁，可以允许同时读，但是不能允许同时写，并且这个写锁是排他的，也就是说写的同时是不允许进行读操作的。

RCU 可以支持一个写操作和多个读操作同时进行。

更多精彩内容且看：

区块链从入门到放弃系列教程 - 涵盖密码学, 超级账本, 以太坊,Libra, 比特币等持续更新
Spring Boot 2.X 系列教程: 七天从无到有掌握 Spring Boot- 持续更新
Spring 5.X 系列教程: 满足你对 Spring5 的一切想象 - 持续更新
java 程序员从小工到专家成神之路（2020 版）- 持续更新中, 附详细文章教程

更多内容请访问 www.flydean.com

什么是 Copy on Write? 它和 read copy update 有什么关系呢？

我们把 Copy on Write 简写为 COW，COW 是并发中经常会用到的一种算法，java 里面就有 java.util.concurrent.CopyOnWriteArrayList 和 java.util.concurrent.CopyOnWriteArraySet。

COW 的本质就是，在并发的环境中，如果想要更新某个对象，首先将它拷贝一份，在这个拷贝的对象中进行修改，最后把指向原对象的指针指回更新好的对象。

CopyOnWriteArrayList 和 CopyOnWriteArraySet 中的 COW 使用在遍历的时候。

我们知道使用 Iterator 来遍历集合的时候，是不允许在 Iterator 外部修改集合的数据的，只能在 Iterator 内部遍历的时候修改，否则会抛出 ConcurrentModificationException。

而对于 CopyOnWriteArrayList 和 CopyOnWriteArraySet 来说，在创建 Iterator 的时候，就对原 List 进行了拷贝，Iterator 的遍历是在拷贝过后的 List 中进行的，这时候如果其他的线程修改了原 List 对象，程序正常执行，不会抛出 ConcurrentModificationException。

同时 CopyOnWriteArrayList 和 CopyOnWriteArraySet 中的 Iterator 是不支持 remove，set，add 方法的，因为这是拷贝过来的对象，在遍历过后是要被丢弃的。在它上面的修改是没有任何意义的。

在并发情况下，COW 其实还有一个问题没有处理，那就是对于拷贝出来的对象什么时候回收的问题，是不是可以马上将对象回收？有没有其他的线程在访问这个对象？处理这个问题就需要用到对象生命周期的跟踪技术，也就是 RCU 中的 RCU-sync。

所以 RCU 和 COW 的关系就是：RCU 是由 RCU-sync 和 COW 两部分组成的。

因为 java 中有自动垃圾回收功能，我们并不需要考虑拷贝对象的生命周期问题，所以在 java 中我们一般只看到 COW，看不到 RCU。

我们将 RCU 和排它锁和读写锁进行比较。

对于排它锁来说，需要这两个 API：

lock()
unlock()

对于对写锁来说，需要这四个 API：

read_lock()
read_unlock()
write_lock()
write_unlock()

而 RCU 需要下面三个 API：

rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()

rcu_read_lock 和 rcu_read_unlock 必须是成对出现的，并且 synchronize_rcu 不能出现在 rcu_read_lock 和 rcu_read_unlock 之间。

虽然 RCU 并不提供任何排他锁，但是 RCU 必须要满足下面的两个条件：

如果 Thread1(T1) 中 synchronize_rcu 方法在 Thread2（T2) 的 rcu_read_lock 方法之前返回，则 happens before synchronize_rcu 的操作一定在 T2 的 rcu_read_lock 方法之后可见。
如果 T2 的 rcu_read_lock 方法调用在 T1 的 synchronize_rcu 方法调用之前，则 happens after synchronize_rcu 的操作一定在 T2 的 rcu_read_unlock 方法之前不可见。

听起来很拗口，没关系，我们画个图来理解一下：

记住 RCU 比较的是 synchronize_rcu 和 rcu_read_lock 的顺序。

Thread2 和 Thread3 中 rcu_read_lock 在 synchronize_rcu 之前执行，则 b = 2 在 T2，T3 中一定不可见。

Thread4 中 rcu_read_lock 虽然在 synchronize_rcu 启动之后才开始执行的，但是 rcu_read_unlock 是在 synchronize_rcu 返回之后才执行的，所以可以等同于看做 Thread5 的情况。

Thread5 中，rcu_read_lock 在 synchronize_rcu 返回之后才执行的，所以 a = 1 一定可见。

RCU 虽然没有提供锁的机制，但允许同时多个线程进行读操作。注意，RCU 同时只允许一个 synchronize_rcu 操作，所以需要我们自己来实现 synchronize_rcu 的排它锁操作。

所以对于 RCU 来说，它是一个写多个读的同步机制，而不是多个写多个读的同步机制。

最后放上一段大神的 RCU 的 java 实现代码：

public class RCU {
    final static long NOT_READING = Long.MAX_VALUE;
    final static int MAX_THREADS = 128;
    final AtomicLong reclaimerVersion = new AtomicLong(0);
    final AtomicLongArray readersVersion = new AtomicLongArray(MAX_THREADS);

    public RCU() {for (int i=0; i < MAX_THREADS; i++) readersVersion.set(i, NOT_READING);
    }

    public static int getTID() {return (int)(Thread.currentThread().getId() % MAX_THREADS);
    }

    public void read_lock(final int tid) {// rcu_read_lock()
        final long rv = reclaimerVersion.get();
        readersVersion.set(tid, rv);
        final long nrv = reclaimerVersion.get();
        if (rv != nrv) readersVersion.lazySet(tid, nrv);
    }

    public void read_unlock(final int tid) {// rcu_read_unlock()
        readersVersion.set(tid, NOT_READING);
    }

    public void synchronize_rcu() {final long waitForVersion = reclaimerVersion.incrementAndGet();
        for (int i=0; i < MAX_THREADS; i++) {while (readersVersion.get(i) < waitForVersion) {} // spin}
    }
}

简单讲解一下这个 RCU 的实现：

readersVersion 是一个长度为 128 的 Long 数组，里面存放着每个 reader 的读数。默认情况下 reader 存储的值是 NOT_READING，表示未存储任何数据。

在 RCU 初始化的时候，将会初始化这些 reader。

read_unlock 方法会将 reader 的值重置为 NOT_READING。

reclaimerVersion 存储的是修改的数据，它的值将会在 synchronize_rcu 方法中进行更新。

同时 synchronize_rcu 将会遍历所有的 reader，只有当所有的 reader 都读取完毕才继续执行。

最后，read_lock 方法将会读取 reclaimerVersion 的值。这里会读取两次，如果两次的结果不同，则会调用 readersVersion.lazySet 方法，延迟设置 reader 的值。

为什么要读取两次呢？因为虽然 reclaimerVersion 和 readersVersion 都是原子性操作，但是在多线程环境中，并不能保证 reclaimerVersion 一定就在 readersVersion 之前执行，所以我们需要添加一个内存屏障：memory barrier 来实现这个功能。

本文介绍了 RCU 算法和应用。希望大家能够喜欢。