所有標籤CS149 L16 分三段:先用 cache coherence 的眼光看鎖怎麼實作(test-and-set、test-and-test-and-set、ticket lock、CAS、LL/SC),再用一條排序 linked list 示範從一把大鎖改成 hand-over-hand 細粒度鎖,最後介紹 lock-free:單一生產者單一消費者佇列、用 CAS 寫的 stack、ABA 問題與 hazard pointer。投影片的結論很務實:在只有你的程式佔用機器的情境下,寫得好的鎖版本常常一樣快,而且好寫得多;lock-free 的價值在於執行緒可能被搶佔、page fault 的系統。
CS149 PA2 要你用 C++ 寫一個多核 CPU 上的任務執行庫,而且要寫四次:每次 run() 都開 thread、改成 spinning 的 thread pool、改成會睡覺的 thread pool,最後擴充成非同步、有依賴的 task graph。每一步都得是完全正確的系統,並跟官方參考實作比速度。官方評分機器是 AWS c7g.4xlarge;校外可以在自己的多核機器上跑,但數字不能直接和官方比。
L4 給了一套平行化的思考流程:先分解(decomposition)找出彼此獨立的工作,再分配(assignment)給工作者,再協調(orchestration)通訊與同步,最後對應到硬體。Amdahl 定律提醒你循序部分決定 speedup 上限。貫穿全講的例子是 2D 網格解算器:原本的相依關係很難平行,改用紅黑著色換一種更新順序後,就能用資料平行或共享位址空間兩種模型寫出來。
Coherence 只管單一位址;memory consistency 管的是不同位址之間的讀寫,在別的 thread 眼中以什麼順序生效。CS149 L15 用兩個 thread、兩個變數的例子說明:sequential consistency 下 r1 = r2 = 0 不可能,但每顆現代處理器都有的 write buffer 會讓讀跑到寫前面,於是它變成可能。TSO、PSO、weak ordering 依序放寬更多順序換取效能,fence 與同步原語再把需要的順序補回來。對應用程式設計師的結論很短:寫沒有 data race 的程式,用同步函式庫,C11、C++11、Java 5 就保證你看到 sequential consistency。
粗鎖好寫但慢,細鎖快但容易寫錯。Transactional memory 讓程式設計師只宣告 atomic { },由系統負責原子性與隔離。CS149 L17 講動機(failure atomicity、composability)與設計空間:資料版本管理分 eager(undo log)與 lazy(write buffer),衝突偵測分 pessimistic 與 optimistic。L18 拆 STM 的執行期資料結構與 McRT 演算法,再講 HTM 怎麼用 cache 的 R/W 位元加上 coherence 協定偵測衝突,最後是 Intel Haswell 的 RTM。Written 4 則把 MSI、LL/SC、鎖與記憶體順序、雙向 linked list 的細粒度鎖串成四題。
用 Vision API 解析 150 頁 PDF 要 29 分鐘(一頁一請求)。分批送頁降到 1.5 倍,加上 5 路併發壓到 24 秒。上線一週後客戶一次傳 23 份 PDF,70 個並行請求打爆 Bedrock 限流——90 頁被跳過、5 份失敗、8 份卡住。最終用 Redis slot 做全叢集上限 + backoff 重試修復。
Looplane 只平行執行同時標成 read-only、concurrency-safe 與 READ effect 的 tool call;tool_program 提供有界的 read-only repeat/branch,tool_transaction 則對可能碰到的 workspace files 做 snapshot 與失敗 rollback。它不是外部副作用的通用交易系統。
Agent loop 是每個 session 序列化的執行。最值得學的是它處理並行的方式:每個被接受的回合會記下 activeWriterRunId 宣告,之後每次逐字稿寫入都要附上 expectedWriterRunId,在交易裡比對——被取代的回合因此無法提交過期資料。