前面寫過一篇關於Linux RCU鎖的文章《RCU鎖在Linux內核的演變》，現在我承認，那個時候我雖然懂了RCU鎖，但是我沒有能力用一種非常簡單的描述把Linux的實現給展示出來，有道是你能給別人用你自己的方式非常簡潔地描述清楚，你才是真正的精通它，否則，無異於背誦。換個說法，如果你在被面試，在短時間內靠嘴說給面試官，且他還要能聽明白，就說明自己真的懂了，這種時候，是不會給你機會分析源代碼的，也不可能讓你背誦源代碼。
近期又碰到了這個話題，我不能自诩自己對RCU鎖是多麼精通，但是起碼，和前面這篇相比，我確實有所進步，因此在這個台風肆虐的次日，我嘗試著用我自己的方式描述一下Linux對RCU鎖的一種實現方式，作為《RCU鎖在Linux內核的演變》這篇文章的補充。本文不配圖，沒代碼，只是文字。
聲明：如果你還不知道RCU鎖是什麼，請自行baidu，本文不再贅述概念，但是這也就等於說，如果我自己有一天忘記了RCU，我也不能指望從本文中得到任何幫助，我總是這樣，不是嗎？能力在忘不在記，得其義而忘其形。
RCU要素
RCU鎖的要素包括
讀標志
如果一個Reader企圖占據一把RCU鎖，它是不需要付出任何代價的，只需要設置一個標志，讓外界知道有Reader在占據這把RCU鎖，多個Reader可以共同持有一把RCU鎖。
寫時拷貝
如果有一個Write企圖更新RCU鎖所保護的數據，那麼它會首先查看該RCU鎖的讀標志，如果有該標志，說明有最少一個Reader持有了該RCU鎖，它需要對原始數據make a copy，寫這個副本並將更新過的副本保存在某處，等待時機用該副本更新原始數據。
更新時機
這個時機就是用副本更新原始數據的時間點，這個時間點如何確定是RCU鎖實現的算法核心，它直接可以確定所有的數據結構。確切來講，Writer必須waitting for all readers leaving，方可Update原始數據，問題是，它是怎麼知道所有的Reader都離開了呢？
Linux內核對RCU鎖的幾種實現
1.原始實現-利用搶占禁止
Linux內核於2.6內核引入了RCU鎖的概念，在第一個版本中，它利用了搶占禁止的方式來標志有Reader持有RCU鎖，這意味著期間不能發生task切換(指的是task_struct所代表的sched entity切換)。那麼所有Reader均已經釋放RCU鎖的標志就是，task切換了，因此很簡單，用副本Update原始數據的時機就是task切換時。
所有的Write會將自己寫的副本掛在一個list上，在task切換的時候會touch這個list，如果該list非空，則遍歷每一個元素，Update原始數據。
評價[該部分與實現無關，純形而上的，可以忽略]
這就是第一版的原始實現，它是否合理姑且不論，確實，它可以工作。但是：
a.它這種實現是否會影響調度子系統的時延
b.由於禁用搶占，搶占粒度變粗，對交互性是否會有影響
c.對CPU間的task負載均衡的影響呢
我們發現，由於RCU的這個實現不是靠自身機制實現的，它不可避免地會影響到系統的核心機制，比如調度，負載均衡等，這意味著它不能長久，也無法經歷復雜的演變，因為隨著它在這條路上的逐步演進，對系統核心機制的影響將越來越大，故而，它必須從系統層面剝離出來。確實，它也是這麼做的，這就是第二代RCU實現-可搶占RCU鎖。
2.新實現-利用階段計數器
需要一種更加有效的方式來標志Reader已經持有鎖-第一要素讀標志，並且這個標志要盡可能精確，且不能使用系統核心的機制，要做成完全封閉的閉環，不依靠外部當然也就不會影響外部。
純天然的想法就是使用計數器，每一把RCU持有一個Reader計數器，一旦有Reader前來持鎖，只需要一個原子操作，將該計數器加1即可，Writer寫數據時，發現計數器不是0就意味著需要make a copy了-第二要素寫時拷貝(COW-Copy On Write)。現在的問題是第三要素，Writer怎麼知道所有的Reade都已經將鎖釋放了呢？？
純天然的想法就是在某個Reader釋放鎖的時候，計數器減1，當計數器重新變為0的時候，這就是副本更新原始數據的時機。確實是這樣，但是按照持鎖和解鎖的分布看，它們應該是均等的，這意味著計數器的值會在一個期望值上下波動，變成0的希望及其渺茫，因此需要引入另一個參量，即階段。
將唯一的那個RCU計數器分裂為兩個計數器：old readers和new readers。
太初，任選某一個時刻，將RCU鎖當前的計數器(稱為原始計數器)值復制一份存入old readers，計數器清0，原始計數器改稱為new readers。復制結束的當下，new readers計數器為0，old readers計數器為現階段持有鎖的reader的數量。並且持鎖者task(即task_struct)與RCU鎖之間保持關聯(難道不是一個task_struct字段可以搞定的嗎？)，task永遠知道自己是new reader還是old reader。
此時，就可以明確定義lock和unlock的行為了：
lock--設置自己的task為new reader，將RCU的new reader計數器加1。
unlock--獲取自己的task是new reader還是old reader，將自己所在的reader計數器減1。
此時很明確的事實是，old reader計數器總是會遞減而不會遞增，而new reader不但會遞增也會遞減，這樣，選擇Update的時機也很明確了，那就是，old reader計數器變為0，這個時刻，就該將所有的副本覆蓋原始數據了。
現在總結所有的三個要素：
讀標志
為該RCU鎖的new reader計數器加1
寫時拷貝
如果該RCU鎖的old reader計數器不為0，則執行寫時復制。
更新時機
每次unlock操作，都會將本task的reader計數器(或者是new reader，或者是old reader)減1，一旦該RCU鎖的old reader計數器變成0，則執行所有的Update操作。
評價[該部分與實現無關，純形而上的，可以忽略]
持有RCU鎖的reader，可以睡眠，可以被搶占，可以調度到別的CPU上，完全是封閉的，和系統其它的機制無關。然而，我一直在思考一個更好的實現，只因瘋子不給力！！
3.RCU Tree實現(實在是沒有2好)
後續補充。