教材:10710周志遠教授平行程式
https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT

20250826 筆記
內容可能有錯僅供參考

7A~7B Pthread:Synchronization Problem & Tools
8A Synchronization Tools & Open Multi-Processing(OpenMP)

今日大綱
1.複習一下 Pthread
2.Pthread Join 與 Detach
3.同步化問題與工具
4.Race Condition 的發生
5.Critical Section
6.Mutex (Lock) 在 Pthread 中的應用
7.Bounded Buffer (生產者-消費者) 問題
8.Condition Variable (條件變數) 在 Pthread 中的應用
9.Thread Pool 介紹

#### **複習一下 Pthreads (POSIX Threads) 是什麼**

`pthread` 指的是 POSIX Threads，它是一個 **thread 的 programming library**。前面的 `P` 指的是 POSIX，因為這個函式庫是在 POSIX API 介面定義之下所實作的。

要使用 `pthread` 函式庫，最主要且常用的函數就是 `pthread_create`。它主要有以下幾個參數：

* **第一個參數：`pthread_t *thread`**
* 這是一個 **reference value**，一個 token。
* 你需要給它一個 **位址 (address) 的 pointer**。
* `pthread_create` 執行後，會在這個位址回傳 **新建立執行緒的 token**。
* 透過這個 token，可以呼叫其他與這個執行緒互動的 API，例如後面會解釋的 `pthread_join`。
* `&threads[tid]` 就是傳入的位址，用來接收新建立的執行緒 ID：

        pthread_t threads[NUM_THREADS];
        // ...
        pthread_create(&threads[tid], NULL, PrintHello, (void *)&tid);

* **第二個參數：`const pthread_attr_t *attr`**
* 這是一個 **attribute 的 pointer**，它是 **optional**。
* 裡面的屬性可以控制新建立執行緒的一些 **configuration**，例如它的一些行為或作業系統如何管理它。
* 有時會有一些設定，你可以透過這個 `attribute` 去設定，它其實裡面都是一些 0/1 的 flag。
* 通常，大家會用 **default**，也就是 `NULL` 就足夠了。
* 比較有用的設定像是將執行緒綁定到特定的 CPU 核心上，或者指定其記憶體位置接近特定的核心，這些系統設定通常透過 `attribute` 來告知 `pthread` 函式庫如何管理這個執行緒。

* **第三個參數：`void *(*start_routine)(void *)` (function pointer)**
* 這是一個 **function pointer**，指向這個新執行緒要 **執行** 的程式碼。
* 當一個執行緒被建立出來之後，它就會去執行這個函數。
* 在程式碼中，`PrintHello` 就是這個函數指標，每個新建立的執行緒都會執行這個 `PrintHello` 函數。

* **第四個參數：`void *arg` (argument pointer)**
* 這是這個函數執行時所需的 **argument 的 pointer**。
* 雖然它只有一個參數，但你可以透過這個 pointer 指向一個 **`struct`**，裡面可以塞入多個 argument variable。
* 然而，你需要根據這個 `struct` 的資料型別去做 **type casting**，在使用之前將其讀取成正確的資料型別。
* `pthread` 函式庫比較 low-level，這個 pointer 是 `void` 型別，所以它沒有資料型別。這也是為什麼在函數內部，還要自己做 **資料型別的 cast 動作**，因為它並不知道實際的資料型別。如果傳入的資料型別與轉換的資料型別不符，可能會導致記憶體長度不匹配，甚至出現 segmentation fault 的問題，這點需要特別留意。
* `(void *)&tid` 就是將 `tid` 的位址作為參數傳入，`PrintHello` 函數內部再將其轉換回 `long *data` 。

### Pthread Join 與 Detach (Pthread Joining and Detaching)

執行緒在執行完之後，會回傳一個值。這個回傳值必須是 **一個 pointer**。如果你只回傳一個 `integer`，它讀到的值會不對，因為唯一讀取回傳值的方式是透過 `pthread_join`。

