Linux IO 多路複用之 Select 簡史

前言

最近我一直在思考 Linux 中的多路複用，即 epoll(7)[1] 系統調用。我很好奇 epoll 與 Windows 等操作系統的 iocp 或 macOS 等操作系統的 kqueue 相比，是更好還是更差呢？我想知道基於批處理 epoll_ctl 調用是否性能更佳。在我們開始認真討論之前，我們不妨往前追溯下，先了解一些背景信息。首要問題是 ---- 文件描述符多路複用是 Unix 設計理念的偏差還是溫和擴展？

要回答這些問題，我們必須首先討論 epoll 的前身：select(2)[2] 系統調用。正好趁此機會對 Unix 系統做一次考古！

在 1960 年代中期，分時系統仍是最近的發明。與以前的批處理系統相比，時間共享確實是革命性的。它大大減少了程序編寫和結果輸出之間的時間浪費。批處理意味着經常要等待數小時才能看到並判斷程序的運行結果。

早期的 Unix

1970 年開發出了 Unix 的第一個版本。需要強調的是：Unix 不是憑空創造出來的 ---- 它試圖解決批處理系統存在的問題。其目的是創造一個更好的、多用戶、分時的環境，以加快最常見的任務處理。“常見任務” 主要是：執行需要大量 CPU 計算和大量磁盤訪問的程序。

在當時，一個程序被執行時，它會在以下幾種事件上 “停止”（阻塞）：

• 等待 CPU

• 等待磁盤 I/O

• 等待用戶輸入（等待 shell 命令）或控制檯（打印數據太快）

在 Linux 進程狀態中，上述 “停止” 表示爲：R、D、S 三種進程狀態碼。

1進程狀態代碼
2    R 運行或可運行狀態（在運行隊列上）
3    D 不可中斷的睡眠狀態（通常是IO）
4    S 可中斷的睡眠狀態（等待事件完成）
5    Z 已失效/殭屍狀態，進程結束但尚未消亡(未被父進程回收)
6    T 停止，要麼是由於作業控制信號，要麼是因爲
7       它正在被調試追蹤
8    [...]

一個進程的生命週期以 R“運行” 狀態開始，以其父進程從 Z“殭屍” 狀態回收它後結束。下圖是其狀態流轉

早期 Unix 中的進程真的不能做得更多。有一個

pipe(2)[匿名管道]

，又抽象出一個叫

命名管道

的技術，但僅此而已。上一個匿名管道的 stdin(標準輸入) 可以作爲下一個管道的 stdout(標準輸出) 或 stderr(標準錯誤輸出)，如下圖所示

讓我們仔細看看 pipe(2)[3]。論文 “UNIX 分時系統：回顧”[4] 的作者 Ritchie 於 1978 年在其論文中寫到：

在沒有通用的進程間消息工具，甚至沒有信號量等有限通信方案的情況下。事實證明，上述管道機制足以實現密切相關的協作進程之間所需的任何通信。[…] 但是管道在與守護進程 (用來爲多個用戶服務) 進行通信時沒有任何用處。

在這裏，Ritchie 似乎已經確認同步管道足以作爲基本的進程間通信設施。

可能已經足夠了！在操作系統 BSD 中，進程被限制最多有 20 個文件描述符。每個用戶被限制爲 20 個併發進程。這些系統真的很簡陋。它們也不需要 IPC(進程間通信) 或複雜的 I/O。

例如，在早期的 Unix 中，沒有文件描述符多路複用的概念。一個很好的例子是 cu 命令 [5]，全稱是 Call Unix 。其手冊頁講到：

當與遠程系統建立連接時，cu 命令 forks 成兩個進程。一個從端口讀取並寫入終端，而另一個從終端讀取並寫入端口。

這是有道理的，因爲所有的 I/O 都被阻塞了，讓操作系統同時使用 read 方法來讀取、write 方法來寫入的唯一途徑是使用兩個進程。

