# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`linachiu`>
## Concurrency (並行) vs. Parallelism (平行)

**Task:** 一件任務


* **Concurrency:** 兩個任務分配到一個CPU核心，在取得的時間片段中交互執行


* **Parallelism:** 有兩個CPU，同個問題分配到兩個CPU上同時執行


### 一些造成等待時間變長的 blocking IO

* fgets --> 可用 mmap()改善
* malloc() --> 可開一個 memory pool 將 linked list會用到的空間先開好


## Thread Pool

在介紹Thread之前,我們必須先把Program和Process這兩個觀念作一個釐清。

* **Program:** 一群程式碼的集合,用以解決特定的問題。以物件導向的觀念來類比,相當於Class。

* **Process:** 由Program所產生的執行個體,一個Program可以同時執行多次,產生多個Process。以物件導向的觀念來類比,相當於Object。每一個Process又由以下兩個東西組成
* **一個Memory Space** :相當於Object的variable,不同Process的Memory Space也不同,彼此看不到對方的Memory Space。
* **一個以上的Thread** :Thread代表從某個起始點開始(例如main),到目前為止所有函數的呼叫路徑,以及這些呼叫路徑上所用到的區域變數。當然程式的執行狀態,除了紀錄在主記憶體外,CPU內部的暫存器(如Program Counter, Stack Pointer, Program Status Word等)也需要一起紀錄。所以Thread又由下面兩項組成
* **Stack:** 紀錄函數呼叫路徑,以及這些函數所用到的區域變數
* **目前CPU的狀態**

**Thread的重點如下**

* 一個Process可以有多個Thread。

* 同一個Process內的Thread使用相同的Memory Space,但這些Thread各自擁有其Stack。換句話說,Thread能透過reference存取到相同的Object,但是local variable卻是各自獨立的。
* 作業系統會根據Thread的優先權以及已經用掉的CPU時間,在不同的Thread作切換,以讓各個Thread都有機會執行。

### Thread Pool

* Thread 執行緒常被定義為一個輕量的(Lightweight) Process，可用來處理 request，
然而雖然是輕量，但在產生 Thread 時仍會有 overhead，此時若 request 量太大，
又沒有善加管理這些 Thread 的話，就會拖累整體系統的效能。
為了解決這種類型的效能問題，所以就有了 Thread Pool 的概念產生。

* Thread Pool 的概念如同其名，就是一個 Thread 的 Pool，其中有固定或變動量的 Thread，當 request 進來時，若有閒置的 Thread 就執行，若沒有的話，可能產生新的 Thread 或把 request 放入 queue 中等待被執行，當一條 Thread 執行完工作而 queue 中仍有 request 在等待時，此 Thread 應該要被分發新的 request 並處理。

* 由以上幾行，我們可以看出 Thread Pool 的工作有：
* 管控 Thread 的產生與回收
* 分發 Thread 處理 request
* 處理 request 的 queue
*

## Lock-free Thread Pool

大多數 thread pool 實做都離不開 lock 的使用，如 pthread_mutex 結合 (condition variable) pthread_cond。一般來說，lock 的使用對於程式效能影響較大，雖然現有的 pthread_mutex 在 lock 的取得 (acquire) 與釋放，已在 Linux 核心和對應函式庫進行效能提昇，但我們仍會希望有不仰賴 lock 的 thread pool 的實做。

**常見 thread pool 實做原理**


如上圖所示，workqueue (工作佇列) 由 main thread (主執行緒) 和 worker thread 共享，main thread 將任務放進 workqueue，worker thread 從 workqueue 中取出任務執行。要注意到，共享 workqueue 的操作必須在 mutex 的保護下安全進行，main thread 將任務放進 workqueue 時，若偵測到目前待執行的工作數目小於 worker thread 總數，則要透過 condition variable 喚醒可能處於等待狀態的 worker thread。