# Chp 4 Threads
###### tags: `作業系統`
[TOC]

## Overview


### Motivation

(原因待補)
1. Process creation:
- heavy-weight
2. Thread creation:
- light-weight
>[color=#00a000]
>
>context switch, memory allocate
>[name=Omnom]

>[color=#FF00FF]創一個process就要重新allocate一塊記憶體給他，連帶也造成Process之間的資料傳遞比較麻煩，相比之下不同的thread仍然是在同一個記憶體空間(main process)
>[name=Neko]

>[color=#000000]增加處理的平行度
>[name=Peter]

* simplify code, increase efficiency

* <font color=#ff0000>**考**</font> Provide two case that multithreading does not provide better performance than a single-threaded solution:
1. sequential program: e.g. calculates an individual tax return
2. shell program: e.g. C-shell or Korn shell

* <font color=#ff0000>**考**</font> multiple kernel threads provide better performance than a single-threaded solution:
- **page fault**, another kernel thread can be switched in to use the interleaving time in a useful manner
- single-threaded process will not be capable of performing useful work when a page fault takes

### Benifits

* **Responsiveness** – allow continued execution if part of process is blocked
* **Resource Sharing** – thread sharing is easier than shared memory or message passing
* **Economy** – cheaper than process creation, thread switching lower overhead than context switching
* **Scalability** – process can take advantage of **multiprocessor** architectures

## Multicore Programming

### Issues of Programming

1. Dividing activities
2. Balance
3. Data splitting
4. Data dependency
5. Testing and debugging

### Parallelism V.S Concurrency

<font color=#ff0000>**考**</font>
* Parallelism: perform more than one task **simultaneously**, at least two threads are executing simultaneously, e.g. multicore processor
* Concurrency: support more than one task making progress, two or more tasks can start, run, and complete in overlapping time periods, e.g. multitasking on a single-core processer


>[color=#00A000]
>
>[Parallelism VS Concurrency](https://medium.com/mr-efacani-teatime/concurrency與parallelism的不同之處-1b212a020e30)
>[name=Omnom]

* Types
1. Data Parallelism
+ distribute **data** across multiple cores
e.g. Multiple same task, different data
(每個core執行相同的operation，只是每個core用的data不一樣)
2. Task parallelism
+ distribute **tasks(threads)** across multiple cores
e.g. Same data with multiple different tasks
(每個core(thread)執行不同的task，可能會用一樣的data)
> [color=#000000] 看到一個不錯的例子
>150份15題的考卷分給三個助教去改，若是**data parallelism**的作法，則每一個助教分別改50份考卷；若是**task parallelism**的方法，則每一個助教分別改150份考卷的前、中、後5題。瞭解嗎？這裡可以分析每個助教的負擔，乍看下是一樣的，然而後者方法中每個助教分別對前、中、後5題有高度熟悉感，那麼後者的方法可以有很好的效能，一下子就把考卷給改完！而前者方法中每個助教都批改15題，無法發揮所長，效能因此較不彰。 [參考](https://cg2010studio.com/2011/10/05/data-parallelism-task-parallelism/)
>[name=Peter Peter]


### Amdahl’s Law

$S$: Serial portion, $1-S$: parallel portion
$N$: # of processing core

:::info

<font color=#000000>

$speedup ≤ \frac{1}{S+\frac{1-S}{N}}$
</font>

:::

+ $N \rightarrow \infty, \ speedup \rightarrow 1/S$

## Multithreading Models

* user_thread-to-kernel_thread

1. Many-to-One(Few system use it)
- Many user-level threads mapped to single kernel thread
- Pro
1. Thread management is done by the thread library in user space, so it is efficient (?)
2. allows the developer to create as many user threads as she wishes
- Con
1. the entire process will block if a thread makes a blocking system call
2. only one thread can access the kernel at a time → unable be parallel


2. One-to-One

- Creating a user-level thread creates a kernel thread
- Pro
1. provides more concurrency
2. allows multiple threads to run in parallel
- Con
1. large number of kernel threads may burden the performance


3. Many-to-Many

- Pro
1. Has advantages from both Many-to-One & One-to-One
- Con
1. in practice it is difficult to implement


4. Two-level (Variation of Many-to-Many)

<font color=#ff0000>**考**</font>
* number of kernel threads < number of processors:
- some of the processors would remain idle
* number of kernel threads == the number of processors
- all of the processors might be utilized simultaneously
* kernel threads > processors
- a blocked kernel thread could be swapped out, in favor of another kernel thread that is ready to execute
## Thread Libraries(待補)

### Pthread
* **Specification**, not implementation

>[color=#FF00FF]說"標準"的原因是Pthread是符合POSIX規範的Thread API，POSIX為可移植作業系統介面，就是說只要函式庫符合POSIX規範，都能夠在支援POSIX規範的系統上運作，至於函式庫的內容是如何實作的就不是很重要了，只要行為符合就好，比方說函式庫是使用哪一種multithread model是沒有規定的。
>推出這個規範是因為Unix系統分支太氾濫，有很多Unix-like的作業系統但是又不全然可以移植程式，為了解決這個問題就誕生了POSIX
>[name=Neko]
## Implicit Threading

* Concept: transfer the creation and management of threading from application developers to compilers and run-time libraries.

* Note: require application developers to identify **tasks**—not threads—that can run in parallel

### Thread Pools
* Mechanism: Create a number of threads in a pool
* Note: **create multiple in advance**
* Pro
1. Servicing a request with an existing thread is often faster
2. thread pool limits the number of threads → limit concurrent threads
3. Separate task performing from task creating → flexibility to run tasks

### OpenMP
* **API** for programs written in C, C++, or FORTRAN that provides support for parallel programming in shared-memory environments

* Mechanism: Identifies parallel regions – blocks of code that can run in parallel

### Grand Central Dispatch

* Mechanism:
1. identification of parallel sections (Block)
2. Blocks placed in dispatch queue
3. Assigned to available thread in thread pool when removed from queue

* Type of dispatch queues
1. serial:
+ one goes out FIFO
+ called main queue
2. concurrent
+ several go out FIFO

## Threading Issues

### Signal Handling (待補)
* Procedure:
1. A signal is generated by the occurrence of a particular event.
2. The signal is delivered to a process.
3. Once delivered, the signal must be handled.
* default signal handler
1. runned by **kernel**
2. can be overridden by **user-defined signal handler**

### Thread Cancellation (待補)

Note: actual cancellation depends on thread state

1. **Asynchronous** cancellation
terminates the target thread **immediately**
會有後遺症，資料不一致，影響另一個Thread的資訊，
>[color=#00a000]
>
>補充說明：[摘自老師]
>target thread 可能正在處理還沒處理完的工作，舉例來說：和其他 thread 可能有 shared data。~~一旦任意將 target thread cancel，可能造成資料不一致，「影響另一個Thread資訊的正確性？」~~
>突然中止，可能導致工作無法正確交接，造成錯誤
>[name=Omnom]
>

2. **Deferred** cancellation
allows the target thread to **periodically check** if it should be cancelled

### Thread-Local Storage (TLS)

* Uniqueness: each thread have its own copy of data
* TLS v.s. local variables
- visibility:
across function invocations
v.s.
during single function invocation

### Scheduler Activations

M:M and Two-level models require communication

Each LWP is attached to a kernel thread

<font color=#ff0000>**考**</font>
* **lightweight process (LWP)**:
+ intermediate **data structure** between user and kernel threads(對user process來說相當於~~virtural process~~是virtual processor)
+ User thread 要mapping到kernel thread才能做scheduling

>[color=#FF00FF]不確定上面描述的內容想表達的跟我想表達的是不是一樣，總之做個補充。
>我們可以想成LWP是一個虛擬的處理器，會執行Process，Process裡面是User thread，一個LWP可以有同一個Process的好幾個thread，這些thread在LWP上面做scheduling的工作(就是決定這些thread要怎麼樣執行)。
>正如課堂所說，OS並不知道User thread有多少，這些也不是他要管的。OS要做的事情是kernel thread的scheduling，而每一個LWP都會關聯到一個kernel thread。
>每個層級schedule的對象不大一樣
>[name=Neko]

* **upcalls**: a communication mechanism from the kernel to the **upcall handler** in the thread library