# 同步處理筆記
* [Part 1: Mutex Locks](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-1:-Mutex-Locks)
* [Part 2: Counting Semaphores](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-2:-Counting-Semaphores)
* [Part 3: Working with Mutexes And Semaphores](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-3:-Working-with-Mutexes-And-Semaphores)
* [Part 4: The Critical Section Problem](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-4:-The-Critical-Section-Problem)
* [Part 5: Condition Variables](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-5:-Condition-Variables)
* [Part 6: Implementing a barrier](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-6:-Implementing-a-barrier)
* [Part 7: The Reader Writer Problem](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-7:-The-Reader-Writer-Problem)
* [Part 8: Ring Buffer Example](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-8:-Ring-Buffer-Example)
* [Part 9: Synchronization Across Processes](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-9:-Synchronization-Across-Processes)

以下節錄自己覺得重要的地方，免得之後要重看英文很煩。
Synchronization, Part 3: Working with Mutexes And Semaphores

// An attempt at a thread-safe stack (version 3)
int count;
double values[count];
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void push(double v) { 
  pthread_mutex_lock(&m); 
  values[count++] = v;
  pthread_mutex_unlock(&m);
}
double pop() {
  pthread_mutex_lock(&m);
  double v = values[--count];
  pthread_mutex_unlock(&m);
  return v;
}
int is_empty() {
  pthread_mutex_lock(&m);
  int result= count == 0;
  pthread_mutex_unlock(&m);
  return result;
}

version 3 是thread-safe（我們已經確保所有臨界區的互斥）但是有兩點需要注意：
1. `is_empty `是thread-safe，但它的返回值可能過時了。（用`is_empty`判斷array為空後，可能又有別的thread呼叫push）
2. 沒有做underflow (popping on an empty stack) or overflow (pushing onto an already-full stack)的保護

第二點可以用counting semaphores解決。

sem_t sitems;
sem_t sremain;
void stack_init(){
  sem_init(&sitems, 0, 0);
  sem_init(&sremain, 0, 10);
}

// Sketch #3 (Error!)
double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);
  double v= values[--count];
  sem_post(&sremain);
  return v;
}

void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);
  values[count++] = v;
  sem_post(&sitems); 
}

用counting semaphores確保對array的存取合法，當count=0時sitems也會=0，此時不可pop，反之亦然。
但上述程式碼又沒有對critical section做保護。

// Simple single stack - see above example on how to convert this into a multiple stacks.
// Also a robust POSIX implementation would check for EINTR and error codes of sem_wait.

// PTHREAD_MUTEX_INITIALIZER for statics (use pthread_mutex_init() for stack/heap memory)

pthread_mutex_t m= PTHREAD_MUTEX_INITIALIZER; 
int count = 0;
double values[10];
sem_t sitems, sremain;

void init() {
  sem_init(&sitems, 0, 0);
  sem_init(&sremains, 0, 10); // 10 spaces
}

double pop() {
  // Wait until there's at least one item
  sem_wait(&sitems);

  pthread_mutex_lock(&m); // CRITICAL SECTION
  double v= values[--count];
  pthread_mutex_unlock(&m);

  sem_post(&sremain); // Hey world, there's at least one space
  return v;
}

void push(double v) {
  // Wait until there's at least one space
  sem_wait(&sremain);

  pthread_mutex_lock(&m); // CRITICAL SECTION
  values[count++] = v;
  pthread_mutex_unlock(&m);

  sem_post(&sitems); // Hey world, there's at least one item
}
// Note a robust solution will need to check sem_wait's result for EINTR (more about this later)

最後同時使用counting semaphores做overflow保護，並且用mutex做c.s.保護。

---------------------------------------
[Mutex and Semaphore](https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/Skh9Z2DpX)
Mutex、Semaphore 跟 Binary Semaphore 的差別網路上講解的非常清楚。Google 搜尋的答覆不外乎以下幾種：

1. Ownership 的概念
2. 使用上本質的差異（資料保護或執行緒同步）
3. Mutex 可以，但 Semaphore 所不能解決的問題 (e.g. priority inversion，recursive deadlock)

實際上pthread的mutex有分以下幾種

  PTHREAD_MUTEX_TIMED_NP,(= PTHREAD_MUTEX_NORMAL =  PTHREAD_MUTEX_DEFAULT)
  PTHREAD_MUTEX_RECURSIVE_NP,
  PTHREAD_MUTEX_ERRORCHECK_NP,
  PTHREAD_MUTEX_ADAPTIVE_NP

