---
# System prepended metadata

title: 'Ch4:Multithreaded Programming'
tags: [Operating System, Review, Ch4]

---

---
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>

![](https://i.imgur.com/Y2BzrfF.png)

### 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，不過要先建立連線。

![](https://i.imgur.com/Co5Airs.png)


### 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

![](https://i.imgur.com/ztZD02q.png)

- Faster inter-process communication vs. MPI

![](https://i.imgur.com/XibfAAK.png)



### Multithcore Programming
- Multithreaded programming: 提供有效率使用 multiple cores 的機制和改善 concurrency (threads can run in parallel)
- Multicore systems: 給系統設計者和應用程式的 programmers 帶來壓力。
> OS designers: 排班演算法使用 cores 去允許 parallel execution

<br>

![](https://i.imgur.com/z54Wm6u.png)

<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}}$

![](https://i.imgur.com/5qPeOrS.png)

當 $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

![](https://i.imgur.com/Om24Auh.png)

#### 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

![](https://i.imgur.com/IrbDlII.png)

#### 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:
    - 管理不易
    - 設計上較難
    
![](https://i.imgur.com/ZnuDnru.png)

<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)

![](https://i.imgur.com/vyUkRji.png)

### 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 形式去傳遞。

![](https://i.imgur.com/du5D0xE.png)

```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);
```

![](https://i.imgur.com/glvAulp.png)

<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

![](https://i.imgur.com/BGXDrhU.png)

<br>

## Threading Isuues
### Semantics of fork( ) and exec( )
- Does `fork( )` 複製只有呼叫的 thread 還是所有 threads?
    - 有些 UNIX 系統支持兩種版本的 `fork( )`

![](https://i.imgur.com/VTdyh1Q.png)

- `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)