iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
2
Software Development

30天之從 0 至 1 盡可能的建立一個好的系統 (性能基礎篇)系列 第 4

30-04 之應用層的運算加速 - 並行運算

黑色好看版 - 傳送門


https://ithelp.ithome.com.tw/upload/images/20190918/20089358YWcXuY0jDd.png

正文開始

假設你已經將你的演算法進行了優化,但是這時發現,這一項演算法工作還是需要花到非常多的時間處理,那要怎麼辦呢 ?

假設你所在的機器是多核心 CPU,那這時的確是有解,那就是本篇文章的主題 :

開啟 Process 或 Thread 來幫忙進行運算。

本篇文章就分為以下三個章節:

  • CPU 運算與 process、thread 的關係。
  • CPU 密集任務處理。
  • 多線程並行處理的淺在問題。

CPU 運算與 Process、Thread 的關係


在實際上理解如何開啟 process 或 thread 前,咱們先從最基本的東西說起。

何謂 process ? 何謂 thread 呢 ?

進程、行程 ( Process )

首先咱們先來看看 process,基本上在你的電腦中每一個應用 ( ex. line、chrome ) 都是至少是一個 process,然後比較重要的一點在於 :

對作業系統來說,它是資源分配的最小單位,並且同時是個『操作單位』

在 linux 系統上,一個 process 的建立過程如下圖 1 所示 :

  1. 母進程執行 fork() 建立一個子進程。
  2. 同時間建立子進程的記憶體空間。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358GhOjRynzUz.png
圖 1 : 作業系統建立進程的概念圖

而上面說的資源分配就是指上面步驟 2 分配記憶體空間。然後這個子進程之後工作時,需用到的記憶體,就是那從那一堆子進程記憶體空間來分配。

~ 小備註 ~

在 linux 中不是只有 fork 可以建立一個 process,還有所謂的 vfork 與 clone 這兩種,感興趣的可以去理解一下這幾個差別。這裡就只是淺淺的談談。

Process 在進行運算時的情況

然後接下來咱們來看一下,process 在處理工作時,以作業系統的角度來看,它是如何的運作。

咱們假設運行在以下的機器設備上 :

  • 一個邏輯 CPU。
  • 有二個 process A 與 B 在工作。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358ghl4OIcWmC.png
圖 2 : 作業系統工作原理

那基本上它運行的過程會如上圖 2 所示,一下 A process、一下 B process,因為只有一個 cpu,然後每一次要轉換工作時,都需要進行所謂的『 上下文切換 ( context switch ) 』,它是由作業系統的核心 ( kerneal ) 來處理這工作。

上下文切換這個工作基本上,就是將正在處理進程 A 的資訊記錄起來,然後再讀取進程 B 之前做到那裡資訊,這樣才能在重新開始進行進程 B 的工作。

~ 小知識 ~

正常情況下,邏輯 cpu = 物理 cpu 個數 X cpu 核數 ( 先別管超線程 )。然後有幾個邏輯 cpu 就代表『 同一個 』時間可以開幾條生產線來工作。

那什麼時後會 Process 的工作轉換呢 ?

  • 時間片段結束
  • process 自已主動或被動睡著。
  • 某一些 system call。

每一個 process 所能分配到 cpu 的時間片段基本都相同,不過也是可以使用 nice 這種作業系統提供的方法來調整進程的優先權,也就是讓某一個進程比較容易被分配到 cpu 來進行工作。

在來說說這個睡著這個,咱們在寫程式碼不是有時會執行 sleep 還啥的嗎,這就是主動睡,而被動通常是出了什麼事,例如硬體或軟體怎麼了,作業系統強制中斷。

然後另一個東西是 system call。它是什麼呢 ?

這就要來理解一些作業系統,下面這張圖代表這,當在一個 process 裡面,有段程式碼,需要執行網路存取,那它的運行流程就如下 :

  1. 進程執行網路存取程式碼 ( ex. http 請求 )。
  2. 呼叫 os 外函式庫。
  3. 呼叫 os 函式庫。
  4. kernel 核心
  5. 硬體 ( ex. 網卡 )

其中 3 至 4 的操作就是謂的的 system call。

所以假設發出來一個 http 請求,那會如下圖 3 那樣運行 :

