---
# System prepended metadata

title: 七周七線程模型練習筆記

---

# 七周七線程模型練習筆記

## 第一章 並行與並發

* 並發是同一時間應對(dealing with)多件事情的能力
* 並行是同一時間執行(doing)多件事情的能力

舉例如下：
* 一個服務生一次只能幫一個客人寫點菜單 -> 非並發
	* 加只有一個廚師一次只能做一道菜 -> 不並發且不並行
	* 加同時有多個廚師分工做菜 -> 非並發但並行
* 一個服務生可以同時接受多個客人的點菜單 -> 並發
	* 加只有一個廚師一次只能做一道菜 -> 並發但不並行
	* 加同時有多個廚師分工做菜 -> 並發且並行

此外並發可能導致不確定的結果(因為時序的錯置)
但並行不會導致不確定的結果

位元級並行
e.g., 32 bit 

指令級並行
e.g., Instruction pipeline

數據級並行
SIMD

任務級並行
Multi-core processor

## 第二章 線程與鎖

### 案例學習
特色：簡單粗暴

> 註：在產品上應該操作像是 std::thread 之類已經包裝過驗證過的線程服務，不應該直接使用 pthread 之類底層的服務。

注意以下特性
1. 共享內存。
2. 亂序執行
3. 線程 A 對內存的修改對於線程 B 可能是不可見的。
	* (未同步前不保證線程間內存可見性)
4. 效能與同步頻率成反比

不同的上鎖方式也會導致效能的大幅區別

哲學家問題

簡單的 pseudo code
```=c
left.lock()
right.lock()
eat()
left.unlock()
right.unlock()
```
以上寫法可能造成 deadlock

can we do better?

```=c
left.lock() or right.lock()
another.lock()
eat()
left.unlock()
right.unlock()
```
但這樣的效率可能不好，有可能只有一個人在 eat() 的時候其他人都拿著一枝筷子在發呆

can we do better?

```=c
table.lock()
try {
    while(left == eat ||  right == eat) {
        table.await()
    }
    left = eat;
    right = eat;
} finally{ table.unlock() }
```

await 時會暫時釋放鎖，直到有 signal 喚醒，這樣可以保證只要左右都沒在 eat 的情況下該哲學家必可以 eat

後面講 thread pool

用生產者消費者題目，計算詞彙出現頻率

1. 一個生產者分配成多個生產者 (解析的效能提昇)
2. 多個消費者用鎖來寫入單一 map (大量的同步導致效能下降)
3. 多個消費者使用 lock striping 的單一 map (統計的效能提昇)
4. 多個消費者各自使用 map 並在最後合併 (統計的效能再提昇)

### 總結

#### 優點

* 應用廣泛
* 正確使用時效率高
* 各語言支援度高

#### 缺點

* 並非直接支援並行
* 無助於分佈式的模型
* 可維護性低
* 難以除錯

## 第三章 函數式編程

> Clojure 我一下子真的看不是很懂，效率起見，先跳過

## 第四章 分離標誌與狀態

> 本章為上一章的延伸，一樣跳過

## 第五章 Actor

> 有點類似 message queue + thread pool + 封裝的概念la (對 trevi 的人來說就是 fiber 啦)

這個函數式語言我比較看得懂了，以下實驗紀錄

對函數式語言來說函數是第一類的物件-可以綁定到變數、作為函數參數、與數據沒有分別

e.g.,
```=clojure
> double = &(&1*2)
> twice = fn(fun) -> fn(x) -> fun.(fun.(x)) end end
> twice.(double).(3)
12
```

以下是轉換為 C++ 的對應寫法

```=c
#include <iostream>
#include <functional>
using namespace std;

int mut(int x) {
    return 2*x;
}

int twice(function<int(int)> func,int a) {
    return func(func(a));
}

int main() {
    using namespace std::placeholders;
    //auto funcObj = &twice;
    cout << mut(2) <<endl;
    cout << twice(bind(&mut,_1),2) <<endl;
    // print 8
    return 0;
}
```

但這個綁定 int 了，挑戰一下能不能用 template 解決

```=c
template <class T> T twice(std::function<T(T)> func, T b) {
    return func(func(b));
}
```

發現好像不行，因為 std::function 本身其實也是 template ，這樣我等於在 template 定義了用 template 當參數，這樣編譯器似乎沒辦法生成對應的函式。

> 現在才驚覺 `#include <functional>` 裡面的功能就是在模擬 functional programming，也所以 lambda 的宣告方式回傳的是 std::function 的 obj

