3.6 程序間的溝通 (Process Communication)

又稱為 inter-process communication IPC
方法有兩種：

  1. Shared Memory
  2. Message Passing
    圖：

目錄

  • Shared Memory
  • Message Passing

Shared Memory 分享記憶體

Def: 指多個 process 藉由共用相同的 memory space 達到行程間溝通之效 (Multiprocessor)
問題：Race Condition 競爭情況
Def: 相同的運作. 因執行順序不同, 造成處理的結果不同謂之
解決：Critical Section 臨界區間
Def: 為一程式片段, 用來提供多 process 共用一 memory space 時的存取控管機制 => 避免 race conditional

Critical Section Design

格式：

良好的 C.S Design 需滿足：

  1. Mutual exclusion (互斥)：指同一時間只允許一個 process 進入 C.S.
  2. Progress (可進行性)：不想進 C.S. 的 process, 不能影響其他欲進入 C.S. 之 process
    • 若有多個 process 欲進入 C.S., 則挑選的時間是有限的 => 避免 deadlock
  3. Bounded waiting (有限性等待)：指 n 個 process 存在於進入 C.S., 最多只需 wait n-1 次 => 公平, No starvation

C.S. Design 目錄

  • algo
    • 2 process => 3 algos (turn, flag)
    • 2 process => 1 algos (turn + flag)
  • Semaphore
    • Binary
    • Counting

2 個 process 的 C.S. Design

algorithm1:

  • 資料結構 (宣告變數)：
    var turn: integer (0~1);
  • Pi 之程式片段：
  • 分析：
    1. 滿足 mutual exclusion (互斥)
      說明：
      當 Pi, Pj 皆欲進入 C.S., 又 turn 不會同時為 i, j (因為 i 不等於 j), 故只能一個 process 進入 C.S.
    2. 不滿足 progress (可進行性)
      說明：
      當 Pj 於 R.S. 中 (因為 j 就是不想上廁所), 但 turn = j, 此時若 Pi 想進入 C.S., 將被卡在 while loop 中無法進入 (因為違反 progress)

algorithm2:

  • 資料結構：
    var flag [0...1] of Boolean;

  • Pi 之程式片段：

  • 分析：

    1. 滿足 mutual exclusion (互斥)
      說明：
      若欲使 Pi, Pj 同時進入 C.S., 則 flag[i] = flag[j] = false, 又當欲進入 C.S. 一開始 flag, 會改為 true, 故上述情況不可能存在
    2. 不滿足 progress (可進行性)
      說明：
      當 Pi, Pj 皆欲進入 C.S., 則 flag[i] = flag[j] = true, 此時 2 者皆會卡在 while loop 中 => deadlock, 故違反 progress

  • 中山

1
2
flag[i] = true;
while (flag[j]) do no-op;

若交換上述兩行程式, 會發生什麼事？
Ans: 違反互斥性, 變成先問對方在舉手

algorithm3:

  • 資料結構：

  • Pi 之程式片段：

  • 分析：

    1. 滿足 mutual exclusion (互斥)
      說明：
      當 2 process 皆欲進入 C.S., 則 flag[i] = flag[j] = true, 但 turn 不會同時為 i, j (因為 i 不等於 j), 故只有一 process 可進入 C.S.
    2. 滿足 progress (可進行性)
      說明：
      • 當 Pj 不想進入 C.S., 又 turn = j, 且此時 flag[j] = false, 故當 Pi 想進入, 可以順利通過 while loop
      • 當 2 process 皆欲進入 C.S., 此時視 turn 的值為 i 或 j, 指向者可進入 C.S., 所以 No deadlock
    3. 滿足 Bounded Waiting (有限性等待)
      說明：
      當 Pi, Pj 皆欲進入 C.S., 而 turn = j時, 則 Pj 可進入, 若 Pj 離開後立即再度欲進入 C.S., 則：
      flag[j] = true;
      turn = i
      因為 turn = i, 故下次必由 Pj 進入 C.S. 中

多 process 的 C.S. Design => Bakery’s algorithm

  • 資料結構：
1
2
var choosing: Array[0....n-1] of Boolean;
    number: Array[0....n-1] of Integer; (initial 皆為 0)

  • 數字假設：

    1. (a, b) < (c, d), if
      1. a < c or
      2. a = c 且 b < d
    2. Max(X0...Xn-1) => 取 X0 ~ Xn-1 中最大值

  • Pi 之程式片段：

Semaphore (號誌) (可有互斥的效果)

  • Def: 為解決同步問題的一種機制, 本身為一整數型別 (通常初始為 1), 會提供 2 個 atomically execution (不可分割, 指過程中不能被中斷) 的運作
    • signal
    • wait
  • 圖：
  • Note:
    Semaphore 初始值為 1 時, 則狀態永遠為 0 或 1, 故 Pj 謂之 Binary Semaphore (二元號誌)

Counting Semaphore (計數號誌)

Def: 有別於 Binary Semaphore, 於 counting semaphore 之中, 值可能為 1, 0, -1, -2…-n, 若值為 -n, 代表有 n 個 process 卡在 wait 之中
=> 製作方式：

  1. 用 Block, wakeup 製作
  2. 用 Binary Semaphore 製作

<法一>：用 Block, wakeup 及 Queue 製作

  • 作法：將 Semaphore 定義成一 Record (紀錄) (like class)
1
2
3
4
type countingSemaphore: record
    value: integer; //initial = 1
    L: Queue;
end;

<法二>：用 Binary Semaphore 製作出 counting semaphore

  • 資料結構：
1
2
3
var c: integer; initial = 1 // 計數器, like value, c 當 signal & wait
    S1: Binary Semaphore; initial = 1 // 對 C 做存取控制
    S2: Binary Semaphore; initial = 0 // 用來模擬 block, wakeup 之效

Compare

Compare busy waiting (spinlock 盤旋鎖) 製作 counting semaphore (簡單的會使用) Block, wakeup 製作 (複雜的通常用)
優點 wait 時不會有 context switching, 若為片刻等待, 適用 wait 時不會用至 CPU
缺點 在 waiting 過程中, 會不斷的耗用 CPU 的資源, 所以浪費 CPU 需 context switching

思考