# 期末專題筆記
* Todo : 閱讀 https://hackmd.io/@sysprog/concurrency 並紀錄問題
* Todo : quiz9/quiz10/quiz12 (or newer)
## 閱讀並行和多執行緒設計
### 概念
Concurrency(並行) ： 將各個程式拆成多個可獨立運作的 process/thread 來執行，並分配在不同時間點做不同的事

Parallelism(平行) ： 在多核或多處理器的架構中，將任務分配給不同的硬體來同時處理，注重在規劃。

上述兩種方式都會遇到同個問題，資料的 **Sychronization(同步處理)**。其作用是確保各個處理單元在運作時，不會因為**處理的先後順序**不同而造成錯誤。

#### mutex 和 semaphore 的差別：

process 使用 **mutex** 時，此 process 便獲得**存取/修改**資源的權限，執行其 Critical Section，結束後再釋放 mutex。

process 使用 **semaphore** 時，各個處理器會發出 signal 和 wait 來決定執行的先後順序，同個 process 不會先後進行 signal 和 wait。來保證 process 的同步處理正確。

**Thread** 在硬體中，代表著實際的處理器中能夠處理的執行續;在軟體中則代表一個 process 能夠被拆成多個 thread。

在 intel 開發了 Hyperthread ，讓單個 CPU 可以同時執行多個 Thread (物理上)，藉由共用 ALU 或 FPU 來完成。

#### Task and Thread
在 Linux 中，並沒有特別強調 task/process/thread 的差異，在多個 CPU 的環境中，會將一個程式分割成最小單元(Thread)，並分配到各個 CPU 中來進行。若要完成某個目標，會需要多個工作，而各個工作又分割成許多 Thread ，即為**多工多執行續系統**。

而多工系統中，每個工作會因為不同的排程，而各自運行到不同的階段，當被暫停切換至另一個工作時，需要使用 **工作切換 (context switch)** 來回復到上次的進度，也就是回到上次執行完的**下一個地址**。因為工作切換也會造成一定程度的**負擔(overhead)**，因此和系統的反應速率有**高度相關**。

#### 排程器

CPU 會為各個工作進行排程，來決定下一個工作，可以是 static 排程，也可以是 dynamic 的排程。

排程有多種演算法，依照時間分割(round-robin scheduling 或 time slicing) 用於處理相同重要性的工作，而任務優先順序的 (priority scheduling)則處理那些有不同時效性的任務，也就是 hard real-time 的工作。
:::info
排程器是在哪裡運行的 是會有一個CPU來完成這些事情嗎 排程這件事算一個task嗎
:::

#### 搶佔式與非強取式核心

兩者的核心差別為，工作交出CPU的使用權是強制性的或是非強制的。

非搶佔式(non-preemptive)不會依照工作的優先順序交出CPU的使用權，而是不定期的交出使用權。為了達到並行，因此頻率要夠快，否則讓使用者感受到等待時間，有下列好處
1. 實作單純
2. 工作中可使用**非再進入程式碼(non-reentrant code)**，換言之，每個工作不需擔心在程式未執行完畢時又重新進入。因此該工作本身所用的記憶區不會有被污染 (corruption) 的可能;
3. 對系統共用記憶區的保護動作可減至最少，因為每一工作在未使用完記憶區時不會放棄 CPU ，無須擔心會被其他工作在半途中修改;
:::info
2、3項不太懂
:::

缺點為反應能力 (responsiveness) 較差，當優先權較高的順序已準備好，卻必須等待較低的工作放棄CPU。



搶佔式核心則是讓優先權較高的工作可以打斷正在執行且較低優先權的工作。優點為系統反應速度快，但其核心設計較複查，也需考量較多因素，且要注意程式碼的再進入性與保護共用資料區。

