Post

CH6 行程排班 (Process Scheduling)

Bounded-Buffer

  • in 代表 buffer 中下一個可以放資料的位置
  • out 代表 buffer 中第一個可以取資料的位置

  • Consumer

    • in = out 代表 buffer 是空的

      [ x ][ x ][ x ][ x ]
      in---
      out---
  • Producer

    • (in + 1) % BUFFER_SIZE = out 代表 buffer 是滿的

      [ o ][ o ][ o ][ x ]
      ---in
      out---
  • 雖然 solution is correct ,但只可以使用到 BUFFER_SIZE -1 個 elements

改良後

多一個 count 變數來計算現在用了幾個 buffer

  • 初始值 count = 0
  • producer 做完就 +1
  • consumer 做完就 -1

Race Condition

在進行 count++ 時,其實在電腦是編譯成三行程式碼

  1. register1 = count => LOAD Reg, Count
  2. register1 = register1 + 1 => ADD #1
  3. count = register1 => STORE Reg, Count

執行 count++ 過程中,如果突然 cpu 的執行權被 count– 搶走了,會發生資料錯誤

例如:當 counter = 6 時,將產生 5、6、7 三種可能結果

這種情形叫做 Race Condition,Synchronization 是來預防此情形發生

Critical Section

Critical Section 是一段不能讓多個行程同時執行的程式碼。

  • 某個 process 在執行他的 Critical Section 時,其他的 process 不能在這段時間內進入他們的 Critical Section 。
  • 一個行程在修改與其他行程所共有的資料,可以將修改共有資料的這段程式碼,寫在 Critical Section 中解決
  • 可以解決 process 在 share data 可能造成資料不一致的問題。
  • 必須同時符合 Mutual Exclusion (互斥)、Progress (進行)與 Bounded Waiting (有限等待)三項條件。
Critical Section Protocol

entry section => critical Section => exit section

Critical Section 的條件

  • Mutual Exclusion (同時只有一個 process 執行他的 cs)
    • 如果某個 process 在執行他的 Critical Section 時,其他的 process 不能在這段時間內進入他們的 Critical Section
  • Progress (要有進度不能卡住)
    • 不想進入 critical section 的 process 不可以阻礙其它 process 進入 critical section,即不可參與進入 critical section 的決策過程。
    • 必須在有限的時間從想進入 critical section 的 process 中,挑選其中一個 process 進入 critical section,隱含 No Deadlock。
  • Bounded Waiting (不能一直無限等)
    • 自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入,則任一 process 至多等待 n-1 次即可進入,隱含 No starvation。
  • 解決的方法不能 depend on process 的 relative speed 和 scheduling policy

交替演算法 turn (問題 : 別人給我 turn 才可以做)

  • 共用一個變數 turn,指出目前允許進入 critical section 的是哪一個 process
  • 滿足 mutual exclusion
    • turn 的值不可能同時為 i 和 j,所以一次只能一個進入 cs
  • 不能滿足 progress
    • 假設現在 turn = i,但是 Pi 並不想進入 cs,Pj 想進入 cs,Pj 就沒辦法進入(一定要等待 Pi 做完把 turn = j,Pj 才可以做)
    • Pj 被 Pi block
  • 滿足 bounded waiting
    • 若 Pi 和 Pj 都想進入 cs,此時 turn = i,所以 Pi 先進入 cs,Pj 就先等待
    • 等到 Pi 離開之後又想進入 cs 時,Pi 會被卡住,因為 Pi 離開的時候有把 turn = j
    • 所以對於 Pj 而言,他最多等待一次就可以進入 cs

旗標演算法 flag (問題 : 一直在互讓)

  • 將交替演算法中共有的變數 turn 改為共有的陣列 flag,記錄系統中個別 process 的狀態。
  • 一開始將陣列所有元素都設為 FALSE
  • 如果 Pi 要進入 critical section,則將 flag[i] 設為 TRUE,並檢查 flag[j],若 flag[j] 為 TRUE,則 Pi 要等 Pj 執行完再進入 critical section
  • 當 Pi 離開 critical section 後,再將 flag[i] 設為 FALSE。讓其他 process 可以接著進入 critical section
  • 滿足 mutual exclusion 的條件
  • 不能滿足 progress 和 bounded waiting 的條件
    • 當 Pi 與 Pj 皆將 flag[i], flag[j] 皆設為 TRUE,則永遠跳不出 while 迴圈(互讓) => deadlock

