《操作系統：設計與實現》筆記

操作系統：設計與實現 (2022 春季學期)的學習筆記

p3 多處理器編程：從入門到放棄 (線程庫；現代處理器和寬鬆內存模型)#

並發程序的三個麻煩
- 原子性
- 順序
- 可見性
gcc 編譯
- 不優化，並查看匯編代碼
  gcc -c -O1 sum.c && objdump -d sum.o
- asm volatile("" : : "memory"); // compiler barrier
統計次數
./a.out | head -n 1000 | sort | uniq -c
現代處理器
- 也是動態編譯器：匯編指令也是由多個 uop 所組成的。
- 維護一個 uop 的 “池子” 指令的有向無環圖
- 亂序執行，順序提交

p4 理解並發程序執行 (Peterson 算法、模型檢驗與軟件自動化工具)#

C 語言的形式語義
- 全局變量加多個堆棧幀；每個堆棧幀有其局部變量和 pc
Peterson 算法
- 看上去是謙讓的，但其實是自私的
- 證明正確性：畫出狀態機
  - 困境：不敢不畫，不敢亂畫
  - 解決： model-checker
  - 把程序的問題變成圖論的問題
    - safety 紅色狀態不可達
    - liveness : 從任意狀態出發，都能到達綠 / 藍色狀態強連通分量
- 許多重要的想法，凝練以後就是概念
並發程序 = 狀態機

Python generator

e.g.

def numbers(init=0,step=1):
    n = init
    while True:
    n += step
    yield n
g = numbers()
g.__next__()

p5 並發控制：互斥 (自旋鎖、互斥鎖和 futex)#

不能解決問題的時候，可以找到所依賴的假設，並大膽地打破它
spin 線程直接共享 locked
mutex 通過系統調用訪問 locked
futex(Fast Userspace muTexes)
- Fast path: 一條原子指令，上鎖成功立即返回
- Slow path: 上鎖失敗，執行系統調用睡眠

p6 並發控制：同步 (條件變量、信號量、製造者 - 消費者和哲♂學家吃飯問題)#

思考：有一堆任務，平均切分成 n 堆。有 x 個線程負責完成該任務 (x < n) 一個線程一次只能完成一個任務，完成後會自動去做下一個任務。要怎麼實現？
有萬能的方法，就要用萬能的方法。
- 他是這樣詮釋的。當項目代碼量不大（一千行以內），項目還是比較好維護的，這時候用寫聰明的寫法沒問題。但當項目到了幾萬行甚至幾百萬行時，這時候就需要多個人來進行協作。而人和人之間最大的障礙就是無法完全溝通，理解對方的心意。
- 不要試圖用聰明的辦法解決並發問題
- 個人想法：第一次聽這種說法，有一定道理。
萬能同步方法 —— 條件變量 (Conditional Variables)
- API
  - wait(cv, mutex) 💤
    調用時必須保證已經獲得 mutex
    釋放 mutex、進入睡眠狀態
  - signal/notify (cv) 💬 私信：走起
    如果有線程正在等待 cv，則喚醒其中一個線程
  - broadcast/notifyAll (cv) 📣 所有人：走起
    喚醒全部正在等待 cv 的線程
- ```
// 需要等待條件滿足時
mutex_lock(&mutex);
while (!cond) {
  wait(&cv, &mutex);
}
assert(cond);
// ...
// 互斥鎖保證了在此期間條件 cond 總是成立
// ...
mutex_unlock(&mutex);

// 其他線程條件可能被滿足時
broadcast(&cv);
```
- debug -> 隔離出 bug 觸發的最小條件

p7 真實世界的並發編程 (高性能計算 / 數據中心 / 人機交互中的並發編程)#

談 block chain > 是個很好的技術。但覺得不太對。因為造成了相當大的資源浪費。
What's so special about the Mandelbrot Set? - Numberphile
atanunq/viu
搜索降低了知識的獲取成本，ChatGPT 等再一次降低了成本。
go 語言，編程友好、性能優化
博客是 web2.0 的第一步
Ajax (Asynchronous JavaScript + XML)
這次課中講了三種並發編程，根據不同的需要，實現並發的方式也不同。

p8 並發 bug 和應對 (死鎖 / 數據競爭 / 原子性違反；防禦性編程和動態分析)#

