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++ 時，其實在電腦是編譯成三行程式碼

register1 = count => LOAD Reg, Count
register1 = register1 + 1 => ADD #1
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

Software：純粹利用軟體演算法來控制流程，不須花費硬體裝置。優點：不用花錢購買新硬體，利用的資源較少。缺點：programmer 必須多花費心思，程式設計上不容易。因為必須考慮中斷的情形發生。
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 改良

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

如果現在是空的，consumer 想要去拿東西，執行 wait(mutex)，再執行 wait(full)，但因為現在沒有東西可以拿，所以要 wait 了並且要讓出 cpu，但是現在 lock 被他搶走了，所以造成 deadlock
如果現在是滿的，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 卻會十分複雜

雖然助教的答案長這樣…

CH6 行程排班 (Process Scheduling)

Bounded-Buffer

改良後

Race Condition

Critical Section

Critical Section Protocol

Critical Section 的條件

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

旗標演算法 flag （問題 : 一直在互讓）

Peterson’s Combined Solution

mutual exclusion

progress

bounded waiting

證明 critical section

Lock

Synchronization Hardware

Test and set （寫入某個記憶體位置，回傳舊值）

Swap（把 a、b 值交換）

Bakery Algorithm (N processes solution)

麵包演算法概念

麵包演算法實作

麵包演算法分析

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

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

Mutex (mutual exclusion) Locks

Semaphore

Semaphore 實作

Semaphore 的缺點 busy waiting

semaphore 改良

問題

Four Typical Uses of Semaphores

Deadlock and Starvation

deadlock

starvation

Priority Inversion

Priority Inversion

Priority Inheritance

synchronization 經典問題

Bounded-Buffer Problem

Bounded-Buffer - 問題

Reader-Write Problem

規則

變數說明

實作

問題

Dining-Philosophers Problem

規則

變數說明

實作

問題

Semaphoro 的缺點

Monitor （公廁的概念）

Signal and wait

Signal and continue

利用 monitor 解決 哲學家問題

實作

資料區（變數說明）

初始區

程序區

問題

比較 semaphore monitor

利用 monitor 解決哲學家問題