https://ithelp.ithome.com.tw/upload/images/20190919/20089358u8myUHrcK8.png
圖 3 : 一個請求的操作流程

這裡簡單說明一下,上下文切換事實上分的很細,如果某個 system call 就只是轉成 kernel 來讓他處理事情的,那這叫特權上下文切換,而如果某個 system call 是要傳送資料這種,那就會進行所謂的進程的上下文切換,就是將 cpu 資源分給其它 process,然後圖 2 的是所謂的『進程的上下文切換』。

~ 小備註 ~
像咱們常常處理的 mysql 操作或 http 請求,底層都是有使用 system call 來去操作網路下的動作,因此在『 某一些情況下 』,它會頻繁的觸發上下文切換,這個在說到 I/O 的文章是會詳談。

線程、執行緒 ( Thread )

在說明完進程 process 以後,接下來我們來說說線程 thread。

它的定義如下 :

對作業系統來說,它是最小的操作單位,且它包含在 process 中。

也就是說,作業系統可以分配 cpu 直接給 thread 來進行工作,然後在同一個 process 中的 thread 都可以共享 process 的記憶體空間。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358vk5pLiZjVx.png
圖 4 : thread 在 process 中的概念

那為什麼會有線程呢 ?

進程 process 與線程 thread 它們都是 cpu 分配的單位,但是為什麼有了 process 還會有 thread 呢 ?

因為 process 太肥了

上面有提到每當 CPU 要從一個進程分配給另一個進程時,需要進行所謂的『上下文切換』,而這個切換所需要做的事情就是將進程資訊記錄起來,而問題就出在進程的上下文切換很耗資源,則也是為什麼會誕生一個,較小的執行單位,因為就可以使切換時所需要記錄的東西就變小囉。

https://ithelp.ithome.com.tw/upload/images/20190919/200893588R8vpEOM9W.png
圖 5 : thread 的運行模式

CPU 密集任務處理


在上面理解完 process 與 thread 的概念以下,接下來我們來說明為什麼開啟它們可以來加速運算,並且進行簡單的示範。

為什麼開啟 process 或 thread 可以加速運算呢 ?

要能加速基本要有以下幾個假設情況下 :

  • 在有多個邏輯 cpu 的情況下。
  • 任務所需的運行是可以拆分的。

首先是一個,要能開啟進程來加速運算第一個條件是有多個邏輯 cpu,上述在說明時有說過,一個進程或線程同一個時間只能有一個邏輯 cpu 來進行運算。

也就是說,當你只有一個邏輯 cpu 時,這也代表你『 不可能同一時間,處理兩件事情 』,它會如下圖 6 所示來處理任務。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358F80Mhks6M0.png
圖 6 : 只有一個 cpu 時的運算情況

而當你有 2 個以上的邏輯 cpu 時才能『 同時間 』處理兩個任務,如下圖 7 所示。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358hUUIZbJL3T.png
圖 7 : 有多個 cpu 時的運算情況

而第二點那就不用說了,如果你的任務不能拆分,那就沒有必要開另一個進程來處理了。

~ 小知識 ~
將一個大問題拆成小問題,是一個並行工作最重要的地方,這個在演算法中也有很多這種類型的題目,有興趣的人可以去研究一下。

Divide-and-conquer Algorithm

順到說一下 DP 類型也算。

~ 小提醒 ~
大部份的語言都可以開多個 thread 來進行並行運算,但是要注意有一些語言不太行,例如 python (cpyton),主要的原因在於有 GIT ( Global Interpreter Lock ) 這東西在,有興趣的友人可以用這個關鍵字去查查。

Nodejs 的並行運算範例

接下來我們將使用 nodejs 來寫個簡單的範例。例範內容如下:

範例 :
給定一串數組陣列,計算出陣列所有加總後的數字

這個範例非常的簡單,並且也是很典型的 cpu 運算,然後這裡我們將要模擬開啟二個 thread 來計算運算,然後在分別將結果加總起來,就是答案。

下面這段是主程式碼。

const { Worker } = require('worker_threads')

// 這一段建立 thread,並且將 workerData 丟給 thread。
function runService(workerData) {
    return new Promise((resolve, reject) => {
      const worker = new Worker('./worker.js', { workerData });
      
      // 監聽有沒有資料從 thread 傳回來。
      worker.on('message', resolve);
    })
  }

