簡(jiǎn)介

在上一篇文章中的并發(fā)和ABA問(wèn)題的介紹中荧恍，我們提到了要解決ABA中的memory reclamation問(wèn)題，有一個(gè)辦法就是使用RCU。

詳見(jiàn)ABA問(wèn)題的本質(zhì)及其解決辦法,今天本文將會(huì)深入的探討一下RCU是什么，RCU和COW(Copy-On-Write)之間的關(guān)系撼港。

RCU(Read-copy update)是一種同步機(jī)制，并在2002年被加入了Linux內(nèi)核中骤竹。它的優(yōu)點(diǎn)就是可以在更新的過(guò)程中帝牡，運(yùn)行多個(gè)reader進(jìn)行讀操作。

熟悉鎖的朋友應(yīng)該知道蒙揣，對(duì)于排它鎖靶溜，同一時(shí)間只允許一個(gè)操作進(jìn)行，不管這個(gè)操作是讀還是寫。

對(duì)于讀寫鎖罩息，可以允許同時(shí)讀嗤详，但是不能允許同時(shí)寫，并且這個(gè)寫鎖是排他的瓷炮，也就是說(shuō)寫的同時(shí)是不允許進(jìn)行讀操作的葱色。

RCU可以支持一個(gè)寫操作和多個(gè)讀操作同時(shí)進(jìn)行。

更多精彩內(nèi)容且看：

• 區(qū)塊鏈從入門到放棄系列教程-涵蓋密碼學(xué),超級(jí)賬本,以太坊,Libra,比特幣等持續(xù)更新
• Spring Boot 2.X系列教程:七天從無(wú)到有掌握Spring Boot-持續(xù)更新
• Spring 5.X系列教程:滿足你對(duì)Spring5的一切想象-持續(xù)更新
• java程序員從小工到專家成神之路（2020版）-持續(xù)更新中,附詳細(xì)文章教程

更多內(nèi)容請(qǐng)?jiān)L問(wèn)www.flydean.com

Copy on Write和RCU

什么是Copy on Write? 它和read copy update有什么關(guān)系呢娘香？

我們把Copy on Write簡(jiǎn)寫為COW苍狰，COW是并發(fā)中經(jīng)常會(huì)用到的一種算法，java里面就有java.util.concurrent.CopyOnWriteArrayList和java.util.concurrent.CopyOnWriteArraySet烘绽。

COW的本質(zhì)就是淋昭，在并發(fā)的環(huán)境中，如果想要更新某個(gè)對(duì)象安接，首先將它拷貝一份响牛，在這個(gè)拷貝的對(duì)象中進(jìn)行修改，最后把指向原對(duì)象的指針指回更新好的對(duì)象赫段。

CopyOnWriteArrayList和CopyOnWriteArraySet中的COW使用在遍歷的時(shí)候。

我們知道使用Iterator來(lái)遍歷集合的時(shí)候矢赁，是不允許在Iterator外部修改集合的數(shù)據(jù)的糯笙，只能在Iterator內(nèi)部遍歷的時(shí)候修改，否則會(huì)拋出ConcurrentModificationException撩银。

而對(duì)于CopyOnWriteArrayList和CopyOnWriteArraySet來(lái)說(shuō)给涕，在創(chuàng)建Iterator的時(shí)候，就對(duì)原List進(jìn)行了拷貝额获，Iterator的遍歷是在拷貝過(guò)后的List中進(jìn)行的够庙，這時(shí)候如果其他的線程修改了原List對(duì)象，程序正常執(zhí)行抄邀，不會(huì)拋出ConcurrentModificationException耘眨。

同時(shí)CopyOnWriteArrayList和CopyOnWriteArraySet中的Iterator是不支持remove，set境肾，add方法的剔难，因?yàn)檫@是拷貝過(guò)來(lái)的對(duì)象，在遍歷過(guò)后是要被丟棄的奥喻。在它上面的修改是沒(méi)有任何意義的偶宫。

在并發(fā)情況下，COW其實(shí)還有一個(gè)問(wèn)題沒(méi)有處理环鲤，那就是對(duì)于拷貝出來(lái)的對(duì)象什么時(shí)候回收的問(wèn)題纯趋，是不是可以馬上將對(duì)象回收？有沒(méi)有其他的線程在訪問(wèn)這個(gè)對(duì)象？ 處理這個(gè)問(wèn)題就需要用到對(duì)象生命周期的跟蹤技術(shù)吵冒，也就是RCU中的RCU-sync纯命。

所以RCU和COW的關(guān)系就是：RCU是由RCU-sync和COW兩部分組成的。

因?yàn)閖ava中有自動(dòng)垃圾回收功能桦锄，我們并不需要考慮拷貝對(duì)象的生命周期問(wèn)題扎附，所以在java中我們一般只看到COW，看不到RCU结耀。