Actor 之間互相用非同步調用的方式通訊，通訊時傳入自己的 pid ，這樣對方就知道 response 的時候要打到哪個 Actor 去。

也可由此得知 Actor 之間的連接是雙向的

Actor 內部自己維護一個 message queue ，用串行的方式處理 queue 內的訊息，再用異步的方式回應到對方的 message queue

由於每個 Actor 各自只負責一個模塊，通過訊息溝通，所以也沒有內存同步的問題。

### 錯誤處理

如果 Actor 崩潰導致預期的回應沒有送達對方的信箱怎麼辦

此語言定義兩個原則
1. 如果沒異常，回應一定會送到
2. 如果有異常，異常訊息一定會被送到

由上往下讓每個 Actor 都有對應的 daemon 管理，如果崩潰則通知其使用者。

daemon 本身崩潰的話上層的管理者也會發現，這樣除了 root 以外的崩潰都會收到異常訊息。

這是 error-Kernel mode
 
哲學 -> 我們不能阻止所有崩潰 -> 任其崩潰 -> 在管理下的崩潰即可


> 以下是自我思考
如果要實現一個有優先度的 message queue ，可以嘗試按照優先度做 hash ，而不是全部排序在同一個 queue 內，效率會好很多。(建立在優先度沒有分太多的情況下)
>
> 如果優先度真的分很多的話可以考慮改用 map (RB tree) ，因為是排序過的，所以只要從頭開始掃就好，內建滿足按照優先度排的需求。

一樣是統計詞彙頻率

拆成 解析器 -> 計數器 -> 累加器

解析器維護一個 message queue ，自己把本地的檔案加到 message queue 內並執行，解析完成之後把文本傳給後面的計數器，並把這個檔案重新加到 message queue 內(這樣如果這次通訊是失敗的，那後面就會自動重試)

只有在累加器確認該文本已經計數並累加完畢之後，再通知解析器把該文本從 message queue 內刪掉。

優點：分佈式的計數器可以崩潰沒關係，只要 daemon 能正常的重啟它就以不斷繼續運行。

缺點：累加器跟解析器的狀態必須同步，在沒有這部份處理的情況下這兩個是不能崩潰的。

## 第六章 CSP

> 怎麼又是 Clojure =_=，就不能是 go 嗎QAQ

CSP 相較於 Actor 的差別是 CSP 注重在通道本身上的操作上， Channel 本身是可以轉移的，變成把 chaneel 本身也當成第一類的物件。
channel 可以開啟或關閉，對於一個關閉的 channel 寫入會直接被丟棄，只能取出內部的值。
取完了的話會回傳 nil ，故將 nil 塞進 channel 是非法的。

Channel 本身是一個 thread safe 的 Queue，並且分為幾種設計。

1. no buffer 
2. slidding buffer
3. droping buffer

對於 no buffer 的寫入會 blocking ， droping buffer 的話則是丟掉新的， slidding buffer 則是會移除最舊的。

:::info
為什麼沒有容量自動擴展的 channel ？
因為就算容量會自動擴展，但實際上還是會有其上限，而且其上限會成為 undefine behavior。
使用者應該一開始就想好緩存塞滿了該怎麼辦，避免製造出隱藏的 bug 。
:::

### thread pool 的缺陷解決方案

當涉及 blocking 的操作時 thread pool 反而可能造成整體系統的崩潰。
一旦 thread 出現 block 將有可能無窮的被佔用。

其一的作法是改為事件驅動的寫法，在這裡 go module 提供了一個狀態機形式的方案。(控制反轉)
它以對 channel 的操作作為分界點，將程式碼的行為切割為一種狀態，只要保存下狀態，這個狀態就可以在任何的 thread 上還原，來解讀一下以下代碼。

```=Clojure
(go
  (let [x (<! ch)
        y (<! ch)]
    (println "sum" (+ x y))))
```

首先會停在 `x (<! ch)` 的部份，直到 channel 內有值可以讀取為止。
注意這個停止並不是 blocking ，而是保存下當前狀態然後直接將這個 thread 讓出給別人執行。

當有值可以讀取之後將狀態機還原在任何一個閒置的 thread 上，然後讀取，然後再停止直到有值可以讀取為止。

由於這樣的作法不會佔用線程資源，所以成本相對低很多，而能夠不在意資源不斷新增並發的任務有相當革命性的意義。

所以各個 module 的傳遞不是靠 lock 之類的而是靠 channel 的寫入跟讀取，一樣以統計詞彙為例：


輪詢 api * n -> 解析連結 * n -> 紀錄已統計連結 -> 統計詞數 * n -> 合併結果 

