--- tags: concurrency --- # [並行程式設計](https://hackmd.io/@sysprog/concurrency): 概念 :::success 解說錄影: [Part 1](https://youtu.be/i23aGY2173g) / [Part 2](https://youtu.be/D7ivz5zxSIw) / [Part 3](https://youtu.be/1LqDZHFGB_M) / [Part 4](https://youtu.be/7kImoW_hISE) / [Part 5](https://youtu.be/8BidMHVGeBE)/ [Part 6](https://youtu.be/6LnGZ_1MfDo) / [Part 7](https://youtu.be/WKj4RSFn0ms) > [sysprog21/concurrent-programs](https://github.com/sysprog21/concurrent-programs) ::: > "A Computer is a state machine. Threads are for people who can't program state machines." -- [Alan Cox](https://en.wikipedia.org/wiki/Alan_Cox) ## 導讀 光看翻譯,Concurrency (並行) 和 Parallelism (平行) 已令許多人困惑,多執行緒程式設計更是工程人員的夢魘。本講座希望帶著學員回歸本質,並透過案例分析來掌握並行程式設計。 Concurrency 指程式架構,將程式拆開成多個可獨立運作的工作,像是驅動程式都可獨立運作,但不需要平行化。Parallelism 則指程式執行,同時執行多個程式。Concurrency 可能會用到 Parallelism,但不一定要用 Parallelism 才能實現 Concurrency。在 Concurrent 中,工作可拆分成「獨立執行」的部份,於是「可以」讓很多事情一起做,但「不一定」要真的同時做。但 Parallelism 著重規劃, 將能夠並行的程式,分配給不同硬體單元,使其同時執行。 接著 Synchronization (同步處理) 則確保多個執行單元運作並存取資源時,執行結果不會因為執行單元的時間先後的影響而導致錯誤。mutex 與 semaphore 的差別在於: 1. process 使用 mutex 時,process 的運作是持有 mutex,執行 CS (critical section) 來存取資源,然後釋放 mutex。換言之,mutex 就像是資源的一把鎖:[解鈴還須繫鈴人](https://dict.concised.moe.edu.tw/dictView.jsp?ID=22201)。 2. process 使用 semaphore 時,process 總是發出信號 (signal),或者總是接收信號 (wait),同一個 process 不會先後進行 signal 與 wait。換言之,process 要不擔任 producer,要不充當 consumer 的角色,不能兩者都是。semaphore 是為了保護 process 的執行同步正確。 建立基本概念後,本講座將透過 POSIX Thread 探討 thread pool, Lock-Free Programming。lock-free 使用的 atomic 操作, memory ordering, thread pool, M:N threading model 等進階議題。 --- ## 軟體開發現況 [The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software](http://www.gotw.ca/publications/concurrency-ddj.htm) * Free (performance) lunch 指的是程式設計的效能可以透過 CPU 時脈的進步而得到改善。會說 over 是因為 CPU 的時脈因耗電和散熱的問題,難以樂觀地持續提升所以程式設計師必須要修改程式才能改善效能 * 文章中 `Figure 1`,可以看到 CPU 時脈並沒有隨著電晶體數量而增加,反而是趨緩了 ![image](https://hackmd.io/_uploads/ryKkTuJpa.png) * 以前 CPU 增進效能的手段 * Clock speed * Execution Optimization * Pipelining、Branch prediction * Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder) * Cache:盡量減少存取 Main memory 的機會 * 現在 CPU 增進效能的手段 * Hyperthreading: 在 single CPU 上同時執行多個 thread,但是共用 ALU、FPU * Multicore:多個 CPU * 迷思:`2 x 3GHz < 6GHz` * Cache 多核處理器成為上述變革的主流解決方案,想要壓榨出更多效能,必須要讓軟體跟上硬體的設計,因此多工/多執行緒是必然的趨勢,其中如何正確的處理不同執行緒之間交互執行衍伸而來的問題,就是 concurrency 探討的方向。 concurrency 牽涉相當廣,從最基本的 lock, mutex, semaphore 等同步用的工具外,如果繼續往下鑽,就會遇到 atomic operation,要透過不可分割的原子操作來實現這些工具。再往下鑽,就會遇到更底層的 memory model 和 memory ordering,因為編譯器會最佳化程式碼順序、處理器會亂序執行、底層硬體又有 cache coherency 的問題,導致程式實際的執行過程和你寫的不一定相同,這在單核處理器上還沒什麼問題,但遇到多個執行緒同時在不同的處理器執行時,就可能會發生悲劇。這些東西不僅牽涉到軟體設計,也牽涉到硬體的觀念,繼續延伸下去,甚至可以討論到如何設計無鎖的(lock-free)的資料結構。 :::success 考慮到繁體中文翻譯慣例,這裡將作業系統的 kernel 翻譯為「核心」,處理器的 multi-core 翻譯為「多核」,而非「多核心」,否則無法區分 multi-kernel (例如 [McKernel](https://github.com/RIKEN-SysSoft/mckernel)),請留意這二個詞彙 ::: --- ## 多工處理 multitasking (多工處理,繁體和簡體對應的詞彙有些落差,見[國家教育研究院: multitasking](https://terms.naer.edu.tw/detail/2454139/)) 是作業系統核心一項重要的機制,依據不同層次,我們可初略將多工處理區分為以下三類: 1. 循序式程式 (sequential program) * 循序的觀念即程式碼的執行遵守一定的流程,且無時間限制的概念。 * 循序式程式易於理解,因為時間的演變與程式的執行同一方向,也就是在一特定時間,僅有一項工作在進行。另外,資料的傳遞也只遵循一個方向,因此資料的保護十分容易達成(不會發生資料競爭的狀況) * 然而,這類型的程式無法對時間作完全掌控。另外,由於所有的工作均擠在同一流程中,對軟體的維護與擴充較無彈性。 2. 前景/背景式程式 (foreground / background program) * 若電腦硬體具備時鐘中斷 (timer interrupt) 的能力,則可對循序式程式進行修改。所謂的前景程式,即是中斷到來時,系統所執行的中斷處理 (interrupt service routine; ISR)。其餘的程式碼則統稱為背景程式。 * 值得留意的是資料的一致性 (data consistency)。例如若中斷在使用者修改控制器參數的途中到來,則可能計算出不正確的控制訊號。因此對前景與背景共用的資料區必需加以保護。 3. 多工程式 (multi-tasking program) * 多工程式設計與並行程式 (concurrent programming) 或多重程式 (multi-programming) 若干觀念有所重疊 (但彼此互不隸屬,詳見 [Difference between Multiprogramming, multitasking, multithreading and multiprocessing](https://www.geeksforgeeks.org/difference-between-multitasking-multithreading-and-multiprocessing/))。 * 並行程式設計在硬體並行處理系統中不可或缺,也就是系統中若包含多個 CPU 或不對等 (heterogeneous) 的執行單元時,必須將工作分散至各執行單元同時執行。 * 於是,我們可想見若各子工作完全獨立,則系統將可達到其最高效率,但子工作完全獨立是幾乎不可能滿足 —— 通常的各執行單元之間仍需溝通資訊,或共用系統資源 (如記憶體、I/O 等)。 並行程式設計的觀念對單一 CPU 的軟體設計來說,同一時間只執行一個工作,但利用高速切換的操作,使程式巨觀上看似多個工作同時在進行。下圖展示這個觀念: ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 5, "end": 12, "task": 1}, {"start": 3, "end": 12, "task": 2}, {"start": 1, "end": 12, "task": 3} ] }, "height": 100, "width": 500, "mark": "bar", "encoding": { "y": { "field": "task", "type": "ordinal", "axis": {"labelFontSize": 17, "titleFontSize": 17, "titleFontWeight": 500} }, "x": { "title": "time", "field": "start", "bin": {"binned": true}, "scale": {"domain": [0, 13]}, "axis": {"labelFontSize": 17, "titleFontSize": 15, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "task"} } } ``` ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 1, "end": 2, "task": 3}, {"start": 2, "end": 3, "task": 2}, {"start": 3, "end": 4, "task": 1}, {"start": 4, "end": 5, "task": 2}, {"start": 5, "end": 6, "task": 1}, {"start": 6, "end": 7, "task": 3}, {"start": 7, "end": 8, "task": 2}, {"start": 8, "end": 9, "task": 1}, {"start": 9, "end": 10, "task": 3}, {"start": 10, "end": 11, "task": 1}, {"start": 11, "end": 12, "task": 2} ] }, "height": 100, "width": 500, "mark": "bar", "encoding": { "y": { "field": "task", "type": "ordinal", "axis": {"labelFontSize": 17, "titleFontSize": 17, "titleFontWeight": 500} }, "x": { "title": "time", "field": "start", "bin": { "binned": true }, "scale": {"domain": [0, 13]}, "axis": {"labelFontSize": 15, "titleFontSize": 15, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "task"} } } ``` > 橫軸是各工作實際佔用 CPU 的時間 從設計軟體的角度而言,多工程式與循序式與前景/背景式程式,有著顯著差異: 1. 系統設計者完全以工作的性質來區分程式,不再遵循程式執行順序的限制; 2. 各工作佔用系統資源的情況,可進行嚴密地管理與時間的分配; 多工程式設計對多數人來說,較難適應,因為人們從需要眼觀四面、耳聽八方的狩獵生活,進入重視分工的農耕生活後,已習慣在同一時間執行一個工作。然而就工作規劃而言,多工程式設計卻高度接近人類的思考方式:人在制定工作目標時,先對目標進行工作分類,並定義各工作的範圍與內容,不過工作的執行並不一定遵循固定的順序,比方說,打字完成列印時,通常會進行其他工作,待列印完後在校正是否列印正確。不難發現,循序式程式設計其實和人類的思考模式相左,而符合「人性」的機制反而是多工機制。 ## 分時多工作業系統的起源 1963 年麻省理工學院的科學記者採訪當時計算中心,並與 [Fernando J. Corbató](https://en.wikipedia.org/wiki/Fernando_J._Corbat%C3%B3) 教授對話,後者是世界上第一個分時多工作業系統 [Compatible Time-Sharing System](https://en.wikipedia.org/wiki/Compatible_Time-Sharing_System) (CTSS) 的主導設計者,Corbató 教授在 CTSS 獲得巨大成功後,帶領 MIT 團隊,和通用電氣 (GE) 及貝爾實驗室發展 [Multics](https://en.wikipedia.org/wiki/Multics) 作業系統,許多慣例和概念一路從 CTSS, [Multics](https://en.wikipedia.org/wiki/Multics),到後來汲取前者經驗而重新打造的 UNIX 作業系統。 在這部短片中,Corbató 教授談及過往批次處理系統的限制,並快速回顧電腦運作原理及如何實作分時多工、依據優先權進行排程等等,是此,電腦猶如電話交換機,同時為多個使用者所操作,每位使用者都能依據需求使用終端機,存取到運算和儲存資源,不會和其他使用系統的人有所衝突。可留意到,Corbató 教授在訪談中提到 [Supervisory program](https://en.wikipedia.org/wiki/Supervisory_program)。 {%youtube Q07PhW5sCEk%} ## 工作 (task) 與執行緒 (thread) 工作與執行緒通常是互通的觀念,均代表著一台電腦執行時的對象。某些作業系統如 Microsoft Windows,對工作與執行緒進行不同的解釋,但在 Linux 核心,工作和行程 (process) 及執行緒之間卻沒有顯著分野,在特定的狀況下,彼此甚至可互相轉換。 > 詳見 [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process) 在多個 CPU 的環境中,並行處理的具體作法即是將一個循序執行的程式打散在個別 CPU 中,而每一 CPU 所執行的部份稱為一個執行緒。因此某個目標的達成,可能需要執行多個工作,而每個工作 (可能是個完整的程式) 被分隔出多個執行緒。這即是多工多執行緒系統(multi-tasking multi-threading systems)。因為工作的規劃是以人為導向,而執行緒則視情況,以 CPU 或當時電腦資源的分配情況為導向。如此一來,CPU 在不同工作中的切換可更有效率。因為核心直接面對 CPU,於是操作的對象應是執行緒。 ## 工作切換 多工作業系統核心其中一項關鍵功能是,切換工作時必須保證被停止的工作可在未來繼續執行。從程式的角度而言,即系統必須記錄被停止的程式下一次執行時的位址 (address),同時必須將 CPU 回復到被停止時的狀態,及保證該工作擁有的資料區不受污染或破壞 (corruption)。這些動作統稱為工作切換或內文切換 (context switch)。內文切換是多工作業系統的一項負擔 (overhead),系統的反應速度,與內文切換的效率高度相關。 ## 排程器 :::info 英國作家 Douglas Adams 在《The Hitchhiker's Guide to the Galaxy》(銀河便車指南) 一書提到: > "Time is an illusion. Lunchtime doubly so." 若時間是真實的,我們就必須跟他周旋,譬如用各種活動或工作塞滿時間,反過來說若時間不存在的,我們就可好整以暇。這句話恰好可解釋排程器運作原理。 ::: 排程器 (scheduler) 又稱分派器 (dispatcher),其功能是決定 CPU 下一個所要執行的工作。排程的演算法很多種,其中經典的演算法包含優先順序式 (priority scheduling) 與時間分割式 (round-robin scheduling 或 time slicing)。特別針對即時系統 (real-time system; RTS),優先順序式排程是相當重要的特徵,通常硬即時 (hard real-time) 的工作,其優先順序較高。時間分割式的排程法,則針對重要性相同的工作,以切割 CPU 的執行時間來達到並行處理的幻覺 (illusion)。 以下圖的 `(a)` 來說,若工作一的執行時間很長,則可能使整個系統處在一個沒有效率的等待狀況。而若對 CPU 的執行時間做切割 (如下圖 `(b)`),則各項工作從巨觀上均能分配到一定的資源與時間。 ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 1, "end": 9, "task": 1}, {"start": 9, "end": 17, "task": 2}, {"start": 17, "end": 25, "task": 3} ] }, "height": 100, "width": 500, "mark": "bar", "encoding": { "y": { "field": "task", "type": "ordinal", "axis": {"labelFontSize": 17, "titleFontSize": 18, "titleFontWeight": 500} }, "x": { "title": "(a)", "field": "start", "bin": {"binned": true}, "scale": {"domain": [0, 26]}, "axis": {"labelFontSize": 15, "titleFontSize": 17, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "task"} } } ``` ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 1, "end": 4, "task": 1}, {"start": 4, "end": 7, "task": 2}, {"start": 7, "end": 10, "task": 3}, {"start": 10, "end": 13, "task": 1}, {"start": 13, "end": 16, "task": 2}, {"start": 16, "end": 19, "task": 3}, {"start": 19, "end": 22, "task": 1}, {"start": 22, "end": 25, "task": 2} ] }, "height": 100, "width": 500, "mark": "bar", "encoding": { "y": { "field": "task", "type": "ordinal", "axis": {"labelFontSize": 17, "titleFontSize": 18, "titleFontWeight": 500} }, "x": { "title": "(b)", "field": "start", "bin": {"binned": true}, "scale": {"domain": [0, 26]}, "axis": {"labelFontSize": 15, "titleFontSize": 17, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "task"} } } ``` 上圖 `(b)` 中的各段 CPU 時間即稱時間切割 (time slice)。CPU 的時間切割可是很小的單位,由系統硬體能力決定。通常各工作均以分配到幾個時間切割來執行。如一個切割是一毫秒 (ms),則工作一可能分配到 10 個切割,工作二分配到 8 個切割等。而時間切割的分配也並非總是靜態的 (static),系統可針對不同的狀況在執行時對分割做動態 (dynamic) 改變。 同樣地,優先順序式的排程也可採動態的方式,甚至有可適應優先順序排程 ([adaptive priority scheduling](https://ieeexplore.ieee.org/document/4631078)),其主要目的均在解決資源分配的公平性與避免系統產生死結 (deadlock) 的情況。然而,排程規則一旦越複雜,系統的負擔往往也就越重。 ## 搶佔式與非強取式核心 搶佔式 (preemptive) 與非搶佔式 (non-preemptive) 核心的差別,在於工作本身對 CPU 使用權的交出是強制達成,抑或是自願性的 (voluntary)。在非搶佔式的作業系統中,各工作的程式碼中必須包含交出 CPU 使用權的動作,為達並行的需求,該動作的頻率必須夠高,否則會讓使用者感受到明顯的等待。非搶佔式多工又稱作合作式多工 (cooperative multitasking),即各項工作間互相合作將 CPU 使用權,不定期交出。這種作法有下列幾項好處: 1. 一般來說,實作較單純,驗證系統行為也容易; 2. 工作中可使用非再進入程式碼 (non-reentrant code),換言之,每個工作不需擔心在程式未執行完畢時又重新進入。因此該工作本身所用的記憶區不會有被污染 (corruption) 的可能; 3. 對系統共用記憶區的保護動作可減至最少,因為每一工作在未使用完記憶區時不會放棄 CPU ,無須擔心會被其他工作在半途中修改; 非搶佔式的核心最致命的問題,在於反應能力 ([responsiveness](https://en.wikipedia.org/wiki/Responsiveness))。當一個優先順序較高的工作準備就緒,必須等待優先順序較低的工作放棄 CPU,才可執行。因此非搶佔式的核心很難估計其反應速度,無法滿足許多即時系統應用的需求。 搶佔式的核心則不同,優先順序高的工作可打斷正在執行、優先順序較低的工作,從而拿到 CPU 使用權。下圖展現非搶佔式與搶佔式核心的行為差異。 ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 3, "end": 4, "task": "排程器", "name": "B"}, {"start": 1, "end": 3, "task": 2, "name": "A"}, {"start": 4, "end": 7, "task": 2, "name": "C"}, {"start": 7, "end": 10, "task": 1, "name": "D"}, {"start": 10, "end": 13, "task": 3, "name": "E"} ] }, "height": 110, "width": 500, "mark": "bar", "encoding": { "y": { "field": "task", "type": "ordinal", "axis": { "title": "Working No.", "labelFontSize": 17, "titleFontSize": 15, "titleFontWeight": 500 } }, "x": { "title": "(a) non-preemptive", "field": "start", "bin": {"binned": true}, "scale": {"domain": [0, 14]}, "axis": {"labelFontSize": 15, "titleFontSize": 17, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "name"} } } ``` ```vega { "$schema": "https://vega.github.io/schema/vega-lite/v4.json", "data": { "values": [ {"start": 3, "end": 4, "task": "排程器", "Name": "B"}, {"start": 1, "end": 3, "task": 2, "Name": "A"}, {"start": 7, "end": 10, "task": 2, "Name": "C"}, {"start": 4, "end": 7, "task": 1, "Name": "D"}, {"start": 10, "end": 13, "task": 3, "Name": "E"} ] }, "height": 110, "width": 500, "mark": "bar", "encoding": { "y": { "title": "Working No.", "field": "task", "type": "ordinal", "axis": {"labelFontSize": 17, "titleFontSize": 15, "titleFontWeight": 500} }, "x": { "title": "(b) preemptive", "field": "start", "bin": {"binned": true}, "scale": {"domain": [0, 14]}, "axis": {"labelFontSize": 15, "titleFontSize": 17, "titleFontWeight": 500} }, "x2": {"field": "end"}, "color": {"field": "Name"} } } ``` 假設系統內有三個工作,工作 1, 2, 3 的優先順序為 $Task_1 > Task_2 > Task_3$,假設工作 2 正在執行。由上圖 `(a)` 所示,當工作 2 執行到中途時 `(A)` ,排程器被觸發 `(B)`,使得工作 1 與工作 3 排定執行。由於是非搶佔式的作法,必須等待工作 2 自動放棄 CPU 使用權 `(C)` 時,才能去執行工作 1 與 3 (`D` 與 `E`)。而搶佔式核心則不然(上圖 `(b)`),當工作 1 就緒時,工作 2 由於優先順序較低,將被迫放棄 CPU 而交由工作 1 使用。由這個比較可知時間分割式的排程法 (time slicing),必須使用搶佔式的核心方可落實。 搶佔式核心的最大優點是系統的反應速度快,對即時的應用是不可或缺的特徵,但其核心設計都比非搶佔式複雜許多,考量因素也多,大幅增加實作的難度。同時,它必須注意各程式碼的再進入性 (reentrancy) 與保護共用資料區等。 ## 程式之可再進入性 一個可再進入 ([reentrancy](https://en.wikipedia.org/wiki/Reentrancy_(computing))) 的函式是可被多個工作同時呼叫,而不會有資料不一致的問題。簡單來說,一個可再進入的函式,會避免在函式中使用任何共享記憶區 (global memory),所有的變數與資料均存在呼叫者的資料區或函式本身的堆疊區 (stack memory)。對常見的 C 編譯器來說,被呼叫 (callee) 之函式在返回之前,不會更動到呼叫者 (caller) 端的堆疊區。因此,即使該函式被不同的工作同時呼叫,由於在不同的堆疊區執行,互相之間是完全獨立的。 > 詳見 [你所不知道的 C 語言:函式呼叫篇](https://hackmd.io/@sysprog/c-function) 裝置驅動程式 (device driver) 通常要實作為可再進入的,例如驅動儲存設備的程式很可能同時為數項工作呼叫。 ## 經典的 Fork-Join 模型 典型的並行/平行程式,由以下 3 個區段所組成: 1. fork: 準備進入要平行化的區域時,主執行緒 (下圖紅色) 產生出一組執行緒 (紅色加黃色) ![image](https://hackmd.io/_uploads/S1wxT_y6a.png) > 注意: 這裡的 "fork" 並非 [fork 系統呼叫](https://en.wikipedia.org/wiki/Fork_(system_call)) 2. parallel region: 這些執行緒合力執行給定的工作 ![image](https://hackmd.io/_uploads/SkF-6_16p.png) 3. join: 工作完成之後, 又回到 fork 之前, 單一執行緒的狀態 ![image](https://hackmd.io/_uploads/BkvMpukTa.png) fork-join 模型就是不斷重複上述過程。 ![image](https://hackmd.io/_uploads/S1lQ6_1pa.png) 每個執行單元都有自己的 stack , 但跟本來的執行執行單元共用 text, heap 與 data section。 ![image](https://hackmd.io/_uploads/SJtQpdyT6.png) 延伸閱讀: [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec) --- ## Concurrency (並行) vs. Parallelism (平行) :::success concurrency 一詞在 1980 年代台灣的出版物就翻譯為「並行」,取「[並行不悖](https://dict.revised.moe.edu.tw/dictView.jsp?ID=19763)」^同時進行,不相妨礙^的意涵,但中國境內大約在 1990 年代末期才有正式的翻譯「併發」,本文尊重台灣資訊科技前輩們的成果,延續以「並行」來稱呼 concurrency 一詞。 [書本翻拍](https://www.facebook.com/photo.php?fbid=10155425951972389&set=pb.541762388.-2207520000..&type=3) ::: UNIX 作業系統和 Go 程式語言的先驅 [Rob Pike](https://en.wikipedia.org/wiki/Rob_Pike) 在 2012 年的演講 [Concurrency is not Parallelism](https://blog.golang.org/concurrency-is-not-parallelism)[,](https://www.youtube.com/watch?v=cN_DpYBzKso) * [投影片](https://web.archive.org/web/20130313120222/https://talks.golang.org/2012/waza.slide) / [重點提示](https://rakhim.org/summary-of-concurrency-is-not-parallellism-a-talk-by-rob-pike/) * [錄影](https://youtu.be/qmg1CF3gZQ0); [後續 stackoverflow 討論](http://stackoverflow.com/questions/11700953/concurrency-is-not-parallelism) Concurrency 對軟體設計的影響 * 想要充分使用到 CPU 的資源 * 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等,但如果 CPU 時脈無法增加,而其他存取方式速度變快,最後會發生 CPU-bound * 軟體效能優化將會越來越重要 * 程式語言必須好好處理 concurrency **Concurrency** 是指程式架構,將程式拆開成多個可獨立運作的工作。案例: 裝置驅動程式,可獨立運作,但不需要平行化。 * 拆開多個的工作不一定要同時運行 * 多個工作在單核 CPU 上運行 ![image](https://hackmd.io/_uploads/rJFV6u16a.png) **Parallelism** 是指程式執行,同時執行多個程式。Concurrency 可能會用到 parallelism,但不一定要用 parallelism 才能實現 concurrency。案例: 向量內積計算 * 程式會同時執行 (例如:分支後,同時執行,再收集結果) * 一個工作在多核 CPU 上運行 ![image](https://hackmd.io/_uploads/rySrTuypa.png) Rob Pike 用地鼠燒書做例子: ![image](https://hackmd.io/_uploads/ByaBTdy66.png) 若增加多一隻地鼠、一個推車或多一個焚燒爐,這樣有機會作到更好的資源使用率,但我們不能保證兩隻或更多地鼠會同時進行 (有限的火爐,只能允許一次進行一次的燒書工作,效率不彰)。 ![image](https://hackmd.io/_uploads/ryuLadkpa.png) 以 Concurrency 的方式去作業,能夠以不同的解構方式去進行,可以是三個地鼠分別負責一部分的工作 (decomposition) ![image](https://hackmd.io/_uploads/S1bdTdkpT.png) 也可以是 Parallelism: ![image](https://hackmd.io/_uploads/SyK_pO1a6.png) 或 ![image](https://hackmd.io/_uploads/SyNF6Oyap.png) **Concurrency:** 是指程式架構,將程式拆開成多個可獨立運作的工作,像是驅動程式都可獨立運作,但不需要平行化 * 拆開多個的工作不一定要同時運行 * 多個工作在單核處理器上運行 ![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613316743_p1.png) **Parallelism:** 是指程式執行,同時執行多個程式。Concurrency 可能會用到 parallelism,但不一定要用 parallelism 才能實現 concurrency。eg:Vector dot product * 程式會同時執行 (如:fork 後,同時執行,再收集結果,即 join 操作) * 一個工作在多核處理器上運作 ![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613329719_p2.png) 線上教材 [Introduction to OpenMP](https://youtu.be/6jFkNjhJ-Z4) 整理以下: - [ ] Concurrent (並行) * 工作可拆分成「獨立執行」的部份, 這樣「可以」讓很多事情一起做, 但是「不一定」要真的同時做。下方情境: ![image](https://hackmd.io/_uploads/rJz5a_yaa.png) * 展示具有並行性,但不去同時執行。 * 並行性是種「架構程式」的概念。寫下一段程式之前, 思考問題架構時就決定好的。 - [ ] Parallel (平行) * 把規劃好、能夠並行的程式,分配給不同執行緒,並讓他們同時執行。 ![image](https://hackmd.io/_uploads/SJh9auJT6.png) * 「平行」是一種選擇。 * 若我們發現程式中發現需要做內積,可用迴圈走訪 3 個元素來運算 (沒有平行化), 也可用 3 個執行緒同時執行每個相應位置元素的乘法 (有平行化) $\to$ 這裡「要不要做平行化」只是種「選擇」 ## 如何確保並行執行的結果正確? 以 Rob Pike 的地鼠燒書為例 ![image](https://hackmd.io/_uploads/ryOiTOy6a.png) * Split a program: 將燒書過程中,切割好各地鼠負責的工作。 * Synchronization: 確保地鼠在交接工作時,能夠有**效率**且**正確**的溝通。 延伸閱讀: * [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync) * [Concurrency in the Kernel](https://web.fe.up.pt/~pfs/aulas/so2021/at/19conc.pdf)