軟件是需求在計算機數字世界的投影。
assert 的使用
沒有工具不做系統
premature optimization is root of all evil
編程語言的缺陷 —— 對程序員的完全信任：因為計算資源的寶貴
動態分析工具 -fsanitize
Canary msvc 中 debug mode 的 canary (b'\xcc' * 80).decode('gb2312')

p9 操作系統的狀態機模型 (操作系統的加載；thread-os 代碼講解)#

大學的真正意義：將已有的知識和方法重新消化，為大家建立好 “台階”，在有限的時間裡迅速趕上數十年來建立起的學科體系。

p10 狀態機模型的應用 (細胞自動機；gdb/rr/perf; 代碼驗證工具)#

分佈式系統也是一種並發程序，但要更複雜。因為並發程序假設了每個 thread 都能正常運行，而分佈式系統則要考慮節點丟失的情況。

p11 操作系統上的進程 (最小 Linux; fork, execve 和 exit)#

Linux 操作系統啟動流程
CPU Reset → Firmware → Loader → Kernel _start () → 第一個程序 /bin/init → 程序 (狀態機) 執行 + 系統調用

Fork Bomb:
:(){:|:&};:

:() {         # 格式化一下
: | : &
}; :

stdout:
終端: line buffer
pipe , file buffer (除非顯示地調用 fflush)
fork
- 程序就是狀態機，正在執行的程序也是狀態機，fork 創建狀態機的副本；
- 創建的進程返回 + 1，子進程返回為 0
- 把所有的寄存器和內存都複製
execve
- 將當前運行的狀態機重置成成另一個程序的初始狀態
_exit

p12 進程的地址空間 (pmap; vdso; mmap; 遊戲修改器 / 外挂)#

端序
- 大端 (big endian): 低地址存放高有效字節
- 小端 (little endian): 低字節存放低有效字節
工具使用
- gdb
- readelf
- pmap
計算機世界沒有魔法。因為程序就是狀態機。
vdso: 不進入操作系統內核，實現系統調用
mmap：
文件 = 字節序列；內存 = 字節序列； everything is a file

p13 系統調用和 Shell (freestanding shell, 終端和 job control)#

cd 是內部命令：改變當前目錄是用系統調用實現的
strace -f gcc a.c 2>&1 | vim - This will pipe both stdout and stderr to vim. The - argument tells vim to read from stdin.
strace pmap 152 |& vim -
|& : This is a shorthand for 2>&1 | in bash and zsh. It passes both standard output and standard error of one command as input to another.
fish, zsh 和 bash 都是常用的命令行 shell; sh 是比較原始的
clear 清屏
,./a.out & 背景執行./a.out

p14 C 標準庫的實現 (系統調用的封裝；內存空間管理)#

文件描述符還是不理解。印象中這是第二次談到了 "everything is a file"
- os 的對象和對象的訪問
gdn 的使用
- No symbol table is loaded. Use the "file" command。可能是編譯選項未包含 debug 信息，如 gcc 沒有添加 - g 選項。
premature optimization is the root of all evil.
脫離 workload 談優化就是耍流氓
經典的設計：
- fast path
- slow path

p15 fork 的應用 (文件描述符的複製；寫時複製；創建平行宇宙的魔法)#

fork 狀態機複製包括持有的所有操作系統對象
包括持有的所有操作系統對象
文件描述符（file discriptor）
- 一個指向操作系統內對象的 “指針”
- dup () 的兩個文件描述符是共享 offset
訪問空指針也會造成缺頁中斷
“Copy-on-write” 只有被寫入的頁面才會複製一份
- 被複製後，整個地址空間都被標記為 “只讀”
- 操作系統捕獲 Page Fault 後酌情複製頁面
- fork-execve 效率得到提升
操作系統會維護每個頁面的引用計數
定義進程所佔用的內存
page 是歸 os 所有的，而非進程
使用 fork 來搜索並行化。

p16 什麼是可執行文件 (調試信息；Stack Unwinding；靜態鏈接中的重定位)#

可執行文件描述了狀態機，是一個描述了狀態機的初始狀態 + 遷移的數據結構
os 沒有魔法，所有東西都有解釋
She-bang #! interpreter [optional-arg]
GNU binutils
- 生成可執行文件
  - ld (linker), as (assembler)
  - ar, ranlib
