---
title: Ch4:Multithreaded Programming
---
# 作業系統Ch4: Multithreaded Programming
###### tags: `Operating System` `Review` `Ch4`
## Thread Introduction
### Threads
- a.k.a <font color=red> lightweight process </font>: basic unit of CPU utilization
- All threads 屬於同一個 process 共享 code section, data section and OS resources (e.g., open files and signals)
- But each thread 有屬於自己的 **thread control block**
- thread ID, program counter, register set and a **stack** (local variables)
<br>
### Motivation
- Example: a web browser
- 一個執行緒顯示內容，當其他執行緒正在從網路上收到 data
> 也就是開啟一個瀏覽器搜尋關鍵字結果，可能會先出現文字，再出現圖片等等，不同 thread 下載不同物件。
- Example: a web server
- one request / process: poor performance
- one request / thread: better performance as code and resource sharing
> create 一個 process 和 一個 thread 所需時間差很多，一個是 system call 而另一個可能只需要 API，而且有些時候 data 需要共享。
- Example: RPC server
- One RPC request / thread
> 當 request 請求發出時，會創造一個 thread 來服務這個 request，不過要先建立連線。
### Benefits of Multithreading
- **Responsiveness**: 允許一個 program 繼續 running 即使 它的某部分被 blocking 或 正在執行較長的 operation。
- **Resource sharing**: 多個不同的 threads 的 activity 都有相同 address space 內。
- Utilization of Multiprocessor arch.: 多個不同 thread 可以 running in parallel on different processors。
- Economy: 為 process 分配 memory and resources 是昂貴的，而且create 速度 很慢，context switch 同樣也是。
### Why Thread?
- Lower creation / management cost vs. Process
- Faster inter-process communication vs. MPI
### Multithcore Programming
- Multithreaded programming: 提供有效率使用 multiple cores 的機制和改善 concurrency (threads can run in parallel)
- Multicore systems: 給系統設計者和應用程式的 programmers 帶來壓力。
> OS designers: 排班演算法使用 cores 去允許 parallel execution
<br>
<br>
**Challenges in Multicore Programming**:
- Dividing activities: divide program into concurrent tasks，以 running in parallel。
- Balance: evenly distribute tasks to cores
- Data splitting: divide data accessed and manipulated by the tasks
- Data dependency: synchronize data access
- Testing and debugging
<br>
:::info
Amdahl's Law (阿姆達爾定律) : 確認自增加額外計算 cores 到應用程式同時具有 serial (nonparallel) 和 parallel 的潛在效能提升。
如果 $S$ 是應用程式中無法提升速度的比例，且在具有 $N$ 核的系統上必須以 performed serially，則公式如下:
$\ speedup\ \le\ \cfrac{1}{S\ +\ \cfrac{1\ -\ S}{N}}$
當 $N$ 趨近於無限大時， $speedup$ 會收斂到 $\cfrac{1}{S}$。
:::
<br>
## Multithreading Models
### User vs. Kernel Threads
- User threads
- 由 user-level threads library 來管理 thread
- POSIX threads
- Win32 threads
- Java threads
- Thread lib 提供 thread creation, scheduling, and deletion
- 一般來說 create and manage 較**快**
- 如果 kernel 是 single-threaded, a user-thread blocks $\rightarrow$ 整個 process blocks 即使其他 threads 準備好要執行
- Kernel threads
- 直接由 Kernel (OS) supported
- Windows 2000 (NT)
- Solaris
- Linux
- Tru64 Unix
- Kernel 執行 thread creation, scheduling, etc.
- 一般來說 create and manage 較**慢**
- 如果 thread 被 blocked， kernel 可以安排另一個 thread for execution
### Multithreading Models
#### Many-to-One
- 多個 user threads 映射到單一 kernel thread
- pros: Thread management is done in user space, so it is efficient
- cons:
- 如果一個 user thread 產生 system call，整個 process 將 block
- 一次只能有一個 thread 存取 kernel，多 threads 不能夠 run in parallel on multiprocessors
#### One-to-One
- 每一個 user-level thread 映射到一個 kernel thread
> kernel threads 數量上可能有限制
- Pros: more concurrency.
- cons: overhead
- creating a thread 需要創造一個相對應的 kernel thread
- E.g.,
- Windows XP/NT/2000
- Linux
- Solaris 9 and later
#### Many-to-Many
- Multiplexes: 許多 user thread 映射到數量不超過 user threads 的 kernel threads
- 允許開發者創造和自己期望一樣多的 user threads
- pros:
- 在 multiprocessor 上，相對應的 kernel threads 可以 run in parallel。
- 當 thread 執行 blocking call， kernel 可以安排其他 thread for execution
- cons:
- 管理不易
- 設計上較難
<br>
## Thread Case Study
- Thread libs
- pthreads
- Java threads
- OS examples
- WinXP
- Linux
### Shared-Memory Programming
- Def: Processes communicate or work together with each other **through a shared memory space** which can be accessed by all processes
> 比起 message passing，較快且較有效率。
- Many issues:
- Synchronization
- Deadlock
- Cache coherence
- Programming techniques
- Parallelizing compiler
> 透過 API 標示出共享的，讓 compiler 識得
- Unix processes
- Threads (Pthread, Java)
### Pthread
- Pthread is the implementation of <font color = red>POSIX standard</font> for thread
#### Pthread Creation
- pthread_create(pthread_t *restrict thread, const pthread_attr_t *restrict attr, void *(*start_routine)(void *), void *restrict arg)
- thread: an unique identifier (token) for the new thread.
- attr: It is used to set thread attributes. **NULL** for 預設值。
- static_routine: The routine that the thread 將執行一次，一旦它被創造了。
- arg: 單一 argument 可以被傳遞給 routine。
> 如果超過一個參數，可以包成 data structure 形式去傳遞。
```cpp=
#include<pthread.h>
#include<unistd.h>
#include<stdio.h>
#define NUM_THREADS 5
void *PrintHello(void *threadId)
{
long *data = (long *)threadId;
printf("Hello World! It's me, thread #%ld!\n", *data);
pthread_exit(NULL);
}
int main(int argc, char *argv[]){
pthread_t threads[NUM_THREADS];
for (long tid = 0; tid < NUM_THREADS; tid++) {
long *id = (long *)malloc(sizeof(long));
*id = tid;
pthread_create(&threads[tid], NULL, PrintHello, (void *)id);
}
/* Last thing that main() should do */
pthread_exit(NULL);
}
```
以 gcc 編譯需 link pthread library，所以需要加上 `-lpthread` 的編譯參數。
#### Pthread Joining & Detaching
- **pthread_join(pthread_t thread, void \*\*retval)**
- 呼叫這個thread 的 Blocks(等待) 直到指定 *threadId* thread 中止
- 在 threads 間完成 synchronization 的一種方法
- Example: to create a pthread barrier
```cpp=
for (int i = 0; i < n; i++)
pthread_join(threads[i], NULL);
```
<br>
- **pthread_detach(threadId)**
- 一旦 thread 被 detached， 它就永遠不能 join。
- Detach a thread 能夠 <font color =red>free some system resources</font>。
<br>
### Java threads
- Thread 創造 by
- Extending Thread class
- Implementing the Runnable interface
- Java threads 實作使用 host system 上的 thread library
> 達到 portable。
- Thread mapping 取決於 <font color =red>JVM</font> 的實作
> 根據作業系統安裝的 JVM 去進行 mapping
### Linux threads
- Linux does **not** support multithreading
> 比較好的說法是，Linux 上 create 一個 thread， 其實跟 process 沒有太大差別，Linux 上沒有嚴格區分這兩者差別。
- pthreads 實作可以用於 user-level 就得到。
- **fork** system call: 創造新的 process 且拷貝 parent process 相關 data 一份。
- **clone** system call: 創造新的 process 且 a link 指向 parent process 的相關資料。
- 一組旗標用於 clone( ) call 用於分享層面的指示物 (indicator)。
- None of the flags is set $\rightarrow$ clone = fork
- All flags are set $\rightarrow$ parent and child share everything
<br>
## Threading Isuues
### Semantics of fork( ) and exec( )
- Does `fork( )` 複製只有呼叫的 thread 還是所有 threads?
- 有些 UNIX 系統支持兩種版本的 `fork( )`
- `execlp()` 跟所有 threads 的版本一樣，全部取代整個 process
- 如果 `exec()` 在 `fork( )` 之後被立即呼叫，那麼複製 all threads 就不是必須的。
### Thread Cancellation
如果發生了 thread 執行完前就被 terminates，會怎麼樣?
- target thread: a thread that is to be cancelled
- 兩種 general 方法:
- Asynchronous cancellation
- The target thread can be canceled at any time (usually immediately, but the system does not guarantee this)
- Deferred cancellation (default option)
- cancellation will be **delayed** until the thread next **calls a function** that is a **cancellation point** (定期檢查 cancellation points)
### Signal Handling
- Signals (synchronous or asynchronous) 在 UNIX 系統中使用來通知 a process 事件已經發生。
- Synchronous: illegal memory access
- Asynchronous: \<control-C>
- **<font color = red> Signal handler</font>** 用來處理 signals
1. 特定事件產生 Signal
2. Signal 傳遞到 process
3. Signal 被處理
- 處理選項
1. 傳遞 Signal 到 the signal 應用的 thread，由這個 thread 去 handle。
2. 傳遞 Signal 到 process 中的所有 threads。
3. 傳遞 Signal 到 process 中的某些 threads。
4. 指定一個 specific (main) thread 收對於 process 的所有 Signals。
### Thread Pools
- 創造在等待工作的 pool 中一定數量的 threads (先創造出來，重複使用)
- 優勢
- 用一個已經存在的 thread 去對於 request 提供服務比起 create a new thread 還要快。
- 允許應用程式中 thread 的數量被限制在 pool 的大小。
- $\#$ of threads: CPU 期望有多少的請求數量且佔有多少 physcial memory。
## Ref
[1] [上課影片 link](https://www.youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX)
[2] [投影片 link](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)
Sign in with Wallet
Connect another wallet