Peterson’s Combined Solution

  • 解決 2 個 process
  • LOAD、STORE 這兩個 instructions 是 atomic (最小單位),代表不能被 interrupted
  • 2 個 process 共用這 2 個變數
    • boolean flag[2] : 每個 process 是否想要進入他的 critical section,想要的就設為 TRUE
      • 初始值都是 FALSE
    • int turn : 目前系統允許哪個 process 進入 critical section
      • 初始值設為 i 或 j

要證明就是把 那三個條件都證明過

mutual exclusion

  • 證明兩個 process 同時都在他們的 critical section
    1. (flag[j] && turn == j) 和 (flag[i] && turn == i)都要是 false
    2. 現在 flag[i] 和 flag[j] 一定是 true
    3. 所以只能 turn == j 和 turn == i 都是 false
    4. 但 turn 不是 = i 就是 = j 所以其中一個是 true,另一個是 false,所以假設不成立
    5. 符合 mutual exclusion

progress

  • 目前沒有 process 在 cs,如果有一個 process 要進去他的 cs,一定可以進去
  • 多個 process 要進去 cs 時,在有限時間內要做出決定
    1. 如果 Pi 有興趣,那就會在 while(flag[j] && turn == j)
    2. Pj 目前沒有興趣
      1. flag[j] = false,Pi 就可以進去 cs
      2. 後來 Pj 有興趣了,flag[j] = true 完,會 turn = i,Pi 就可以進去 cs
    3. 符合 progress

bounded waiting

  • 找出次數的上限
    1. 如果 Pi 有興趣
    2. 如果 Pj 不在他的 cs,那 flag[j] = false,Pi 可以進去了
    3. 如果 Pj 正在他的 cs,等 flag[j] = false,Pi 就可以進去了
    4. 如果 Pj 在 entry section,如果 Pi 先執行 while 就可以進去了。否則 Pj 進去,Pi 要等到 Pj 把他的 flag[j] = false 才能進去
    5. 符合 bounded waiting

證明 critical section

  • Mutual exclusion
    • 假設兩個(以上)的 processes 可以同時進出 CS, 找出其矛盾
  • Progress
    • 沒有 process 在 CS 中,一個 process 要進去 CS,一定可以進去
    • 多個 process 要進 CS,在有限的時間內做出決定
  • Bounded waiting
    • 找出次數的上限

Lock

acquire lock => critical section => release lock

Synchronization Hardware

  • 單 CPU 的系統中,可以很簡單地讓行程在修改共用的變數時,停止接受中斷而解決同步的問題。
  • 但是在多 CPU 的系統中並不合適,因為停止所有 CPU 的中斷除了很耗時間之外,也會增加行程進入 critical section 所花費的時間。
  • 現代機器提供特殊 atomic hardware instructions _ Atomic : non-interruptable _ Test and set (TS) : test memory word and set value * Swap : contents of two memory words

Test and set (寫入某個記憶體位置,回傳舊值)

  • Definition
    • TestAndSet 指令會傳回參數 target 目前的值,並同時將 target 的值設為 TRUE
    • 在執行完整個指令之前都不會被中斷
  • Solution
    • 利用共用變數 lock 並將初始值設為 false
  • 滿足 mutual exclusion
    1. 現在 Pi 和 Pj 都想進去 cs
    2. Pi 先執行 TestAndSet ,然後 return false 並且把 lock 的值設為 true,進到 cs
    3. Pj 執行 while()的時候,return true 並且把 lock 的值設為 true,所以一直卡在 while
  • 滿足 progress
    • 不想進 cs 的 process 不會去搶 TestAndSet 的指令
    • 有限時間內,一定會有人搶到 TestAndSet,所以一定有人可以進 cs
  • 不滿足 bounded waiting
    • Pi 已經進 cs 了,而 Pj 卡在 while loop 中等待要進 cs,此時如果 Pi 離開 cs,又想進 cs,Pi 很有可能再度先於 Pj 執行 TestAndSet 指令,而再度進到 cs,所以 Pj 可能會 Starvation