附帶說明一下，如果您是 Golang 程序員，這可能聽起來很熟悉。在 Golang 中，讀寫調用通常是阻塞的，所以當你想同時讀寫時，你不得不使用兩個協程。

TCP/IP 誕生後

這一切都在 1983 年隨着 4.2BSD 的發佈而改變。此版本引入了 TCP/IP 堆棧的早期實現，最重要的 ---- BSD 套接字 API。

儘管今天我們認爲 BSD 套接字 API 存在是理所當然的，但其 API 的設計是正確的嗎？STREAMS 框架是 System V Revision 3 上的比較完善的 API 設計。

1在計算機網絡中，STREAMS 是 Unix System V 中用於實現字符設備驅動程序、網絡協議和進程間通信的本地框架。 在這個框架中，流是在程序和設備驅動程序之間（或在一對程序之間）傳遞消息的協程鏈。 
2STREAMS 的設計是一種模塊化架構，用於在內核和設備驅動程序之間實現全雙工 I/O。 它最常用於開發終端 I/O（線路規程）和網絡子系統。

隨後 BSD 套接字 API 出現 select() 這個系統調用。爲什麼它的出現是有必要的呢？

我一直認爲編寫網絡服務器的 “正確”Unix 方法是爲每個連接創建一個工作進程。在 TCP/IP 服務器的情況下，這代表着 accept-and-fork 模型：

 1// 端口綁定
 2sd = bind();
 3while (1) {
 4    // 接受連接請求
 5    cd = accept(sd);
 6    // fork函數返回兩個值，對於子進程，返回0; 父進程，返回子進程ID.
 7    if (fork() == 0) {
 8        close(sd);
 9        // TODO：worker進程處理套接字“cd“相關邏輯.
10        exit(0);
11    }
12    // TODO：回到“accept”循環，避免泄漏套接字“cd”相關邏輯。
13    close(cd);
14}

雖然這個模型可能足以編寫基本的網絡服務 ，但對於複雜程序來說還不夠。

終端複用

1983 年左右，貝爾實驗室的 Rob Pike 正在開發 Blit---- 第八代 Unix 實驗版 (Research Unix 8th Edition) 的一個可編程位圖圖形終端。

Blit 顯然做了終端多路複用。它允許用戶通過單個串行鏈路與多個終端連接後進行交互。

我向 Pike 先生詢問了 select 的歷史：

正如你所說的那樣，Accept-and-fork 使得多個客戶端無法在服務器上共享狀態。這不僅僅是關於網絡， Blit 也受其影響。

雖然運行兩個同步進程來爲 cu (早期的 Unix 一章中有說到) 供電就足夠了，但不足以爲 Blit 供電。Blit 確實需要某種套接字多路複用工具才能順利工作。

有人可能會嘗試擴展 cu 模型並將文件描述符和多路複用器組合在一起，方法是生成多個阻塞 I/O 的進程並讓它們在某種 IPC 上同步。

不幸的是，在 BSD 上沒有適合的 IPC 機制。System V(Unix 操作系統的一個版本) 的 IPC 於 1983 年 1 月發佈，但在與 BSD 上實現相比沒有任何的可比性。4.2BSD 的手冊頁上也找不到任何真正的 IPC。

由於缺乏任何嚴格的 IPC 機制，Blit 似乎只需要 select 就可以進行控制檯多路複用。

套接字

Kirk McKusick(美國著名計算機科學家，致力於 BSD UNIX 相關工作) 解釋了爲什麼會出現 select：

引入 select 是爲了允許應用程序進行 IO 多路複用。

你可以思考下：有一個簡單的應用程序，例如遠程登錄。它的 descriptor(描述符) 可以對終端設備和雙向套接字進行讀寫。這個程序可以讀取終端鍵盤的字符並將它們寫入套接字，也可以從套接字讀取字符並寫入終端。讀取沒有數據的空描述符導致應用程序阻塞，直到數據到達。應用程序不知道是從終端讀取還是從套接字讀取，如果猜錯將也導致錯誤地阻塞。所以 select 登場了，它可以幫助程序找出哪個描述符已經準備好讀取數據。如果兩者都沒有，程序會被 select 堵塞住，直到數據到達。然後 select 會去喚醒程序並告訴它哪個描述符有數據要讀取。