- 分析可執行文件
  - objcopy/objdump/readelf
  - addr2line, size, nm
objdump -d a.out | less disasm
addr2line 401122 a.out
elf: 小精靈；dwarf：矮人
將一個 assembly (機器) 狀態映射到 “C 世界” 狀態很難
gcc 等仍存在著許多不完美
編譯器，匯編器，鏈接器

p17 動態鏈接和加載 (靜態 ELF 加載器實現；調試 Linux 內核；動態鏈接和加載)#

自定義了一個二進制格式文件
GOT ： global offset table
PLT : procedure linkage table

p23 1-Bit 數據的存儲 (延遲線 / 磁芯 / DRAM/SRAM/ 磁帶 / 磁碟 / 光碟 / Flash SSD)#

volatile: 確保該變量的實際值與內存中的值一致，每次讀取都是最新值，也禁止編譯器對其進行優化。
core dumped 磁性內存年代開始的概念。
局部性原理 -> 可以按照大塊來讀寫

p24 輸入輸出設備模型 (串口 / 鍵盤 / 磁碟 / 打印機 / 總線 / 中斷控制器 / DMA 和 GPU)#

DMA: direct memory access : 一個專門執行 "memcpy" 程序的 cpu
IPC: Instruction per second
GPU:
- 一個通用計算設備
- 大量並行相似的任務
異構計算：都能做，但選那個最合適的。（jjy 在 22 年說的現在已經能感覺到有相關的趨勢了。不過倒不是裡面舉例的挖礦，而是 llm 模型）

p25 設備驅動程序 (Linux 設備驅動；GPU 和 CUDA; 存儲設備抽象)#

設備抽象成支持各類操作的對象 (文件)
- read - 從設備某個指定的位置讀出數據
- write - 向設備某個指定位置寫入數據
- ioctl - 讀取 / 設置設備的狀態
stty -a
GPU
- Single Instruction, Multiple Thread
讀優先的正確性

p26 文件系統 API (設備在應用間的共享；目錄和文件 API)#

信息的局部性
Windows 從 c 盤開始時是受其前身 Dos 系統的影響，那个有 a、b
mount disk.img /mnt
umount /mnt
硬（hard）鏈接
- ln /usr/local/python3 python
- 目錄中僅存儲指向文件數據的指針
- 允許一個文件被多個目錄引用.
- 無法用來鏈接目錄，也不能跨文件系統
- 通過ls -i查看是否為硬鏈接
軟 (symbolic) 鏈接
- “快捷方式”
- ln -s ../p24 p24
- 目錄從 “樹” 變為了 “圖”，還是有環圖
cd的特殊性
- 每個進程都有一個對應的工作目錄（pwd），而這個目錄只有系統調用才能夠修改

p27 FAT 和 UNIX 文件系統 (數據結構視角的文件系統；FAT 手冊導讀和目錄樹遍歷)#

數據結構的假設：數據是以字節來存儲的。
RAM 和 block 的區別
FAT(File Allocation Table)
- 將指針集中存放在文件系統的某個區域
- 適合小文件
- 會產生碎片（fragmentation）
- 基本假設
  - 鏈表無環且長度和文件大小一致
  - FREE 的 cluster 不能有入邊
cluster
sector
ext2
- 大文件的隨機讀寫性能提升明顯 (O (1))
- 支持鏈接 (一定程度減少空間浪費)
- inode 在磁碟上連續存儲，便於緩存 / 預取
- 碎片

p28 持久數據的可靠性 (RAID; 崩潰一致性；FSCK 和日誌)#

虛擬化
- cpu 的虛擬化：通過分時等技術讓多個進程並行，相當於虛擬出了多個 cpu
- 內存的虛擬化：一份內存通過 mmu，虛擬成每個進程的地址空間
- RAID：反向的虛擬化：多個磁碟虛擬化一個磁碟
RAID
- RAID0 : 交錯排列：提升容量和帶寬
- RAID1 : 提升容錯和讀帶寬
- RAID4 : 額外的一塊校驗盤
  - 致命缺陷：隨機寫的性能只能有校驗盤性能的一半