#### `pthread_join` 函數

`pthread_join` 的主要目的有兩個：

1. **取回執行緒的回傳值 (Return Value)**
* 當執行緒完成執行並回傳後，它的回傳值會被放在 `status` 變數中，你就可以取得它。
* `pthread_join` 會 **block** 當前呼叫它的執行緒 (通常是 `main thread`)，直到它要 join 的那個執行緒結束 (也就是它回傳時)。這時 `pthread_join` 才會從 block 的程式碼中回傳。

2. **同步化 (Synchronization)**
* 另一個使用情境不是為了取回回傳值，純粹是為了 **同步化**。
* 就像 barrier 一樣，`pthread_join` 也可以用來強制兩個或多個執行緒之間達到同步。例如，如果你用一個 `for` 迴圈建立了很多執行緒，也可以用一個 `for` 迴圈 `join` 回來，這就等於是讓所有執行緒之間做一個 barrier 一樣的事情。
* 如果你的程式架構是 `main thread` 建立很多 `worker threads`，讓 `worker threads` 完成各自的工作後，再 `join` 回 `main thread`，這樣 `main thread` 就可以控制整個流程。這些 `worker threads` 在需要時被建立，完成後又回到 `main thread`。通常 `main thread` 和 `worker threads` 之間不會有頻繁的溝通，而是全部做完後再 `join` 回來。

**與 MPI 的差異：**
`pthread` 的平行程式設計模型是 **每個執行緒都執行獨立的 function code**。這與 MPI 很不一樣，MPI 的大家其實是執行同一個函數，只是用分支來區分。因此，`pthread` 的執行緒可以完全做不同的事情，這使得它們的應用範圍非常不同。如果每個執行緒做的事情都不一樣，通常很難擴展到很大規模，因為大家要完成同一件事會非常困難。因此，`pthread` 通常應用在較小規模的、有限的 CPU 核心數量上，且每個執行緒做的事情通常很快完成，然後再 `join` 回 `main thread`。

#### `pthread_detach` 函數

有時候，你的函數程式碼不需要回傳值，而且許多應用情境是 `main thread` 把事情交給 `worker thread` 之後，就 **不再理會** 這個 `worker thread`。`worker thread` 做的事情與 `main thread` 毫無關聯性。一個最好的例子就是 **web server**。

* **Web Server 範例：** Web server 會不斷接收許多 requests。`main thread` 只負責監聽是否有 request 進來。每收到一個 request，`main thread` 就會建立一個 `worker thread` 來處理這個 request (例如下載檔案、開啟檔案或進行計算)。這些 `worker thread` 的工作其實與 `main thread` 已經無關，`main thread` 只是交代事情，`worker thread` 自己去做就好，所以也 **不需要回傳值**。`worker thread` 和 `main thread` 之間也沒有任何關聯性。

在這種情況下，**不只不用呼叫 `pthread_join`，事實上還必須要呼叫 `pthread_detach`**。

* **為什麼要 `detach`？**
* 如果你不 `join`，其實反而會 **block 住 `main thread`**，這不是你想要的。
* 但你也不能不呼叫 `pthread_detach`。如果你的程式不呼叫 `pthread_join` 也不呼叫 `pthread_detach`，許多函式庫會認為你遲早會 `join`，因此程式可能會卡住。因為函式庫會假設程式設計師有可能會去 `join`，如果沒有執行 `join` 或 `detach`，你的程式就會停在那裡。
* `detach` 的意義在於它會告訴 `pthread` 函式庫，這個 `worker thread` 之後 **再也不需要與 `main thread` 透過 `join` 做聯絡了**。因此，只要這個 `worker thread` 結束，並且 `main thread` 也完成了它該做的事情，整個程式就可以結束，不會卡在那裡等待。
* 更重要的是，`detach` 的目的在於 **釋放資源**。為了 `join`，系統會分配一些中間資源，如果 `detach` 了，這些資源就可以被直接釋放掉，系統就不會期待 `join` 的發生。如果不 `detach`，這些資源會一直被分配，造成 memory leak ，甚至讓系統卡住。
* 呼叫 `pthread_detach` 之後，你就 **不能再呼叫 `pthread_join`** 了。這是一個選擇：你建立執行緒後，要嘛讓它被 `join`，要嘛讓它被 `detach`，必須二選一，這取決於你的程式設計目的。如果沒有需要，就 `detach`。
* 通常，應該在 **建立執行緒後立刻呼叫 `pthread_detach`**，告知 `main thread` 不必等待這個 `worker thread` 結束。它不僅可以節省資源，有些函式庫甚至會強制你呼叫，否則你的程式會卡住。

