前言

本篇是略讀「Multithreaded JavaScript」這本書第六章：「多執行緒實作模式」（Multithreaded Patterns），整理的一些筆記

本章節介紹了一些多執行緒常見的實作模式，有以下：

  1. 執行緒池（Thread Pool）
  2. 互斥鎖（Mutex）
  3. 環形緩衝（Ring Buffers）
  4. 演員模型（Actor Model）

執行緒池（Thread Pool）

  • 多執行緒應用程式很常使用的一個實作方式
  • 執行緒池是一個集合，裡面含有同質性（homogeneous）的 worker 執行緒，每個 worker 都可用來處理重負載、複雜運算的工作
  • Node.js 的 libuv 函式庫提供了執行緒池的功能，預設為四個執行緒，可以處理底層 I/O 的一些操作
  • 概念很類似分散式系統
  • 分為兩部分討論：執行緒池的大小（Pool Size）與委派策略（Dispatch Strategies）

執行緒池的大小（Pool Size）

  • 一般而言不會動態改變執行緒池的大小
  • 通常在作業系統中，處理器核心跟執行緒並沒有直接的關聯
  • 當執行緒的數量遠超過處理器核心數量時，效能反而會下降
  • 以 Node.js 的 libuv 函式庫為例，裡面包含三個執行緒，分別是：主執行緒、worker 執行緒、垃圾回收執行緒（Garbage Collection Thread）

查看核心數量

// browser
cores = navigator.hardwareConcurrency;

// Node.js
cores = require("os").cpus().length;

決定執行緒池的大小

  • 別忘了還有主執行緒，所以是 n + 1
  • 依據不同的目的來決定執行緒的數量
    • 對於挖礦而言，99.9% 的工作在於 worker 上所執行繁重的運算，幾乎沒有 I/O，主執行緒也沒有特別的事情，因此可以開與核心數量相同的 worker 執行緒
    • 對串流影音或轉檔而言，則有大量的 CPU 運算及 I/O 操作，因此必須預留兩個核心給這兩個程序，剩下再分配給 worker 執行緒
  • 如果不確定要如何分配，那麼留一個核心給主執行緒是一個安全的作法

委派策略（Dispatch Strategies）

我們將高成本、繁重的運算收集整理起來，然後分配個 worker 執行緒去執行這些任務，這裡介紹三個常見的委派策略：

輪詢調度（Round Robin）

  • 按照順序指派工作，指派到最後一位，下一次就回到第一位 worker 身上
  • 可以確保每位 worker 都有事做
  • 可能造成每位 worker 的負擔不均
  • HAProxy 稱此委派策略為 roundrobin

隨機調度（Random）

  • 就如字面的意思，隨機選取一個 worker 來處理工作
  • 可能造成每位 worker 的負擔不均

閒置優先調度（Least Busy）

  • 將新的任務指派給負載最低的 worker
  • 當有最低負載的 worker 有兩個的時候，隨機選取一個指派
  • HAProxy 稱此委派策略為 leastconn

互斥鎖（Mutex）

  • Mutex 全名為 mutually exclusive lock.
  • 互斥鎖是一個存取共享資料的控制機制
  • 此機制確保共享資料在同一時間，只允許一項任務執行
  • 互斥鎖在有人存取共享資料的時候上鎖，並在結束後解鎖
  • 在上鎖及釋放鎖定之間，稱之為「臨界區段」（Critical Section）

串流資料與環形緩衝（Ring Buffers）

  • 環形緩衝是「先進先出」（first-in-first-out, aka FIFO）佇列的典型實作，利用一組「配對指標」指向當下的記憶體位址
  • 當佇列的指標在陣列末位，下一步會移動到陣列首位，形成環形結構的概念
  • 在北美餐廳中常被使用的點餐圓盤（order wheel）則是類比世界中，同樣的概念實踐

構成要素

  • head 指標：指向下一個寫入佇列的位置
  • tail 指標：指向下一個讀取佇列的位置
  • 佇列長度：我們想要建立多大的佇列，一個陣列長度，head 指標、tail 指標會在上面移動

運作規則

借用一下書中的示意圖：

ring buffer

  • 當寫入佇列時，head 指標移動的下一個位置
  • 當讀取佇列時，tail 指標移動的下一個位置
  • 當指標位在佇列末位，下一次就會移到首位
  • 因為是環形，所以沒有頭尾之分，因此指標在哪個位置並不重要
  • tail 指標最多只會跟 head 指標在同一個位置，不能超過 head 指標
  • 緩衝區滿載的時候，若要再寫入佇列，則有兩種策略：
    • 覆蓋最舊的佇列：相較於未處理的舊資料，新資料比較重要
    • 拋出異常，且不寫入佇列：資料順序性很重要的時候
  • 必須正確讀出最舊佇列

FIFO、LIFO、動態佇列

  • 儲存在環形緩衝裡的每個元素不會做移動，只有加入與移除，適合實作「先進先出」（first-in-first-out, aka FIFO）佇列
  • 「非環形緩衝」若要實作 FIFO，則必須在處理完一個任務之後，移動佇列上所有的元素
  • 「非環形緩衝」較適合實作「後進先出」（last-in-first-out, aka LIFO）佇列
  • JavaScript 的堆疊（stack）就是 LIFO 的實作
  • 動態改變佇列的大小，意味著必須重新賦予記憶體，會影響效能。若要實作動態佇列，鍊表（linked list）則較為適合

演員模型（Actor Model）

  • 演員模型是實踐同步運算的一種程式設計模式
  • 一個 actor 代表一個執行程式碼的容器
  • 在 Erlang 程式語言中，actor 是一級公民，但在 JavaScript 中也可以模擬其實作
  • 每個 actor 皆具有三種功能：執行運算、建立新的 actor、actor 之間的相互傳遞訊息
  • 每個 actor 擁有自己的訊息佇列（message queue），以 FIFO 佇列順序處理每個任務
  • 因為 actor 都無法操作共享記憶體（shared memory），因此避免了多執行緒容易發生的情況：race condition 及 deadlock
  • actor 是單執行緒，一次執行一件事
  • 使用 actor 的系統必須能夠接受延遲或順序不一致的現象
  • 每個 actor 可以擁有一個位址，例如：tcp://127.0.0.1:1234/3 代表著在 1234 port 中，第三個 actor

借用一下書中的示意圖：

actor model

參考資料