Swap(把 a、b 值交換)

  • Definition
    • Swap 指令會交換參數 a 與 b 兩個記憶體的內容。
    • 在執行完整個指令之前都不會被中斷。
  • Solution
    • 利用共同變數 lock 並將初始值設為 false,每一個 process 有個 local 變數 key 來與 lock 做交換
  • 滿足 mutual exclusion
    1. 現在 Pi 和 Pj 都想進去 cs,key 都會設成 true
    2. Pi 先執行 Swap,然後 lock 和 key 會交換,因此 lock = true、key = false,Pi 就可以進 cs
    3. Pj 執行 Swap 時,因為 lock = true,所以交換後 lock = true、key = true,這時候 Pj 就會卡在 while loop
  • 滿足 progress
    • 不想進 cs 的 process 不會去搶 swap 指令
    • 有限時間內,一定會有人搶到 swap 指令,所以一定有人會進入 cs
  • 不滿足 bounded waiting
    • Pi 已經進 cs 了,而 Pj 卡在 while loop 中等待要進 cs,此時如果 Pi 離開 cs,又想進 cs,Pi 很有可能再度先於 Pj 執行 swap 指令,而再度進到 cs,所以 Pj 可能會 Starvation

Bakery Algorithm (N processes solution)

麵包演算法概念
  • 每位顧客(process)到店中會領一張號碼牌,店家依號碼牌依序服務客戶。
  • number 可能會重複,但 Process ID 是唯一的。如果有 process 拿到相同的號碼,會以 pid 較小的優先
麵包演算法實作
  • boolean chooseing[1,…,n-1]
    • 預設 false
    • true 代表我想進去
    • false 代表我不想進去
  • int number[1,…,n-1]
    • 預設 0
    • 0 代表我不想進去(或是做完了)
    • 大於 0 代表我的號碼
  • (a , b) < (c , d)
    • 如果 a < c 或 (a = c 或 b < d)
    • a、c 代表 number,b、d 代表 pid
  • max(a0,a1,…an-1) return 裡面最大的值

麵包演算法分析
  • 滿足 mutual exclusion
    1. 一開始 choosing 都設為 false,number 都設為 0
    2. 現在 Pi 和 Pj 都想進去 cs,choose[i] = true,choose[j] = true,各自領了號碼牌,再將 choose[i] = false,choose[j] = false
    3. Pi 先執行第二個 while,順利的進入 cs
    4. Pj 想進去,但因為 (number[i],i) < (number[j],j),所以 Pj 一直被卡在第二個 while 沒辦法進去 cs
    5. 滿足 mutual exclusion
  • 滿足 progress

    1. 如果 Pj 不想進入 critical section,其 Number[i] = 0 且 Choosing[i] = false。如果此時 Pi 想進入 critical section 時,就不會被 Pj 卡在 while 中 = > Pj 並不會阻擋 Pi 進入 critical section
    2. 如果現在有多個 processes 想進入各自的 critical section,因為有領號碼牌,所以一定可以在有限的時間內,找出一個最小的號碼牌或是同為最小號碼牌但 pid 比較小的 process 進入 critical section
  • 滿足 bounded waiting
    • 依照 number 讓 process 先到的先做,別人不可以插隊,只要等到 number 比他小的 process 做完,就可以進去 cs 了,所以進到 cs 的次數是有限的
  • 額外問題
    1. Is it possible that many processes receive the same number?
      • 有可能,因為取號碼牌可以分成三個動作
        1. 挑最大值
        2. 加 1
        3. 將結果 assign 給 number[i] => Pi 和 Pj 有相同 number 值
    2. If we remove the first while loop (i.e., while(Choosing[j]); ), the mutual exclusion is still maintained?
      • 不正確,會違反 mutual exclusion
      • 假設現在 choosing[0]~choosing[n-1] 皆為 0
      • 現在有兩個 process Pi 和 Pj 想進去 cs,且 Pi pid < Pj pid

  • while(Choosing[j]); 這行
    • 代表想要比較的 process 正在拿號碼牌(拿到一半、搞不好還沒有號碼),你要等人家拿完才可以做比較啊,搞不好人家的號碼牌比你小耶

