行程與事件驅動並行 (Process & Event-Based Concurrency)

Overview Table

並行程式設計的動機與三種途徑 (p.1008-1009)

第 8 章定義:邏輯控制流若在時間上重疊 (overlap in time) 即為並行 (concurrent)。並行不僅是 kernel 執行多程式的機制,應用程式本身也能利用應用層並行 (application-level concurrency),這類程式稱為 concurrent programs。應用層並行的五大用途:

• 存取慢速 I/O 裝置:等待磁碟等慢速裝置時,用其他有用工作重疊 I/O 請求(仿效 kernel 讓 CPU 忙碌的作法)。
• 與人互動:視窗系統對每個使用者動作(如滑鼠點擊)建立獨立並行邏輯流,才能同時 resize 視窗與列印文件。
• 延後工作以降低延遲:如動態配置器把 free 的 coalescing 延後給低優先權的並行流吸收閒置 CPU 週期。
• 服務多個網路 client:第 11 章的 iterative server 一次只能服務一個 client,一個慢 client 就能讓所有人被拒絕服務;concurrent server 為每個 client 建立獨立邏輯流。
• 在 multi-core 機器上平行計算:切成並行流的程式在多核上是真正平行 (parallel) 執行而非交錯 (interleaved)。

現代 OS 提供三種建構並行程式的基本途徑:

12.1 以行程實作並行 (p.1009-1011)

最簡單的並行作法:用熟悉的 fork、exec、waitpid。自然設計是父行程在 accept 接受連線請求,再 fork 一個子行程服務每個新 client。描述子演變流程(listenfd = 3):

Step 1: accept client 1 → connfd(4)      Step 2: fork 子行程後各自 close
                                          Client 1 ⇄ Child 1 (connfd 4)
Client 1 ──connection──▶ listenfd(3)               Child: close(listenfd)
   clientfd              Server                    Parent: close(connfd 4)
                         connfd(4)        Server 只留 listenfd(3) 繼續等

Step 3: accept client 2 → connfd(5)      Step 4: 再 fork Child 2
Client 2 ──connection──▶ listenfd(3)     Client 1 ⇄ Child 1 (connfd 4)
                         Server          Client 2 ⇄ Child 2 (connfd 5)
                         connfd(5)       Parent 繼續等下一個連線

• fork 後子行程取得父的描述子表完整副本 (complete copy of descriptor table),父子的 connfd 指向同一個 file table entry。
• 子行程關掉它不需要的 listenfd 副本;父行程關掉它的 connfd 副本。

12.1.1 Process-based concurrent echo server(Figure 12.5, p.1012)

echoserverp.c 的三個重點:

• SIGCHLD handler 收割 zombie:伺服器長期執行,必須安裝 handler。因 handler 執行期間 SIGCHLD 被 block、且 Linux signals 不會排隊 (not queued),handler 必須用迴圈 while (waitpid(-1, 0, WNOHANG) > 0); 準備一次收割多個 zombie(對照 08-Exceptional-Control-Flow/05-Signals)。
• 父子各自 close 自己的 connfd 副本:child 在 echo 完後 close,parent 在 fork 後立即 close(尤其父端最關鍵)。
• Reference count 語意:socket file table entry 的 refcount 使得父與子的 connfd 副本都關閉後,連線才真正終止。

while (1) {
    connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
    if (Fork() == 0) {
        Close(listenfd);  /* Child 關 listening socket */
        echo(connfd);     /* Child 服務 client */
        Close(connfd);    /* Child 關連線 */
        exit(0);
    }
    Close(connfd);        /* Parent 關 connected socket(重要!) */
}

Refcount 追蹤(Practice Problem 12.1):accept 回傳 → refcount 0→1;fork → 1→2;parent Close(connfd) → 2→1;child 端關閉 → 1→0,連線終止。

12.1.2 Processes 的優缺點 (p.1011)

12.2 以 I/O Multiplexing 實作並行 (p.1013-1016)

動機情境:echo server 同時要回應兩種獨立 I/O 事件——(1) 網路 client 的連線請求、(2) 使用者在 stdin 打字。先等哪個都不對:卡在 accept 就無法回應鍵盤;卡在 read 就無法回應連線。解法是 I/O multiplexing:用 select 要求 kernel 暫停行程,直到一個或多個 I/O 事件發生才把控制權還給應用程式,例如:

• read set {0, 4} 中任一描述子 ready for reading 時返回
• write set {1, 2, 7} 中任一描述子 ready for writing 時返回
• 等待 152.13 秒後 timeout

書中只討論第一種情境(等待一組描述子 ready for reading):

#include <sys/select.h>
int select(int n, fd_set *fdset, NULL, NULL, NULL);
                /* 回傳 ready 描述子個數(非零),錯誤回傳 -1 */

FD_ZERO(fd_set *fdset);          /* 清除 fdset 全部位元 */
FD_CLR(int fd, fd_set *fdset);   /* 清除位元 fd */
FD_SET(int fd, fd_set *fdset);   /* 設定位元 fd */
FD_ISSET(int fd, fd_set *fdset); /* 位元 fd 是否為 1? */