所以，建立執行緒之後，你就要在 `join` 和 `detach` 之間做一個選擇。

### 同步化問題與工具 (Synchronization Problem and Tools)

當多個執行緒同時存取同一個記憶體，並且同時修改它的時候，就會產生 **同步化 (synchronization) 問題**。這些問題可能導致程式碼執行錯誤。

#### 同步化問題的定義

同步化問題就是說，當程式在執行時，**最終的結果不應該根據程式執行順序的調換而受到影響**。這非常合理，因為我們寫的程式跑在電腦裡，但電腦不是一個單一核心的，它有平行計算能力，多數電腦都是 multi-core。

* **執行緒的執行順序是不可控的：**
* 執行緒的先後順序是可以調換的，你無法控制它。
* 這是由作業系統甚至硬體排程器來決定的，而不是你寫程式碼的順序。
* **指令層級的順序交換：**
* 更精確地說，影響結果的是 **instruction 順序的調換**。你寫的程式碼是 high-level language 的 statement，例如 `x = 3`。但它在處理器上執行時，其實是 instruction (例如 assembly)。
* 即使 instruction level 的順序被調換了，你都必須確保程式能正確執行。

#### Race Condition 範例：Counter 加減問題

為什麼 instruction level 的順序調換會導致錯誤呢？我們來看一個典型的例子：假設有兩個執行緒，一個做 counter 加一，一個做 counter 減一。`counter` 是一個**共用的 variable**，目的是讓兩個執行緒同時對它進行操作。

* **表面上的一行程式碼，實則多個指令：**
* `counter++` 或 `counter--` 看似只有一行 statement，但實際上，在處理器層級，它會被分解成 **三個 instruction**：
1. **Load ：** 從 `counter` 的記憶體位置將值載入到 register 。
2. **Modify ：** 對 register 進行加一或減一的操作。
3. **Store ：** 將修改後的值從 register 寫回到 `counter` 的記憶體位置。

* **Race Condition 的發生：**
* 假設 `counter` 的初始值是 5。
* 執行緒 A (加一) 開始執行，載入 5 到 register，並加一變成 6。
* 此時，發生了 **context switch**，執行緒 B (減一) 開始執行。
* 執行緒 B 也從記憶體載入 `counter` 的值，此時 `counter` 在記憶體中仍然是 5 (因為執行緒 A 還沒寫回去)，並減一變成 4 (在執行緒 B 的 register 中)。
* 如果執行緒 A 先完成其最後一個 instruction (將 6 寫回 `counter` 記憶體)，`counter` 會變成 6。
* 接著，執行緒 B 完成其最後一個 instruction (將 4 寫回 `counter` 記憶體)，`counter` 會變成 4。
* **結果是 4。** 但一個加一一個減一，初始值 5，正確答案應該是 5。
* 如果最後兩個指令的順序調換，結果可能會是 6。
* 所以，如果沒有做任何同步化，當兩個程式同時執行並存取同一個記憶體時，答案可能是 4、5 或 6，但只有 5 是正確的。

這種情況就代表程式有 **同步化問題**。

#### Critical Section

