最後更新於 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);
- Express + MongoDB 實作使用者增刪改查 API 及登入 API - 2022 年 7 月 2 日
- 解決 React Highcharts 資料筆數過多造成圖表渲染卡頓的情形 - 2022 年 6 月 28 日
- React 那些好看、有趣、實用的函式庫、組件庫推薦(2) - 2022 年 6 月 26 日