Chapter 10 Process Communication

前一章 | 首頁

Process Communication的方式(資訊交換、同步)

  1. Message Passing
  2. Share Memory
  Message Passing Share Memory
溝通方式 Process之間要溝通,需
  1. 先建立Link
  2. 建立後,才相互傳輸訊息
  3. 釋放Link
Process彼此之間透過對共享變數的存取,藉由其值之變化達到溝通(同步)之目的
共用性 Link是專屬於溝通之雙方,不會被其它人共用 共享變數是所有processes皆可存取
OS支援 OS會提供如Link Management等額外支援 OS僅提供Share Memory空間,不提供任何額外支援
Programmer負擔 輕(OS Load較重) Programmer負擔重
其它機制 需提供如Link Creation, Link Capacity控制, Message Lost等處理機制 需提供對共享變數之互斥存取控制,否則會有問題

Share Memory溝通方式下的可能問題

  1. 執行結果不正確(不如預期)
  2. Rece Condition

例:Producer/Consumer Problem

  1. Def:
    Producer:產生資訊供其它process使用者
    Consumer:消耗其它人所產出之item者
  2. 在Share Memory溝通方式之下:
    在此model之下,可再細分為兩種
    1. Bounded Buffer Producer/Consumer(★)
      • Buffer為滿,則Producer被迫wait
      • Buffer為空,則Consumer被迫wait
    2. UnBounded Buffer Producer/Consumer
      • Producer無須wait
      • Buffer為空,則Consumer被迫wait

Bounded Buffer Producer-Consumer Problem之程式

Algorithm 1:頂多利用Buffer n-1個空間

  1. 共享變數
  2. 宣告:
    1. n→Buffer size
    2. Buffer[0..n-1] of item (circular array)
    3. in, out:integer = 0
  3. Producer之程式片段如下
  4. 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
    
  5. Consumer程式之片段如下:
  6. 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

Algorithm 2:充分利用n個空間

  1. 共享變數
  2. 宣告:多加一個Count:integer變數
    意義:
    Count(Buffer資料個數) = 動作:
  3. Producer之程式片段如下
  4. 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
    
  5. Consumer程式之片段如下:
  6. 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;

Share Memory溝通下的可能問題

  1. 執行結果不正確(結果不正確)
    例:
        Producer             Consumer
    -------------------------------------
    Count = Count +1     Count = Count -1
    
    Count為此二個processes之共享變數
    假設Count值目前為5,且Producer會作一次加1動作,Consumer會作一次減1動作
    我們預期Count之正確值為5,然而Count值卻可能為4(或為6),此為不正確之結果

    說明:
    Count = Count + 1可以分解成下列三條機器指令(或組合語言指令)

    1. Register1 = Count
    2. Register1 = Register1 + 1 (INC)
    3. Count = Register1
    同理,Count = Count - 1 拆成:
    1. Register2 = Count
    2. Register2 = Register2 - 1
    3. Count = Register2
    若Producer與Consumer以下列順序交替執行:
    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
    ∴不正確

  2. Race Condition(執行順序不同、值不同)
    1. 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

    OSC:
    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.

Share Memory溝通問題之解決策略

  1. Disable Interrupt
    1. Def:
      為確保共享變數之存取敘述執行時不受任何中斷干擾,可以automically executed,可以採序如下方式
      Disable Interrupt
         執行敘述
      Enable Interrupt
      
    2. 優點:simple,易於實施,適用於uniprocessor(單一CPU)環境
      缺點:不適用於Multiprocessors環境,因為效益很差
      • 說明:process需發出Disable Interrupt請求給各其它CPUs,並且必須等到所有其它CPUs回覆"Interrupt已Disable"之回應訊息,才可以執行敘述
        同時,完成後,再發訊息通知其它CPUs Enable Interrupt
  2. Critical Section Design
    目的:提供對共享變數之存取的互斥控制,確保資料的正確性

Critical Section(臨界區間)

  1. Def:
    process中對共享變數進行存取的敘述之集合區間
  2. Processi之程式架構
    repeat
       entry section
          critical section
       exit section
          remainder section
    until false   
    
  3. Critical Section Design
    是在Design Entry SectionExit Section

OSC 7.2

Critical Section Design必須滿足的三個性質

  1. Mutual Exclusion
    Def:
    最多只允許一個process在其Critical Section內活動,若其它processes也想進入它們本身的Critical Section,則必須等待值到該process離開Critical Section才能再擇一進入(即不允許多個processes在各自Critical Section內同時活動)
  2. Progress
    Def:
    1. 不想進入Critical Section的process(即在Remainder Section內活動),不能妨礙(阻止)其它process進入Critical Section
      (不能參與進入Critical Section的決策過程)
    2. 決定哪個process可以進入Critical Section的時間是有限的(不能無窮止境)⇒No DeadLock
  3. Bounded Waiting
    Def:
    自process提出欲進入Critical Section的請求到其獲准進入Critical Section的等待時間是有限的(⇒No starvation)
    若有n個processes欲進入Critical Section,則任一process至多等待(n-1)以後必可進入Critical Section
OSC:
  1. Mutual Exclusion
    If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
  2. 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.
  3. 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.

Software Solution for Critical Section Design

  1. 2個processes
  2. n個processes

2個processes之software solution

Algorithm 1

假設Pi與Pj兩個processes
  1. 共享變數之宣告
    turn:integer,值為i或為j,初值無所謂 (turn:權杖)
  2. 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;
    
分析:
  1. 滿足Mutual exclustion (∵turn不會同時為i且為j)
  2. 不滿足"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
  3. 有滿足Bounded waiting

Algorithm 1

  1. 共享變數之宣告
    flag[i..j] of boolean; (false:表無意願;trun:有意願)
    初值:flag[i] = flag[j] = false
  2. Pi之程式片段如下:
    repeat
    
    flag[i] = true; //表明Pi有意進入critical section while(flag[j])do no-op; //flag[j]成立,表Pj也有意進入 ∴Pi wait
    critical 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-意願
  1. 共享變數之宣告
    1. flag[i..j] of boolean; 初值皆為false
    2. turn:integer,值為i或為j,初值無所謂
  2. 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:
  1. 滿足"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
  2. 滿足"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
  3. 滿足"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

n個processes之software solution

Algorithm 4