作業系統 - 學習筆記 (3) Multi-programming

本文介紹作業系統 Multi-programming 的概念。

Multi-programming

並發 (Concurrent)

  • 利用排程建立班表,使多個 Process 快速切換、處理 (e.g. A 先做 1 秒、B 做 2 秒、C 做 1 秒……),感覺好像同時處理很多事情
  • 單核心的實現方式只有一個執行緒

平行、並行 (Parallelism)

  • 真的可以同時進行多個 Process
  • 多核心才能做、單核心不能做
  • 兩個以上的執行緒

舉例說明

  • 假設有 150 份 15 題的考卷,由 3 個助教來批改
  • Data Parallelism - 每個助教分別改 50 份考卷 (1~15 題)
    • 資料的分割
  • Task Parallelism - 每個助教改 150 考卷,分別改前、中、後 5 題
    • 指令的分割
    • 理論上 Task Parallelism 效率較好,但會有溝通的問題,所以實作上兩者速度會差不多

Thread 的分類

兩種不同階級的 Thread

User Thread

  • 使用者端操作的部分的 thread
  • 在 User 端使用 thread library 產生 thread
  • e.g. Pthread, Win32 Thread, Java Thread

Kernel Thread

  • 提供 OS 服務的 thread
  • 用來處理 OS 各種服務 (e.g. system call, daemon 的使用,以及處理 User Thread)
  • 三種方法:Grand Central Dispatch (GCP), Open MP, Thread Pool

Multi-threading Model

Many-to-One

  • LWP:一個「負責排程」的小 process
  • 最後還是全部分配給一個 Kernel Thread (感覺這個多執行緒有跟沒有一樣)

One-to-One

  • 一個 User Thread 各給一個專屬的 Kernel Thread
  • 例如:Java 產生兩個 Thread,分別經過兩個 LWP,各自分配一個 Kernel Thread 去執行
  • 這個一對一看似很美好,但是它一定要有一個機制去限制使用者產生的執行緒的數量!

    因為不論是 User 還是 Kernel Thread,它的記憶體都是有限的,若不斷的生出一堆 User Thread,每個都還要再分配給一個 Kernel Thread,作業系統會受不了,會被榨乾的!

    因此衍生出另外一種比較折衷的方式 …

Many-to-Many

  • 顧名思義:多個連多個
  • 限制 Kernel Thread 的數量,讓無限多個 User Thread 去使用有限多個 Kernel Thread
  • Kernel Thread 可能會爆掉,OS 可能被榨乾,所以改為只能產生有限的 Kernel Thread 的數量,而可以產生無限個 User Thread
    • 因此會產生三個 User Thread 共用兩個 Kernel Thread 的狀況,同時又有另一個 User Thread 使用另一個 Kernel Thread 的一對一的狀況

Thread Pool

游泳池 = Swimming Pool
水餃池 = Dumpling Pool
執行緒池 = Thread Pool

  • 有工作時,thread pool 會彈出一個 thread 分派給 task 去執行
  • 完成之後小蝌蚪會再回到 thread pool 待命,等待下一個工作

Q:如果所有 thread 都在工作呢?
A:task 先放到 Ready Queue 裡面等待,等到有 thread 遞補回來的時候才使用

Grand Central Dispatch (GCP)

  • 將一個一個工作包裹成 Block (小積木),放在 Dispatch Queue 裡面,再丟到 Thread Pool 去處理
  • 跟 Thread Pool 根本 87% 像,只是包裝成 Block 跟換個格式而已
  • 蘋果電腦執行的方式 (果然尊爵不凡)

OpenMP

  • 跨平台
  • 主執行緒用 fork() 產生一系列的子執行緒,結束後子執行緒用 join() 併回去主 thread,之後有需要的話再 fork(),做完再 join()…

Signal (訊號)

  • 像是一種給 Thread 聽的 System Call
  • User > user-defined signal > 自己寫程式產生 Signal
  • Kernel > default signal > Kernel 預設的 Signal
  • 可傳給特定的 Thread、所有的 Thread,或者傳給一些或任一 Thread

補充一個網路上看到的問題

  • Q:兩個 Thread 進行 Context Switch 的時間是不是會比兩個 Process 進行 Context Switch 的時間短呢?為什麼?
  • A:是的。因為 Process 的轉換需要的是一種記憶體空間的轉換,很花費時間;而 Thread 轉換時仍然處於同一個 Process,因此需要調度的東西比 Process 少很多,也就有效率很多了
    • 也是因為這樣大部份多工的程式 (e.g. 拼音檢查) 會使用 threading 來實作,而不是 multi-process

以上資源是我自己整理過後的筆記,若有錯誤歡迎隨時和我聯繫