# 作業系統 CH4 Multithreaded Programming
###### tags: `作業系統 Operating System`

## Threads
Threads 又稱為 ==`Lightweight process`==，是使用 CPU 的最小單位，同 Process 的 Threads 有共享的記憶體空間。在 Parent Process 創造 Threads 時就會 allocate ，因此省去在空間管理及處理上的執行動作。
- 同 Process 中，Threads 共用以下內容
- code section
- data section (global variable, heap)
- OS resources (e.g. open files and signals)
- 但以下部份各自獨立
- stack
- register set -->
可能 instruction 的執行位置不同，甚至執行不同的 function call
- thread ID
- program counter

## Motivation
- web browser
- 如一個 thread 負責顯示文字，其他 thread 接收資料等
- web server
- One request / process: poor performance
- One request / thread: 因為 code 及 data sharing，效率較高
- 會有一個 main thread 一直在等待，當接收到新 request 時，會產生一個 thread 專門處理，讓 main thread 可以繼續等待連接
- RPC server
- One RPC request / thread

## Benefits of Multithreading
- Responsiveness : 即使 program 的一部分被 block 住，或是執行冗長的操作，仍可繼續運行，加速響應時間
- Resource sharing : 不同的 threads 可利用相同的記憶體位置來共享資源
- Utilization of MP arch : 因為現在都是多核心，因此 thread 可以在不同 processors 上平行執行
- Economy : thread 無須記憶體空間管理及處理，建立 Thread的 cost 比 process 來得小。而且因為 thread 共用 process 資源，thread 之間的 context switch 也比 process 來得快。

## Multicore Programming
- Multithreaded programming 提供一種更有效率使用多核心的機制，改善共時性 (concurrency)
- 多核心系統使 system designer 以及 application programmer 面對更多挑戰
- 對 OS 設計者 : 如何設計 scheduling algorithms 讓多核心可以平行執行

## Challenges in Multicore Programming
- Dividing activities : 將 program 拆成多個可以同時處理的任務
- Data splitting : 除了計算任務要拆，資料也要能夠拆開給不同任務處理。有時候 data 很複雜，不一定是平分給所有任務處理
- Data dependency : shared data 的同步，是平行程式中最複雜且重要的部份
- Balance : 各個任務的執行時間要差不多，否則會受限於執行最久的任務
- Testing and debugging 非常困難

## User vs. Kernel Threads
- User threads : 由 user 透過 threads library 進行的 thread 控制。雖然由 user 創建，但實際 thread 要執行任務時， OS 會將該 thread binding 到某一個 kernel thread 上，每次可對應到不同的 kernel thread。
- POSIX Pthreads
- Win32 threads
- Java threads
- 所謂 user thread 就是 thread library，更重要的是 user level 的 thread，不由 kernel 直接控制，通常在創建及管理上會比較快
- 但如果 kernel thread 只有一個的話，即便有多個 user threads，因為有 binding 的關係，只要某個 user thread 執行時呼叫 I/O 或 sleep()，則其他 threads 就沒辦法再使用該 kernel thread
- Kernel threads : 由 kernel(OS) 直接控制
- Windows 2000(NT)
- Solaris
- Linux
- Tru64 UNIX
- 由 kernel 進行創建及管理，速度較慢
- 若某個 thread 被 block，仍可由 kernel 安排其他 threads 執行工作

## Multithreading Models
Kernel mapping threads 的方式通常有以下幾種：
1. Many-to-One
- 許多 user thread mapping 到一個 kernel thread
- 在不支援多 threads 的 kernel 使用
- Thread 管理在 user space 完成，效率高
- 但整個 process 可能被 block
- 一次只有一個 thread 可以 access kernel，多執行緒在多處理器的環境下也無法平行化
2. One-to-One
- Windows XP/NT/2000
- Linux
- Solaris 9 and later
- 每個 user thread mapping 到一個 kernel thread
- 因為 kernel thread 數量通常受到限制，所以 user thread
- More concurrency
- 因為創建一個 user thread 必須同時創建一個對應的 kernel thread，所以有較高的 overhead
3. Many-to-Many
- 多個 user threads 對應到相同或較少數量的 kernel threads，而且是在 runtime 期間做 mapping
- user threads 數量不受限制
- kernel threads 可以在多核心系統中平行執行
- 當某個 thread 被 block 時，可安排其他 kernel thread 來執行