描述子集合 (descriptor sets) 的語意 (p.1014)

• fd_set 邏輯上是大小為 n 的位元向量 $b_{n-1},\dots ,b_1,b_0$;描述子 k 屬於集合 ⟺ $b_k=1$。
• 對 descriptor sets 只允許三件事:(1) 配置、(2) 同型別變數相互指定、(3) 用四個 FD_* macro 修改與檢查。
• select 兩個輸入:read set(fdset)與其 cardinality n(實際上是任何描述子集合的最大 cardinality,慣用 maxfd+1)。
• select 阻塞直到 read set 至少一個描述子 ready for reading。描述子 k ready for reading ⟺ 對它讀 1 byte 不會阻塞。
• 副作用 (side effect):select 就地修改 fdset,改成 ready set(read set 中已 ready 的子集);回傳值 = ready set 的 cardinality。

範例:select 版 iterative echo server(Figure 12.6, p.1015)

初始 read_set ({0,3}):   fd:  3(listenfd) 2  1  0(stdin)
                         bit:     1       0  0     1
使用者按 Enter 後 select 回傳的 ready_set ({0}):
                         bit:     0       0  0     1

主迴圈:ready_set = read_set; Select(listenfd+1, &ready_set, ...),然後用 FD_ISSET 判斷:stdin ready → 呼叫 command() 讀命令;listenfd ready → Accept 後呼叫 echo(connfd) 直到 client 關閉連線。

12.2.1 基於 I/O multiplexing 的並行事件驅動伺服器 (p.1016-1020)

I/O multiplexing 可作為 concurrent event-driven programs 的基礎:流因事件 (events) 而推進。核心手法是把邏輯流建模為狀態機 (state machine)——狀態 (states)、輸入事件 (input events)、轉移 (transitions) 的集合;轉移把 (輸入狀態, 輸入事件) 對映到輸出狀態;self-loop 是輸入輸出同一狀態的轉移。狀態機畫成有向圖:節點=狀態、有向邊=轉移、邊標籤=輸入事件。

對每個新 client k,伺服器建立新狀態機 $s_k$ 並與 connected descriptor $d_k$ 關聯(Figure 12.7):

                input event:
        "descriptor dk is ready for reading"
                     │
                     ▼
        ┌─────────────────────────────┐
        │           State:            │ ──┐ transition:
        │ "waiting for descriptor dk  │   │ "read a text line
        │  to be ready for reading"   │ ◀─┘  from descriptor dk"
        └─────────────────────────────┘        (self-loop)

echoservers.c 架構(Figure 12.8-12.11):活躍 client 集合維護在 pool 結構中:

typedef struct {
    int maxfd;                    /* read_set 中最大描述子 */
    fd_set read_set;              /* 所有活躍描述子集合 */
    fd_set ready_set;             /* ready for reading 的子集 */
    int nready;                   /* select 回傳的 ready 個數 */
    int maxi;                     /* clientfd 陣列 high-water index */
    int clientfd[FD_SETSIZE];     /* 活躍描述子(-1 = 空槽) */
    rio_t clientrio[FD_SETSIZE];  /* 對應的 Rio read buffers */
} pool;

事件迴圈資料流:

          ┌──────────────────────────────────────────────┐
          ▼                                              │
  ready_set = read_set                                   │
  nready = Select(maxfd+1, &ready_set, ...)              │
          │                                              │
          ├─ listenfd ∈ ready_set? ──▶ Accept →          │
          │                        add_client(connfd)    │
          │                        (建立新狀態機/邏輯流)   │
          ▼                                              │
  check_clients(&pool) ── 對每個 ready 的 connfd:         │
      Rio_readlineb 讀到一行 → echo 回去(執行狀態轉移)     │
      讀到 EOF → Close + FD_CLR + clientfd[i] = -1        │
                 (刪除狀態機)────────────────────────────┘

各函式與狀態機模型的對應(p.1020):

• maxi 讓 check_clients 不必掃整個陣列;迴圈條件 (i <= p->maxi) && (p->nready > 0) 靠遞減 nready 提早結束。
• Practice Problem 12.4:pool.nready 每輪都要用 select 回傳值重新初始化,因為它儲存的是本輪 ready 描述子總數,供 add_client 與 check_clients 遞減計數。

12.2.2 I/O Multiplexing 的優缺點 (p.1021)

Exam/Test Patterns

Related Notes

• 12-Concurrent-Programming/02-Threads
• 12-Concurrent-Programming/03-Shared-Variables-and-Semaphores
• 12-Concurrent-Programming/04-Parallelism-and-Thread-Safety
• 08-Exceptional-Control-Flow/04-Process-Control
• 08-Exceptional-Control-Flow/05-Signals
• 10-System-IO/03-File-Sharing-Redirection-and-Standard-IO
• 10-System-IO/02-Rio-Package-and-File-Metadata
• 11-Network-Programming/03-Sockets-Interface
• 11-Network-Programming/04-Web-Servers-and-Tiny
• 01-Computer-Systems-Tour/04-Amdahls-Law-and-Concurrency-Themes