4.1 : 淺談同步機制

Linux 核心設計: 淺談同步機制 === :::warning 注意！這是上課筆記 ::: :::info 原始課程在這裡 - [影片](https://www.youtube.com/watch?v=lNt-ewfygy8) - [講義](https://hackmd.io/@sysprog/linux-sync?type=view) Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) ::: --- | Section | Time| Description | | -------- | -------- | -------- | | 1 | [00:00:11](https://youtu.be/lNt-ewfygy8?si=8FirCI-fOR8gE5FT&t=11) | 1. [Operating Systems 投影片](https://hackmd.io/@sysprog/linux-sync?type=view&stext=4481%3A26%3A0%3A1739002685%3AZBVvjk) 2.Consistency | | 2 | [00:11:12](https://youtu.be/lNt-ewfygy8?si=-MgL36-1cnKCaWOD&t=672) | 1. 同步機制的簡介。 2. multiple CPUs 的環境。 3. barrier 4. ipi(inter-processor interrupt) cpu | 3 | [00:20:19](https://youtu.be/lNt-ewfygy8?si=_LgWyVDbpiFoFGc5&t=1219) | 1.CPU Topology 2. Reentrancy 3. Big Kernel Lock / spinlock 4. Killing the Big Kernel Lock | | 4 | [00:37:14](https://youtu.be/lNt-ewfygy8?si=ecudID1M2ioUkdhd&t=2234) | 1. Performance Scalability 2. Coarse v.s. Fine-grained locking | | 5 | [00:47:51](https://youtu.be/lNt-ewfygy8?si=ybTJR-epIfzMJ4Uk&t=2871) | 1. Atomic instructions 2. lock-free data structure 3. priority inversion 4. lock-free example | | 6 | [01:04:04](https://youtu.be/lNt-ewfygy8?si=2lIFE74qfH7Ai36E&t=3844) | 1. PRNG need atomic instruction for seed. 2. Atomic instruction with lcok. 3. Waiting strategies. | | 7 | [01:14:29](https://youtu.be/lNt-ewfygy8?si=j_tH0M-laJG24E5O&t=4469) | 1. linux lock type. 2. why spinlock needs 2 loops? 3. CPU cache line 的問題。 4. 船停在港口是最安全的，但這不是造船的目的。 | | 8 | [01:25:03](https://youtu.be/lNt-ewfygy8?si=LyW5HCeJdTe3BIck&t=5103) | 1. cache line bouncing. 2. Atomic operation 的成本論文。 3. spinlock non-scalable 文章。 4. ticket spinlock / 馬可夫鏈模型分析. 5. Linux 的三大難題：linux is alive. / linux 面對各式議題. / linux 有各種好玩的議題。 | | 9 | [01:37:28](https://youtu.be/lNt-ewfygy8?si=f3dDJMwlV52PQ_W-&t=5848) | 1. Test&Test&Set lock. 2. Reader/Writer locks.(CAS=compare and swap) | | 10 | [01:50:01](https://youtu.be/lNt-ewfygy8?si=xmzrawswcpf0m4hd&t=6601) | 1. 線上搶票的議題。 2. seqlocks. 3. RW-spinlock / seqlock 使用情境。| | 11 | [02:02:48](https://youtu.be/lNt-ewfygy8?si=DYbIjcScKST34_bO&t=7368) | 1. Deadlock解法：lock ordering. 2. Semaphore. 3. seqlock 補充資料。| | 12 | [02:14:52](https://youtu.be/lNt-ewfygy8?si=_BhMrfmNvV2rHOZw&t=8092) | 1. 相關學術研究。 2. 介紹 Nicholas. 3. Worst-case execution time. | | 13 | [02:24:54](https://youtu.be/lNt-ewfygy8?si=zMR-I-RwbQi_jslb&t=8694) | 1. 回應網友問題。 2. Memory Consistency. 3. bit flips. 4. Sequential Consistency. | | 14 | [20:39:24](https://youtu.be/lNt-ewfygy8?si=n5C0hkZYRxjeJixE&t=9564) | 1. cc-numa. 2. 無法每次都做 Sequential Consistency，成本太高。 3. 羅習五教授投影片。| | 15 | [02:51:54](https://youtu.be/lNt-ewfygy8?si=oRVtJIyP6cn6bcBC&t=10314) | 1. semaphore and spinlock 差異。 2. Dekker's algorithm. 3. multics 支援多個處理器(1964年)。 4. 羅習五教授投影片。 5. 總結。