* **概念：** 產生同步化問題的原因在於兩個程式在執行過程中 **同時對同一個記憶體位址的內容進行存取和修改**。
* **解決方案的核心：** 如果我們一次只讓一個人去存取這個記憶體，並且確保這個存取過程是 **穩定的** (修改完成並寫回記憶體)，那麼就沒有問題。
* **程式設計者的責任：** 程式設計師在編寫共享記憶體程式時，有責任判斷哪些資料 (記憶體內容) 是在多個執行緒之間共享的。
* **定義 Critical Section：** 如果資料是共享的且會被修改，那麼就必須將存取和修改這段程式碼定義為 **critical section**。這段程式碼需要被保護起來，確保 **一次只有一個執行緒可以執行** 這段程式碼。
* **效果：** 即使有很多執行緒同時執行，但當它們遇到 Critical Section 時，都必須排隊輪流使用和修改，這樣就不會有同時存取的狀況發生。

#### Mutual Exclusion (互斥)

* **目的：** 提供 **mutual exclusion**，也就是說，一次只有一個執行緒在 Critical Section 內執行。
* **工具：** 寫程式時，通常會使用 **lock** 來保護 Critical Section。

### Mutex (Lock) 在 Pthread 中的應用

#### Mutex 介紹

Lock 的概念其實很簡單。在一個簡化的實作中，當 `lock` 的值是 1 時，程式會一直卡在一個 `while` 迴圈 (spinlock)，無法執行下一步。等到 `lock` 變成 0 時，它才能進入 Critical section。進入後，它會將 `lock` 設為 1，阻止其他人進入。完成計算並離開時，它會再次將 `lock` 設為 0 (unlock)。

然而，**`pthread` 函式庫中的 lock 稱為 Mutex**，它的全名就是 **mutual exclusion (互斥)**。

* **pthread_mutex API ：**
* `pthread_mutex_t mutex`：`mutex` 是一種特殊的資料型別，它不是一個簡單的 `integer` 值，而是一個複雜的資料結構。
* **`pthread_mutex_init(&mutex, NULL)`：** 必須先對 `mutex` 進行 **初始化 (init)**。通常參數可以設為 `NULL`。初始化後才能開始使用。
* **`pthread_mutex_lock(&mutex)`：** 呼叫此函數來 **鎖住 (lock)** `mutex`。如果 `mutex` 已經被鎖住，呼叫的執行緒會被阻塞，直到 `mutex` 被釋放。
* **`pthread_mutex_unlock(&mutex)`：** 呼叫此函數來 **解鎖 (unlock)** `mutex`。
* **`pthread_mutex_destroy(&mutex)`：** 當不再需要 `mutex` 時，應該對其進行 **銷毀 (destroy)**，就像釋放記憶體一樣，避免記憶體問題。

* **`Mutex` 變數的特性：**
* `Mutex` 可以被重複使用。
* `Mutex` 變數 **必須是一個 global variable**。因為多個執行緒要共享同一個 `lock` 才能保護同一個 Critical section。
* 在一個程式中，你可以建立非常多的 `mutex`。你可以自己決定哪些共享資料要用哪一個 `lock` 來保護，甚至為每個共享資料建立一個 `lock`。
* 核心概念是：**如果一個 `lock` 被建立後，你想保護一個共享資料，就用 `lock` 和 `unlock` 將它包起來，並且所有要保證互斥的執行緒都應該使用同一個 `lock`，並遵循這個協定，這樣才能避免同步化問題**。

#### Bounded Buffer (生產者-消費者) 問題

這是一個很有名的問題，其中有兩個程式或執行緒：

* **Producer (生產者)：** 不斷產生資料，並將資料放入一個 **memory buffer** 中。
* **Consumer (消費者)：** 接收資料的人，不斷從這個 buffer 中取出資料項目，然後處理這些資料。
* **溝通方式：** 兩者透過這個 **共享的 memory buffer** 進行溝通。

這個問題需要同步化的原因在於：

