Linux 核心設計: RCU 同步機制
===
:::warning
注意！這是上課筆記
:::

:::info
原始課程在這裡
- [影片 Part 1](https://www.youtube.com/watch?v=i25ojG2aknQ)
- [影片 Part 2](https://www.youtube.com/watch?v=N9pVyv09Kx0)
- [講義](https://hackmd.io/@sysprog/linux-rcu)

Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)
:::

---

# Part 1

| Section | Time| Description |
| -------- | -------- | -------- |
| 1 | [00:00:11](https://youtu.be/i25ojG2aknQ?si=-0ql3sNcrw9nDoiz&t=11) | 1. 簡介。<br> 2. Universal Scalability Law(USL). |
| 2 | [00:18:42](https://youtu.be/i25ojG2aknQ?si=yl4HX4znFB_Q-7NN&t=1122) | 1. spinlock.<br> 2. ticket spinlock.<br> 3. ARM 指令：WFE(wait for event) / dsb_sev(): 發送訊號給所有 core. |
| 3 | [00:37:58](https://youtu.be/i25ojG2aknQ?si=A9KQI82Xq2n2GuIp&t=2278) | 1. semaphore.<br> 2. ARm 指令：LDREX and STREX.<br> 3. 繼續講 semaphore.|
| 4 | [01:04:38](https://youtu.be/i25ojG2aknQ?si=2VKv2MrFR_Ptjq0R&t=3878) | 1. read-write lock(rwlock).|
| 5 | [01:21:02](https://youtu.be/i25ojG2aknQ?si=KcZP7gDNNcuwA3oW&t=4862) | 1. passive rwlock.<br> 2. Queue/MCS spinlock.<br> 3. ==Much Ado About Blocking== |
| 6 | [01:43:24](https://youtu.be/i25ojG2aknQ?si=XRGcnxe9eY-8-QZj&t=6204) | 1. lock 對 scalability 衝擊極大。<br> 2. sel4 for 波音 軍火使用，號稱 無法被駭的系統。<br> 3. Exim 郵件處理系統。<br> 4. ticket spin locks 是 non-scalable 的實作。|
| 7 | [02:08:33](https://youtu.be/i25ojG2aknQ?si=vllIEC4uzvHZeina&t=7713) | 1. RCU.<br> 2. RCU 基礎 (蝸窩科技)。 |
| 8 | [02:24:00](https://youtu.be/i25ojG2aknQ?si=D-bjxWIRdlHQ3POJ&t=8640) | 1. 投影片 "Intro to RCU"。<br> 2. 考慮 memory ordering.<br> 3. Using RCU for linked lists — a case study. |
| 9 | [02:36:43](https://youtu.be/i25ojG2aknQ?si=iOmw3DmUZ1nZe11p&t=9403) | ==Yet another introduction to Linux RCU== |
| 10 | [02:46:32](https://youtu.be/i25ojG2aknQ?si=IGZIk3LBMhq8HBi8&t=9992) | 1. ==Hierarchical RCU==<br> 2. ==sleepable RCU 的實現==<br> 3. 形式化驗證。

# Part 2

| Section | Time| Description |
| -------- | -------- | -------- |
| 1 | [00:00:11](https://youtu.be/N9pVyv09Kx0?si=tmRLfH8yfIqn2xDV&t=11) | ==Introduction to RCU Concepts==<br> 1. Avoid Mutual exclusion.<br> 2. Publication of and Subscription to New Data.<br> 3. RCU removal. |
| 2 | [00:23:30](https://youtu.be/N9pVyv09Kx0?si=2pkVVH1EMfvXLrsH&t=1410) | 1. RCU 應用場景。<br> 2. NMI: non-maskable interupt.<br> 3. Intel MINIX for debugging.<br> 4. handle_nmi(). |
| 3 | [00:45:20](https://youtu.be/N9pVyv09Kx0?si=8Af1PC-lt9StEIjb&t=2720) | 1. 回答網友問題。<br> 2. kdump.<br> 3. 三大研討會：SOSP, OSDI, ???<br> 4. Memory ordering.<br> 5. ==Using RCU to Protect Dynamic NMI Handlers== |
| 4 | [01:06:44](https://youtu.be/N9pVyv09Kx0?si=RatDEVRzcFzbOTvc&t=4004) | 1. Hungry bird: single consumer multiple producer ???.<br> 2. ==Multiprocessor Synchronization using Read-Copy Update.==<br> 3. 台灣業界的可悲。 |
| 5 | [01:26:24](https://youtu.be/N9pVyv09Kx0?si=z1jw7Hp8mhdnMjFS&t=5184) | 1. Grace Period.<br> 2. lock contention.<br> 3. stale data tolerance for readers.<br> 4. Linked List read/write operations. |
| 6 | [01:56:00](https://youtu.be/N9pVyv09Kx0?si=P8PF9FqDsORFERF4&t=6960) | 1. File descriptor Table.<br> 2. 42: The Hitchhiker's Guide to the Galaxy.<br> 3. memory reclamation.<br> 4. quiescent state. |
| 7 | [02:19:22](https://youtu.be/N9pVyv09Kx0?si=o16cL-6ST9490eUW&t=8362) | 1. How to make RCU scalable?<br> 2. Linux RCU example.<br> 3. ==Lock-free Data Structures. The inside. RCU== |
| 8 | [02:32:10](https://youtu.be/N9pVyv09Kx0?si=s58ZKHXImf-rR1KI&t=9130) | 1. Kernel Scalability.<br> 2. Disable preemption during RCU read.<br> 3. rcu_example demo. |
| 9 | [03:00:30](https://youtu.be/N9pVyv09Kx0?si=TKZktl5nSWYDbQKs&t=10830) | ==Notes on Read-Copy Update==<br> 1. garbage collection(jserv OGC).<br> 2. memory barrier.<br> 3. 介紹 孔祥重。