多行程 Process 間的協調與通訊機制

前一篇講了CPU 調度的方式，跟如何排程，這篇繼續寫 Process 間如何互相通訊，跟如果有很多 Process 之間如何運作。

CPU 調度與排程策略（CPU Scheduling）

目標：處理多個應用程式的競爭與協作

Interprocess Communication（IPC, 行程間通訊）

當多個行程需要共享資料或彼此通訊時，作業系統會提供各種方法來進行協作。這邊我看英文版有點難懂，所以加上一些比喻，應該會容易懂一些。

Inter Process Communication (IPC)

比喻：學校專題報告小組合作

假設你和幾個同學組成一個專題小組，需要一起完成報告。

1. 訊息佇列 (Message Queue)：
2. • 你們透過 記事本留言區 傳遞訊息。例如，小組長貼了一個「今天要完成資料收集」的訊息，其他人按順序查看、完成並回報。
   • 重點：訊息按順序排隊，每個人按順序取用。
2. 共享記憶體 (Shared Memory)：
3. • 你們共用一個 線上雲端文件 (Google 文件)，所有組員都能同時查看和編輯內容。無論誰更新，其他人都能即時看到最新的資料。
   • 重點：所有人能同時存取和更改相同的資料空間。
3. 管道 (Pipes)：
4. • 假設每位組員之間都有 Line 聊天室好友，可以一對一地討論。這個管道是專屬的，別人無法參與或偷聽。
   • 重點：兩個行程之間的直接溝通。
4. 信號 (Signals)：
5. • 小組長完成報告後，按下 群組通知按鈕 (例如群組LINE通知) tag 所有人，「報告完成，準備交件！」。
   • 重點：即時廣播給所有相關人員，通常用來發送重要或緊急訊息。

Race Condition (競爭條件)、Critical Section (臨界區)、Dekker's Algorithm (德克演算法)

Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm

比喻：多人同時對一張照片按讚

想像一張熱門照片，很多人同時對它按讚。如果系統沒有處理好，就可能發生競爭條件，導致按讚數錯誤。

1. Race Condition (競爭條件)

當多個使用者同時按下「讚」，伺服器需要更新按讚數。如果沒有適當的同步機制，可能出現以下狀況：

• 使用者 A 按讚，伺服器讀到「目前按讚數是 3」，準備加 1。
• 同時 使用者 B 也按讚，伺服器也讀到「目前按讚數是 3」，準備加 1。

理論上，按讚數應該是 5，但由於兩個請求同時進行，兩人都認為目前的按讚數是 3，最後結果只變成 4。

關鍵問題： 這就是競爭條件，因為伺服器同時處理了兩個請求，卻沒有正確同步，導致按讚數錯誤。

2. Critical Section (臨界區)

為了避免這種情況，設定了臨界區，一次只能有一個人( process )進入伺服器，進入後必須執行一段「讀取目前讚數，+1，更新讚數」的程式碼。

如何解決？

• 當伺服器發現某個使用者正在更新按讚數時，必須暫時鎖住這個區域，直到處理完成。其他使用者只能 排隊等候，不能同時進入。

指針指到才可以進入

3. Dekker's Algorithm (德克演算法)

如果同時有兩個人想要進入 critical section，如何讓對方知道呢?

• 兩個使用者想按讚：
• • 每個人先「按警示燈」，看看伺服器是否有人在更新。（我個人覺得很像地下停車場上下樓層的警示燈)
  • 如果有人在更新，另一個人必須等待。
  • 如果兩個人同時按警示燈，伺服器會 交替 允許其中一個人進行，另一個人下次再試，確保每個請求都會被處理到。

作業系統 Deadlock影片 這個3分鐘影片很有趣~

Deadlock 與形成的四個條件

當多個行程互相等待彼此釋放資源，卻沒有一方能繼續執行時，就會發生 Deadlock (死結)，系統因此停滯不前。

比喻：

想像兩輛車在狹窄巷道中相遇：

• A 車想前進，但前面被 B 車擋住。
• B 車也想前進，但前面被 A 車擋住。
  結果兩輛車都無法動彈，形成「死結」。

形成死結的四個必要條件

1. 互斥 (Mutual Exclusion)：
2. • 資源只能由一個行程使用。
   • 比喻： 巷道只能容納一輛車通過。
2. 占有與等待 (Hold and Wait)：
3. • 一個行程已占有資源，卻仍在等待其他資源。
   • 比喻： A 車已經在巷道內，卻還想進一步前進。
   • 用影片槍跟子彈的比喻，雙方都需要對方手上的資源。
3. 不剝奪 (No Preemption)：
4. • 資源無法強制收回，必須由行程自願釋放。
   • 比喻： A 車和 B 車都不願意倒車。
4. 循環等待 (Circular Wait)：
5. • 多個行程間形成循環等待鏈。
   • 比喻： A 車等 B 車讓路，而 B 車等 A 車讓路，形成無限等待。

解決死結的方法

1. 死結預防 (Deadlock Prevention)：
2. • 設計時避免同時滿足所有死結條件。例如：資源分配時設定固定順序。
2. 死結避免 (Deadlock Avoidance)：
3. • 根據程式的需求進行動態資源分配，確保系統永遠不進入死結狀態。
3. 死結偵測與回復 (Deadlock Detection and Recovery)：
4. • 系統不主動避免死結，但可偵測到後強制回收資源或中止程式。
4. 資源分配協議 (Resource Allocation Protocol)：
5. • 設定系統資源分配規則，避免循環等待。