* **Buffer 是有限的 (bounded)：**
* 如果 `producer` 不斷寫入資料，可能會覆蓋掉之前的資料 (如果 Buffer 已滿)。
* `producer` 需要知道 **什麼時候 buffer 是滿的**。
* `consumer` 需要知道 **什麼時候 buffer 是空的**。

* **`in` 和 `out` 指標的判斷：**
* 一種判斷方式是透過 `in` (寫入指標) 和 `out` (讀取指標)。
* 當 `in == out` 時，表示 **buffer 是空的** (因為 `consumer` 讀完所有資料後，`out` 會移動到與 `in` 相同的位置)。
* 當 `(in + 1) % BUFFER_SIZE == out` 時，表示 **buffer 是滿的**。這裡犧牲掉一個儲存空間，以區分「空」和「滿」的兩種狀態 (避免 `in == out` 既代表空也代表滿的混淆)。

* **同步化解決方案：**
* **Producer 的邏輯：** 它會判斷 buffer 是否為滿。如果滿了，它會一直等待 (lock/spin-lock)，直到 buffer 不滿才寫入資料，並移動 `in` 指標。
* **Consumer 的邏輯：** 它會檢查 buffer 是否為空。如果空了，它會一直等待，直到 buffer 不空才讀取資料，並移動 `out` 指標。

* **使用 Lock 保護 Counter 範例：**
* 如果我們使用一個 `counter` 變數來記錄 buffer 中有多少資料，那麼 `producer` 會 `counter++`，`consumer` 會 `counter--`。
* 這正是我們前面提到的 **Race Condition 問題**。
* 有了 `lock` 和 `unlock` 工具，解決方案就是將 `counter++` 和 `counter--` 這些對共享資料的操作放在 `pthread_mutex_lock` 和 `pthread_mutex_unlock` 之間，形成一個 Critical Section。這樣兩個程式就可以同時運作，而不用擔心同步化問題。

### Condition Variable (條件變數) 在 Pthread 中的應用

除了 `lock` (Mutex)，第二個非常重要的同步化工具是 **condition variable (條件變數)**。

#### Condition Variable 介紹

* **目的：** 它解決的問題與 `mutex` 略有不同，主要用於 **同步程式執行的時間點**。
* **概念：** Condition variable 是一個變數，你可以對它呼叫 `signal` 和 `wait`。它的目的就是當 **某個 condition 發生時**，你可以透過 `signal` 這個變數，讓所有在 `sleep` 或 `wait` 這個變數的程式 **全部被喚醒**。這就像在等待一個 event 發生，當事件發生時，有人通知你，你就可以被叫醒並開始做事情。
* **pthread_cond_t API ：**
* `pthread_cond_t cond`：`condition variable` 本身也是一個 token，一個特殊的資料型別。
* **`pthread_cond_init(&cond, NULL)`：** 必須先對 `condition variable` 進行 **初始化 (init)**。
* **`pthread_cond_wait(&cond, &mutex)`：** 當一個執行緒呼叫 `wait` 某個特定的 `condition variable` 時，它會被 **block (阻塞) 住並進入 sleep (睡眠) 狀態**。作業系統會排程它，不會浪費 CPU 資源。它會一直等待，直到有人對這個 `condition variable` 呼叫 `signal` 或 `broadcast`。
* **`pthread_cond_signal(&cond)`：** 喚醒 **一個** 正在等待這個 `condition variable` 的執行緒。通常是等待時間最少的那個。
* **`pthread_cond_broadcast(&cond)`：** 喚醒 **所有** 正在等待這個 `condition variable` 的執行緒。
* **`pthread_cond_destroy(&cond)`：** 不再需要時銷毀 `condition variable`。

#### Condition Variable 與 Mutex 的互動 (Why Mutex is needed)

在 `pthread` 中，你會發現 `pthread_cond_wait` 除了 `condition variable` 之外，還需要一個 `mutex` 作為參數。

**1. 為何 `wait` 和 `signal` 必須在 Critical Section 內？**