## Shared-Memory Programming
- 定義：Processes 透過 shared memory space 進行溝通及協作
- 比 message passing 更快也更有效率
- 有許多議題需要處理：
- Synchronization
- deadlock
- Cache coherence
- Programming 的技巧
- Parallelizing compiler
- Unix Processes
- Threads (Pthreads, Java)
### What is Pthread
- POSIX (Portable Operating System Interface，只定義行為不定義實作，也就是 API 層面必須一模一樣) 標準針對 Unix 類的不同系統 (MacOs, Linux...等)，程式碼只需要重新編譯而不用修改即可執行
- Message passing 的 library MPI 也有相同概念
- Pthread 即是定義在 POSIX 標準下的 thread 庫
#### Pthread Creation
- pthread_create(thread, attr, routine, arg)
- 有時我們會指定某個 thread 榜在某個指定的 core 上，因為不同 core 的 L1 cache 不共享，這個行為可以透過 attr 參數來控制
#### Pthread Joining & Detaching
- pthread_join(threadId, status)
- Block 直到特定 threadId 的 thread 結束
- 達成 threads 之間同步化的一種方法
- 範例：產生 pthread barrier

        for (int i = 0; i < n; i++) pthread_join(thread[i], NULL)

- 要注意的是，若今天 thread 執行完之後，我們不需要把資料讀回來，則不用 call pthread_join，但多數的 thread 庫會要求 programmer call pthread_detach，告訴 library thread 結束後就直接 free 掉。若不去 call detach， OS 無法知道 thread 是否之後會被 join，導致 thread 的回傳值一直在等待，程式無法結束
- pthread_detach(threadId)
- 一但 thread 被 detached，則永遠無法被 join
- Detach 一個 thread 可以 free 掉 thread 的資源

### Linux Threads
- Linux 在 kernel 不 support multithreading(因為 Linux 只有 process 或 task)
- User-level 可以使用 Pthreads 來實作多執行緒
- `fork` system call: 產生新的 process 並完全複製 parent 的 data 及程式執行狀態
- `clone` system call: 產生新的 process 並控制哪些 segment 要與 parent share 哪些不需要。因為 Linux 沒有 thread ，所以用 `clone` system call 來達到 thread 的概念
- 有一系列的 flag 來控制資料共享的程度，共享的資料以 pointer 的方式指向

## Threading Issues
- Semantics of fork() and exec()
- 若 process 有兩個 thread，其中一個 thread call `fork()` 可能有以下兩種情況
- 部份 UNIX 系統支援兩種 `fork()` 的方式
- `execlp()` 會取代整個 Process，而不是單一 thread
- Thread Cancellation
- 一個 thread 若執行結束後， main thread 必須有一系列 cancel 的動作
- Asynchronous cancellation : main thread 會馬上中止 target thread
- Deferred cancellation (default option) : target thread 會預設一些中斷點，main thread 會週期性地確認是否執行到中斷點，等 target thread 執行到中斷點才中斷。
- Signal Handling
- Signals(synchronous or asynchronous) 在 UNIX 系統中用來告知 process 某個事件發生
- synchronous : 如不合法的記憶體存取
- asynchronous : control-C
- Signal handler 處理 signals 的順序
1. Signal 被特定事件產生
2. Signal 被送到 process
3. Signal 被處理
- Signal 處理的 Options
- 傳送 signal 給 deliver signal 的 thread
- 傳送 signal 給所有 thread
- 傳送 signal 給特定的 thread
- 直接由 main thread 來處理 signal，如 file handler 的操作
## Thread Pools
- 很多應用是直接產生一定數量的 threads，避免動態 thread 的產生、刪除時造成的 overhead，程式執行比較有效率，如 web server
- 優點
- 直接接收 request 通常比創建一個新的 thread 再接收 request 來得快
- 可以控制 threads 數量，進而控制系統的資源用量
- threads pool size 的決定: 利用 # of CPUs, 預期的 # of request 以及記憶體大小來決定

## Refernece
1. [清大開放課程 - 作業系統](https://www.youtube.com/watch?v=aK0_PBLWCAM&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=38)
2. [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)