# **背景**
* 進程可以並發執行 => 但可能隨時被中斷，部分完成執行
* 對共享數據的併發訪問可能導致數據不一致
* 保持數據一致性需要機制來確保協作進程的有序執行
* 當我們使用由生產者和消費者同時更新的計數器(counter)來考慮有界緩衝區問題時，這導致了競爭關係(Race Condition)
## **競爭條件(Race Condition)**
`counter++` 可以利用以下程式碼實現
```
register1 = counter
register1 = register1 + 1
counter = register1
```
`counter--` 可以利用以下程式碼實現
```
register2 = counter
register2 = register2 - 1
counter = register2
```
為什麼不直接`counter = counter + 1`?
=> Value can be calculated in ALU of CPU.(ALU can only work on registers)
考慮這個執行最初與「count = 5」交錯
S0: producer execute register1 = counter {5=5, register1 = 5}
S1: producer execute register1 = register1 + 1 {6=5+1, register1 = 6}
S2: consumer execute register2 = counter {5=5, register2 = 5}
S3: consumer execute register2 = register2 – 1 {4=5-1, register2 = 4}
S4: producer execute counter = register1 {6=6, counter = 6}
S5: consumer execute counter = register2 {4=4, counter = 4}
但這裡是先counter++在counter- -，S5這邊的counter應該要是5才對，這就是Race Coundition
* Race condition：當多個進程同時訪問並操作共享數據時出現的情況，共享數據的最終值取決於哪個進程最後完成
* 為了防止Race condition，我們需要確保同一時間只有一個thread可以操作變量計數器。為了做出保證，需要對進城進行某種形式的同步
* 進程 P0 和 P1 使用 fork() 系統調用創建子進程
* 對內核變量 next_available_pid 進行競爭條件，該變量表示下一個可用的進程標識符（pid）
* 除非有一個機制防止 P0 和 P1 訪問變量 next_available_pid，否則相同的 pid 可能被分配給兩個不同的進程！
# **Critical-Section Problem**
* 考慮一個由n個進程{p0，p1，... pn-1} 組成的系統
* 每個進程都有一段代碼，稱為關鍵區段，在該區段中
* 每個進程可能會更改共享變量、更新表格、寫入文件等
* 問題在於確保當一個進程處於關鍵區段時，其他任何進程都不得處於其關鍵區段中，即互斥。
=>critical section can only work individually independently at the same time.
* Critical-Section Problem是設計一個協議來解決這個問題
* 每個進程必須在進入關鍵區段時請求許可，在進入區段後可能會跟隨關鍵區段的退出部分，然後是剩餘部分。
下圖是while迴圈的做法，先做entry section，如果有符合條件就執行critical section，然後接著執行exit section，同樣如果有符合條件就執行remainder section
## 解決critical-section problem的要求：
1. Mutual Exclusion(互斥性) - 如果進程 Pi 正在執行其關鍵區段，其他進程不能同時在其關鍵區段中執行。
2. Progress(進展性) - 如果沒有進程正在執行其關鍵區段，且存在一些希望進入其關鍵區段的進程，則下一個進入關鍵區段的進程的選擇不能**無限期地**延遲。
3. Bounded Waiting(有界等待) - 在一個進程發出進入其關鍵區段的請求並且該請求被授予之前，允許其他進程進入其關鍵區段的次數必須有一個限制。
* 假設每個進程以非零速度執行
* 對於進程的相對速度沒有任何假設
## Interrupt-based Solution
* Entry section：disable interrupts
* Exit section：enable interrupts
* 這樣做能解決問題嗎？
* 如果critical section是運行一小時的代碼呢？=> 一些進程可能會被餓死，永遠無法進入它們的critical section。
* 如果有兩個 CPU 呢？
## Software Solution 1
* 兩個進程的解決方案(it can not work if it have three process or more)
* 假設load(加載)和store(存儲)的機器語言指令是atomic(原子的)，即不能被中斷
* 這兩個進程共享一個變量：
* `int turn;`
* 變量 `turn` 表示進入critical section的是誰的回合
* 最初，`turn` 的值設置為 i（某一特定值）
## Algorithm for Process Pi
```
while (true){
while (turn == j);
/*critical section*/
turn = j;
/*remainder section*/
}
```
## Correctness of the Software Solution
* 互斥性被保持
=> 只有當 turn = i 時，進程 Pi 才能進入關鍵區段，且 turn 不可能同時為 0 和 1。
* what about the Progress/Bounded-waiting requirement？
# Peterson's Solution
* 兩個進程的解決方案
* 假設load和store的機器語言指令是atomic，即不能被中斷
* 這兩個進程共享兩個變量：
* `int turn;`
* `boolean flag[2];`
* 變量 turn 表示進入關鍵區段的是誰的回合
* flag 數組用於指示進程是否準備進入關鍵區段。flag[i] = true 意味著進程 Pi 準備就緒
## Algorithm for Process Pi
```
while(true){
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
/* critical section */
flag[i] = false;
/* remainder section */
}
```
while loop中，進程 Pi 首先將 flag[i] 設置為 true，表示它準備進入關鍵區段，然後將 turn 設置為 j，表示現在是進程 j 的回合。然後進程 Pi 進入一個循環，檢查 flag[j] 是否為 true 且 turn 是否等於 j，如果是，表示現在是進程 j 的回合且進程 j 準備就緒，則進程 Pi 等待。一旦進程 j 結束了它的關鍵區段，flag[j] 會被設置為 false，進程 Pi 可以進入關鍵區段執行操作，然後在剩餘區段將 flag[i] 設置為 false，表示進程 Pi 完成了它的關鍵區段。
## Correctness of Peterson’s Solution
保證滿足三個關鍵區段的要求：
1. 互斥性被保持
=>進程 Pi 只有在 flag[j] = false 或者 turn = i 時才能進入關鍵區段。
2. 進展性要求得到滿足
3. 滿足有界等待要求
## Peterson’s Solution and Modern Architecture
* 儘管Peterson’s Solution對於演示算法很有用，但不能保證在現代架構上正常工作。
* 為了提高性能，處理器和/或編譯器可能會重新排序沒有依賴關係的操作。
* 了解為什麼它不起作用對於更好地理解競爭條件是有用的。
* 對於單線程來說，這是可以的，因為結果將始終相同。
* 對於多線程來說，重新排序可能會產生不一致或意外的結果。
## Modern Architecture Example
* Two threads share the data：
```
boolean flag = false;
int x=0;
```
* Thread 1 performs：
```
while(!flag){
print(x);
}
```
* Thread 2 performs：
```
x=100;
flag = true;
```
* 這裡預期的結果應該是在Thread 1 的地方輸出100
=>然而，由於變數flag跟x是相互獨立的，因此指令：flag = true; x = 100； Thread 2可能會重新排序。如果發生這種情況，輸出可能會變成0
**To improve system performance, processors and/or Compilers may reorder read and write operations that have no dependencies.**
## Peterson's Solution
* Peterson's Solution中指令重新排序的影響
這會導致兩個processes同時處在他們的Critical section中
為了確保Peterson's Solution在modern computer architecture上正確工作，我們必須使用**Memory Barrier(內存屏障)**。
## Memory Barrier
* Memory Model是computer architecture(計算機架構)對application programs(應用程式)的memory guarantees(內存保證)
* Memory Model可以是：
* Strongly ordered(強排序) – 其中一個處理器對內存的修改立即對所有其他處理器可見
* Weakly ordered(弱排序) – 其中一個處理器對內存的修改可能不會立即對所有其他處理器可見
* Memory Barrier是一種特殊的指令，他用於確保內中的修改對所有處理器受可見的。Memory Barrier會強制執行內存操作的序列，以確保任何後續的讀寫或寫入操作不會被重新排序，從而維護了內存的一致性。
## Memory Barrier Instructions
* 內存屏障指令的作用是，系統確保在執行任何後續的加載或存儲操作之前，所有的加載和存儲操作都已完成。
* 因此，即使指令被重新排序，內存屏障確保存儲操作在內存中完成並對其他處理器可見，然後才執行後續的加載或存儲操作。
## Memory Barrier Example
利用上面**Modern Architecture Example**的例子，可以利用下指令中添加Memory Barrier來確保Thread 1輸出100：
Thread 1 now perform：
```
while (!flag)
memory_barrier();
print x
```
Thread 2 now perform：
```
x = 100;
memory_barrier();
flag = true;
```
* 對於 Thread 1，我們保證 flag 的值在 x 的值之前加載。
* 對於 Thread 2，我們確保將值分配給 x 發生在將值分配給 flag 之前。
# Synchronization Hardware(同步硬件)
* 許多系統提供硬件支持來實現critical section code
* Uniprocessors(單處理器) - 可以禁用中斷
* 當前運行的code將在沒有搶占的情況下執行
* 在多處理器系統上通常效率太低
* 使用此方法的操作系統不具有廣泛的可擴展性
* 我們將介紹三種形式的硬件支持：
1. Hardware instructions(硬件指令)
2. Atomic variables(原子變量)
## Hardware instructions
* 特殊的硬件指令允許我們在原子（不可中斷）地測試和修改一個字的內容，或者原子地交換兩個字的內容。
* 測試和設置指令（Test-and-Set instruction）
* 比較和交換指令（Compare-and-Swap instruction）
### Test-and-Set instruction
* Definition：
```
boolean test_and_set(boolean *target){
boolean rv = *target; (rv=false)
*target = true; (*target=true)
return rv： (rv=false回傳)
}
```
**test=>original
set=>new value(這裡的new value是true)**
* Properties：
* 原子地執行
* 返回傳遞參數的原始值
* 將傳遞參數的新值設置為 true
### Solution Using test_and_set()
共享的boolean variable `lock`，初始化為 false
=>lock = true，do nothing
lock = false，exit loop，go into CS
Solution：
```
do {
while (test_and_set(&lock))
;/* do nothing */
/* critical */
lock = false;
/* remainder section */
} while (true);
```
這個解決方案解決了關鍵區段問題嗎？
是的，這個解決方案使用了 test_and_set() 指令來實現互斥性。當一個進程進入關鍵區段時，它將 lock 設置為 true，其他進程在 while 循環中等待 lock 變為 false。這確保了同一時間只有一個進程可以進入關鍵區段。
### Compare-and-Swap instruction
* Definition
```
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
```
* Properties：
* 原子地執行
* 返回傳遞參數 value 的原始值
* 只有當 *value == expected 時，才將變量 value 的值設置為傳遞的 new_value。換句話說，只有在這個條件下才進行交換。
### Solution using compare_and_swap
共享整數變量 `lock`，初始化為 0
Solution:
```
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
```
這個解決方案解決了Critical-section problem嗎？
是的，這個解決方案使用了 compare_and_swap() 指令來實現互斥性。當一個進程想要進入Critical-section時，它將 lock 的值從 0 更改為 1，這樣其他進程就無法進入關鍵區段。這確保了同一時間只有一個進程可以進入關鍵區段。
但是，這個解決方案不滿足bounded-waiting condition，因為一個進程可能無限期地等待 lock 變為 0，而不允許其他進程進入關鍵區段。
### Bounded-waiting with compare-and-swap
```
while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare_and_swap(&lock, 0, 1);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
```
這個解決方案中，當一個進程希望進入關鍵區段時，它會設置 waiting[i] 為 true，然後使用 compare-and-swap 指令將 lock 的值從 0 更改為 1。如果在這期間有其他進程正在關鍵區段中（即 waiting[i] 為 true），或者有其他進程已經設置了 key 為 0，那麼這個進程將繼續等待。
一旦進程進入了Critical-section，它會將 waiting[i] 設置為 false。然後它會在剩餘部分檢查是否還有其他進程在等待，如果沒有則將 lock 設置為 0，否則將下一個等待的進程設置為 false，以便它可以進入關鍵區段。這樣，所有進程都有機會進入關鍵區段，從而滿足了有界等待條件。
## Atomic Variables
* Atomic Variables通常是使用比較和交換等指令作為其他同步工具的基礎。
* 其中一個工具是Atomic Variables，它提供了對基本數據類型（如Integer和boolean）的原子（不可中斷）更新。
* 例如：
* 讓 sequence 是一個Atomic Variables
* 讓 increment() 是對Atomic Variables sequence 的操作
* 命令 increment(&sequence); 確保 sequence 在沒有中斷的情況下進行增量操作。
* Atomic Variables的增量操作可以實現如下：
```
void increment(atomic_int *v) {
int temp;
do {
temp = *v;
} while (temp != (compare_and_swap(v, temp, temp + 1)));
}
```
這段代碼中，我們通過比較和交換（compare_and_swap）指令來實現原子的增量操作。首先，我們讀取原子變量的當前值並將其存儲在 temp 中。然後，使用 compare_and_swap() 函數來嘗試將原子變量的值從 temp 更改為 temp + 1。如果 compare_and_swap() 返回的值等於 temp，則說明成功將原子變量的值增加了 1，否則我們需要重新讀取原子變量的值並重試操作，直到成功。這樣可以確保增量操作是原子且不可中斷的。
# Mutex Locks
* 先前的解決方案較為複雜，通常對應用程序開發者不太可用
* 操作系統設計者構建了軟件工具來解決關鍵區段問題
* 最簡單的是mutex lock
* 使用一個boolean variable來指示lock是否可用
* 利用以下指令保護critical-section
* 首先要acquire() a lock
* 然後再release() the lock
* acquire()和release()的調用必須是原子的
* 通常通過硬件原子指令（如 compare-and-swap）實現
* 但這種解決方案會導致busy waiting(Why?)
* 因此這種lock稱為spinlock
## Solution to CS Problem Using Mutex Locks
```
while (true) {
acquire_lock();
/* critical section */
release_lock();
/* 剩餘部分 */
}
```
在這個解決方案中，我們使用了一個無限循環來保證持續地執行。在循環內部，首先調用 acquire_lock() 函數來獲取互斥鎖，這將確保在進入關鍵區段之前，只有一個進程可以獲取鎖。然後，執行關鍵區段的代碼。完成關鍵區段後，調用 release_lock() 函數來釋放鎖，以允許其他進程進入關鍵區段。最後，執行剩餘部分的代碼。這樣可以確保同一時間只有一個進程可以進入關鍵區段，從而解決了關鍵區段問題。
# Semaphore
* Semaphore是一種比mutex lock更複雜的同步工具，用於進程同步它們的活動。
* 信號量 S 是一個整數變量。
* 只能通過兩個不可分割（原子）操作來訪問：
* wait() 和 signal()
* （最初被稱為 P() 和 V()）
* wait() 操作的定義：
```
wait(S) {
while (S <= 0); // 忙等待
S--;
}
```
* signal() 操作的定義：
```
signal(S) {
S++;
}
```
在 wait() 操作中，當 S 小於等於 0 時，進程將進入忙等待狀態，直到 S 變為正數為止，然後將 S 減 1。在 signal() 操作中，S 將被增加 1。這樣就可以使用信號量來實現進程間的同步。
* 計數信號量（Counting semaphore）- 整數值可以在無限域範圍內變化
* 二進制信號量（Binary semaphore）- 整數值只能在0和1之間變化
* 與mutex lock相同
* 可以使用Binary semaphore來實現Counting semaphore
* 使用semaphore，我們可以解決各種同步問題。
## Semaphore Usage Example
* 解決Critical-section problem的示例：
* 創建一個名為 "mutex" 的semaphore，初始化為 1
```
wait(mutex); // 進入CS
// CS的代碼
signal(mutex); // 離開CS
```
* 考慮 P1 和 P2 兩個進程，其中有兩個語句 S1 和 S2，並且要求 S1 必須在 S2 之前執行：
* 創建一個名為 "synch" 的信號量，初始化為 0
```
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
```
P1=>declare that the S1 has completed by placing synch there
P2=>after getting the synch (means S1 has com pleted), S2 can continue
在這個例子中，當 P1 執行完 S1 後，通過 signal() 函數釋放 "synch" 信號量，以允許 P2 繼續執行。當 P2 遇到 wait() 函數時，將等待 "synch" 信號量被釋放，然後執行 S2。這樣可以確保 S1 必須在 S2 之前執行。
Synch=0
| P1 | P2 |
|:----------------------:| -------------------- |
| S1 | |
| Signal(Synch)=>Synch=1 | |
| | wait(Synch)=>Synch=0 |
| | S2 |
## Semaphore Implementation with no Busy waiting
* 每個信號量都有一個相應的等待隊列
* 等待隊列中的每個項目都有兩個數據項：
* 值（類型為整數）
* 指向列表中下一個記錄的指針
* 有兩個操作：
* block：將調用該操作的進程放置在適當的等待隊列上
* wakeup：從等待隊列中移除一個進程並將其放置在就緒隊列中
* Waiting queue
```
typedef struct {
int value;
struct process *list;
} semaphore;
//
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
// 將這個進程添加到 S->list
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
// 從 S->list 中移除一個進程 P
// 喚醒進程 P
wakeup(P);
}
}
```
這個實現中，wait 操作將Semaphore的值減 1，如果減少後的值小於 0，則將調用該操作的進程添加到信號量的等待隊列中，然後將該進程阻塞。而signal 操作將Semaphore的值增加 1，如果增加後的值小於等於 0，則從Semaphore的等待隊列中移除一個進程，並將其喚醒。
## Problems with Semaphores
* 在使用信號量操作時可能出現的問題：
* 不正確地使用信號量操作：
* signal(mutex) 後跟 wait(mutex)
* wait(mutex) 後跟 wait(mutex)=>
* 省略 wait(mutex) 和/或 signal(mutex)
=> 應該要先wait(mutex) 再 signal(mutex)
* 這些以及其他情況都是信號量和其他同步工具使用不正確時可能出現的例子。
# Monitors
* 是一種高層次的抽象，提供了一個方便有效的進程同步機制(abstraction=>means contained inside，packed inside)
* 是一種抽象數據類型，internal variable(內部變量)只能由程序內部的代碼訪問=>protected
* 在監視器中一次只能有一個進程處於活動狀態
* 監視器的偽代碼語法：
```
monitor monitor-name {
// shared variable declarations(共享變量聲明)
function P1 (...) { .... }
function P2 (...) { .... }
function Pn (...) { ...... }
initialization code (...) { ... }
}
```
在這裡，monitor-name 是監視器的名稱，P1、P2、Pn 是監視器的方法或操作，initialization code 是初始化監視器的代碼塊。監視器內部的變量只能由監視器內部的方法訪問，確保了對共享資源的安全訪問。
## Schematic view of a Monitor
## Monitor Implementation Using Semaphores(Skip)
* 變量 semaphore mutex，初始化為 1
* 每個程序 P 被替換為：
```
wait(mutex);
// P 的主體
signal(mutex);
```
這樣就確保了監視器內的互斥。在這個實現中，每個進程在訪問監視器內容之前都需要獲取 mutex 信號量，這樣就保證了同一時間只有一個進程可以訪問監視器內的變量和方法。當進程完成對監視器的訪問後，會釋放 mutex 信號量，讓其他進程可以訪問監視器。這樣就確保了在監視器內部的互斥。
## Condition Variables
* condition x, y;
* Condition Variables(條件變量)上允許兩種操作：
* x.wait() - 調用該操作的進程被暫停，直到 x.signal() 被調用
* x.signal() - 恢復調用了 x.wait() 的一個進程（如果有的話）
* 如果沒有 x.wait() 在該變量上被調用，則對該變量的操作不會產生影響
## Monitor with Condition Variables
## Usage of Condition Variable Example
* 考慮 P1 和 P2 需要執行兩個語句 S1 和 S2，並且要求 S1 必須在 S2 之前執行：
* 創建一個監視器，其中包含兩個程序 F1 和 F2，分別由 P1 和 P2 調用
* 一個條件變量 "x"，初始化為 0
* 一個布爾變量 "done"
* F1:
```
S1;
done = true;
x.signal();
```
* F2:
```
if done = false
x.wait();
S2;
```
在這個示例中，P1 和 P2 分別調用監視器中的 F1 和 F2。當執行 F1 時，先執行 S1，然後將 done 設置為 true，最後通過 x.signal() 喚醒可能在 x 上等待的進程。當執行 F2 時，如果 done 為 false，則進程將在 x 上等待，直到被其他進程通過 x.signal() 喚醒。一旦 done 為 true，進程將執行 S2。這樣就確保了 S1 必須在 S2 之前執行。
## Monitor Implementation Using Semaphores
* 變量：
* semaphore mutex; // 初始值為 1
* semaphore next; // 初始值為 0（用於等待進程挂起）
* int next_count = 0; // 在監視器內等待的進程數量（用於計算挂起在 next 上的進程數）
* 每個函數 F 將被替換為：
```
wait(mutex);
// F 的主體
// 如果有進程在 next 上等待，則釋放 next 信號量
// 否則釋放 mutex 信號量
if (next_count > 0)
signal(next)
else
signal(mutex);
```
這樣就確保了監視器內的互斥。當進程進入監視器時，它首先獲得 mutex 信號量，這樣就確保了同一時間只有一個進程能夠訪問監視器內的方法。在進程離開監視器時，它根據等待在 next 信號量上的進程數量來決定是釋放 mutex 還是 next 信號量，這樣就確保了監視器內的互斥。
## Monitor Implementation – Condition Variables
* 對於每個條件變量 x，我們有：
```
semaphore x_sem; // 初始值為 0
int x_count = 0;
```
* x.wait() 操作可以實現為：
```
x_count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x_count--;
```
在這個實現中，當一個進程調用 x.wait() 時，它首先將 x_count 增加 1。然後，它檢查是否有進程在 next 信號量上等待，如果有，則釋放 next 信號量，否則釋放 mutex 信號量。接著，進程將等待在 x_sem 信號量上，直到被其他進程通過 signal() 喚醒。當進程被喚醒後，它將 x_count 減少 1。這樣就確保了對條件變量的等待和釋放是原子操作，同時也確保了監視器內的互斥
* x.signal() 操作可以實現為：
```
if (x_count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
```
在這個實現中，當一個進程調用 x.signal() 時，它首先檢查是否有進程在 x 上等待（即 x_count > 0）。如果有等待的進程，則將 next_count 增加 1，並通過 signal() 喚醒一個在 x_sem 上等待的進程。被喚醒的進程將從等待中恢復，然後將 next_count 減少 1。這樣就確保了對條件變量的信號操作是原子且有效的。
## Resuming Processes within a Monitor
* 如果有多個進程在條件變量 **x** 上排隊，並且執行了 **x.signal()**，那麼應該恢復哪個進程呢？
* 先到先得 (FCFS) 經常不夠用
* 使用條件等待（conditional-wait）結構形式 x.wait(c)，其中：
* c 是一個整數（稱為優先級數）
* 具有最低數字（最高優先級）的進程被安排為下一個執行
## Single Resource allocation
* 在競爭進程之間分配單個資源，使用優先級號碼指定進程計劃使用資源的最大時間。
* 最短時間的進程首先被分配資源。
* 讓 R 是 ResourceAllocator 類型的一個實例。
* 通過以下方式訪問 ResourceAllocator：
```
R.acquire(t);
// 訪問資源
R.release;
```
這裡的 t 是進程計劃使用資源的最大時間。
## A Monitor to Allocate Single Resource
```
monitor ResourceAllocator {
boolean busy;
condition x;
void acquire(int time) {
if (busy)
x.wait(time);
busy = true;
}
void release() {
busy = false;
x.signal();
}
initialization code() {
busy = false;
}
}
```
| P1 | P2 | P3 |
| ----------------------------- | ----------- |:-----------:|
| acquire(10) | | |
| | acquire(20) | |
| | x.wait(20) | |
| | | acquire(15) |
| | | x.wait(15) |
| release();busy=false;x.signal | | |
這個監視器實現了資源的分配和釋放功能。當一個進程嘗試獲取資源時，如果資源已經被佔用，它會等待，直到資源被釋放或達到最大等待時間。當資源被釋放時，它會喚醒可能在等待的進程。初始化代碼用於初始化 busy 變量。
* 使用方法：acquire...release
* 監視器操作的不正確使用：
* release() ... acquire()
* acquire() ... acquire()
* 忽略 acquire() 和/或 release()
# Liveness
* 在嘗試獲取同步工具（如互斥鎖或信號量）時，進程可能不得不無限等待。
* 無限等待違反了本章開頭討論的進度和有界等待標準。
* 活性是指系統必須滿足一組屬性，以確保進程能夠取得進展。
* 無限等待是活性失敗的一個例子。
* 死鎖：兩個或多個進程無限期地等待只有其中一個等待進程才能引發的事件
* 假設 S 和 Q 是兩個初始化為 1 的信號量
* 考慮如果 P0 執行 wait(S)，而 P1 執行 wait(Q)。當 P0 執行 wait(Q) 時，它必須等待直到 P1 執行 signal(Q)
* 然而，P1 正在等待直到 P0 執行 signal(S)。
* 由於這些 signal() 操作永遠不會被執行，P0 和 P1 陷入了死鎖狀態。
* 其他形式的死鎖：
* 飢餓（Starvation）：無限阻塞
* 一個進程可能永遠不會從它被暫停的信號量隊列中移除
* 優先級反轉（Priority Inversion）：一個低優先級的進程持有一個高優先級進程所需的鎖時，出現的調度問題
* 通過優先級繼承協議解決
## 優先級繼承協議（Priority Inheritance Protocol）
* 考慮以下情境：有三個進程 P1、P2 和 P3。P1 的優先級最高，P2 次之，P3 最低。假設進程 P1 需要一個由進程 P3 持有的資源 R。因此，P1 必須等待 P3 使用完該資源。然而，當進程 P2 可以運行並搶占了 P3 時，發生了這樣的情況：一個優先級低於 P1 的進程 P2 間接地阻止了 P3 獲得該資源的訪問。
* 為了防止這種情況發生，使用了優先級繼承協議。這個協議簡單地允許將等待訪問共享資源的最高優先級的線程的優先級分配給當前正在使用該資源的線程。因此，資源的當前擁有者的優先級被賦予了希望獲得該資源的最高優先級線程的優先級。
# **Important sentence**
1. Value can be calculated in ALU of CPU.(ALU can only work on registers)(20)
2. when one porcess in critical section，no other may be in its critical section
3. who set up the value of `turn` will decide the final value of `turn`(97)
4. when exit the loop，it will check the array to see who should be the next one to go into Critical-section(263)
5. busy waiting is not good because it will consume CPU power and waste CPU cycle(315)
6. The semaphore is not available and it must go to the waiting list(405)
Sign in with Wallet
Connect another wallet