#### 程式之可再進入性
可再進入的函式可以同時被多個工作呼叫，而不會造成資料不一致的問題。一個可再進入 [(reentry) ](https://en.wikipedia.org/wiki/Reentrancy_(computing))會避免使用共享記憶體(global memory)，而變數和資料存在於呼叫者的資料區或堆疊區。

三種不同的函式

* Neither reentrant nor thread-safe

`tmp` 為全域不符合 reentrant，且沒有進行同步，非 thread-safe。

int tmp;

void swap(int* x, int* y)
{
    tmp = *x;
    *x = *y;
    /* Hardware interrupt might invoke isr() here. */
    *y = tmp;    
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}

* Thread-safe but not reentrant

`_Thread_local`

_Thread_local int tmp;

void swap(int* x, int* y)
{
    tmp = *x;
    *x = *y;
    /* Hardware interrupt might invoke isr() here. */
    *y = tmp;    
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}

* Reentrant and thread-safe

void swap(int* x, int* y)
{
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;    /* Hardware interrupt might invoke isr() here. */
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}

### Concurrency (並行) vs. Parallelism (平行)
**Concurrency** 是指程式架構，將程式拆開成多個可獨立運作的工作。案例: 裝置驅動程式，可獨立運作，但不需要平行化。

**Parallelism** 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。案例: 向量內積計算

### Atomics 操作
在並行程式設計中，會使用 lock 來避免發生 race condition，

使用 `lock` 可能會發生 `lock contention` ，進而使用atomic 操作
但會有 ABA 、memory barrier 的問題

CAS(comapre and swap)
讀取 target 的值到 compare，再讀取target 確保兩者一樣
LL/SC
LL讀取記憶體，並標註exclusive SC 寫入則清除
### POSIX THREADs

#### mutex lock

`pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER` :宣告一個mutex lock
`int pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexattr_t *attr)` : 初始化 lock
`int pthread_mutex_destroy(pthread_mutex_t *mutex)`: 刪除 lock

* `int pthread_mutex_lock(pthread_mutex_t *mutex)` : 獲得 lock or 等待得到 lock
* `int pthread_mutex_unlock(pthread_mutex_t *mutex)` : 釋放 lock 給其他 thread
* `int pthread_mutex_trylock(pthread_mutex_t *mutex)`: 獲得 lock or 回傳無法得到 lock

#### condition variables

* `int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr)`: 初始化條件變數
* `int pthread_cond_destroy(pthread_cond_t *cond)`：刪除條件變數

* `int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)`：釋放目前的 lock ，並等待條件成立，再獲得 lock

* `int pthread_cond_signal(pthread_cond_t *cond)` : 發送條件內容。
* `int pthread_cond_broadcast(pthread_cond_t *cond)`： 喚醒所有執行續。

// 宣告 mutex lock 和 condition variable
pthread_mutex_t *lock;
pthread_cond_t *notFull, *notEmpty;
//
void consumer(char* buf) {
   for(;;) {
//獲得 mutex
	pthread_mutex_lock(lock);
// 若沒有空間時
	while(count == 0)
// 發送一 notEmpty 的訊號，呼叫 producer 生產物件，並釋放 mutex，等待直到 not Empty
		pthread_cond_wait(notEmpty, lock);
// buff內容減少
	useChar(buf[count-1]);
	count--;
// 傳送 norFull 的訊號
	pthread_cond_signal(notFull);
// 釋放 mutex
	pthread_mutex_unlock(lock);
   }
}

#### semaphores

* `sem_t semaphore;` : 宣告 semaphore
* `int sem_init(sem_t *sem, int pshared, unsigned int value)` : 初始化 semaphore， `pshared` 表示此 semaphore 是 thread 間共享還是 process 間共享。為 `0` 代表示 thread 間共享，存放地址應該要能夠讓所有 thread 都讀取; 不為 `0` 則代表為 process 間共享，這時就會使用到 `mmap`。

* `int sem_wait(sem_t *sem);` ： 若目前 sem 值大於 0， 則可以 decrement 並 return ; 相反則會等待直到 sem 值大於 0
* `int sem_post(sem_t *sem);` ： 將 sem 值加一。

`sem_wait` 和 `sem_post` 成功時會回傳 0 ，失敗回傳 -1 。

Mutex 雖然可以確保 CS ，但卻無法確保 thread 的先後順序，則 condition variable 可以完成上述任務

### 使用 實作輕量級的 Mutex Lock
futex 為一種系統呼叫，當在確認 task 是否會競爭資源時，會以系統呼叫來確認，便會造成不必要的浪費。 Futex 則可以在userspace 上完成 mutex 、 condvar 等操作。

通常在condvar 和 mutex 合用的實作中，會需要 condvar 的情況成立和獲得 mutex 才會進行動作，而頻繁的確認 mutex 也會造成一定的資源浪費，而 futex 將兩種動作合為一次呼叫即可完成。

* `futex_wait` :

static inline void futex_wait(atomic int *futex, int value)
{
    syscall(SYS_futex, futex, FUTEX_WAIT_PRIVATE, value, NULL);
}