专栏首页程序那些事并发和Read-copy update(RCU)

并发和Read-copy update(RCU)

简介

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

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

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

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

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

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

Copy on Write和RCU

什么是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

我们将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必须要满足下面的两个条件:

  1. 如果Thread1(T1)中synchronize_rcu方法在Thread2(T2)的rcu_read_lock方法之前返回,则happens before synchronize_rcu的操作一定在T2的rcu_read_lock方法之后可见。
  2. 如果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虽然没有提供锁的机制,但允许同时多个线程进行读操作。

注意,RCU同时只允许一个synchronize_rcu操作,所以需要我们自己来实现synchronize_rcu的排它锁操作。

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

RCU的java实现

最后放上一段大神的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算法和应用。希望大家能够喜欢。

本文分享自微信公众号 - 程序那些事(flydean-tech),作者:flydean

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 在Spring Boot使用H2内存数据库

    在之前的文章中我们有提到在Spring Boot中使用H2内存数据库方便开发和测试。本文我们将会提供一些更加具体有用的信息来方便我们使用H2数据库。

    程序那些事
  • 在java中构建高效的结果缓存

    缓存是现代应用服务器中非常常用的组件。除了第三方缓存以外,我们通常也需要在java中构建内部使用的缓存。那么怎么才能构建一个高效的缓存呢? 本文将会一步步的进行...

    程序那些事
  • java中Runnable和Callable的区别

    在java的多线程开发中Runnable一直以来都是多线程的核心,而Callable是java1.5添加进来的一个增强版本。

    程序那些事
  • istio-1:部署与体验istio-1.4.2

    istio搁置有一段时间了,并且现在开始介入的是最新版本1.4.2,所以难免有些错误的地方,非常欢迎指正与讨论。

    千里行走
  • ThinkPHP一些默认规则

    1. 每个应用模块都有独立的配置文件(位于模块目录的Conf/config.php),定义格式默认采用PHP数组定义

    公众号php_pachong
  • MySQL高可用方案-PXC环境部署记录

    之前梳理了Mysql+Keepalived双主热备高可用操作记录,对于mysql高可用方案,经常用到的的主要有下面三种: 一、基于主从复制的高可用方案:双节点主...

    洗尽了浮华
  • Web Api 入门实战 (快速入门+工具使用+不依赖IIS)

    平台之大势何人能挡? 带着你的Net飞奔吧!:http://www.cnblogs.com/dunitian/p/4822808.html 屁话我也就不多说了,...

    逸鹏
  • 10 个强大的 Apache 模块

    1.SSO Module - LemonLDAP LemonLdap 是 Apache 的一个实现了 Web SSO 的模块,可处理超过 20 万的用户。 we...

    wangxl
  • Django-DRF | 身份验证

    Django REST框架构建Web API。Django网络应用开发的5项基础核心技术包括模型(Model)的设计,URL 的设计与配置,View(视图)的编...

    小团子
  • 女神被打码了?一笔一划脑补回来,效果超越Adobe | 已开源

    这个算法来自加拿大的安大略理工大学,叫做EdgeConnect,修复效果甚至超越了Adobe登上CVPR 2018的算法。

    小小詹同学

扫码关注云+社区

领取腾讯云代金券