// 這裡建立兩個 thread 來並行計算 nums 數組。
// 第一個 thread 負責計算第 0 至 4 個
// 第二個 thread 負責計算第 5 至 8 個
async function run() {
    const nums = [1,3,4,7,8,9,19,11,12];
    const result = await Promise.all([
        runService({
            nums,
            start: 0,
            end: 4 
        }),
        runService({
            nums,
            start: 5,
            end: 8 
        })
    ])
    return result[0] + result[1];
}

(async () => {
    const res = await run();
    console.log(res);
})()

而這一段是負責運算用的 thread 程式碼。


const { workerData, parentPort } = require('worker_threads');
// workerData 為從母進程傳送過來的資料

const nums = workerData.nums;
const start = workerData.start;
const end = workerData.end;

let sum = 0;
for (let i=start; i <= end; i++){
    sum += nums[i];
}

// 將運算結果回傳至母進程。
parentPort.postMessage(sum);

上面這些就是簡單的開啟二個 thread 來分別進行計算,然後在將結果返回。

以這個問題來看是可以不用這方法,不過這只是範例,別太在意。

~ 小知識 ~

nodejs 忘了在幾版以後就有 thread 可以使用了,在比較舊以前的 nodejs 世界只能開 process。然後這裡我用的是 nodejs v12.10.0,不過注意一下它的狀態還是『 Stability: 1 - Experimental 』。

v12.10.0-nodejs-thread

多 Thread 並行處理的問題 - 資源共享競爭


上面有提到,thread 是可以共享 process 的記憶體空間,因此可以所有在裡面的 thread 都可以讀取那個共享的變數,而這在某些情況下,就會發生問題。

最有名的例子下面這段 java 程式碼。

public class System {
    private int count;
    public int getCount(){
       return count++;
    }
}

這一段程式碼有什麼問題呢 ? 假設咱們開 2 個 thread 來執行 getCount,就可能會發生如下圖的問題,明明執行兩次 count++ 但是最後結果卻只有一次。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358N7Z8QiNzA9.png
圖 8 : 並行的問題。

~ 小備註 ~
這裡就是咱們第一個碰到的一致性問題,後面還有一堆這種問題,慢慢看。

解法 1 : 加鎖

在 java 最多人使用的解法就是『 加鎖 』,如下程式碼,它會將這個方法所屬物件給鎖定起來,也就是說在同一個時間,只能一個 thread 來執行這一段。

public synchronized int getCount() {
     return count++;
}

而當使用這個方法時,事實上運行就變成下面這張圖的感覺,因此這也代表,性能被限制住了。

https://ithelp.ithome.com.tw/upload/images/20190919/20089358swAyJ6yOGT.png
圖 9 : 加鎖後的運行圖

解法 2 : 不要用共享資源

有寫過 golang 的友人們應該是有看過下面這一句話。

Do not communicate by sharing memory; instead, share memory by communicating.

這句話是說,不要使用共享記憶體來進行溝通,而是使用溝通來分享資料。上述 nodejs 的範例就是屬於這一種思想方案。

~ 小備註 ~
上網仔細查了以後,基本上發現以這種思想所產生的模式事實上有兩種『 Actor 』與『 CSP 』。像 Java/Scala 的 Akka 庫就是 Actor 實現,而 golang 則是 CSP 的實現,之後會開篇文章來詳細說明。

結論與心得


本篇文章中咱們學習到了應用層的一項運算加速的方法,並行運算,不過要使用這個東西有兩個條件 :

  • 在有多個邏輯 cpu 的情況下。
  • 任務所需的運行是可以拆分的。

同時咱們學詳細的學習了 process 與 thread 這兩個在作業系統中的運算單位。理解它是如何運作與產生,同時在這裡也碰到第一個一致性問題,這個問題只要是在性能與可用這條路上會形影不離的追隨這咱們的。

參考資料



上一篇
30-03 之應用層的運算加速 - 演算法
下一篇
30-05 之應用層的 I / O 加速 - 零拷貝 ( Zero Copy )
系列文
30天之從 0 至 1 盡可能的建立一個好的系統 (性能基礎篇)30

尚未有邦友留言

立即登入留言