# RCU

RCU的重點是：一個物件如果是read-only的，那就可以安全地被多個執行緒同時讀取，且reader沒有overhead。當該物件需要被修改時，就需要複製一份並對其進行修改，並用新的物件位址替換舊的。然而缺點是writer需要回收舊的物件，就需要等待所有reader結束讀取。另外多個writer的情況下也需要協調寫入權。

釋放舊物件的工作會交由writer來執行。首先writer保存舊物件，並寫入新物件，接著等待所有reader進入一次靜默期(grace period)。就代表已經沒有人會再讀取到舊的物件，這時候writer就可以釋放了。

也因此觀測所有reader都進入grace period就是實作的重點。在kernel實作時的關鍵是context switch。進入critical section時關掉中斷，離開時啟用中斷。這樣的話當每個CPU都進行過一次context switch，就代表他們已經經過一次grace period。

### userspace qsbr

在userspace執行時，由於執行到一半有可能被中斷，因此我們需要引入其他做法。qsbr是一種侵入式做法，需要對原有的程式碼進行改動，但overhead是最低的。

首先每個thread註冊一次並維護一個local version number，當reader讀取時讀取global version number更新到自己身上

writer首先取得global version number並將其+1，開始用spin等待所有reader thread都通過一次靜默期

通過靜默期是將local version number設置為等於global version number

如此一來writer thread可以free min(all reader thread local version number)的memory