Bounded-waiting Mutual Exclusion with TestAndSet() (TestAndSet 另一種方法)

  • process 共用變數 waiting 陣列,紀錄哪些 process 正在等待進入 cs
    • 初始值 false
  • lock 代表目前 cs 是否可以進去
    • 初始值 false
  • mutual exclusion
    • 如果有一個 process 想進去 cs 時,會將 lock 設為 true,其他想進去的 process 只能卡在 while 那邊等,當進去的 process 想離開的時候,會在出口區把下一個 waiting[j] = false,讓下一個 process 可以進來,因此符合 mutual exclusion。
  • progress
    • 若沒有 process 等著進入 cs,要離開 cs 的 process 會將 lock 變數設為 FALSE,也會將下一個 process 的 waiting 陣列值設為 FASLE,讓只要有等待進入 cs 的 process,一定可以進入,因此滿足了 progress 的條件
  • bounded waiting
    • 如果現在有 n 個 processes,離開 critical section,process 設定 waiting 陣列值的方法,是依序檢查到 process 的 waiting 陣列值為 TRUE,就把他設為 false,所以每個 process 最多只會等待 n-1 次,就可以進入 critical section,所以滿足 bounded waiting 的條件。

critical section 中,硬體演算法和軟體演算法的比較

  • 都會 busy waiting
  1. Software:純粹利用軟體演算法來控制流程,不須花費硬體裝置。 優點:不用花錢購買新硬體,利用的資源較少。 缺點:programmer 必須多花費心思,程式設計上不容易。因為必須考慮中斷的情形發生。
  2. Hardware:利用硬體來製造不可分割的指令或是 disable 中斷來實作。 優點:programmer 設計程式較為容易。 缺點:要花錢購買硬體裝置。 _ 只有 kernel mode 能用 _ need time _ 多處理機上會失效,單處理機上不好(busy waiting) _ starvation

Mutex (mutual exclusion) Locks

  • 用 acquire() 取得 lock (atomic)
  • 用 release() 釋放 lock (atomic)
  • 來保護 critical section
  • 若無法取得 lock,則進入 busy waiting

Semaphore

  • Semaphore 是一個同步物件,用於保持在 0 至指定最大值之間的一個計數值。(Semaphore 不需要 busy waiting,用到 waiting queue)
  • 大部分的作業系統都已經實作了 Semaphore,作為行程同步的工具
  • 變數 int S (Semaphore) 記錄著有多少 process 可以再進入 cs
  • S 的存取只能用 wait() signal(),這兩個方法都是 atomic 不可中斷
  • 必須保證沒有兩個 process 可以同時執行 wait() 和 signal(),也就是說要把 wait()和 signal() 也放入 critical section

  • binary semaphore

    • integer value can range only between 0 and 1; can be simpler to implement
    • Also known as mutex locks

    • 現在有兩個 P1 的 statement 叫 S1,P2 的 statement 叫 S2
    • 我們想要 S2 只在 S1 完成後才執行

    • 共用變數 mutux 初始值是 1
    • force suspend 初始值是 0

Semaphore 實作

Semaphore 的缺點 busy waiting
  • 如果已經有 process 進入了 cs,那麼其他想要進入 cs 的 process 都會在入口區中一直地執行迴圈來等待,會很浪費 cpu
  • busy waiting 的 semaphore => spinlock 旋轉鎖。
  • 為了避免忙碌等待所造成的 CPU 資源浪費,可以修改 wait() 和 signal() 兩個函式。
semaphore 改良
1
2
3
4
typedef struct {
int value;
struct process *list; //waiting queue
} semaphore;

  • block()
    • wait() 呼叫時,執行 S->value– 完,如果其值 <0,不讓 process busy waiting,直接讓 process 將自己 block 起來
      • 放這些 process 的地方叫做 waiting queue
  • wakeup()
    • 把 process 從 waiting queue 移出

問題
  • waiting list 如果使用不適當的實作方式,例如後進先出串列,可能會造成無限阻隔或是飢餓現象。
    • 可以使用先進先出串列來實作號誌串列。
    • 必須保證 wait() 和 signal() 在執行的過程中不會被中斷(atomic)。
  • 改良後的 semaphore 雖然不能完全不使用 busy waiting,但是大幅地縮短了 busy waiting 的時間。
  • 由整個 cs 縮短到只有實作 wait() 和 signal()的 cs 所造成的 busy waiting。
  • 可以提高系統的效能。

