最後更新於 2021 年 10 月 17 日
建議先了解 IPC 再繼續閱讀：作業系統 – Process溝通方式(IPC)
在 Share Memory 方式下可能之問題：Race Condition ( 競爭情況 )
競爭情況
一組Processes在Shared Memory溝通方式下，若未對共享變數提供互斥存取等同歩機制，則會造成共享變數之最終結果値因Processes之間執行順序不同而有所不同，導致不可預期之錯誤發生。
例：有兩個Processes P1及P2，共享一個Count變數，且該變數目前的値為10。現在，P1 及P2各作一次Count加1與減1之動作，則Count可能有不止一種結果。
為維護資料的一致性需要機制以確保合作行程間有次序地執行，並且同時段只能有一個Process使用該變數。
解決競爭情況之策略：
- Disable Interrupt (停止使用中斷)
- Critical Section Design (臨界區間設計)
停止使用中斷(Disable Interrupt)
為了確保對共享變數進行存取時不會被中斷，所以在該指令敘述執行之前先 Disable Interrupt，完成敘述後再Enable Interrupt。
- 優點：簡單，易於實施
- 缺點：只適用於Single Processor環境，不適用於Multiprocessor 環境。(∵Performance變差，且風險性增加)
- 因為在Multiprocessor環境下關掉單顆CPU的中段功能沒有用，要全部的CPU中斷功能都關掉才有用。
- Disable Interrupt的作法會導致其它更緊急的工作無法執行。
臨界區間設計(Critical Section Design)
臨界區間：在程式中，針對共享變數進行存取之指令敘述所形成之集合。
- 當一個行程在臨界區間時，不允許其它的行程在該臨界區間。
- 非 Critical Section(C.S.) 之指令敘述集合稱為 Remainder Section (剩餘區間:R.S.)
- 每一個行程必須要求允許才能進入臨界區間的入口區段，緊跟著臨界區間的出口區段(exit section) ，然後是剩餘區段(remainder section)
臨界區間問題
- 互斥(mutual exclusion)： 如果有一行程正在臨界區間內執行，則其它的行程不能在其臨界區間內執行。
- 進行(Progress)： 如果沒有行程在臨界區間內執行，同時有些行程想要進入臨界區間，在外面等待的行程必須在有限的時間內進入臨界區。
必須同時滿足下方兩個要件：
a. 不想進入C.S.的Process不可以阻礙其它Process進入C.S.
b. 必須在有限的時間內，自那些想進入C.S.的Process之中，挑選出一個Process進入C.S. (隱含：避免Deadlock) - 限制住的等待(bound waiting)： 在一個行程已經要求進入其臨界區間，而此要求尚未被答應之前，允許其它的行程進入其臨界區間的次數有一個限制。
- 自Process提出進入C.S.之申請，到它獲准進入C.S.之等待時間是有限的。即：若有 n 個Processes想進入C.S.，則任一Process至多等待 n-1次，即可進入C.S. (隱含：No Starvation)
解決臨界區間問題的方法
Peterson演算法
假設有兩個process不可中斷，共享兩個變數：
int turn // 代表輪到誰進入臨界區間 Boolean flag[2] // 用來標示哪個行程準備就緒進入臨界區間
flag[i] = true 表示Pi準備進入它的臨界區間。
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
} while (true); 證明
- 互斥性存在
- 進行的要求能被滿足
- 限制性的等待要求亦能符合
分析
- 滿足Mutual Exclusion
turn值僅會是 i 或 j 不會兩者皆是。
若Pi想要執行，則 flag[j] = false 或 turn = i (代表 j 不想執行，或是優先權在 i 手上)。 - 滿足Progress
以 Pj 要執行為前提，可能發生三種情況：- Pi不想執行 Pj 直接進入
- Pi、Pj 同時想執行，優先權在i手上(turn = i)，Pi 先執行
- Pi、Pj 同時想執行，優先權在j手上(turn = j)，Pj 先執行
- 滿足Bounded Waiting
假設Pi 與Pj 皆想進入自已的C.S. ，且此時Pi 已先進入C.S.，而Pj 卡在while loop 等待。若Pi 離開C.S.後又企圖立刻進入自已的C.S.，此時Pi 一定會執行 turn = j 之設定，使得Pi 無法再搶先於Pj 進入自已的C.S.而被卡在while loop 等待。所以對Pj 而 言，它至多等待一次即可進入C.S.。
同步硬體
- 許多系統對於臨界區間程式碼提供硬體支援
- 所有的解都是以鎖(locking)為前提
- 藉由鎖保護臨界區間
目前的機器提供特殊不可分割(Atomic)的硬體指令，主要有兩種方式：
- 測試記憶體字元組或設定數值 (test_and_set 指令)
- 交換兩個記憶體字元組的內容 (compare_and_swap 指令)
do {
acquire lock
critical section
release lock
remainder section
} while (true);test_and_set 指令
把值寫到一個新的地方，回傳舊值
test_and_set Instruction不會被中斷，以下是他的定義：
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = true;
return rv:
}共用 boolean 變數 lock一開始設為 false
解決方法：
do {
while (test_and_set(&lock)); // do nothing
/* critical section */
lock = false;
/* remainder section */
} while (true); lock是共享的變數，當執行test_and_set(&lock)，會將lock變數記憶體的位置傳入test_and_set()這時會被上鎖，等執行完後lock才會被解鎖。
compare_and_swap 指令
compare_and_swap指令不可被中斷，下方為它的定義：
int compare and swap(int *value, int expected, int new value) {
int temp = *value;
if (*value == expected)
*value = new value;
return temp;
} 共用 boolean 變數 lock一開始設為 false; 每一個行程有一個區域Boolean變數 key
解決方法：
do {
while (compare and swap(&lock, 0, 1) != 0); /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
} while (true);lock是共享變數，初始值為0 (0代表不能進去，1代表可以進去)，當執行compare_and_swap(&lock , 0 , 1)，會去比對lock跟expected的值，如果相同就會把值做交換。
互斥鎖(Mutex Lock)
- 前面的解答很複雜，並且應用程式人員無法接觸到。
- OS設計者可以建立軟體工具來解決臨界區間的問題。
- 最簡單的是互斥鎖(mutex lock)。
- 行程在進入臨界區間前必須呼叫函數acquire()取得鎖；離開臨界區間前呼叫函數release()釋放鎖。
- Boolean變數available用來表示鎖是否可以使用。
- acquire()和release()必須是不可中斷的函數。
- 通常藉由硬體的不可分割指令製作。
- 但這個解答要求忙碌等待(busy waiting)。
- 這種型態的互斥鎖被稱為自旋鎖(spinlock)。
acquire() {
while (!available); /* busy wait */
available = false;;
}
release() {
available = true;
}
do {
acquire lock
critical section
release lock
remainder section
} while (true); 號誌(Semaphore)
- 不需要忙碌等待的同步工具
- 號誌 S –整數變數
- 兩個標準操作修改 S: wait() and signal()
- 原先稱為 P() 和 V()
- 比較不複雜
- 只能藉由2個不可不分割(atomic)的運算存取
wait (S) {
while (S <= 0); // busy wait
S--;
}
signal (S) {
S++;
}利用wait()和signal()來改變，當執行完wait()則S減1，而執行完signal()則S加1。當S = 0時，就要等到執行完signal()才能再執行wait()。
簡單的同步問題
假設有P1和P2兩個 Current Execution的Processes如下： 今規定“S1的敘述一定要在S2敘述之前執行”，請利用Semaphore滿足此一問題設計。
Ans:
宣告一個共享變數S: Semaphore，初値為0。
因為當 S = 0 時需要等待，直到 signal(S) 執行後 S++，S不再 <= 0 的時候才能去執行 S2。
號誌的用法
- 計數號誌(Counting semaphore ) – 範圍不受限制的整數值
- 二元號誌(Binary semaphore) – 數值可以是0或1
- 可以用來取代互斥鎖
號誌製作
- 必須保證沒有兩個行程可以對相同的號誌同時執行 wait() 和 signal()。
- 因此，製作變成臨界區間問題，wait 和signal 程式碼被放在臨界區間。
- 應用程式可能耗費很多時間在臨界區間，因此這不是一個好的解結方法。
典型的同步問題
典型的同步問題被用來測試每一個新提出的同步技術
- 有限緩衝區問題
- 讀取者-寫入者問題
- 哲學家進餐的問題
有限緩衝區問題
n個緩衝區,每一個緩衝區保存一項資料
- 號誌 mutex 一開始設定為 1
- 號誌 full 一開始設定為 0
- 號誌 empty 一開始設定為 n
生產者行程的結構
do {
... /* produce an item in next_produced */
...
wait(empty);
wait(mutex);
... /* add next produced to the buffer */
...
signal(mutex);
signal(full);
} while (true);消費者行程的結構
do {
wait(full);
wait(mutex);
... /* remove an item from buffer to next_consumed */
...
signal(mutex);
signal(empty);
... /* consume the item in next consumed */
...
} while (true);讀取者-寫入者問題
- 一個資料集可以被一些並行的行程所共用
- 讀取者– 只能讀取資料集;它們不能執行資料集
- 寫入者– 可以讀和寫資料集
- 問題
- 同一時間只有一個寫入者可以存取資料
- 讀取者和寫入者如何被對待有許多不同的方法，所有的方法都牽涉到優先權
- 共用資料
- 資料集
- 號誌 rw_mutex 一開始設定為 1
- 號誌 mutex 一開始設定為 1
- 整數 read_count 一開始設定為 0
寫入者行程的結構
do {
wait(rw mutex);
... /* writing is performed */
...
signal(rw mutex);
} while (true);讀取者行程的結構
do {
wait(mutex);
read count++;
if (read count == 1)
wait(rw mutex);
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read count--;
if (read count == 0)
signal(rw mutex);
signal(mutex);
} while (true);哲學家進餐
- 哲學家一次只能拿一枝筷子
- 需要兩枝筷子才能吃，吃完同時放下兩枝筷子
- 在5哲學家的情況，共用資料：
- 碗裡的飯(資料集)
- 號誌 chopstick [5] 開始時設定為1
哲學家 i 的結構
do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (true);
![1582557657 Ngmvlql8zgWiDyS [楓之谷私服]小遊戲系列NPC腳本(2) - BJ、GEMS、OX遊戲、Mastermind、猜數字](https://namepluto.com/wp-content/uploads/2021/09/1582557657_Ngmvlql8zgWiDyS-150x150.png "[楓之谷私服]小遊戲系列NPC腳本(2) - BJ、GEMS、OX遊戲、Mastermind、猜數字 1582557657 Ngmvlql8zgWiDyS")