RCU的流程和API

我們將RCU和排它鎖和讀寫鎖進(jìn)行比較留夜。

對(duì)于排它鎖來(lái)說(shuō)，需要這兩個(gè)API：

lock()
unlock()

對(duì)于對(duì)寫鎖來(lái)說(shuō)图甜，需要這四個(gè)API：

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

而RCU需要下面三個(gè)API：

rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()

rcu_read_lock和rcu_read_unlock必須是成對(duì)出現(xiàn)的碍粥，并且synchronize_rcu不能出現(xiàn)在rcu_read_lock和rcu_read_unlock之間。

雖然RCU并不提供任何排他鎖黑毅，但是RCU必須要滿足下面的兩個(gè)條件：

1. 如果Thread1(T1)中synchronize_rcu方法在Thread2（T2)的rcu_read_lock方法之前返回嚼摩，則happens before synchronize_rcu的操作一定在T2的rcu_read_lock方法之后可見(jiàn)。
2. 如果T2的rcu_read_lock方法調(diào)用在T1的synchronize_rcu方法調(diào)用之前矿瘦，則happens after synchronize_rcu的操作一定在T2的rcu_read_unlock方法之前不可見(jiàn)枕面。

聽(tīng)起來(lái)很拗口，沒(méi)關(guān)系缚去，我們畫個(gè)圖來(lái)理解一下：

image

記住RCU比較的是synchronize_rcu和rcu_read_lock的順序潮秘。

Thread2和Thread3中rcu_read_lock在synchronize_rcu之前執(zhí)行，則b=2在T2易结，T3中一定不可見(jiàn)枕荞。

Thread4中rcu_read_lock雖然在synchronize_rcu啟動(dòng)之后才開(kāi)始執(zhí)行的，但是rcu_read_unlock是在synchronize_rcu返回之后才執(zhí)行的搞动，所以可以等同于看做Thread5的情況躏精。

Thread5中，rcu_read_lock在synchronize_rcu返回之后才執(zhí)行的鹦肿，所以a=1一定可見(jiàn)矗烛。

RCU要注意的事項(xiàng)

RCU雖然沒(méi)有提供鎖的機(jī)制，但允許同時(shí)多個(gè)線程進(jìn)行讀操作箩溃。注意高诺，RCU同時(shí)只允許一個(gè)synchronize_rcu操作，所以需要我們自己來(lái)實(shí)現(xiàn)synchronize_rcu的排它鎖操作碾篡。

所以對(duì)于RCU來(lái)說(shuō)虱而，它是一個(gè)寫多個(gè)讀的同步機(jī)制，而不是多個(gè)寫多個(gè)讀的同步機(jī)制开泽。

RCU的java實(shí)現(xiàn)

最后放上一段大神的RCU的java實(shí)現(xiàn)代碼：

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

簡(jiǎn)單講解一下這個(gè)RCU的實(shí)現(xiàn)：

readersVersion是一個(gè)長(zhǎng)度為128的Long數(shù)組牡拇，里面存放著每個(gè)reader的讀數(shù)。默認(rèn)情況下reader存儲(chǔ)的值是NOT_READING，表示未存儲(chǔ)任何數(shù)據(jù)惠呼。

在RCU初始化的時(shí)候导俘，將會(huì)初始化這些reader。

read_unlock方法會(huì)將reader的值重置為NOT_READING剔蹋。

reclaimerVersion存儲(chǔ)的是修改的數(shù)據(jù)旅薄，它的值將會(huì)在synchronize_rcu方法中進(jìn)行更新。

同時(shí)synchronize_rcu將會(huì)遍歷所有的reader泣崩，只有當(dāng)所有的reader都讀取完畢才繼續(xù)執(zhí)行少梁。

最后，read_lock方法將會(huì)讀取reclaimerVersion的值矫付。這里會(huì)讀取兩次凯沪，如果兩次的結(jié)果不同，則會(huì)調(diào)用readersVersion.lazySet方法买优，延遲設(shè)置reader的值妨马。

為什么要讀取兩次呢？因?yàn)殡m然reclaimerVersion和readersVersion都是原子性操作杀赢，但是在多線程環(huán)境中烘跺，并不能保證reclaimerVersion一定就在readersVersion之前執(zhí)行，所以我們需要添加一個(gè)內(nèi)存屏障：memory barrier來(lái)實(shí)現(xiàn)這個(gè)功能脂崔。

總結(jié)

本文介紹了RCU算法和應(yīng)用液荸。希望大家能夠喜歡。

本文作者：flydean程序那些事

本文鏈接：http://www.flydean.com/concurrent-read-copy-updatercu/

本文來(lái)源：flydean的博客

歡迎關(guān)注我的公眾號(hào):程序那些事脱篙，更多精彩等著您！