- RAID5 : Rotating Parity
RAID 帶來的聯想：
多個磁碟虛擬化為一個又大又快又可靠的磁碟，多台電腦虛擬化為一個又大又快又可靠的電腦
那能不能多個神經網絡虛擬化為一個更好的神經網絡
崩潰一致性 (Crash Consistency)
- 場景：寫入的時候突然斷電了怎麼辦？
- 方法 1：按照一定順序來寫，且 “all or nothing”
  - 困難：磁碟不提供多塊讀寫 “all or nothing” 的支持，甚至為了性能，沒有順序保證。
- 方法 2： File System Checking (FSCK)
  - 根據磁碟上已有的信息，恢復出 “最可能” 的數據結構
  - 困難：難；如果修復的時候再掉一次電？
- 方法 3：日誌
- 具體：
  - 數據結構操作發生時，用 (2) append-only 記錄日誌
  - 日誌落盤後，用 (1) 更新數據結構
  - 崩潰後，重放日誌並清除 (稱為 redo log；相應也可以 undo log)
- 優化: journaling (jdb2)

p30 現代存儲系統 (關係數據庫和分佈式存儲系統)#

數據庫
- 關鍵
  - 索引
  - 查詢優化
- magic：你只管寫 sql 語句，相應的搜索優化它來做
- 要求：acid
  - Atoming
  - Consistency
  - Isolation
  - Durability
圖靈獎
- 這門課聽下來，聽到了好多知識點背後都是獲得過圖靈獎的研究，甚至開創了一整個產業。
關係型數據庫跟不上社交網絡的需求
cap theorem
- Consistency
- Availability
- Partition Tolerance
分佈式存儲系統

感想#

蒋炎炎這門課還是別人推薦的。第一次看到還不以為意，但出現的次數多了就覺得有必要去看看。發現是一大驚喜。

收穫#

原版書能看得下來了。大段的英文，之前看著有點怕，現在覺得也能看下來，並且速度還可以。

EuDs

《操作系統：設計與實現》筆記

p3 多處理器編程：從入門到放棄 (線程庫；現代處理器和寬鬆內存模型)#

p4 理解並發程序執行 (Peterson 算法、模型檢驗與軟件自動化工具)#

p5 並發控制：互斥 (自旋鎖、互斥鎖和 futex)#

p6 並發控制：同步 (條件變量、信號量、製造者 - 消費者和哲♂學家吃飯問題)#

p7 真實世界的並發編程 (高性能計算 / 數據中心 / 人機交互中的並發編程)#

p8 並發 bug 和應對 (死鎖 / 數據競爭 / 原子性違反；防禦性編程和動態分析)#

p9 操作系統的狀態機模型 (操作系統的加載；thread-os 代碼講解)#

p10 狀態機模型的應用 (細胞自動機；gdb/rr/perf; 代碼驗證工具)#

p11 操作系統上的進程 (最小 Linux; fork, execve 和 exit)#

p12 進程的地址空間 (pmap; vdso; mmap; 遊戲修改器 / 外挂)#

p13 系統調用和 Shell (freestanding shell, 終端和 job control)#

p14 C 標準庫的實現 (系統調用的封裝；內存空間管理)#

p15 fork 的應用 (文件描述符的複製；寫時複製；創建平行宇宙的魔法)#

p16 什麼是可執行文件 (調試信息；Stack Unwinding；靜態鏈接中的重定位)#

p17 動態鏈接和加載 (靜態 ELF 加載器實現；調試 Linux 內核；動態鏈接和加載)#

p23 1-Bit 數據的存儲 (延遲線 / 磁芯 / DRAM/SRAM/ 磁帶 / 磁碟 / 光碟 / Flash SSD)#

p24 輸入輸出設備模型 (串口 / 鍵盤 / 磁碟 / 打印機 / 總線 / 中斷控制器 / DMA 和 GPU)#

p25 設備驅動程序 (Linux 設備驅動；GPU 和 CUDA; 存儲設備抽象)#

p26 文件系統 API (設備在應用間的共享；目錄和文件 API)#

p27 FAT 和 UNIX 文件系統 (數據結構視角的文件系統；FAT 手冊導讀和目錄樹遍歷)#

p28 持久數據的可靠性 (RAID; 崩潰一致性；FSCK 和日誌)#

p30 現代存儲系統 (關係數據庫和分佈式存儲系統)#

感想#

收穫#

課外資料#