範例參考我原本想丟 perfbook 的範例就好，但覺得不是很好理解，不小心又發現 Linux 的文件有一堆 RCU 的介紹，所以我決定改看 Linux 的文件來介紹
文件中有表示存在 LWN.net 的文章可以閱讀，這真的是我非常喜歡的一個網站，寫的都非常詳細＠＠
目前會先閱讀第一份文章，其他再議
我們之前只介紹過 RWLock，但在講 RCU 之前還需要對 Seqlock 有點認識，顧名思義是 sequential locks，應用在 resource 是極小又簡單的情況，且少有 Write 需求
演算法很簡單
Writer: 增加 counter 的數值，然後使用 Spinlock，成功執行後，釋放 spinlock 並再次增加 counter 的數值
Reader: 讀取 Counter 的數值，確認 Counter 數值是否一樣，一樣的話，就能進入 critical section
在我看來這只是一個 Spinlock 的特化應用，用來讓使多個 Reader 同時讀取
還可以發現一點，他與 RWlock 極其相似，他們到底是差在哪呢？差在 RWLock 中 Writer 必需要等待到 Reader 都消失才能做存取，但是 Seqlock 只要輪到 Writer ，就會直接上鎖@@
參考 RCU 初步認識
什麼是 RCU ? 這跟 Lock 系列的機制不同，RCU 是一個允許多個 Reader 及單個 Writer 同時運作的機制，沒錯！這又是一個 Lock-Free 系列的東西，這也是他與與 Seqlock/RWlock 最大的差別，不用因為寫入而上鎖
那麼他是怎麼做到的呢？？這是透過維護多個版本來實作，如下圖所示
如果是 RWlock 為了保證每個 Reader 看到的資料都是一樣的，一定要全部鎖起來；而 RCU 是同時有多個 Reader ，看到多個不同的版本，只能保證等下一次讀取資料時，會更新到目前的狀態，這就是所謂的維護多個版本，也可以說這就是訂閱機制啦
那麼有這麼多個 Reader 我們怎麼知道，這個 Reader 現在是讀取什麼版本呢？？？
RCU 把這個部份分為兩個狀態「Removal」「Reclamation」，以下以刪除指標為例
Removal
移除某個指標，但因為我們允許多個 Reader 同時運行，所以這時有些 Reader 的資料是還沒有被刪除的
注意：移除的動作必須是 Atomic
Reclamation
確保沒有 Reader 會再次使用這筆資料，可以真正把他刪除
但是事情有這麼簡單嘛？？？我們之前光是探討 Concurrent Linked List 就發現，那是一篇論文＝＝
所以我們必須遵守以下兩個規定，才能真正的執行成功
符合以上兩個規定的話，我們可以把 synchronize_rcu 簡單表示如下
void synchronize_rcu(void) {
int cpu;
for_each_cpu(cpu);
run_on(cpu);
}
這邊我並不確定是否存在允許 Preempt 的 synchronize_rcu 的實作，但這會妨礙我們理解 RCU ，所以也暫不研究
Grace Period
Removal -> Reclamation 這段時間，也就是 for_each_cpu(cpu) 的時間，等待所有 CPU 執行完畢
從圖中我們可以發現，只有在 Grace Period 中才會存在多個版本＠＠ 其他時候大家看到的都一樣
在上圖中，我們看到了很多 API 的調用，以下作一些解釋，下圖表示這些 API 之間的關係
rcu_assign_pointer()
+--------+
+---------------------->| reader |---------+
| +--------+ |
| | |
| | | Protect:
| | | rcu_read_lock()
| | | rcu_read_unlock()
| rcu_dereference() | |
+---------+ | |
| updater |<----------------+ |
+---------+ V
| +-----------+
+----------------------------------->| reclaimer |
+-----------+
Defer:
synchronize_rcu() & call_rcu()
可以發現在執行 RCU 的時候，會有三種角色
rcu_read_lock()
通知 Reclaimer 有一個 Reader 進入 read-side critical section
但如果有設置 CONFIG_PREEMPT_RCU 則會允許他被搶佔＝＝，這非常可能表示存在 Preempt 版本的 synchronize_rcu
rcu_read_unlock()
通知 Reclaimer 有一個 Reader 離開 read-side critical section
synchronize_rcu() / call_rcu()synchronize_rcu 代表同步，等待所有 CPU 執行完畢
CPU 0 CPU 1 CPU 2
----------------- ------------------------- ---------------
1. rcu_read_lock()
2. enters synchronize_rcu()
3. rcu_read_lock()
4. rcu_read_unlock()
5. exits synchronize_rcu()
6. rcu_read_unlock()
注意：我們只會等待在 synchronize_rcu 執行之前的 rcu_read_lock 執行結束，如範例所示，並不會等待 CPU 2
就算真的等到所有 CPU 了，涵式也不一定會馬上回傳，為了各種效率考量，會跟 Schedule 去作配合
call_rcu 是 synchronize_rcu 的 callback function
Updater 並不是直接監視所有 Reader ，而是透過 Reclaimer 來觀測 Reader 的狀態
rcu_dereference()rcu_dereference 我相信大家都是擅長寫 C 語言的朋友，dereference 不就是我們的指標嗎@@
取得最新的資料，如果只是一般的取值是不夠的，我們需要保證他執行的順序，會使用到各種 Memory Barrier
/* 1st read-side critical section */
rcu_read_lock();
p = rcu_dereference(head.next);
rcu_read_unlock();
/* outside read-side critical section */
x = p->address; /* BUG!!! */
/* 2nd read-side critical section */
rcu_read_lock();
y = p->data; /* BUG!!! */
rcu_read_unlock();
注意：在 read-side critical section 之外的地方，調用 rcu_deference 取得的指標是非法的，在另外一個 read-side critical section 調用也是非法的
rcu_assign_pointer()
修改指標，與 rcu_derefence 相同，要使用各種 Memory Barrier
rcu_deference rcu_assign_pointer 兩者之間的關係，如何實作與資料結構有非常大的關係，因為我還沒看這一部份，所以我並知道如何描述他們在對什麼東西進行操作
因為要去比 2019 全國智慧製造大數據分析競賽(imbd)了，花了很多時間在研究如何調校模型會比較好，很可惜的是今天比賽也沒有好的成果，資料分析真的不是我的專業==
也花了非常非常多時間刷 Leetcode，Leetcode 刷破 50 題了@@
老實說很久沒寫競賽題目，以前打 ITSA 或是 NCPC 的時候還會加減刷，現在真的都忘記了，完全寫不快，Medium 就算知道怎麼寫，也需要花個 20-30 分鐘才能刷一題， Hard 就等靈感＠＠
BTW 如果想超過一個禮拜想不出答案，我就會去看答案了
一個禮拜刷了 10 幾題吧，其中有幾題我印象特別深刻
142. Linked List Cycle II
這題只是一個龜兔賽跑問題的變形，因為我實在不了解，為什麼可以從相遇的點再出發，就可以找到入口
但無所謂＠＠ 我直接把之前介紹的 Concurrent Linked List 實作中的技巧應用上去，我把每個經過的點都標記，就順利的找到入口了
1192. Critical Connections in a Network
這題我解不出來，是看答案的，但以前沒有想過如何在一個無向圖中尋找 Circle，解法似乎蠻有名的，「Tarjan 演算法」
原理非常簡單，使用 DFS 暴力搜尋，但重點是額外紀錄兩個東西
當然在實作的時候，還需要注意 parent 是誰，又或者答案要存在哪，不過這是小事＠＠
至於更多 RCU 的介紹，就等明天我再來閱讀了
iThome鐵人賽
看影片追技術