Four Typical Uses of Semaphores

  • Mutual exclusion
    • Mutex locks
  • Force suspend
    • Keep the execution in a particular order
  • Count-down lock
    • A semaphore has an implicit counter
  • Notification
    • Indicate that an event has occurred

  • S1 = 1 ,S2 = 0
    • output => 1 2 1 2 1 2
  • S1 = 0 ,S2 = 1
    • output => 2 1 2 1 2 1
  • S1 = 0 ,S2 = 0
    • S1、S2 都會被卡在 wait,無法繼續執行下去
  • S1 = 1 ,S2 = 1
    • S1、S2 同時進入 cs,output 會取決於誰先搶到 cpu,有無限多種可能

Deadlock and Starvation

deadlock

  • 兩個或多個 processes 在無限等待,可能是因為一個 process 在等待某一項資源

  • 例如 S、Q 初始值為 1,signal()永遠不會被執行到,所以行程 deadlock

starvation

  • 在 semaphore waiting queue 裡面無限等待

Priority Inversion

  • 當低優先權的 process 有 高優先權的 process 的 lock 會產生排程問題
Priority Inversion
  • 假設有三個 processes Task1、Task2、Task3,其優先權順序是 H > M > L

Priority Inheritance
  • 優先權繼承協定必須允許 Task3 暫時地繼承 Task1 的優先權,因此才能阻止 Task2 搶先它的執行。

synchronization 經典問題

  • bounded-buffer
  • readers and writers
  • dining-philosophers

Bounded-Buffer Problem

  • n 個 buffers
  • mutex
    • 初始值為 1
  • full
    • 初始值為 0
    • 使用過的欄位
  • empty
    • 初始值為 n
    • 空的欄位
  • 如果 buffer 是 full,producer 會被 block
  • 如果 buffer 是 empty,consumer 會被 block

Bounded-Buffer - 問題

  • 如果 mutex 在 full、empty 之外,則當全空或全滿時會形成 deadlock
  1. 如果現在是空的,consumer 想要去拿東西,執行 wait(mutex),再執行 wait(full),但因為現在沒有東西可以拿,所以要 wait 了並且要讓出 cpu,但是現在 lock 被他搶走了,所以造成 deadlock
  2. 如果現在是滿的,producer 想要去放東西,執行 wait(mutex),再執行 wait(empty),但因為現在是滿的所以沒辦法放東西,所以就要 wait 了並且讓出 cpu,但是 lock 現在被他搶走了,所以也會造成 deadlock

Reader-Write Problem

  • 一個系統中經常會有數個 processes 共同分享同一份資料物件
  • 如果一個讀取者和一個寫入者同時存取所共享的資料,可能會發生錯誤
規則
  • readers:
    • 只能讀 data set,不能更改
    • 可允許同時很多 reader 一起讀資料
  • writers:
    • 可以讀和寫
    • 同一時間只能有一個 writer 可以更改資料
  • 如果 writer 在寫,reader 就不能讀
  • 如果還有 reader 在讀,writer 就不能寫
    • reader 的優先權比較高
變數說明
  • int readcount
    • 記錄正在讀取資料的讀取者數目
    • 初始值為 0
  • semaphore wrt
    • 如果 writer 正在寫的時候,要 block reader
    • 初始值為 1
  • semaphore mutex
    • readcount 的 mutex
    • 初始值為 1
實作

  • 第一個 reader 要讀的時候,如果有 writer 在,那 reader 就會被卡在 wait(wrt)
  • 最後一個 reader 要離開的時候,要 signal(wrt) 通知 writer
  • 當 writer 要離開的時候,如果後面有 reader 和 writer 在等,這時候由 scheduler 來決定誰可以先進
  • 如果有一個 writer 離開,後面有 reader 進了,那麼所有在 waiting 的 reader 也會跟著進去
問題
  • First variation
    • 除非 writer 可以使用 shared object,不然不能讓 reader 等待
  • Second variation
    • 當 writer 已經 ready 後,就立刻 write
  • 以上兩種都可能會造成 starvation
  • 解決方法
    • 部分作業系統由核心的 kernel 提供

Dining-Philosophers Problem

規則
  • 有 5 位哲學家和 5 枝筷子
  • 哲學家思考時,就不會用餐
  • 如果哲學家想吃飯時,要依序拿取位於左右兩邊的筷子,進行用餐
  • 用餐完畢,要把筷子放下

變數說明
  • semaphore chopstick [5]
    • 初始值為 1