* **保護共享變數：** 就像你們提供的 `action()` 和 `counter()` 範例中，**`x` 是一個共享變數**。任何執行緒呼叫 `counter()` 都可以修改 `x` 的值。你的事件 (例如 `x == 0`) 是依賴於這個共享變數 `x` 的。因此，**`x` 本身就應該被保護在 critical section 裡**。
* 如果你們的 `action()` 函數沒有使用 `lock`，那麼在 `counter()` 將 `x` 設為 0 之後，`action()` 等待的條件可能會在它檢查之前就被其他執行緒修改，導致問題。
* 如果 `counter()` 函數沒有使用 `lock`，那麼 `x--` 和 `if (x==0)` 這兩步操作就無法保證是 `atomic (原子性)` 的 。
* **避免常見程式錯誤：** `pthread` 函式庫的 API 規定，**`conditional wait`、`signal` 和 `broadcast` 都必須在 critical section 裡面**。這是一種比較嚴格的規定，目的是提醒程式設計師，避免他們忘記保護那些影響事件時間點的變數。即使有些情況下可能看似不需要 `mutex`，但這個定義可以避免當你真正需要時卻忘記的情況。
* **確保 `x` 值的正確性：** 把這些操作放在 critical section 裡面，可以保證 `x` 的值是正確的。當 `action()` 執行緒被 `wake up` 時，它也可以保證 `x` 的值一定是 0。

**2. `pthread_cond_wait` 的內部機制：**

`pthread_cond_wait` 不僅僅是讓執行緒進入睡眠狀態，它還做了兩件非常重要的事情：

* **自動釋放 `Mutex`：**
* 當 `action()` 執行緒取得 `lock` 並進入 critical section 後，如果 `x != 0`，它會呼叫 `pthread_cond_wait(&cond, &mutex)`。
* 在進入睡眠之前，`pthread_cond_wait` 的內部實作會 **自動釋放持有的 `mutex`**。
* **如果沒有這個機制，就會發生 Deadlock**。想像一下，如果 `action()` 取得了 `lock` 但不釋放，然後進入 `wait` 狀態。而 `counter()` 執行緒需要先取得同一個 `lock` 才能進入 critical section 呼叫 `signal` 來喚醒 `action()`。結果就是 `action()` 等待 `counter()` 喚醒，`counter()` 等待 `action()` 釋放 `lock`，兩者互相等待，程式永遠無法跑完。

* **被喚醒後重新獲取 `Mutex`：**
* 當 `action()` 執行緒被 `counter()` 的 `signal` 喚醒後，它並不能立刻繼續執行。
* 它被喚醒後的第一件事是 **重新獲取 (acquire) 之前釋放的 `mutex`**。
* 只有當它成功重新取得 `mutex` 之後，才能繼續執行 `wait` 之後的程式碼。
* 這樣做的好處是，無論是 `action()` 還是 `counter()`，在 critical section 裡面執行時，**任何時間點都只有一個執行緒在裡面執行**。這樣就解決了同步化問題。
* 所以，程式設計師不需要自己手動在 `pthread_cond_wait` 前後加上 `unlock` 和 `lock`，這個函數本身就幫你處理了。

**3. 程式碼範例分析 (Using Condition Variable):**

pthread_cond_t cond;  pthread_cond_init(&cond, NULL);
pthread_mutex_t mutex;  pthread_mutex_init(&mutex, NULL);

// action() 函數
// - action() 的目的：等待 x 等於 0 的狀態
// - 一旦 x 等於 0，它就可以離開等待狀態並執行 take_action()
action() {
    pthread_mutex_lock(&mutex); // 進入 critical section
    while (x != 0) { // 使用 while 迴圈檢查條件，防止"假的喚醒"
        pthread_cond_wait(&cond, &mutex); // 等待條件滿足。會自動釋放 mutex
    }
    pthread_mutex_unlock(&mutex); // 離開 critical section
    take_action(); // 執行實際的動作
}

