作業系統 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
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

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
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

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 讓多核心可以平行執行
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

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 的方式通常有以下幾種：

Many-to-One
- 許多 user thread mapping 到一個 kernel thread
- 在不支援多 threads 的 kernel 使用
- Thread 管理在 user space 完成，效率高
- 但整個 process 可能被 block
- 一次只有一個 thread 可以 access kernel，多執行緒在多處理器的環境下也無法平行化
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →
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
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →
Many-to-Many
- 多個 user threads 對應到相同或較少數量的 kernel threads，而且是在 runtime 期間做 mapping
- user threads 數量不受限制
- kernel threads 可以在多核心系統中平行執行
- 當某個 thread 被 block 時，可安排其他 kernel thread 來執行
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

Shared-Memory Programming

定義：Processes 透過 shared memory space 進行溝通及協作
- 比 message passing 更快也更有效率
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →
有許多議題需要處理：
- 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 參數來控制
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

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 的資源
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

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() 可能有以下兩種情況
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →
- 部份 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

Guest Hayes2024/08/31 09:17:57

Linux 在 kernel 不 support multithreading(因為 Linux 只有 process 或 task)

但 linux kernel 有 kthread ，請問為什麼會不 support multithreading 呢 ?

Chang-Chia-Chi

2024/08/31 12:30:00

稍微追個 code，先看 kthread_run (https://github.com/torvalds/linux/blob/master/include/linux/kthread.h) /** * kthread_run - create and wake a thread. * @threadfn: the function to run until signal_pending(current). * @data: data ptr for @threadfn. * @namefmt: printf-style name for the thread. * * Description: Convenient wrapper for kthread_create() followed by * wake_up_process(). Returns the kthread or ERR_PTR(-ENOMEM). */ #define kthread_run(threadfn, data, namefmt, ...) ({ struct task_struct *__k = kthread_create(threadfn, data, namefmt, ## __VA_ARGS__); if (!IS_ERR(__k)) wake_up_process(__k); __k; }) 可以看到當創建一個 kthread 後，會透過 wake_up_process 喚醒一個進程 (Edited)

2024/08/31 12:33:25

kthreadd https://github.com/spotify/linux/blob/master/kernel/kthread.c 這是 linux kernel 負責管控 kthread 的 process，其實就是一個無窮迴圈，會調用 create_kthread 建立 kthread int kthreadd(void *unused) { ... 省略 for (;;) { set_current_state(TASK_INTERRUPTIBLE); if (list_empty(&kthread_create_list)) schedule(); __set_current_state(TASK_RUNNING); spin_lock(&kthread_create_lock); while (!list_empty(&kthread_create_list)) { ... 省略 create_kthread(create); ... 省略 } spin_unlock(&kthread_create_lock); } return 0; (Edited)

2024/08/31 12:38:44

最後看到 create_kthread，本質其實是建立一個進程 static void create_kthread(struct kthread_create_info *create) { int pid; #ifdef CONFIG_NUMA current->pref_node_fork = create->node; #endif /* We want our own signal handler (we take no signals by default). */ pid = kernel_thread(kthread, create, create->full_name, CLONE_FS | CLONE_FILES | SIGCHLD); if (pid < 0) { /* Release the structure when caller killed by a fatal signal. */ struct completion *done = xchg(&create->done, NULL); kfree(create->full_name); if (!done) { kfree(create); return; } create->result = ERR_PTR(pid); complete(done); } } (Edited)