# Chap. 04 - Multithreaded programming

> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

**Note:** [#Thread](#Q-請說明-process-與-thread-的差異-)
## Content

* [Threaded introduction](#Threaded-introduction)
* [1. Advantage](#1-Advantage)
* [2. Multicore programming](#2-Multicore-programming)
* [3. User v.s. kernel threads](#3-User-vs-kernel-threads)
* [Multithreadeding models](#Multithreadeding-models)
* [1. Many-to-one](#1-Many-to-one)
* [2. One-to-one](#2-One-to-one)
* [3. Many-to-many](#3-Many-to-many)
* [Threaded case study](#Threaded-case-study)
* [1. Thread libraries](#1-Thread-libraries)
* [1.1 Pthreads](#11-Pthreads)
* [1.2 Java threads](#12-Java-threads)
* [1.3 Linux threads](#13-Linux-threads)
* [Threading issues](#Threading-issues)
* [1. `fork()` and `exec()`](#1-fork-and-exec)
* [2. Thread cancellation](#2-Thread-cancellation)
* [3. Signal handling(暫略)](#3-Signal-handling暫略)
* [4. Thread pools](#4-Thread-pools)

## Threaded introduction

Thread(執行緒)是 **process 的子集**，是一種**輕量的簡化版 process**，也是**使用 CPU 核心的基本單位**。每個 thread 可分為兩個部分組成

(1) Sharing
屬於同一個 process 的所有 threads 會共享以下的資源

* Code section
* Data section
* OS resource(e.g., open files and signals)

(2) Independency
每個 threads 也同時有屬於自己的以下內容

* Thread ID
* Prorgam counter
* 代表每個 thread 執行的位址都不同
* Register set
* Stack


常見使用到 threads 的場境，例如網路瀏覽器(web browser)，當我們在開網頁的過程中，不同區塊的文字、圖片先後出現，就是使用 multi-threaded 進行下載的。

> [!Tip] **Interview Ques.**
> ##### Q: 請說明 process 與 thread 的差異 ?
> Process 是載入到記憶體中開始執行的程式。而 thread 是 process 的子集，可以視為一種更輕量化的 process。它是真正使用 CPU 核心的基本單位。一個 process 中的多個 thread 會共享某些資源(Ex. code/data/resource)也會有某些獨立的內容(Ex. PC/thread ID/...)

### 1. Advantage

(1) Responsiveness
Process 在執行的過程中，即使某個 thread 被**阻擋(block)或執行時間過長**，整個 process 的**其他 threads 仍然可以==繼續執行==**，不受影響。例如 GUI 中背景程式在下載資料，但前端依然可以進行操作與其他作業。

(2) Recource sharing
因為 thread 會共享部分的空間與資源，所以能夠增加溝通效率(透過 OS 溝通速度太慢)。

(3) Utilization of multi-programming architecture
多個 threads 能夠在不同的 processor 中同步平行執行。

(4) Economy

如下圖所示，`fork()` 是創建 process 的 API，`pthread_create()` 是創建 thread 的 API。在不同的處理器中，thread 的速度會比 process 快上 15-30 倍。


### 2. Multicore programming

從 software 的角度來看，multi-threaded programming 提供**更有效使用多核心(multiple core)的機制**，並且提供了**同步(concurrency)執行**的功能。OS 扮演的角色重點在於**如何把 thread 與 multi-core 做結合**。


但同時 multi-core programming 也會遇到一些困難與挑戰

* Dividing activities：如何**將 program 拆解成多個任務(task)**
* Data splitting：除了 program 要做分解，**data 也必須分給不同的 task**
* Data dependency：某些**資料是無法做分割**的，需要做**同步化**的處理
* Balance：確保能夠**適當的分配任務給每個核心**，避免過載或閒置(idle)
* Testing and dubugging

### 3. User v.s. kernel threads

Thread 在使用上還會再細分為兩種: (1) user threads 與 (2) kernel threads

(1) User threads：由使用者自行管理的 threads
由 **thread library 提供 API** 給使用者，讓使用者能夠**自行創建、排程與刪除** threads，因為只涉及到 user level，不會接觸到 system call，所以速度較快，常見的 user thread library 如下：

* POSIX Pthreads
* Win32 threads
* JAVA threads

但實際上 thread 在執行任務時 OS **還是會將其中 user thread 連結到某一個 kernel thread 上執行**。所以若是只有單一個 kernel thread，則當某個 user thread 被阻擋(block)時，整個 process 都會停止運作。

(2) Kernel threads：由 **OS 支援管理**的 threads
Kernel thread 是**真正意義上使用 CPU 核心的基本單位**，因為涉及到 system call，所以執行速度比 user thread 慢。此外 kernel thread 是獨立執行，所以當某個 kernel thread 被阻擋(block)時，其他 kernel thread 仍然可以運作。常見的 kernel threads 如下：

* Windows 2000
* Solaris
* Linux

## Multithreadeding models

如上所述，OS 會將 user thread 連結到某一個 kernel thread 執行，連結的方式有以下三種：

* Many-to-one：多個 user threads 使用一個 kernel thread
* One-to-one(常見)：一個 user thread 對應一個 kernel thread 使用
* Many-to-many：多個 user threads 使用多個 kernel threads


### 1. Many-to-one

* 優點
* 因為只有一個 kernel thread，所以 threads 的管理只要在 user space 進行就好，效率高
* 缺點
* 若有一個 process 被阻擋(block)，則整個 process 都會停止
* 不利於 multi-processors 的平行化

### 2. One-to-one

* 優點
* 能夠同時進行多個 threads 的使用(平行化)
* 缺點
* 效能受 kernel threads 的數量限制
* 容易過載(overhead)，因為每創建一個 thread 都必須創建對應的 kernel threads

### 3. Many-to-many

* 優點
* 平行化運算
* 當某個 thread 被阻擋(block)時，可以透過排程(schedule)的方式使用其他的 thread

## Threaded case study

:::info
**Shared-memory programming**
Process communicate or work together with each other through a shared memory space which can be accessed by all processes.

Thread programming 共享資源的方式是使用 shared-memory(另一種是 message passing)

* 優點：更快、更有效率
* 缺點
* 同步化(synchronization)問題
* Deadlock
* Cache coherence

<img src="https://hackmd.io/_uploads/rJOEA58wkl.png" width=500>
:::

### 1. Thread libraries

#### 1.1 Pthreads

:::info
**What is Pthread ?**

Pthread 是一個遵循 POSIX 協議的函式庫，裡面有多種函式來實現 POSIX 協議所定義的功能。雖然 OS 不同，但只要符合 POSIX 協議則上層的 API 都相同，不用重新 recompile 就可以在不同 OS 執行。
:::

幾個常用的 Pthread 函式介紹如下：

* Pthread creation: `pthread_create(thread, attr, routine, arg)`
* 用來**創建**一個新的 thread 並**指定**它要完成的工作
* `thread`：一個**唯一的 thread ID**，提供給新的建立的 thread 使用
* `thread` 參數其實是一個**指標(pointer)**，用來控制 thread 的後續行為
* 會**先: (1)創建**一塊用來存放 thread 的記憶體空間並 (2)用**指標指向**該區域，創建後 (3) 再把 thread **塞進指向的空間**位址
* `attr`：設定 thread 的屬性，預設是 `NULL`
* `routine`：thread 被建立後將會**執行的例行公事(函式)**
* 事實上 routine 就是一個 thread **之後會執行的函式**
* Thread 被**建立後執行的動作**其實就是 **==function call==**
* `arg`：要傳給 routine 的參數
* Pthread join: `pthread_join(threadID, status)`
* 用來**等待指定的 thread(`threadID`) 完成**
* 當呼叫 `pthread_join()` 時會將 main processs 阻擋(block)直到 thread 執行完成，是做到**同步化**的其中一種方式
* `status` 用於**接收指定的 thread 的回傳值**
* Pthread detaching: `pthread_detach(threadID)`
* 用來將指定的 thread(`threadID`) 設定為**分離狀態**，被分離後的 thread **不會被其他 process/thread 等待或接收**
* 指定的 thread(`threadID`) 完成後會**自動釋放資源**

如下圖所示，使用 `pthread_create` 後會傳入一個記憶體位址 `&thread1` 用來存放被建立的 thread。而 thread 的工作其實就是執行一個 function call，執行完後再將結果回傳至 `pthread_join()`


完整的 thread programming model 如下。一開始的 master 是不平行運算，當呼叫了 `pthread_join()` 後會產生兩個 thread 開始同步執行，且 master thread 因為呼叫 `pthread_join()` 的關係會暫停執行，直到兩個 threads 執行結束回傳後 master thread 再繼續進行。


#### 1.2 Java threads

因為有 virtual machine 的關係，所以可以在不同的 OS 上執行

#### 1.3 Linux threads

Linux threads 是屬於核心層級的執行緒(kernel thread)。而 Pthread 是遵守 POSIX 協定的使用者層級的執行緒(user thread)。Pthread 提供了一些 API 讓使用者能夠間接的使用 kernel thread。

事實上在 **Linux kernel 中並==沒有區分== process 與 thread 的概念**(i.e., process=thread)。在 Linux kernal 中，執行緒(thread)可以視為一種特殊的 process，會共享記憶體空間與部分資源。所以對 Linux 來說，thread 的概念其實是透過共享資源 process 來執行。在 Linux 中同樣可以使用 Pthread 來建立與管理 thread 的使用。

* `fork()` system call
* 複製 parent process 的記憶體空間並建立一個完全獨立的 new process
* `clone()` system call
* 建立一個 new process 以及與 parent process 的連結，不完全是獨立的

從上述兩個 Linux 提供的 system call 可以看到 Linux 提供了一個更靈活的 system call 來共享 processes 之間的部分資源，模擬 thread 的行為

> [!Note]
OS 在執行 process 時會主動為該 process 建立(至少)一個主執行緒(main thread)，因為 thread 才是使用 CPU 的基本單位。如果程式中沒有刻意調動使用 thread 的 API，則**所有工作都會由 main thread 完成**

## Threading issues

### 1. fork() and exec()

> Does `fork()` duplicate only the calling thread or all thread when a particular thread call `fork()` ?

部分的 Unix-like system 支援兩種運算

* 複製完整的資料
* 只複製呼叫的 thread


### 2. Thread cancellation

> What happen if a thread reterminates before it has completed ?

兩種取消 thread 的方式

* Asynchronous cancellation：強制停止目標執行緒，但可能造成**資源未正確釋放**
* Deferred cancellation：定期檢查目標執行緒是否該終止，並在**正確釋放資源**後才會終止目標執行緒

### 3. Signal handling(暫略)

### 4. Thread pools

前面所介紹關於 thread 的使用都是在 run time 期間產生，之後再刪除。但實作上常用 **thread pools** 的方式，在一開始就**產生一堆的 threads**，有需要時再從 thread pool 中提取，使用完後再釋放回 thread pools。

* 優點：速度稍快，因為不用頻繁的建立與刪除
* 缺點：thread 的數量受限於 pool size

:::info
可建立的 thread 的數量與 CPU 數量、要求(request)的次數與 physical memory 的大小有關
:::