// counter() 函數
// - counter() 的目的：修改 x 的值，並在 x 等於 0 時發出訊號
counter() {
    pthread_mutex_lock(&mutex); // 進入 critical section
    x--; // 遞減共享變數 x
    if (x == 0) { // 如果 x 達到 0
        pthread_cond_signal(&cond); // 喚醒一個等待的執行緒
    }
    pthread_mutex_unlock(&mutex); // 離開 critical section
}

* **關鍵點：`while (x != 0)` 而不是 `if (x != 0)` 。** 在實際使用 Condition Variable 時，即使執行緒被喚醒，也應該重新檢查條件 (`while` 迴圈) 。這是因為有可能發生 "spurious wakeups" (偽喚醒)，或者在喚醒後到執行緒重新取得 `mutex` 之間，條件又被其他執行緒改變了。`while` 迴圈確保在執行緒離開 `wait` 狀態後，條件確實被滿足

### Thread Pool 介紹

`mutex` 和 `condition variable` 這兩個工具可以應用在許多地方，其中一個很重要的應用就是 **thread pool (執行緒池)**。

#### 概念與優勢

* **問題：** 就像 Web Server 的例子，每來一個 request 就動態建立一個執行緒，完成後就釋放。這樣雖然可以實現平行化，但缺點是無法控制會建立多少執行緒，而且動態建立和銷毀執行緒也需要時間。如果執行緒數量過多，作業系統可能無法負荷，導致程式崩潰。
* **Thread Pool 的概念：** 在指派執行緒工作之前，就 **預先建立好一批執行緒**。這些執行緒作為一種資源，等待被指派任務函數並執行。
* **優勢：**
* **控制資源：** 你可以控制執行緒池的大小 (例如，根據物理 CPU 核心數量的 N 倍來設定)。當池中的執行緒都用完了，新的 request 就會排隊等待可用的執行緒。
* **提升效率：** 執行緒是持續存在的，不需要頻繁地建立和銷毀。你只需指派函數指標給它，這會比動態建立執行緒快得多。
* **避免過度競爭：** 如果物理資源不足，建立再多的執行緒也沒有幫助，反而會導致更多的 context switch overhead 或執行緒競爭，使程式跑得更慢。因此，控制執行緒數量非常重要。

#### 實作技巧

Thread Pool 的實作方式有很多種，但核心思想是結合 `condition variable` 和 `lock`。

* **`Task` 結構：**
* 通常，每個要執行的工作會被包裝成一個 `struct`。
* 這個 `struct` 會包含一個 **function pointer** (指向真正的任務函數) 和該函數所需的 **argument pointer**，這與 `pthread_create` 的參數非常類似。

* **`Task Queue` (共享資料結構)：**
* 所有待處理的 `task` 會被串接在一個 **queue** 中，這是一個 **共享的資料結構**。
* 當有新的工作來時，就將它丟到這個 `task queue` 裡。

* **執行緒池的通用執行緒函數：**
* `thread pool` 裡的每個執行緒都執行 **同一個通用函數** (例如 `thpool_worker` 之類的)。
* 這個通用函數是一個 **無限迴圈 (`infinite for loop`)**。
* 它的角色就是不斷地 **等待被指派工作**。

* **Mutex 與 Condition Variable 的結合應用：**
* **保護 `Task Queue`：** `task queue` 是一個共享資料結構，當執行緒從中取出 task (dequeue) 時，這個操作需要透過 `lock` 和 `unlock` 來保護，以避免同步化問題。
* **等待任務：** 如果執行緒發現 `task queue` 是空的 (`count == 0`)，表示沒有事情可做。這時，它就會呼叫 **`pthread_cond_wait` 讓自己進入 sleep 狀態**。這樣可以避免浪費 CPU 資源。
* **喚醒執行緒：** 當有新的 `task` 加入 `task queue` 時，並且有閒置 (idle) 的執行緒時，就會呼叫 `pthread_cond_signal` 或 `pthread_cond_broadcast` 來 **喚醒一個或所有正在等待的執行緒**。
* **執行任務：** 被喚醒的執行緒會從 `task queue` 中取出一個 `task` 結構，取得裡面的 `function pointer` 和 `argument`，然後直接呼叫執行該 `task` 的函數。
* **循環：** 執行完畢後，執行緒會回到無限迴圈的開頭，繼續檢查是否有新的工作。如果沒有，它又會再次進入 `sleep` 狀態。

