Chapter 10 Process Communication
前一章 | 首頁- Process Communication的方式
- Message Passing(少考)
- 型式
- 指令
- 解決同步問題
- Link Capacity, Message Lost, Process Addition/Deletion
- Share Memory
- Producer/Consumer Problem
- Algorithm 1：利用Buffer的n-1空間
- Algorithm 2：充分利用Buffer的n個空間
- 可能的問題
- 結果不正確
- Race Condition
- 解決策略
- Disable Interrupt
- Critical Section Design
- Critical Section
- Def
- 程式架構
- Design What?
- Critical Section Design必須滿足的三個性質
- Mutual Exclusion
- Progress
- Bounded Waiting
- Critical Section Design的方法
- Software Solution
- Hardware Instruction支援
- Semaphore(號誌) (同步問題解法)
- Monitor (同步問題解法)
- Critical Region (同步問題解法)
- 同步問題之解決
- Producer/Consumer Problem
- Reader/Writer Problem
- First
- Second
- Dining Philosopher Problem
- Sleeping Barber
- Smoking
- Critical Section
- Producer/Consumer Problem
- Message Passing(少考)
Process Communication的方式(資訊交換、同步)
- Message Passing
- Share Memory
| Message Passing | Share Memory | |
|---|---|---|
| 溝通方式 | Process之間要溝通，需
| Process彼此之間透過對共享變數的存取，藉由其值之變化達到溝通(同步)之目的 |
| 共用性 | Link是專屬於溝通之雙方，不會被其它人共用 | 共享變數是所有processes皆可存取 |
| OS支援 | OS會提供如Link Management等額外支援 | OS僅提供Share Memory空間，不提供任何額外支援 |
| Programmer負擔 | 輕(OS Load較重) | Programmer負擔重 |
| 其它機制 | 需提供如Link Creation, Link Capacity控制, Message Lost等處理機制 | 需提供對共享變數之互斥存取控制，否則會有問題 |
Share Memory溝通方式下的可能問題
- 執行結果不正確(不如預期)
- Rece Condition
例：Producer/Consumer Problem
- Def：
Producer：產生資訊供其它process使用者
Consumer：消耗其它人所產出之item者 - 在Share Memory溝通方式之下：
在此model之下，可再細分為兩種- Bounded Buffer Producer/Consumer(★)
- 當Buffer為滿，則Producer被迫wait
- 當Buffer為空，則Consumer被迫wait
- UnBounded Buffer Producer/Consumer
- Producer無須wait
- 當Buffer為空，則Consumer被迫wait
- Bounded Buffer Producer/Consumer(★)
Bounded Buffer Producer-Consumer Problem之程式
Algorithm 1：頂多利用Buffer n-1個空間
- 共享變數 宣告：
- n→Buffer size
- Buffer[0..n-1] of item (circular array)
- in, out：integer = 0
- Producer之程式片段如下
- Consumer程式之片段如下：
repeat ... produce an item in nextp; ... while((in + 1) mod n == out) do no-op; //成立：Buffer滿，Busy-waiting型式 Buffer[in] = nextp; in = (in + 1) mod n; until false
repeat while(in == out) do no-op; //成立：Buffer空 nextc = Buffer[out]; out = (out + 1) mod n; ... counume the item in nextc until false
OSC Section 4.4
- share variables:
#difine BUFFER_SIZE 10 typedef struct { ... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; - producer:
while (1) { /* produce an item in nextProduced */ while (((int + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; } - consumer:
while (1) { while (in == out) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; /* consume the item in nextConsumed */ }
Algorithm 2：充分利用n個空間
- 共享變數 宣告：多加一個Count：integer變數
- 0(初值)：表Buffer為空
- n：表Buffer為滿
- Producer：Count++;
- Consumer：Count--;
- Producer之程式片段如下
- Consumer程式之片段如下：
意義：
Count(Buffer資料個數) =
repeat ... produce an item in nextp; while(Count == n) do no-op; Buffer[in] = nextp; in = (in + 1) mod n; Count = Count + 1; ... until false
repeat while(Count == 0) do no-op; nextc = Buffer[out]; out = (out + 1) mod n; Count = Count - 1; ... counume the item in nextc until false
OSC 7.1
int counter = 0;
- producer:
while (1) { /* produce an item in nextProduced */ while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; } - consumer:
while (1) { while (counter == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; /* consume the item in nextConsumed */ }
Share Memory溝通下的可能問題
- 執行結果不正確(結果不正確)
例：Producer Consumer ------------------------------------- Count = Count +1 Count = Count -1
Count為此二個processes之共享變數
假設Count值目前為5，且Producer會作一次加1動作，Consumer會作一次減1動作
我們預期Count之正確值為5，然而Count值卻可能為4(或為6)，此為不正確之結果說明：
Count = Count + 1可以分解成下列三條機器指令(或組合語言指令)
- Register1 = Count
- Register1 = Register1 + 1 (INC)
- Count = Register1
- Register2 = Count
- Register2 = Register2 - 1
- Count = Register2
T0：(P) Register1(5) = Count(5) T1：(C) Register2(5) = Count(5) T2：(P) Register1(6) = Register1 + 1 T3：(C) Register2(4) = Register2 - 1 T4：(P) Count(6) = Register1 T5：(C) Count(4) = Register2
∴最後，Count值為4
∴不正確 - Race Condition(執行順序不同、值不同)
- Def：
一組processes在以Share Memory溝通方式下，若未對共享變數提供互斥存取控制(或未能確保對共享變數進行存取的敘述在執行時，不會受到任何中斷干擾，而能一口氣順利完成才釋放CPU)則共享變數的最後結果值會因為processes之間的執行順序不同而有所不同例：
執行順序若為： 1→4→2→5→3→6⇒則Count值為4
1→4→2→5→6→3⇒則Count值為6
or
1→2→3→4→5→6⇒則Count值為5
4→5→6→1→2→3⇒則Count值為5
∴Race Condition Occurs
Race condition: The situation where several processes access – and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. - Def：
Share Memory溝通問題之解決策略
- Disable Interrupt
- Def：
為確保共享變數之存取敘述執行時不受任何中斷干擾，可以automically executed，可以採序如下方式Disable Interrupt 執行敘述 Enable Interrupt
- 優點：simple，易於實施，適用於uniprocessor(單一CPU)環境
缺點：不適用於Multiprocessors環境，因為效益很差- 說明：process需發出Disable Interrupt請求給各其它CPUs，並且必須等到所有其它CPUs回覆"Interrupt已Disable"之回應訊息，才可以執行敘述
同時，完成後，再發訊息通知其它CPUs Enable Interrupt
- 說明：process需發出Disable Interrupt請求給各其它CPUs，並且必須等到所有其它CPUs回覆"Interrupt已Disable"之回應訊息，才可以執行敘述
- Def：
- Critical Section Design
目的：提供對共享變數之存取的互斥控制，確保資料的正確性
Critical Section(臨界區間)
- Def：
process中對共享變數進行存取的敘述之集合區間 - Processi之程式架構
repeat entry section critical section exit section remainder section until false - Critical Section Design
是在Design Entry Section及Exit Section
- Figure 7.1 General structure of a typical process Pi.
do{ entry section critical section exit section remainder section }while(1); - Figure 7.2 The structure of process Pi in algorithm 1.
do { while (turn != 1); critical section turn = j; remainder section }while(1);
Critical Section Design必須滿足的三個性質
- Mutual Exclusion
Def：
最多只允許一個process在其Critical Section內活動，若其它processes也想進入它們本身的Critical Section，則必須等待值到該process離開Critical Section才能再擇一進入(即不允許多個processes在各自Critical Section內同時活動) - Progress
Def：- 不想進入Critical Section的process(即在Remainder Section內活動)，不能妨礙(阻止)其它process進入Critical Section
(不能參與進入Critical Section的決策過程) - 決定哪個process可以進入Critical Section的時間是有限的(不能無窮止境)⇒No DeadLock
- 不想進入Critical Section的process(即在Remainder Section內活動)，不能妨礙(阻止)其它process進入Critical Section
- Bounded Waiting
Def：
自process提出欲進入Critical Section的請求到其獲准進入Critical Section的等待時間是有限的(⇒No starvation)
若有n個processes欲進入Critical Section，則任一process至多等待(n-1)以後必可進入Critical Section
- Mutual Exclusion
If process Pi is executing in its critical section, then no other processes can be executing in their critical sections. - Progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. - Bounded Waiting
A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.- Assume that each process executes at a nonzero speed
- No assumption concerning relative speed of the n processes.
Software Solution for Critical Section Design
- 2個processes
- Algorithm 1 (x)
- Algorithm 2 (x)
- Algorithm 3 (ok)
- n個processes
- Algorithm 4 (ok)
- Bakery's Algorithm (ok)
2個processes之software solution
Algorithm 1
假設Pi與Pj兩個processes- 共享變數之宣告
turn：integer，值為i或為j，初值無所謂 (turn：權杖) - Pi之程式片段如下：
repeat //while(條件式) do no-op; ⇒ Busy waiting while(turn ≠ i) do no-op; //若權杖≠i，則Pi wait critical section turn = j; //將turn交給Pj remainder section until false;
- 滿足Mutual exclustion (∵turn不會同時為i且為j)
- 不滿足"Progress"(i)
說明：
若Pi不想進入critical section(或Pi在remainder section內活動)
且目前turn值為i。此時，若Pj想進入critical section
則Pj無法進入critical section(∵turn為i，∴Pj卡在while(turn≠j)do no-op;中)
∴Pj被Pi所妨礙(阻止)進入critical section - 有滿足Bounded waiting
Algorithm 1
- 共享變數之宣告
flag[i..j] of boolean; (false:表無意願；trun：有意願)
初值：flag[i] = flag[j] = false - Pi之程式片段如下：
repeat
flag[i] = true; //表明Pi有意進入critical section while(flag[j])do no-op; //flag[j]成立，表Pj也有意進入 ∴Pi waitcritical section flag[i] = false; remainder section until false;
不滿足"Progress"(ii)
說明：
Pi Pj ------------------------------------------------------------------- T0：flag[i]=true T1：flag[j]=true T2：while(flag[j])do no-op;(Pi卡) T3：while(flag[i])do no-op;(Pj卡)∴Deadlock發生
Algorithm 3
Algorithm 1：turn-權力Algorithm 2：flag-意願
- 共享變數之宣告
- flag[i..j] of boolean; 初值皆為false
- turn：integer，值為i或為j，初值無所謂
- Pi之程式片段如下：
repeat
flag[i]=true; //Pi表明意願 turn = j; //禮讓對方 while(flag[j] and turn == j) do no-op;critical section flag[i] = false; remainder section until false;
pf：
- 滿足"Mutual exclustion"
若Pi、Pj皆想進入critical section (即flag[i] = flag[j] = true)
當Pi、Pj各自執行到while測事實，表示已分別執行過 turn = j 及 turn = i 之設定(只是先後差別而已)
因此 turn 的最終值會為i或為j，但不會同時為兩者
∴確保只有Pi或Pj進入critical section - 滿足"Progress"
pf：(i)若Pi不想進入critical section，即flag[i]為flase，且此時turn值為i
若此時Pj想進入critical section，則Pj必可通過 while loop(∵while(flag[i](false) and turn == i(true))而進入critical section
∴Pi不會阻止Pj進入critical section
(ii)若Pi、Pj皆想進入critical section，則在"有限的時間"內避可決定出turn值為i或為j
∴可決定出Pi或Pj進入critical section - 滿足"Bounded Waiting"
若Pi、Pj皆想進入critical section，且此時turn值為i
∴Pi進入critical section而Pj等待
當Pi離開critical section後又再度企圖進入critical section
則Pi必定會將turn值設為j，使得Pj得以進入critical section
而Pi會卡在while中
∴Pj至多等一次後，即可進入critical section
沒有留言:
張貼留言