實作

  • 當哲學家要吃飯的時候,要 wait(左邊筷子),wait(右邊筷子),都有才可以吃飯,吃完飯要,signal(左邊筷子),signal(右邊筷子)
問題
  • deadlock
    • 當毎位哲學家依序拿起位於自己左邊的筷子後,則毎位哲學家都拿不到右邊的筷子,而呈現全部 wait,無人可 eating 的情況
  • 解決 deadlock
    1. 限制用餐人數:最多允許 4 位哲學家同時用餐
      • 此法雖無 deadlock,但有 starvation
    2. 規定除非哲學家可以順利取得左右兩邊的筷子,否則,哲學家不准拿任何筷子
      • 打破 Hold and Wait
    3. 採用非對稱作法:奇數號的哲學家先拿左、再拿右,偶數號的哲學家先拿右、再拿左。
      • 打破 Circular Wait
    4. 採用 Monitor 來解

Semaphoro 的缺點

  • Programmer 可能會誤用 Semaphore 的 wait 及 signal 運作,導致錯誤的状況發生:
    • 違反 Mutual Exclusion
    • 造成 Dead Lock

Monitor (公廁的概念)

  • 為一個解決同歩問題的高階資料結構(物件導向),由以下三部份組成:
    • 共享資料區
      • 此區域會宣告一些共享變數,且只提供給 Monitor 內各 Procedure 所共用,外界 Process 不得直接使用。
      • monitors 沒有 public data
    • 初始區
      • 設定某些共享資料變數的初値
    • 一組 Procedures (Operations)
      • 供外界呼叫使用
  • Monitor 本身已經確保 mutual exclusion 的性質
    • 一次只有一個 process 可以進去

  • 為解決同步問題,Monitor 會提供一種特殊型態的變數供 Programmer 使用:Condition 型態變數
  • 假設宣告 x 為 condition 型態變數
    • condition x
  • 則在 x 變數上,會提供 2 個 Atomic Operations:
    • x.wait()
      • 強迫 Process 暫停,並把該 Process 放入 x 的 Waiting Queue 中
    • x.signal()
      • 如果有 Process 卡在 x.wait 的 Waiting Queue 中,則此運作會從該 Waiting Queue 中取出第一個 Process,將其 wakeup。否則 x.signal 無任何作用。
  • condition 形態的變數並沒有 value and cannot be modified

  • 可以有四種狀態
    • Active
      • 正在 running
    • Entering
      • 被 monitor block 住
    • Waiting
      • 等 condition 變數
    • Inactive
      • Those waiting on the waiting bench
Signal and wait
Signal and continue

利用 monitor 解決 哲學家問題

實作

資料區(變數說明)
  • 每個哲學家會有三種不同的狀態(State):thinking, hungry, eating
  • 當哲學家發生搶不到筷子的情況(Condition)時之同步處理
初始區
  • 每個 Process 的初始狀態皆設定為 thinking
  • 不需針對 Condition 型態變數設定初值,因為它是用來卡住哲學家
程序區
  • 每個 Procedure 的輸入參數皆為哲學家編號
  • 哲學家 i 在拿起筷子(pickup)時:
    • 先將自已的狀態設成飢餓(hungry)
    • 再測試(test)左右兩邊的人是否正在 eating;
      • 若是,代表搶不到兩枝筷子,則會將自已卡住(wait)而去睡覺。
      • 若否
        • 則將自已設成 eating 狀態。
        • 若哲學家先前曾因搶不到筷子而被卡住(wait),則將會被喚醒(signal);否則 signal 指令無作用。
        • 【因為被卡住的哲學家不會喚醒自已 ! 而是有別的哲學家因吃完飯、放下筷子(putdown)時嘗試將他喚醒以進行吃飯】
  • 哲學家 i 在放下筷子(putdown)時:
    • 先將自已的狀態設成思考(thinking)
    • 再測試(test)左右兩邊的人是否因為我在 eating 而被卡住;若有,則解救他們,讓他們可以吃飯。
問題
  • 雖然沒有 deadlock,但還是有可能 starvation

比較 semaphore monitor

使用 monitor 可以輕易地模仿出 semaphore 的效果, 可是使用 semaphore 來模擬 monitor 卻會十分複雜

雖然助教的答案長這樣…

This post is licensed under CC BY 4.0 by the author.