`pthread` 是一個比較 low-level 的函式庫。如果想使用這些功能，通常需要自己去寫這些實作。但許多高階語言 (例如 Java) 可能已經內建了類似 `thread pool` 的 class (類別)，其底層實作概念與這裡提到的非常相似。

---
其他課程連結

[平行程式1C~2B Introduction parallel programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Syxh3H7Kxe)
[平行程式3A~3D The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJh7QFVKle)
[平行程式4A~4B IO Parallel IO and Program Analysis](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJLMsuHFgg)
[平行程式5A~5B The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/SJh57hIFle)
[平行程式6A~6B Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/r1X9kX_Fle)
[平行程式 6C~6D Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/S1DPjoYFlx)
[平行程式 7A~8A Pthread:Synchronization Problem & Tools](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJu-_0tKge)
[平行程式 8B~8D Synchronization Tools & Open Multi-Processing(OpenMP)](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1ki4E2Fee)
[平行程式 9A~9B Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJTYMrpKlx)
[平行程式 10A~10B Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/B1cY6M1qee)
[平行程式 10C~10D Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BkgFaNg5gg)
[平行程式 11A~11B Parallel Work Pool and Termination / Parallel Sorting](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1hfOw-5xl)
[平行程式 12A~12B Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Symo-zQ9eg)
[平行程式 12C~12D Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJYNKDVceg)
[平行程式 13A-13B Sychronous Parallelism](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJ2UJ2Bqex)
[平行程式 14A~14B Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BksS4yP5eg)
[平行程式 14C~14D Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJrfTUd9xx)
[平行程式 15A~15B Parallel Programming Model on GPU](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/ByWnl-t5gg)
[平行程式 16A~16B What is Compute Unified Device Architecture(CUDA)?](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HyYpsjcqgl)
[平行程式 17A~18A 平行運算的CUDA](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1dUeBT5lg)
[平行程式 18B~19A 記憶體層級 / CUDA的優化](https://hackmd.io/@JuitingChen/HyF44e1jge)
[平行程式 19B~19D 記憶體層級 / CUDA的優化 ](https://hackmd.io/@JuitingChen/ryPEu4lieg)
[平行程式 20A~20B CUDA優化全域和區域記憶體/共享記憶體](https://hackmd.io/@JuitingChen/r1X659Zoxl)
[平行程式 21A~21B Parallel Reduction / Distributed Computing Framework](https://hackmd.io/@JuitingChen/HyiOpozjxl)
[平行程式 NTHU-PP-Chap10-Big Data-Part1 ](https://hackmd.io/@JuitingChen/Hyc-e3Golx)
[平行程式 NTHU-PP-Chap10-Big Data-Part2 ](https://hackmd.io/@JuitingChen/ryC_QTXoxl)
[平行程式 NTHU-PP-Chap11-MapReduce](https://hackmd.io/@JuitingChen/HJgBXJOsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part1](https://hackmd.io/@JuitingChen/ryh5hBtsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part2](https://hackmd.io/@JuitingChen/rJ2G7kdjxg)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part3](https://hackmd.io/@JuitingChen/HkA471dilx)
[平行程式 NTHU-PP-Chap13-UCX-Part1](https://hackmd.io/@JuitingChen/rJbq103ieg)
[平行程式 NTHU-PP-Chap13-UCX-Part2](https://hackmd.io/@JuitingChen/SJpNmk_ixl)
[平行程式 NTHU-PP-Chap13-UCX-Part3](https://hackmd.io/@JuitingChen/HkIUYa13xe)