若mutex使用以下initializer
`pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;`
參考 [man page pthread_mutex_unlock()](https://linux.die.net/man/3/pthread_mutex_lock) 裏面有提到

> If the mutex type is **PTHREAD_MUTEX_DEFAULT**, attempting to
> recursively lock the mutex results in undefined behavior.
> **Attempting to unlock the mutex if it was not locked by the
> calling thread results in undefined behavior.** Attempting to
> unlock the mutex if it is not locked results in undefined
> behavior.

**若mutex是PTHREAD_MUTEX_DEFAULT，它的unlock實作並沒有檢查ownership，所以其他的thread執行unlock也能解鎖成功。**
若想確保此性質須使用
`pthread_mutex_t mutex=PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP;`

[Avoid using PTHREAD_MUTEX_NORMAL type mutex locks](https://wiki.sei.cmu.edu/confluence/display/c/POS04-C.+Avoid+using+PTHREAD_MUTEX_NORMAL+type+mutex+locks)中說到
> This type of mutex does not provide deadlock detection. A thread attempting to relock this mutex without first unlocking it shall deadlock. An error is not returned to the caller. Attempting to unlock a mutex locked by a different thread results in undefined behavior. Attempting to unlock an unlocked mutex results in undefined behavior.
>
因此，不應使用 NORMAL MUTEX，並且在使用mutex時應明確定義使用 ERRORCHECK 或 RECURSIVE MUTEX。

-------------------------------
以下資料來源節錄自[並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads#Synchronization)
* [Mutex vs. Semaphores – Part 1: Semaphores](https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-1-semaphores/)
* [Edsger Dijkstra](https://en.wikipedia.org/wiki/Edsger_W._Dijkstra) 在 1965 年提出 binary semaphore 的構想，嘗試去解決在 concurrent programs 中可能發生的 race conditions。想法便是透過兩個 function calls 存取系統資源 Semaphore，來標明要進入或離開 critical region。
* 使用 Semaphore 擁有的風險
* Accidental release
* This problem arises mainly due to a bug fix, product enhancement or cut-and-paste mistake.
* Recursive deadlock
* 某一個 task 重複地想要 lock 它自己已經鎖住的 Semaphore，通常發生在 libraries 或 recursive functions。
* 某一個 task 其持有的 Semaphore 已經被終止或發生錯誤。
* Priority inversion
* Semaphore as a signal
* **Synchronization** between tasks is where, typically, one task waits to be notified by another task before it can continue execution (unilateral rendezvous). A variant of this is either task may wait, called the bidirectional rendezvous. **Quite different to mutual exclusion, which is a protection mechanism.**
* 使用 Semaphore 作為處理 Synchronization 的方法容易造成 Debug 困難及增加 "accidental release" 類性的問題。

* [Mutex vs. Semaphores – Part 2: The Mutex](https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/)
* 作業系統實作中，需要引入的機制。"The major use of the term mutex appears to have been driven through the development of the common programming specification for UNIX based systems."
* 儘管 Mutex 及 Binary Semaphore 的概念極為相似，但有一個最重要的差異：**the principle of ownership**。
* 而 Ownership 的概念可以解決上一章所討論的五個風險
* Accidental release（別的thread意外執行unlock）
* Mutex 若遭遇 Accidental release 將會直接發出 Error Message，因為它在當下並不是 owner。
* Recursive Deadlock
* 由於 Ownership，Mutex 可以支援(相同的thread) relocking/locking 相同的 Mutex 多次，只要它被 released 相同的次數。
* Priority Inversion
* Priority Inheritance Protocol
* [Priority Ceiling Protocol](https://en.wikipedia.org/wiki/Priority_ceiling_protocol)
* [投影片](https://tams.informatik.uni-hamburg.de/lehre/2016ss/vorlesung/es/doc/cs.lth.se-RTP-F6b.pdf): 介紹 PCP，並實際推導兩個例子。
* Death Detection
* 如果某 task 因為某些原因而中止，則 RTOS 會去檢查此 task 是否擁有 Mutex ;若有, RTOS 則會負責通知所有 waiting 此 Mutex 的 tasks 們。最後再依據這些 tasks 們的情況，有不同的處理方式。
* All tasks readied with error condition
* 所有 tasks 假設 critical region 為未定義狀態，必需重新初始化。
* Only one task readied
* Ownership 交給此 readied tesk，並確保 the integrity of critical region，之後便正常執行。
* Semaphore as a signal
* Mutex 不會用來處理 Synchronization。

* [Mutex vs. Semaphores – Part 3: Mutual Exclusion Problems](https://blog.feabhas.com/2009/10/mutex-vs-semaphores-%E2%80%93-part-3-final-part-mutual-exclusion-problems/)
* 但使用 mutex 還是有一些問題。
* 可能產生Circular deadlock
* One task is blocked waiting on a mutex owned by another task. That other task is also block waiting on a mutex held by the first task.
* Necessary Conditions
* Mutual Exclusion
* Hold and Wait
* Circular Waiting
* No preemption
* Solution: Priority Ceiling Protocol
* 使用 PCP 方法，每個互斥鎖都有一個定義的優先級上限，設置為擁有互斥鎖的任務的ceiling value。 任何使用互斥鎖的任務都以其自己的優先級執行——直到第二個任務嘗試獲取互斥鎖。 第一個任務的優先級被提升到ceiling value，防止了搶佔cpu，從而消除了“Hold and Wait”的情況。
* Non-cooperation
* 我們在解決同步問題時不管是使用semephore還是mutex，都要靠程式設計師自己設計。（易出錯，想要有OS幫忙）
* Solution: Monitor
* Not typically supplied by the RTOS
* A monitor simply encapsulates the shared resource and the locking mechanism into a single construct.
* Access to the shared resource is through a controlled interface which cannot be bypassed.

* [Mutexes and Semaphores Demystified](http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore)
* Myth: Mutexes and Semaphores are Interchangeable
* Reality: 即使 Mutexes 跟 Semaphores 在實作上有極為相似的地方，但他們通常被用在不同的情境。
* The correct use of a semaphore is for **signaling** from one task to another.
* A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects.
* 還有一個重要的差別在於，即便是正確地使用 mutex 去存取共用資源，仍有可能造成危險的副作用。
* 任兩個擁有不同優先權的 RTOS task 存取同一個 mutex，可能會創造 **Priority Inversion**。
* Definition: The real trouble arises at run-time, when a medium-priority task preempts a lower-priority task using a shared resource on which the higher-priority task is pending. If the higher-priority task is otherwise ready to run, but a medium-priority task is currently running instead, a priority inversion is said to occur. [[Source]](https://barrgroup.com/Embedded-Systems/How-To/RTOS-Priority-Inversion)
* 例子:有三個行程（其優先權從高到低分別為T1、T2、T3），有一個臨界資源CS（T1與T3會用到）。這時，T3先執行，取得了臨界資源CS。然後T2打斷T3。接著T1打斷T2，但由於CS已被T3取得，因此T1被阻塞，這樣T2獲得時間片。直到T2執行完畢後，T3接著執行，其釋放CS後，T1才能取得CS並執行。這時，我們看T1與T2，雖然T1優先權比T2高，但實際上T2優先於T1執行。這稱之為優先權逆轉。
* 但幸運的是，Priority Inversion 的風險可以透過修改作業系統裡 mutex 的實作而減少，其中會增加 acquiring and releasing muetexs 時的 overhead。
* 當 Semaphores 被用作 signaling 時，是不會造成 Priority Inversion 的，也因此是沒有必要去跟 Mutexes 一樣去更改 Semaphores 的實作。
* This is a second important reason for having distinct APIs for these two very different RTOS primitives.
*
以下節錄自[Jserv老師](https://hackmd.io/@sysprog/linux-sync?type=view)

在 Linux 核心中，起初僅有 semaphore 這個核心物件 (kernel object)，直到 v2.6.16 核心才將 mutex 自 semaphore 實作中抽離。儘管 Mutex 與 Semaphore 兩者都是休眠鎖，但 Linux 核心實作 mutex 時，運用加速技巧，將上鎖區分以下三個步驟：
1. Fast path: 嘗試使用 atomic operation，減少 counter 數值來獲得鎖
2. Mid path: 上一步若失敗，嘗試使用特化的 MCS spinlock 等待，再取鎖。
* 當持鎖的 thread 還在執行，且系統不存在更高優先權的任務時，即可推定，持鎖的 thread 很快就會把鎖釋放出來，因此會使用一個特化的 MCS spinlock 等待鎖被釋放。特化的 MCS spinlock 可在被重新排程時，退出 MCS spinlock queue。當走到這步時，就會到 Slow path。
3. Slow path: 鎖沒有辦法取得，只好把自己休眠。
* 走到這一步，mutex 才會將自己加入 wait-queue 然後休眠，等待有人 unlock 後才會被喚醒。

這樣付出的代價是，mutex 成為 Linux 核心最複雜的 lock，在 x86-64 的環境下需要使用 40 bytes，相較之下，semaphore 只用 24 bytes，這意味著對 CPU cache 的效率和 cache coherence 的衝擊。

以下節錄自[Important properties of spinlocks](https://geidav.wordpress.com/2016/03/12/important-properties-of-spinlocks/)
## Important properties of spinlocks
通常，當一個線程試圖獲取一個已經鎖定的mutex時，它將進入睡眠狀態並放棄其時間片，從而允許另一個線程立即運行。如果互斥鎖的持有時間非常短，那麼讓等待線程休眠並再次喚醒它重試的時間很容易變長。在這種情況下，可以使用自旋鎖來提高性能，方法是在不休眠的情況下不斷嘗試獲取鎖。注意：在具有單個 CPU 內核的系統中使用自旋鎖是沒有意義的。輪詢自旋鎖只會阻止單個可用 CPU 內核運行另一個線程來釋放鎖。

### 重要性質1:Scalability
現有的不同自旋鎖實現在爭用(contented)下具有非常不同的性能特徵。當有多個線程在獲取鎖時同時嘗試獲取鎖時，就說該鎖是contented。不可擴展的自旋鎖實現的性能隨著嘗試同時獲取鎖的線程數量的增加而下降。例如，簡單的Ticket locks或TAS Locks的性能隨著線程數量的增加呈指數下降。相比之下，可擴展的自旋鎖實現——例如MCS locks – 即使對於大量線程，性能也不會下降。下圖描述了最佳自旋鎖與Tickets locks的可擴充性。
自旋鎖可擴充性的關鍵是獲取和釋放鎖時發生的緩存行失效(cache line invalidations )的數量。緩存行失效發生在例如一個線程修改一個同步變量，同時留下一個臨界區（CS），其他線程同時輪詢該臨界區。突然間，存儲在其他 CPU 內核緩存中的緩存行副本不再有效。因此，這些緩存行必須失效並從修改它的 CPU 內核的緩存中重新獲取。因此，當獲取/釋放自旋鎖時發生的高速緩存行失效的數量通常用作相互比較自旋鎖實現的度量。通常，可伸縮自旋鎖需要 O(1) 多次緩存行失效才能獲取/釋放鎖，而不可伸縮自旋鎖需要 O(#threads) 多次。
進階的可擴展自旋鎖實現可能不僅會考慮系統中 CPU 內核的總數，還會考慮底層緩存一致性機制的細節。例如，在具有多個 CPU 和非統一內存訪問時間 (NUMA) 的系統中，內核間通信成本可能會有很大差異。例如，在具有多個多核 CPU 的 NUMA 系統中，完全有可能將鎖傳遞給同一 CPU 中的另一個內核，所用時間比傳遞給另一個 CPU 的內核的時間要短。
### 重要性質2:Fairness
公平自旋鎖保證如果有其他線程同時嘗試獲取同一個鎖，公平自旋鎖在嘗試獲取鎖的線程之間保持先進先出 (FIFO) 順序。
通常，不公平的自旋鎖用延遲換取吞吐量，而公平的自旋鎖用吞吐量換取延遲。考慮以下示例。假設我們正在運行 t 個線程，每個線程執行 n/t 次循環迭代，它們試圖進入 CS。當使用不公平的自旋鎖時，在最壞的情況下每個線程都可以連續進入 CS n/t 次，而不是在線程之間交替獲取鎖。在某些情況下，這可以顯著提高吞吐量，因為減少了昂貴的高速緩存行失效的數量。但是任何其他線程直到順利進入 CS 的時間都會增加。從理論上講，這會導致飢餓。在實踐中，緩存一致性協議應該確保不會發生飢餓。
通常，當競爭同一個鎖的線程數大於系統中的 CPU 內核數時，公平自旋鎖的性能會急劇下降。原因是序列中下一個獲取鎖的線程可能正在休眠。與不公平自旋鎖相比，在下一個線程休眠期間，由於公平鎖保證了嚴格的獲取順序，因此沒有其他線程可以獲取鎖。此屬性有時稱為 preemption intolerance.。
### 重要性質3:Memory footprint(記憶體占用)
通常，存儲自旋鎖所需的內存量幾乎無關緊要，因為大多數鎖的內存佔用量約為每個線程幾十個字節。但是，在某些情況下，內存佔用量起著重要作用。示例是內存極其受限的環境或需要大量自旋鎖的應用程序，例如用於對大量小塊數據進行細粒度鎖定(fine-grained locking)。