[…] 非阻塞是在 select 的同時添加的。但是在讀取描述符時使用非阻塞 IO 並不好。因爲你需要寫一個 for 循環來讀取每個描述符的數據，要決定什麼時候暫停對每個描述符的讀取，還要考慮多久讀一次描述符，這個過程很複雜，相比而言 Select 的效率要高得多。

Select 還允許你創建一個單獨的 inetd 守護程序，而不必爲每個服務都有一個單獨的守護程序。(inetd 守護程序通過僅在需要時調用其他守護程序以及通過在內部提供幾個簡單的 Internet 服務而不調用其他守護程序來減少系統負載)

McKusick 先生確認非阻塞 I/O 在 select 之前根本不存在。此外，他引用了 cu 終端用例 ---- 如果沒有 I/O 多路複用，很難編寫 telnet 客戶端。最後，他提到了 inetd 守護進程，雖然後來在 4.3BSD 中引入了它，但如果沒有 select，它是不可能實現的。

章節回顧

必須運行兩個進程才能讓 cu 工作是一種 hack。由於缺乏任何嚴格的 IPC，所以如果沒有 select，就不可能在 Blit 中模擬套接字多路複用。

此外，還需要 select 來實現 inetd。在架構級別 select 需要實現有狀態的服務器，允許客戶端連接之間的一些狀態共享。

這是 1966 年 “UNIX 分時系統：回顧” 頁面的另一個片段：

[在 UNIX 中] 輸入和輸出通常看起來是同步的；程序得先等 I/O 完成。[…] 仍然有一些特殊的應用程序希望在多個流上啓動 I/O 並延遲直到僅在其中一個流上完成操作。當流的數量很少時，可以用幾個進程來模擬這種用法。然而，Arpanet UNIX ncp(網絡控制程序) 接口的作者認爲真正的異步 I/O 會顯著改進他們的實現。

早期的 Unix 系統非常基礎，根本不需要 select。並不是說 C 語言中的阻塞 I/O 模型被認爲是每個人的最佳編程範式。這個模型很有意義，因爲你所能做的只是對文件進行簡單的操作。

這一切都隨着網絡的出現而改變。網絡應用程序需要諸如 inetd、有狀態服務器和終端仿真器（如 telnet）之類的東西。如果操作系統不允許套接字多路複用，這些事情將很難實現。

結論

在這次討論中，我害怕說出核心問題。Unix 進程是否打算成爲 CSP 風格的進程？文件描述符是 CSP 派生的 “channels"(通道) 嗎？select 是否等同於 ALT 語句？

1來自維基百科：
2
3通信順序進程 (CSP) 是一種用於描述併發系統中交互模式的正式語言。 它是基於通過通道傳遞消息的併發數學理論家族的成員，稱爲進程代數或進程演算。CSP 在指令式過程式編程語言的設計中具有很大的影響力，也影響了 Limbo、RaftLib、Erlang、Go、Crystal等編程語言的設計。

我想不是的。即使有設計相似之處，它們也是偶然的。因爲文件描述符出現的時間比 CSP 論文早。

似乎套接字 API 的發展完全脫離了普通的程序員，它不像 CSP 編程範式那樣讓普通程序員簡單快速地編程併發程序。雖然很可惜，但看到一個與用戶空間程序的編程範式一致的操作系統會很有趣。

引用

[1]https://man7.org/linux/man-pages/man7/epoll.7.html
[2]https://man7.org/linux/man-pages/man2/select.2.html
[3]https://linux.die.net/man/2/pipe
[4]https://ia601600.us.archive.org/30/items/bstj57-6-1947/bstj57-6-1947_text.pdf
[5]https://www.computerhope.com/unix/ucu.htm

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/sV6Gdny33bLd9Fnc-dCtqw