Skip to content
所有標籤

#concurrency

8 篇文章

細粒度鎖與 lock-free:從 test-and-set 到 ABA 問題|Stanford CS149 第 16 堂

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 的系統。

從零打造 task execution library——thread pool、sleep 到有依賴的 task graph|Stanford CS149 程式作業 2

CS149 PA2 要你用 C++ 寫一個多核 CPU 上的任務執行庫,而且要寫四次:每次 run() 都開 thread、改成 spinning 的 thread pool、改成會睡覺的 thread pool,最後擴充成非同步、有依賴的 task graph。每一步都得是完全正確的系統,並跟官方參考實作比速度。官方評分機器是 AWS c7g.4xlarge;校外可以在自己的多核機器上跑,但數字不能直接和官方比。

拿到一個程式,怎麼把它平行化?——分解、分配、協調,以及 Amdahl 定律|Stanford CS149 第 4 堂

L4 給了一套平行化的思考流程:先分解(decomposition)找出彼此獨立的工作,再分配(assignment)給工作者,再協調(orchestration)通訊與同步,最後對應到硬體。Amdahl 定律提醒你循序部分決定 speedup 上限。貫穿全講的例子是 2D 網格解算器:原本的相依關係很難平行,改用紅黑著色換一種更新順序後,就能用資料平行或共享位址空間兩種模型寫出來。

記憶體一致性:write buffer 讓 r1 = r2 = 0 變成可能|Stanford CS149 第 15 堂

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 與 Written 4:把「這段要原子」交給系統|Stanford CS149 第 17–18 堂/書面作業 4

粗鎖好寫但慢,細鎖快但容易寫錯。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 的細粒度鎖串成四題。

aidebug

每修一次都以為好了:Vision PDF 解析的三階段優化

用 Vision API 解析 150 頁 PDF 要 29 分鐘(一頁一請求)。分批送頁降到 1.5 倍,加上 5 路併發壓到 24 秒。上線一週後客戶一次傳 23 份 PDF,70 個並行請求打爆 Bedrock 限流——90 頁被跳過、5 份失敗、8 份卡住。最終用 Redis slot 做全叢集上限 + backoff 重試修復。

Looplane 的 tool programs、transactions 與 safe concurrency

Looplane 只平行執行同時標成 read-only、concurrency-safe 與 READ effect 的 tool call;tool_program 提供有界的 read-only repeat/branch,tool_transaction 則對可能碰到的 workspace files 做 snapshot 與失敗 rollback。它不是外部副作用的通用交易系統。

OpenClaw Agent Loop:序列化、寫入者宣告,與那個防止舊回合覆寫逐字稿的柵欄

Agent loop 是每個 session 序列化的執行。最值得學的是它處理並行的方式:每個被接受的回合會記下 activeWriterRunId 宣告,之後每次逐字稿寫入都要附上 expectedWriterRunId,在交易裡比對——被取代的回合因此無法提交過期資料。