中間解析完連結之後就可以直接詢問 `紀錄已統計連結` 有沒有存在該連結，沒有存在則繼續往下。
合併完結果在嘗試把以統計連結更新(不過這樣的寫法有點脆弱，已統計連結會不斷增加直到爆掉為止)

### 優點
1. 閒置的 module 不會佔用線程。
2. 各 module 可以透過 thread safe 的 channel 交互，比起要 link 才能交互的 actor 更靈活。
3. 一個 module 甚至可以監聽兩個以上的 channel 。
4. 透過 channel 來取代 callback 可以讓程式更加清晰高效。
5. 透過控制反轉的原理，甚至可以在瀏覽器上用 Js 模擬並發的行為。

> 註：瀏覽器上的 Js 是單線程的，不支援並行，但這不影響並發。且通過 Web Worker 現代的瀏覽器已經某種程度上支援多線程了。

### 缺點
1. 由於各個 module 並不像 Actor 真的建立了雙向的連接，所以不確定性是存在的。
2. 此外 channel 用的不好的話 deadlock 也有可能發生。
3. SCP 相較於 Actor 還缺少全套 daemon 的機制，所以對分佈式跟容錯性的支持較差。

本書總結如下： Actor 注重容錯性及分佈式的架構， CSP 注重效能以及整體流程的簡潔，兩者依使用情境而定。

:::info
有一部份我覺得還是按照寫程式的方式而定吧，在前兩章的案例中 Actor 也沒辦法做到完全 stateless， CSP 也有做到部份的 stateless ，這部份就可以拆成分佈式，所以總歸還是看寫的人怎麼寫。
:::

## 第七章 SIMD

並行的進行獨立運算

此處以 OpenCL 為例

例如 A 陣列 + B 陣列
`result[i] = A[i] + B[i]` 本身是獨立運算
該運算本身被稱為 kernel ，屬於一個物件
需要先把一個 test.cl 讀入，`clBuildProgram` 編成物件
然後傳入運算本身，運算次數，緩存大小之類的給 command queue

由於 buffer 都是 Clike 的(支援 vla)，所以取得不同平台預設長度的行為變成透過不輸入參數呼叫同一個 function 來取得該 function 的該平台參數。

此外 OpenCL 不支援一維以上的陣列，要自己計算偏移來模擬二維行為。

此外 OpenCL 也支援 CPU 加速，內部有整合 SSE 或是 AVX 之類的實作

支援 barrier 的使用，在類似折疊運算的技巧上很常用到。

## 第八章 Lambda 架構

Functional programming + MapReduce + SIMD

Hadoop 對文件切分交給 Mapper
Mapper 負責將輸入對應到 key
Reducer 負責將 pair 轉換成最終輸出

Hadoop 保證 consistent hash ，相同的 pair 一定會被交給相同的 Reducer 處理

這是一個比較大的架構，需要在 Aws 上實作，故此處只紀錄大概方向

幾個要點

1. 讓所有原始數據唯讀
	* 這樣可以避免 race condition，有寫入需求時就另外寫一筆附加資料進去
	* 需要統計時再統計所有的原始資料+附加資料
2. 寫入讀取分離(批處理層)
	* 將寫入區和讀取區獨立開來，讀取區為固定的 const data，每次操作都只是添加在寫入層之上，過一陣子之後在透過批處理將寫入層的資料一次更新到讀取層，由於寫入層的都只是獨立操作，所以可以用並行運算快速處理完成。
3. 異步調用
	* 異步的使用 message 處理 client 端的事件
4. 加速層
	* 寫入讀取分離的一種解決方案，針對秒級應用維護一個加速層，加速層在批處理區間維護最新的狀態，並且在批處理完畢後同步並切換，加速層採取無限增量的策略，每次操作都增加在源數據之上，直到批處理完成之後加速層馬上廢棄所有當前狀態，以下舉例

批處理層 A = 10
加速層 A+2, A+3, A+9, A-3, A+1, A+5...
不斷疊加上去，取用的時候就取用批處理 + 加速全部的運算結果(可並行，因為每次都是獨立操作)來使用
一旦批處理層更新完畢，就會變成這樣
批處理層 A = 27
加速層 null

按照批處理的速度不同，可能會需要 N 個加速層交替使用。

### 優點
1. 架構級的解決方案，有處理大數據的能力
2. 非常適合產生報表，統計分析
3. 在分散式的架構下具有高容錯性

### 缺點
1. 成本高，硬體軟體的成本都高
2. 架構級的解決方案，對於較為細小的問題沒有幫助