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

## 第一章 並行與並發

* 並發是同一時間應對(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

left.lock()
right.lock()
eat()
left.unlock()
right.unlock()

以上寫法可能造成 deadlock

can we do better?

left.lock() or right.lock()
another.lock()
eat()
left.unlock()
right.unlock()

但這樣的效率可能不好，有可能只有一個人在 eat() 的時候其他人都拿著一枝筷子在發呆

can we do better?

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.,

> double = &(&1*2)
> twice = fn(fun) -> fn(x) -> fun.(fun.(x)) end end
> twice.(double).(3)
12

以下是轉換為 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 解決

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 上還原，來解讀一下以下代碼。

(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. 架構級的解決方案，對於較為細小的問題沒有幫助