--- title: UNIX 作業系統 fork/exec 系統呼叫的前世今生 image: https://i.imgur.com/xm1056l.png description: 文不僅探究 fork 和 exec 的歷史,也涵蓋 fork, exec, exit, wait 這些系統呼叫背後緊密的關聯,最終談論到 Linux 核心實作的 clone 系統呼叫是如何重新定義 fork。唯有理解歷史,才能洞見未來。 tags: LINUX KERNEL, LKI --- # UNIX 作業系統 fork/exec 系統呼叫的前世今生 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) > 改寫自 dog250 的網誌 [1](https://blog.csdn.net/dog250/article/details/100538009), [2](https://blog.csdn.net/dog250/article/details/100168430), [3](https://blog.csdn.net/dog250/article/details/100560290) > 授權條款: [CC 4.0 BY-SA](http://creativecommons.org/licenses/by-sa/4.0/) 本文不僅探究 fork 和 exec 的歷史,也涵蓋 fork, exec, exit, wait 這些系統呼叫背後緊密的關聯,最終談論到 Linux 核心實作的 clone 系統呼叫是如何重新定義 fork。唯有理解歷史,才能洞見未來。 ## fork 的由來 儘管 fork 系統呼叫在 [UNIX 第一版](https://github.com/jserv/unix-v1/blob/master/src/lib/fork.s)就出現 (1969 年,針對 [PDP-7](https://en.wikipedia.org/wiki/PDP-7) 硬體),距今已有 50 年歷史,不過 fork 系統呼叫背後的概念可追溯到 1963 年,也就是早於 UNIX 的 6 年前即存在。 :::success 可線上查閱 UNIX 第一版的技術手冊,[section 2](http://man.cat-v.org/unix-1st/) 即是系統呼叫 ::: 1960 年代中期啟動 [Project MAC](https://multicians.org/project-mac.html) (與阿波羅登月計畫平行,由 DARPA 贊助的大型計畫) 的 [Multics 專案](https://web.mit.edu/multics-history/),定位開發多人分時多工作業系統,並運作於多處理器的硬體環境 (multi-processor),更有意思的是,Project MAC 這麼龐大的計畫卻由麻省理工學院 (MIT) 領軍開發關鍵技術,並由 GE (美國通用電氣,也稱奇異公司) 提供硬體及 AT&T 旗下的 Bell Labs 開發軟體和技術支持 (受到反壟斷條款的處分,AT&T 不得涉及硬體銷售,但研發專利技術並授權他人不在此限),今日我們熟知的 C 語言開創者 —— 已故的 [Dennis M. Ritchie](https://en.wikipedia.org/wiki/Dennis_Ritchie) (縮寫 dmr) 和仍活躍於產業的 [Ken Thompson](https://en.wikipedia.org/wiki/Ken_Thompson) (縮寫 ken) —— 即服務於 Bell Labs。 以商業的角度來說,Multics 是個失敗的作業系統,但 ken 和 dmr 卻汲取其中的養分,帶著戲謔的口吻,開發出名為 UNICS 的作業系統,"uni-" 和 "multi-" 是對比的前綴,後來 UNICS 被正名為 UNIX,自此為世人熟知,並且影響你我生活的個別面向。UNIX 初期用組合語言開發,提供檔案系統的服務,後來用 C 語言重寫,其中 [Research UNIX](https://en.wikipedia.org/wiki/Research_Unix) version 6 (簡稱 `V6`) 是大量被學校和公司行號採用的作業系統 (在 Bell Labs 擁有者 AT&T 所屬的律師團對外界收取天價授權費之前)。UNIX 的發展中,不難發現其向已存在的資訊系統借鏡的影子,fork 系統呼叫就是這樣的案例。 1963 年,電腦科學家 [Melvin Conway](https://en.wikipedia.org/wiki/Melvin_Conway) 博士 (以 [Conway's Law](https://en.wikipedia.org/wiki/Conway%27s_law) 聞名於世) 發表論文〈[A Multiprocessor System Design]( https://archive.org/details/AMultiprocessorSystemDesignConway1963/page/n7)〉,正式提出 fork 思想。從論文標題不難發現,fork 的思想最初是作為一種「多處理器並行處理」執行模型,這個想法非常有意思,該想法源於下方流程圖。 :::success 此處「並行」通指 [concurrent](https://dictionary.cambridge.org/dictionary/english/concurrent) (形容詞) 和 [concurrency](https://dictionary.cambridge.org/dictionary/english/concurrency) (名詞),這詞彙在中國簡體稱為「并发」。「並行」這譯詞在 1970 年代就出現於台灣的資訊科技刊物中,本文沿用。 ::: 我們考慮以下流程圖: ```graphviz digraph Graph1 { graph [splines=ortho]; node [style=rounded shape=box label=""]; A; subgraph cluster_fork { style="rounded"; label=" fork 點" B[style=diagonal shape=diamond]; } subgraph cluster_join { style="rounded"; label=" join 點" D; } subgraph cluster_parallel1 { label="可並行 " CL; } subgraph cluster_parallel2 { label=" 可並行" CR; } E; A -> B; B -> {CL CR}; {CL CR} -> D; D -> E; } ``` 若我們確立電腦程式可用一套明確的流程來表達,我們即可聲明該並行處理的方案是可行的。流程圖的分岔處,fork —— 叉子,多麼生動的類比。 一個流程圖上的分支點分裂出來的分支顯然是邏輯獨立的,這便是可並行化處理的前提,於是他們便可表現為不同的*行程 (process)* 的形式。當時的表達還只是 **process** 這個術語,還不具備現代作業系統的「行程」概念。 join 表示多個並行處理的行程由於某種原因不得不進行同步的時間點,也就是多個並行行程會合之處。在當今的多執行緒程式中,這個點依然叫作 join。比如 Java 核心套件裡頭的 [java.lang.Thread](https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html) 的 join 方法以及 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 函式庫的 [pthread_join](http://man7.org/linux/man-pages/man3/pthread_join.3.html) 函式。 廣義來說,join 也意味著不同的行程必須經過的執行路徑,因此減少 join 的數量將會提高並行的效率。 Conway 的論文另一個創舉是,他將行程 (也就是後來作業系統中的 process 的概念) 及執行該行程的處理器 (即 CPU processor) 分離出來,抽象出 scheduler 層面。 大意是說:「只要滿足系統中的活動處理器數量是總處理器數量和並行行程總和的最小值即可」。這意味著 scheduler 可以將多處理器系統的所有處理器和系統所有行程分別看成是統一的資源提供者和消費者來一起排程。 ```graphviz digraph Graph2 { graph [nodesep=2] node [shape=box]; B [label="一堆處理器"]; A [label="一堆行程"]; B -> A [style=dotted dir=both label=" 多對多映射"]; A -> B [dir=both label=" scheduler"] } ``` 在 Unix 引入 fork 之後,這種多處理器並行的設計思想就深入到 Unix 的核心。這個思想最終也影響 Unix 及後來的 Linux,並延續至今。 關於這個設計思想為何得以影響 Unix (及其家族) 超過五十年,和 [Conway's law](https://en.wikipedia.org/wiki/Conway%27s_law) 不無關係。這定律中提到: > Any organization that designs a system (defined broadly) will produce a design whose structure is a copy of the organization's communication structure. 美國威斯康辛大學教授 Remzi H. Arpaci-Dusseau 和 Andrea C. Arpaci-Dusseau 撰寫的開放存取式教科書《[Operating Systems: Three Easy Pieces](http://pages.cs.wisc.edu/~remzi/OSTEP/)》,在〈[The Abstraction: The Process](http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdf)〉一章提到: > HOW TO PROVIDE THE ILLUSION OF **MANY CPUS**? Although there are only a few physical CPUs available, how can the OS provide the illusion of a nearly-endless supply of said CPUs? 作業系統藉由虛擬化 (virtualize) CPU 資源來達到在單一處理器實作出有如同時多個程式執行於各自的處理器之上的假象 —— 其中關鍵的手法就是分時多工 (time-sharing),而 Unix 的第一篇論文《[The UNIX Time Sharing System](http://www.cs.berkeley.edu/~brewer/cs262/unix.pdf)》,由 Ken Thompson 和 Dennis Ritchie 在 1973 年 10 月 ACM [Symposium on Operating Systems Principles](http://www.sosp.org/) (SOSP) 中提出,該論文在 1974 年 7 月的 [Communications of the ACM](https://cacm.acm.org/) 發表,正是採用分時多工作為主題。 :::success 至於《[Operating Systems: Three Easy Pieces](http://pages.cs.wisc.edu/~remzi/OSTEP/)》(可簡稱為 `OSTEP`) 的 "Three Easy Piece" 也有典故,是向已故物理學家費曼致敬,後者著有《Six Easy Pieces: Essentials Of Physics Explained By Its Most Brilliant Teacher》。用 `OSTEP` 作者的話說,作業系統只有物理學一半難度,那就折半為 《Three Easy Pieces》,該書的三大主軸: * 虛擬化 (Virtualization); * 並行 (Concurrency); * 持續保存 (Persistence): 主要探討檔案系統; ::: fork 的源頭已初步觸及,接下來看 Unix 作業系統 fork 的另一個脈絡。 ## 早期 Unix 的覆疊 (overlay) 技術 1969 年最初的 Unix 採用一種從現在眼光會覺得非常奇怪的方案。 較早期的 Unix 現稱為 [Research UNIX](https://en.wikipedia.org/wiki/Research_Unix),2002 年稍早自 SCO 取得 UNIX 業務的 Caldera Systems 公司宣布以 [BSD 授權條款](https://en.wikipedia.org/wiki/BSD_licenses)重新釋出 [Research UNIX](https://en.wikipedia.org/wiki/Research_Unix),這些原始程式碼和相關資訊整理於 [The Unix Heritage Society](https://www.tuhs.org/),這讓我們不僅可瞻仰資訊科技前輩的足跡,更得以追溯作業系統的演化。[Research UNIX](https://en.wikipedia.org/wiki/Research_Unix) 在 1975 年 5 月由 Bell Labs 發布後,為許多大學院校採用,廣泛運作於相對低廉的 PDP-11 硬體上。1977 年澳洲的新南威爾斯大學 (UNSW) 的高級講師 (英國體制,相當於相當於北美的副教授職等) John Lions 針對 V6 UNIX 原始程式碼進行註解,集結成冊《[Lions' Commentary on UNIX 6th Edition, with Source Code](http://en.wikipedia.org/wiki/Lions%27_Commentary_on_UNIX_6th_Edition,_with_Source_Code)》(簡稱 Lions Book),獲得廣泛流傳。該書對電腦科學的影響,猶如普羅米修斯將火種 (V6 UNIX 的運作奧秘和程式碼) 帶到人類世界。 因此,大部分論及 Unix 的材料是從 v6 UNIX 講起,算是較為「現代」的版本,即便是[在 PDP-7 上執行的 Unix](https://github.com/DoctorWkt/pdp7-unix) (也被稱為 [Unix Edition Zero](https://www.tuhs.org/Archive/Distributions/Research/McIlroy_v0/)),也是引入 fork 之後的版本,而在那之前最原始版本已難見蹤跡。 1969 年 Ken Thompson 最初開發的 Unix 極為簡陋,可在 dmr 的〈[The Evolution of the Unix Time-sharing System](http://www.read.seas.harvard.edu/~kohler/class/aosref/ritchie84evolution.pdf)〉窺知樣貌。最初的 Unix 是個分時系統 (Time-sharing System),裡頭只有兩個 shell 行程,分別屬於兩個終端機,不難見其簡陋。 > Processes (independently executing entities) existed very early in PDP-7 Unix. There were in fact ==precisely two of them, one for each of the two terminals attached to the machine.== There was no *fork*, *wait*, or *exec*. There was an *exit*, but its meaning was rather different, as will be seen. The main loop of the shell went as follows. 最初的 Unix 為了體現分時系統的特性,實作最低限度的兩個 shell 行程。需要注意到最初的 Unix 沒有 fork,也沒有 exec,甚至缺乏多行程的概念。為了跟 [Research UNIX](https://en.wikipedia.org/wiki/Research_Unix) 各版本有所區隔,本文將 1969 年最初的 Unix 稱為 "Ken Unix"。 事實上,Ken Unix 用僅有兩個元素的區塊 (Process Control Block, PCB) 來容納所有行程。當然,這裡的**區塊**也是抽象的概念,因為當時的系統是用 PDP-7 組合語言撰寫,還沒有後來 C 語言的資料結構。 > 關於 Unix 執行在 DEC PDP-7 主機的樣貌,可參見 [UNIX Version 0, Running on A PDP-7](https://hackaday.com/2019/11/17/unix-version-0-running-on-a-pdp-7-in-2019/),內附場景重現的短片 我們現在考慮其中一個終端的 shell 行程如何工作,問題馬上就浮現:**這個 shell 行程該如何執行別的程式**? 如果說系統中最多只能容納兩個行程,一個終端只有一個行程的話,當該終端的 shell 執行其他程式時他自己該怎麼辦? :::warning 注意: 不要用現代的眼光去評價 1969 年的 Unix。按照現代的眼光,執行一個程式 (Program) 必然要產生一個新的行程 (Process),顯然這在初版的 Unix 中並不適用。 ::: 答案是根本不用產生新的行程,直接將程式碼載入記憶體並**覆疊**掉 shell 的程式碼即可!當程式執行完後,再用 shell 的程式碼覆疊回去。針對單獨的終端,系統其實一直在執行下面的覆疊循環。以下摘自〈[The Evolution of the Unix Time-sharing System](http://www.read.seas.harvard.edu/~kohler/class/aosref/ritchie84evolution.pdf)〉論文的 Process Control 章節: > 1. The shell closed all its open files, then opened the terminal special file for standard input and output (file descriptors 0 and 1). > 2. It read a command line from the terminal. > 3. ==It linked to the file specifying the command, opened the file, and removed the link. Then it copied a small bootstrap program to the top of memory and jumped to it; this bootstrap program read in the file over the shell code, then jumped to the first location of the commmand (in effect an exec).== > 4. the command did its work, then terminated by calling *exit*. The *exit* call caused the system to read in a fresh copy of the shell over the terminated command, then to jump to its start (and thus in effect to go to step 1). 這會讓很多人跌破眼鏡。 然而,在 `fork` 被引入 Unix 之前,就是如此運作:一個終端上一直都是那個行程,一下子執行 shell,一下子執行其他命令程式的程式碼。以下是一個覆疊程式的結構 (圖片摘自〈[FreeBSD 作業系統設計與實作](https://dl.acm.org/citation.cfm?id=2659919)〉一書): ![](https://i.imgur.com/ZzPoSTX.png) 結合上圖和覆疊循環的第 3 步,你會發現這個第 3 步其實就是 exec 的邏輯。如果你熟悉 Linux 核心 `execve` 系統呼叫載入 ELF 執行檔的邏輯,你會發現對他們而言,這裡所謂的 bootstrap 其實就是 load_elf_binary 函式。 然而,當時畢竟還沒有將這個邏輯封裝為 exec 系統呼叫,所以每一個行程都需要實作這些動作: * shell 需要執行命令程式時,執行 disk I/O 來載入命令程式覆疊掉自己 * 命令程式結束時,exit 讓 disk I/O 把 shell 程式載入回來 exec 邏輯是 shell 程式的一部份,由於顧及會被所有的命令程式使用到,這個邏輯也被封裝到 exit 這個呼叫中。 ## fork 引入 Unix 前的表象 歸納上述,我們得知兩道線索: 1. 1963 年 Melvin Conway 提出 fork 的思想,作為在多處理器中並行執行行程的一個手段; 2. 1969 年 Ken Unix 僅有兩個 shell 行程,而且使用覆疊技術來執行命令; 截至目前,我們看到的表象是: > Ken Unix 沒有 fork、沒有 exec、沒有 wait,其 exit 也和現在的 exit 系統呼叫大相逕庭。顯然 Ken Unix 並非一個多行程系統,而只是個可以跑兩個終端的簡陋分時系統。 ## Unix fork 的誕生 fork 如何引入 Unix 呢? 這要從採用覆疊技術的 Ken Unix 固有的問題談起,論文中提到 > It also exhibited some irritating, idiosyncratic problems. For example, a newly recreated shell had to close all its open files both to get rid of any open files left by the command just executed and to rescind previous IO redirection. 以及 > Moreover, the shell could retain no memory across commands, because it was reexecuted afresh after each command. Thus a further file system convention was required: each directory had to contain an entry *tty* for a special file that referred to the terminal of the process that opened it. If by accident one changed into some directory that lacked this entry, the shell would loop hopelessly. 要解決這些問題,ken 提出簡單的執行方案: * 留著 shell 行程而不是銷毀。執行命令時將其置換 (swap) 到磁碟 (disk) 即可 很顯然,命令程式不能夠覆疊掉 shell 行程。解決方案是用 **置換**。 置換技術和覆疊技術其實都被拿來解決有限記憶體的多行程使用問題,不同點在於兩者的方向不同: * 覆疊技術指的是用不同的行程磁碟映像覆疊目前行程的記憶體映像 * 置換技術指的是將行程的記憶體映像置換到磁碟,再載入別的行程的磁碟映像 使用置換技術解決覆疊的問題,意味著要建立新的行程: * 在新的行程中執行命令程式 Unix 需要進行改動,兩個 PCB 的空間顯然不夠用。當然,解決方案也不麻煩: 1. Expansion of the process table 2. Addition of a fork that copied the current process to the disk swap area, using the already existing swap IO primitives, and made some adjustments to the process table. 現在,剩下唯一的問題就是如何建立新行程!誰來臨門一腳呢? 要講效率,創造不如抄襲,建立新行程最直接的就是複製目前 shell 的行程,在複製的新行程中執行覆疊,讓命令程式覆疊掉複製過來的新行程,而目前的 shell 行程則被置換到磁碟保存。 **覆疊跟置換結合,Unix 離現代化更近一步!** 確定了複製目前行程的方案後,進一步的問題是要怎麼複製它。 現在要說回 fork。 在 Conway 提出 fork 思想後,馬上就有 fork 的實作原型 (正如 Conway 自己所說,他只是提出一個可能的想法而未實作出來),[Project Genie](https://en.wikipedia.org/wiki/Project_Genie) (1964 年始於 UC Berkeley 的分時多工作業系統,也由 DARPA 經費支持) 算是實作 fork 比較完善的系統之一,Project Genie 的成果最終商業化為 [SDS 940](https://en.wikipedia.org/wiki/SDS_940),而 Ken Thompson 在 UC Berkeley 進修時,一度投入 SDS 940 的開發。 Project Genie 系統的 fork 不僅僅是盲目地複製行程,對 fork 的過程有精細的控制權,比如說可決定要配置多大的記憶體空間、複製哪些必要的資源等等。顯然,Project Genie 的 fork 依循著 Conway 的多處理器並行邏輯而實作。 Unix 如果想要實作複製行程,有 Project Genie 這個現成的典範可參考,但 Project Genie 的 fork 對於 Unix 太過精細且複雜,而 Unix 顯然不需要有這麼精細的控制 —— Unix 僅想要讓 fork 出來的新行程被覆疊,而非顧及執行於多處理器上的並行邏輯。 換句話說,Unix 只是借用 fork 的複製邏輯,最終作出不同的實作。於是,Unix 非常粗暴地實作 fork! (就是完全複製父行程而已) 而這仍是我們現在使用的 fork 系統呼叫。 ```cpp FORK(2) Linux Programmer's Manual FORK(2) NAME fork - create a child process SYNOPSIS #include <sys/types.h> #include <unistd.h> pid_t fork(void); ``` 沒有參數,非常簡潔,顯得非常優雅: > fork 本來就不是讓你來覆疊新行程的,不然為何多此一舉? fork 是讓你來分解程式流程來並行處理。 **Unix fork** 就此誕生! 我們回顧 Unix fork 誕生前的景象: ```graphviz digraph Graph3 { rankdir=LR; node [shape=record]; disk [label="<f0>|<f1>shell|<f2>|<f3>cmd|<f4>"] memory [label="<f0>行程|<f1>current\ncode|<f2>current\ndata"] disk:f1 -> memory:f1 [label="覆疊"]; disk:f3 -> memory:f2 [label="覆疊"]; } ``` 每個終端單一的行程循環覆疊,再來看 fork 誕生後的景象: ```graphviz digraph Graph4 { rankdir=LR; node [shape=record] memory1 [label="<f0>行程|<f1>shell\ncode|<f2>shell\ndata"]; memory2 [label="<f0>行程|<f1>cmd\ncode|<f2>cmd\ndata"]; disk [label="<f0>|<f1>\n\nshell\n\n\n|<f2>|<f3>\n\ncmd\n\n\n|<f4>"]; fork [shape=plain] disk:f1 -> memory1:f1 [label="置換" dir="back"]; disk:f3 -> memory2:f1 [label="覆疊"] memory1:f2 -> fork [arrowhead=none] fork -> memory2:f0 {rank=same; disk;} {rank=same; memory1; memory2} } ``` 有 fork 之後,Unix 行程變可組合出無限可能,正式成為一個名副其實的多使用者、多行程現代作業系統了。fork 孕育無限的可能性 (Linux 上可以用 [pstree](http://man7.org/linux/man-pages/man1/pstree.1.html) 命令來觀察): ```graphviz digraph Graph5 { graph [splines=ortho] node [shape=box] subgraph cluster_disk { label="磁碟" style=filled d1 [style=invis] d2 [style=invis]; d3 [style=invis]; d4 [style=invis]; d1 -> d2 -> d3 -> d4 [style=invis]; } d5 [label="置換\n覆蓋" shape=plain] subgraph cluster_memory { label="記憶體" A1[label="init\n行程"]; A2[label="行程"]; A3[label="行程"]; A4[label="行程"]; A1 -> A2 -> A3 -> A4 [label=" fork"]; B1d[style=invis] B2[label="行程"]; B3[label="行程"]; B4[label="行程"]; A1 -> B1d [style=invis]; A2 -> B2 [label=" fork"]; A3 -> B3 [label=" fork"]; A4 -> B4 [label=" fork"]; B1d -> B2 -> B3 -> B4 [style=invis]; C1d[style=invis]; C2[label="行程"]; C3[label="行程"]; C4d[style=invis]; B1d -> C1d [style=invis]; B2 -> C2 [label=" fork"]; B3 -> C3 [style=invis]; B4 -> C4d [style=invis]; C2 -> C3 [label=" fork"]; C1d -> C2 [style=invis]; C3 -> C4d [style=invis]; D1d[style=invis]; D2d[style=invis]; D3[label="行程"]; D4[label="行程"]; C1d -> D1d [style=invis]; C2 -> D2d [style=invis]; C3 -> D3 [label=" fork"]; C4d -> D4 [style=invis]; D3 -> D4 [label=" fork"]; D1d -> D2d -> D3 [style=invis]; E1d[style=invis]; E2d[style=invis]; E3[label="行程"]; E4[label="行程"]; D1d -> E1d [style=invis]; D2d -> E2d [style=invis]; D3 -> E3 [label=" fork"]; D4 -> E4 [label=" fork"]; E1d -> E2d -> E3 -> E4 [style=invis]; {rank=same; A1; B1d; C1d; D1d; E1d;} {rank=same; A2; B2; C2; D2d; E2d;} {rank=same; A3; B3; C3; D3; E3;} {rank=same; A4; B4; C4d; D4; E4} } d1 -> d5 [dir=back style=dotted] d5 -> A2 [style=dotted] } ``` 於是 Unix 正式邁開現代化建設的步伐,一直走到今日。 ## Unix 經典的 fork-exec-exit-wait 組合 關於 exec,就是關於上述覆蓋邏輯的封裝,我們只需使用 exec 系統呼叫而不用自己實作覆蓋邏輯。值得一提的是,當 fork 引入 Unix 後,exit 的語意發生巨大的改變。 在原本 Ken Unix 中,因為每個終端只有一個行程,意味著覆蓋永遠是在 shell 程式和某個命令程式之間進行的: * shell 執行命令 A: 命令程式 A 覆蓋記憶體中 shell 的程式碼 * 命令 A 執行結束: shell 覆蓋結束的命令 A 在記憶體中的程式碼 然而,fork 引入 UNIX 後,雖然 shell 執行某個命令依然是特定的命令程式覆蓋 fork 出來的 shell 子行程。但是當命令執行完後,exit 邏輯卻不能再讓 shell 覆蓋目前命令程式,因為 shell 從來沒有結束過,他作為父行程只是被交換到磁碟而已 (後來出現記憶體後可容納多個行程時連交換都不需要)。 那麼 exit 將讓誰來覆蓋目前行程呢? 答案是不用覆蓋,按照 exit 的字面意思,他只要結束自己即可。 本著**自己的資源自己管理的責任原則**,exit 只需要清理掉自己配置的資源,比如清理掉自己的記憶體空間以及其他的資料結構。 對於子行程本身而言,由於它由父行程所產生,所以子行程被父行程管理釋放。至此,經典的 Unix 行程管理 fork + exec + wait + exec 等系統呼叫的組合正式成軍: ```graphviz digraph Graph6 { node [shape=box] rankdir=LR A [label=<<B>fork</B>>] B [label="create task" style=filled] C [label="fork task"] D [label="copy resource" style=filled] E [label=<<B>exec</B>>] F [label="release resource" style=filled] G [label="reload resource" style=filled] H [label="fork ret" style=filled] I [label=<<B>exit</B>>] J [label="release resource" style=filled] K [label="new task"] L [label=<<B>wait</B>>] M [label="release task" style=filled] d1 [style=invis shape=plain] d2 [style=invis] A -> {H B}; B -> C -> D; C -> E -> F -> G; E -> I; I -> J; I -> K; H -> d1 [arrowhead=none] d1 -> I [dir=back style=dotted label="notify parent"] d1 -> L -> M -> K; K -> d2 [style=invis]; J -> d2 [style=invis]; {rank=same; A;H;d1;L;} {rank=same; B;M;} {rank=same; C;E;I;K;} {rank=same; D;F;G;J;d2} } ``` fork 為何成為神話?因為 Unix 系統的設計思想從 1970 年代開始壟斷作業系統的設計,當時沒有任何足以抗衡的作業系統以不同手法來實作行程管理。要問何以 fork 幾十年都不變,答案是 [積重難返](https://www.moedict.tw/%E7%A9%8D%E9%87%8D%E9%9B%A3%E8%BF%94)! ## fork 的後續 Andrew Baumann (Microsoft Research), Jonathan Appavoo (Boston University), Orran Krieger (Boston University), Timothy Roscoe (ETH Zurich) 等人撰寫的投影片 [A fork() in the road](https://www.microsoft.com/en-us/research/uploads/prod/2019/04/fork-hotos19-slides.pdf) 清晰地交代 fork 系統呼叫是如何一步一步走向今日複雜的面貌。 PDP-7 的記憶體映射非常簡單,當時的程式也非常小,fork 直接複製整個父行程是最簡單有效的方案。這一點並沒有隨著時間的發展而發生什麼比較大的變化。一直到 1980 年代的中期,fork 的開銷依然可接受。 隨著計算機結構的發展,電腦的能力愈來愈強,商業邏輯的繁複也促進程式技術的發展。程式越來越大,記憶體映設機制越來越複雜,fork 的開銷開始不容忽視,此時 Copy-on-Write ([CoW](https://en.wikipedia.org/wiki/Copy-on-write)) 來救場。然而,最終仍須有更大的變革。 計算機結構發展帶來效益,代價卻是管理開銷的增加。以分頁表為例,如果你覺得 32 位元系統一個稀疏地址空間的行程分頁表開銷還可以接受,算一下 64 位元系統中一個稀疏地址空間的分頁表開銷。在這樣的背景下,fork 機制即便輔以 CoW,系統也將不堪重負 (分頁表的 CoW 以及分頁錯誤的例外處理) > Linux 在 Aarch64 (64 位元的 Arm 架構) 的記憶體支援中,甚至允許指定 3 層或 4 層的虛擬記憶體轉換表,分別對應到 39-bit 虛擬定址空間 (即 512GB) 或 48-bit 虛擬定址空間 (即 256TB),其實就是避免分頁開銷過度增長。 > 參見: [Memory Layout on AArch64 Linux](https://www.kernel.org/doc/Documentation/arm64/memory.txt) **是時候讓 fork 回歸他 1963 年的本源,使其處理多處理器的並行化,並用更直接的方式來建立新行程。** fork 不僅是個擁有 50 年歷史的古老系統呼叫,更是個傳奇。一個程式開發者可永遠不用 read / write,也可不懂 mmap,但該懂 fork,因為這是種格調! fork 沒有參數,其簡潔的形式成為**建立新行程的典範**。fork 站在原地,似乎蔑視著 Microsoft Windows 的 [CreateProcess](https://docs.microsoft.com/en-us/windows/win32/procthread/creating-processes) —— 後者的參數量高達 10 個且使用繁瑣。在 Unix 的世界,簡潔幾乎是最高指導原則。 ## 詭異的 fork C 語言教科書往往無法簡明地交代 fork 系統的使用,因為 fork 不符合 C 語言函式呼叫慣例。C 語言和作業系統原本是兩門正交的課程:C 語言標準函式可在沒有作業系統的微控制器上使用,但 fork 似乎不行。 若想要理解 fork 的回傳值,要先理解作業系統行程。換句話說,對 fork 的理解依賴作業系統,包含以下系統呼叫: 1. `execl` 和 `execv` 系列: 正確執行時,沒有回傳值; 2. `fork`: 正確執行時,2 個回傳值; 為何一個函式可返回兩次?按照對 C 語言函式的認知,建立行程的函式原型宣告應該要長這樣: ```cpp int create_process(void *(*start)(void*), void *arg, ...); ``` 然後可在 `start` (看作是 [callback function](https://en.wikipedia.org/wiki/Callback_(computer_programming))) 裡頭呼叫 `exec` 來載入新的執行檔。 和上述 `create_process` 相比,fork 簡直是個醜陋的幽靈,如此詭異的東西怎會在 50 年間吹捧為簡潔設計的典範呢? Linux 不也有個 [clone](http://man7.org/linux/man-pages/man2/clone.2.html) 系統呼叫嗎?用法如下: ```clike #define _GNU_SOURCE #include <sched.h> int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ... /* pid_t *ptid, void *newtls, pid_t *ctid */ ); ``` 我們來看 clone 的手冊: > clone() creates a new process, in a manner similar to fork(2). > … > When the child process is created with clone(), it commences execution by calling the function pointed to by the argument fn. (This differs from fork(2), where execution continues in the child from the point of the fork(2) call.) The arg argument is passed as the argument of the function fn. 光是 clone 的參數列表,跟 Windows API 的常見冗長風格有得拼,與 UNIX 崇尚的簡潔風格大異其趣。 ## 貫徹「懶惰」思維的fork fork 不需要任何參數,也就是說,你沒辦法在建立一個新行程之前去設定這個新行程的任何參數,比如優先等級等。在呼叫 fork 之前什麼都沒有,然而在 fork 呼叫結束後就什麼都有了。也就是說,新行程繼承父行程的一切! 記住,一切都繼承自父行程,連同程式碼也是。所以說,你想要設定新行程的優先權,你就必須在新行程中進行變更: ```cpp if (fork() == 0) { // 變更優先等級 nice(-3); } else { ... } ``` 而非這樣: ```cpp int prio = -3; ret = create_process(new_process, &argv[0], prio, ...); ``` 那麼,**為何一切都繼承父行程呢?** 因為懶!這可是 Dennis Ritchie 自己說的話。 **Genie 分時多工系統** 被認為是首個實作 fork 的作業系統,而非 Unix。Genie 的 fork 遠比 Unix 的 fork 靈活的多,後來 Unix 出現就鳩佔鵲巢。 Unix 的 fork 其實是對 Genie 作業系統裡頭 fork 的拙劣摹仿,也就是想照抄 Genie 分時多工系統的 fork,然而抄到一半覺得太麻煩,乾脆把父行程複製一遍就好。換句話說,沒有參數的 fork 呼叫就是 Unix 一種臨時取巧的方案,後者最終遺留許多問題,令人驚訝的是,這些填坑的方案竟也成為經典! Unix 作業系統的 fork 取巧實作留下了坑,促使後來的 CoW (Copy on Write) 來填坑,卻仍未能填平。 在 Unix 剛出現的年代,記憶體空間很小,一般的行程也很小,所以 fork 中完全複製父行程沒有問題。然而隨著較大的行程出現,記憶體開銷開始越來越大,才採用 COW 技術來緩解這種大的記憶體開銷。 即便使用 CoW,但對於資料結構的複雜操作仍無法忽略,這點在稍後的程式碼會證實。 Linux 核心是個類似 Unix 的系統核心,而程式碼唾手可得,懂他的人也不在少數。現在只要提到 Unix,Linux 都可作為替代。AIX, Solaris, HP-UX 這種老牌經典 Unix 現在已不易取得和實驗 (通常根本缺乏 x86 硬體架構的支援),所以一般用 Linux 來替代。 以下展示的程式碼都針對 Linux。 ## fork 的開銷 如果你去參加科技公司面試,一提到 fork,預期的標準答案似乎都是 > **避免用行程,因為建立行程的開銷太大,儘量用執行緒** 席間,或許還會談到執行緒會共享記憶體空間,而行程不會。更進一步,如果採用 fork 子行程的話,切換地址空間需要切換分頁表...切換分頁表就一定不好嗎?不好,為何?因為要清除 cache 等等議題。 fork 尚有明確的開銷是圍繞於 CoW,後者會帶來可觀的分頁錯誤,而處理分頁錯誤需要付出時間。本文嘗試避開 cache 和分頁錯誤,來一窺 fork 過程那些除此之外隱藏的開銷,關注一些不為人知的祕密。 ## Linux 核心資料結構的開銷 通常,大樓愈低,電梯配置越少、可居住的比例則高,反之,如果樓層數量偏高,光是電梯就要很多部 (公共設施也更多,特別是符合安全規範),留下的住宅空間比例自然也就越低。 同樣,在作業系統中也千萬不要忽略核心資料結構的開銷。本文講的是 fork,與其有關的兩種資料結構也該提及: 1. 分頁目錄和分頁表 2. `vm_area_struct` 先說分頁表的開銷,在行程的地址空間比較稀疏的情況下,光是分頁表就會佔據很大的記憶體空間。在 64 位元的系統中該問題會更加嚴重,具體可參考以下: * [CPU高速缓存与反置页表&调度的科普](https://blog.csdn.net/dog250/article/details/94955775) * [操作系统页表&进程调度 Tips](https://blog.csdn.net/dog250/article/details/94734640) 換句話說,多層次的分頁表主要解決稠密地址空間不必要的分頁表分配問題,本身無法節省記憶體。相反地,在稀疏地址空間,這樣做更會浪費記憶體空間。 如下圖,我們構建一個稀疏的地址空間的多層分頁表。若僅有一層,只有葉節點需要佔據記憶體,多層分頁表則整棵樹都要佔據記憶體空間: ```graphviz digraph Graph7 { rankdir=LR; node [shape=record] page_f [label="<f0>分頁目錄|<f1>|<f2>|<f3>|<f4>...||||||"]; page_m1 [label="分頁中間目錄|<f1>|<f2>...|<f3>"]; page_m2 [label="分頁中間目錄|<f1>|<f2>...|<f3>"]; page_m3 [label="分頁中間目錄|<f1>|<f2>...|<f3>"]; page_m4 [label="分頁中間目錄|<f1>|<f2>...|<f3>"]; page_c [label="<f0>分頁表|<f1>|<f2>|<f3>|<f4>...|<f5>|<f6>||||"]; page_f:f1 -> page_m1:f1 page_f:f5 -> page_m2:f1 page_m1:f1 -> page_m3:f1 page_m2:f3 -> page_m4:f1 page_m3:f1 -> page_c:f1 } ``` 下面的例子中,展示用的程式將構建一個稀疏的地址空間,以此放大 fork 呼叫的 CoW 帶來的分頁表開銷。 再來看 `vm_area_struct`,我們知道使用者層級行程申請的每塊記憶體空間,在系統核心中均以 `vm_area_struct` 所維護。如果我呼叫 10000 次 mmap,那就有 10000 個 `vm_area_struct` 物件被建立。在 fork 呼叫中,即使沒有任何對記憶體寫入的操作,這 10000 個 `vm_area_struct` 依然會被複製。因此在這個例子中,一次 fork 呼叫的記憶體消耗至少是 `10000 * sizeof(struct vm_area_struct)` 這往往沒必要,因為子行程一般都會呼叫 `exec`,從而釋放掉這些地址空間的記憶體以及對應的 `vm_area_struct` 物件。 之所以來這麼一齣,完全為了迎合那個沒有參數的 fork! ## fork 的 CoW 帶來的記憶體開銷 :::warning 以下實驗可能無法重現 ::: 考慮以下程式碼: ```cpp #include <unistd.h> #include <printf.h> #include <stdlib.h> #include <stdio.h> #include <sys/mman.h> /* 注意這個 magic 數字的由来。這是依據 /proc/$pid/maps 檔案計算而得: * 計算方法: 用 stack 頭减去 heap 尾即可,然後根據 OOM 資訊手動修改 */ #define CNT 8638055936 char *data; int cnt = 0; int main(int argc, char *argv[]) { long i, j = 0; // base 就是 heap 尾端的大致位置。 unsigned long st1, base = 0x7f510721e000; pid_t pid; int ps = sysconf(_SC_PAGE_SIZE); // 由於我要fix映射,所以需要頁面對齊。 base = ((unsigned long)base & 0xfffffffffffff000); // Cow 備用 st1 = base; // 循環構建稀疏地址空間,即將 CNT/ps/16 個頁面均匀攤到 heap 和 stack 之間的所有區域。 // 受限於系统記憶體,CNT 的值可以修改 for (i = 0; i < CNT; i += ps*ps/16) { // FIX映射,PRIVATE映射 data = mmap((void *)base, ps-1, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0); // 為展示 CoW 的開銷,父行程的稀疏頁面需要在記憶體中 mlock(data, ps - 1); base += ps * ps / 16; cnt++; } printf("mmap:%p %lx cnt:%d\n", data, base, cnt); /*slabtop; cat /proc/meminfo|grep Slab; cat /proc/meminfo|grep SUnreclaim; free -m 後回車*/ printf("請觀察fork之前的記憶體用量!\n"); printf("请注意稀疏mmap對分頁表記憶體佔用的影響!\n"); printf("敲任意鍵執行fork!\n\n"); getchar(); if ((pid = fork()) < 0) { printf("create failed\n"); exit(1); } if (pid == 0) { /*slabtop; cat /proc/meminfo|grep Slab; cat /proc/meminfo|grep SUnreclaim; free -m 后回车*/ printf("請觀察fork之後,exec之前的記憶體用量!\n"); printf("敲任意鍵執行exec!\n\n"); getchar(); printf("現在請觀察exec之後的記憶體用量!\n"); if (execl("/bin/echo", "echo", "skinshoe" ,NULL) <0 ) perror("error on exec"); } // 寫稀疏記憶體! // 如果這個發生在子行程 exec 之前,將會導致不必要的 Cow for (i = 0; i < CNT; i += ps * ps / 16) { *(char *) st1 = 122; st1 += ps * ps / 16; } sleep(1000); return 0; } ``` 程式碼很簡單。在執行前,先看看系統分頁表的記憶體開銷 ```shell $ cat /proc/meminfo | grep PageTables PageTables: 2564 kB ``` 在執行程式後 ``` $ sudo ./a.out mmap:0x7f5309f1e000 7f530a01e000 cnt:8238 請觀察fork之前的記憶體用量! 請注意稀疏mmap對分頁表記憶體占用的影響! 敲任意鍵執行fork! ``` 此時的開銷為: ```shell $ cat /proc/meminfo |grep PageTables PageTables: 19504 kB ``` 稀疏地址空間果然花費 19 MiB 的記憶體空間! 在執行 fork 後: * 父行程寫稀疏地址空間 * 子行程不執行 exec 得到以下結果: ```shell $ cat /proc/meminfo |grep PageTables PageTables: 36004 kB ``` 果不其然增加了一倍!父行程分頁表佔據的 18 MiB 記憶體是四層分頁表的錯,應該用反轉分頁表。但 fork 之後分頁表消耗的記憶體加倍,成為 36 MiB,絕對是 fork 所導致。 再繼續執行,exec 之後分頁表佔用為 ```shell $ cat /proc/meminfo |grep PageTables PageTables: 19064 kB ``` 記憶體空間恢復!如果你想看父子行程自己的分頁表開銷有多大,可以透過下面的方式取得 ```shell for pid in `ps -e|grep bash|awk '{print $1}'`; do cat /proc/$pid/status|grep VmPTE; done ``` 可看到在 exec 前,父子行程都分配同樣的記憶體空間在分頁表,然而子行程根本就不需要! 只是為了印出 "skinshoe",而且父行程發生 CoW 就要消耗 19 MiB 的記憶體。雖然這個消耗止於 exec 呼叫,但卻不必要。 為了確認分頁表記憶體的釋放確實是因為 exec 呼叫而不是因為子行程退出而倒置的,我們把 `echo skinshoe` 換成一個不會退出的程式試試,比如換成 `sleep 3600`。 ```cpp if (execl("/usr/bin/sleep", "sleep", "3600" ,NULL) < 0) { ``` 重新執行,在 exec 完成後,記憶體消耗為 ```shell $ cat /proc/meminfo |grep PageTables PageTables: 19108 kB $ ps -elf|grep [s]leep 0 S root 21434 21430 0 80 0 - 26989 hrtime 13:15 pts/2 00:00:00 sleep 3600 ``` 這個實驗說明在下面的條件被滿足的場景中,fork 呼叫光是分頁表的記憶體開銷相當巨大: * 父行程地址空間是稀疏的; * 子行程 exec 在父行程之前發生 CoW; 這些條件在大型伺服器的背景服務 (daemon) 中非常容易被滿足,比如 memcached, redis。若在記憶體吃緊的時候誤用 fork,說不定會失敗,更嚴重甚至會觸發系統核心的 OOM。 往往 fork 出來的子行程只是進行一些非常簡單的工作。這種分頁表的開銷完全沒有必要。 現在讓我們把 mmap 參數的 FIXED 去掉,並且也不再指定 base,映射相同大小的記憶體,這樣父行程地址空間便是稠密地址空間,分頁表開銷將非常小。同樣的測試在 fork 前、fork 後和 exec 前發生 CoW,exec 後的分頁表消耗結論如下: ```shell $ cat /proc/meminfo |grep PageTables PageTables: 2576 kB $ cat /proc/meminfo |grep PageTables PageTables: 2660 kB $ cat /proc/meminfo |grep PageTables PageTables: 2644 kB ``` 這種情況下,沒有人會在意什麼分頁表消耗。 這個問題之所以沒有成為普遍的問題,確實有一部份的原因是並非所有的父行程都是稀疏地址空間,且恰好子行程 exec 前發生 CoW。但這並不能掩蓋問題本身,上面的例子不就建立這樣的場景嗎? 此外,問題不被重視還有個很重要的原因是,即便是稀疏地址空間的分頁表影響記憶體消耗,這個消耗是稍縱即逝。一般而言,子行程會馬上呼叫 exec,對作業系統核心的影響彷彿是被針扎一下,稍後就無感。換言之,不是不想發現問題,而是過往的工具捕捉不到如此精細的事件,同樣的事情也發生在 Linux 核心中排程負載領域,詳見 [The Linux Scheduler: a Decade of Wasted Cores](http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf)。 當然,該問題也可透過 vfork 解決,但這對父行程顯得不公道。 ### fork 帶來的 `vm_area_struct` 開銷 這個部份和 CoW 無關。 fork 呼叫在核心內部,父行程的整個地址空間會被複製到子行程。這裡的地址空間是以 `vm_area_struct` 來表達的。 我們可以很容易得想像這個複製的過程和結果會產生什麼樣的影響 * 如果父行程 `vm_area_struct` 物件非常多,複製的時間會非常長。 * 如果父行程 `vm_area_struct` 物件非常多,子行程 `vm_area_struct` 物件佔用的記憶體就會很大。 和上個不分的分頁表記憶體佔用一樣,`vm_area_struct` 物件記憶體也常駐於核心空間的實體記憶體,用多少物件,實體記憶體就縮減多少。因此,實體記憶體緊縮的後果在 fork 中可能會發生,結論是建立子行程失敗,而根本的原因竟然是 **fork 機制的複製是不合理的**。 讓我們建立超級多的 `vm_area_struct` 物件。這很簡單,呼叫超級多次 mmap 即可。 也許你把事情想簡單了,下面這樣可達到我們的要求嗎? ```cpp for (i = 0; i < 100000000; i++) { data = mmap(NULL, ps - 1, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE); cnt++; } ``` 答案是不行! Linux 核心的最佳化策略用漢語來說,就是「見縫插針」。如果你按照上面的邏輯呼叫 mmap,核心十有八九會把超級多個 mmap 區域 (即 `vm_area_struct` 物件) 合併成一個。可進行合併操作的前提很簡單,只要兩個 `vm_area_struct` 物件的首尾連續即可。 為了不讓核心進行這種合併,我們還是要保留 mmap 的 FIXED 參數。 ```cpp for (i = 0; i < CNT; i ++) { // FIX 映射 ps - 2 的大小,每次跨越一個頁面,阻止 vm 區域合併 data = mmap(base, ps - 2, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE | MAP_FIXED, -1, 0); base += ps*2; cnt ++; } ``` 這次我們來看 slab 的開銷,觀察在測試開始前,fork 前、fork 後 、exec 前,還有 exec 後等 4 個 slab 用量為 ```shell $ cat /proc/meminfo |grep Slab Slab: 29500 kB $ cat /proc/meminfo |grep Slab Slab: 251624 kB $ cat /proc/meminfo |grep Slab Slab: 473864 kB # 不必要的 vm 區域複製操作 $ cat /proc/meminfo |grep Slab Slab: 251620 kB ``` 很多人不理解,這裡沒有寫入什麼記憶體,也沒有配置新的記憶體空間,為何記憶體會減少呢?這裡給出答案。 同時 `watch -d -n 1 free -m` 以及觀察 slabtop 會更有趣。 有時你如果只看 `free -m`,你會發現 used 並不多,為何可用的記憶體少呢?這時候就要分析核心管理資料結構的開銷。 和上個部份的分頁表開銷一樣,這個 `vm_area_struct` 物件的開銷也是轉瞬即逝的,很難捕捉到。無論如何這個開銷是沒有必要的,根本原因還是一樣,fork 中的全面複製沒有必要! 不要小看這個轉瞬即逝的記憶體用量激增現象。如果剛好此時網路子系統需要配置 skb,就可能因記憶體不足而失敗。但因只是一個短暫的記憶體激增現象,又很難有工具可以捕捉到,問題也就難以排除。**記憶體明明夠用,也沒有碎片化,為何 skb 的配置會失敗呢?** ## fork 帶來的死結問題 UNIX 作業系統發展的前期,根本就沒有執行緒的概念。那個時候行程就是一切,而行程的一切就是個**獨享的地址空間**。後來事情慢慢起了變化: * 執行緒出現,多個執行緒共享同個地址空間; * 地址空間不再是一切,還包括很多其他不在主記憶體的硬體狀態上下文 (context); 對於 Linux 核心的實作,不管是執行緒還是行程 (只有一個執行緒的行程),一切都是 `task_struct`。fork 發生之際,子行程複製的僅是呼叫執行緒的 `task_struct`。倘若這時操作同一個地址空間的其他 task_struct 持有 lock,即便呼叫 fork 的 `task_struct` 並不知道這件事 (要持有 lock 後才知),但這個事實還是會悄無聲息地傳給子行程。子行程如果這時候想去持有 lock,會發生死結! 根源是,**多個 task_struct 在操作同一個地址空間,但 fork 只參照呼叫者的狀態進行地址空間的複製!** 重現的程式碼很簡單: ```cpp #include <unistd.h> #include <stdio.h> #include <stdlib.h> #include <pthread.h> pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; void *mmap_unmap(void *arg) { while (1) { pthread_mutex_lock(&mutex); sleep (4); pthread_mutex_unlock(&mutex); } } int main(int argc, char *argv[]) { pthread_t tid; pthread_create(&tid, NULL, mmap_unmap, NULL); sleep(1); if (fork() == 0) { pthread_mutex_lock(&mutex); pthread_mutex_unlock(&mutex); printf("未死結!\n\n"); } sleep(1000); return 0; } ``` 由於這是 fork 自己的問題,所以 POSIX Thread 引入特殊的函式來處理: ```cpp int pthread_atfork(void (*prepare)(void), void (*parent)(void), void (*child)(void)); ``` 和這個風格相似的還有類似 `FD_CLOSEEXEC` 這種,本來就是 fork 的事,fork 完全沒有參數,直接把問題丟給 exec。 ## fork 對 `mm_struct` 的同步開銷 fork 呼叫的實作是無條件複製父行程的整個地址空間所有 `vm_area_struct` 物件。複製的過程是需要持有 lock,具體來講就是 `dup_mmap` 的操作。 ```cpp down_write_nested(&mm->mmap_sem, SINGLE_DEPTH_NESTING); ``` 這個旗號 (semaphore) 在所有操作地址空間的呼叫中都要拿。在多核多執行緒的場景下,如果執行緒頻繁操作地址空間的話,fork 呼叫則必然會與之產生競爭,徒增時間開銷。 僅為了 fork 實作的便利,竟然如此折騰。 ## fork 的其他開銷 前面提及分頁表、`vm_area_struct` 物件、鎖等帶來的空間或者時間開銷,及棘手的死結問題,還有嗎? 實在太多!來觀察 `copy_process` 這個函式,看看 fork 都需要複製什麼就知道。 fork 的確過時!在多執行緒、多核 SMP、分散式系統的時代,fork 不合時宜。 諷刺的是,在記憶體空間很小的年代,fork 還能被接受。如今記憶體如此廉價,為什麼 fork 就不合時宜呢?可見,空間開銷只是事情的一面,時間和空間開銷才讓 fork 病入膏肓。 ## vfork 和 fork 的後繼者 [vfork](http://man7.org/linux/man-pages/man2/vfork.2.html) 與 fork 具有相同呼叫方式,但僅能在特定情況使用。[vfork](http://man7.org/linux/man-pages/man2/vfork.2.html) 源於 3BSD,後者是首個支援虛擬記憶體的 UNIX。但 vfork 已在 2004 年的版本中被標為過時,並在後續版本中被 [posix_spawn](http://man7.org/linux/man-pages/man3/posix_spawn.3.html) 所取代。 在發出一個 vfork 系統呼叫時,父行程被暫停,直至子行程完成執行或被新的可執行映像取代(經由系統呼叫之 exec 家族中的一項)。子行程借用父行程的 MMU 設定和記憶體頁面,在父行程與子行程之間共享,不進行複製,尤其是缺乏 CoW 的行為。因此,若子行程在任何共享頁面中進行修改,不會建立新的頁面,且修改的頁面對父行程同樣可見。 System V 在 Release 4 (SVR4) 之前,不支援 [vfork](http://man7.org/linux/man-pages/man2/vfork.2.html),因為記憶體共享容易出錯: > Vfork does not copy page tables so it is faster than the System V fork implementation. But the child process executes in the same physical address space as the parent process (until an exec or exit) and can thus overwrite the parent's data and stack. A dangerous situation could arise if a programmer uses vfork incorrectly, so the onus for calling vfork lies with the programmer. The difference between the System V approach and the BSD approach is philosophical: Should the kernel hide idiosyncrasies of its implementation from users, or should it allow sophisticated users the opportunity to take advantage of the implementation to do a logical function more efficiently? > ——Maurice J. Bach 同樣,Linux 對 [vfork 的手冊頁面](http://man7.org/linux/man-pages/man2/vfork.2.html) 強烈不鼓勵使用: > It is rather unfortunate that Linux revived this specter from the past. The BSD man page states: "This system call will be eliminated when proper system sharing mechanisms are implemented. Users should not depend on the memory sharing semantics of vfork() as it will, in that case, be made synonymous to fork(2)." 使用 vfork 的其他問題包括 deadlock,並可能發生在多執行緒程式中,由於與動態連結造成非預期的行為。POSIX 引入 posix_spawn 函式家族,它結合 fork 和 exec 的動作,可實作為 fork 的程式庫常式 (如在 Linux),或者為了更好的效能而實作為 vfork (如 Solaris)。不過,POSIX 規範中註明 vfork 是「為核心操作設計」,尤其是用於執行在受限硬體和即時系統上的作業系統。 --- ## Linux 對於 fork 實作的手法 作為多行程的替代機制,多執行緒的本質和 fork 的原始意義其實沒有太大分歧,區別就是資源共享的深度不同。 Linux 核心的設計者很早就意識到這點:早期 Linux 核心就沒去設計一個表示行程進程的結構體,而是實作 `task_struct` (以下簡稱 `task`),該結構體包含有讓一個指令流能運行所需要的最基本的元素,當然,隨著時間的推移,這個 `task` 變得相當複雜,可參見 [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process)。有趣的是,早期的 `task` 不包含特指行程和執行緒的描述 —— 一個 task 物件只是一個原材料,它和其它 task 物件對資源的共享關係,決定它該是什麼。對應底層關於 task 靈活的設計,必須給予應用程式有對應的程式介面調,以適應這種靈活,也就是透過 Linux 的 clone 系統呼叫達成,後者在 Linux 核心(至少是 2.2 版本) 中就已存在: ![](https://i.imgur.com/XYjVy4g.png) 在傳統 UNIX 系統或者類 UNIX 系統,則沒有 clone 這樣的系統呼叫。箇中原因可能是 UNIX 一開始就明確定義行程的實作,到後來,當 UNIX 不得不支持執行緒的時候,就要引入一個所謂輕量級行程 (LWP) 的概念,意思是可共享某些資源的行程,這以 Solaris 的 LWP 實作最為出名。在這些老牌 Unix 系統中,一開始過重的行程概念在引入多執行緒機制時造成阻礙。然而對於 Linux,為了支持執行緒而引入新的資料結構則完全沒有必要 —— Linux 核心內部沒有表示 LWP 的結構體。 Linux 核心在底層 task 設計及系統呼叫介面如此這般的設計,注定它實現 POSIX Thread 規範可相當容易,一個參數的指定即可達成: ![](https://i.imgur.com/Ui7JgYv.jpg) 注意上述 `(since Linux 2.4.0)` 訊息,這意味著在 Linux 核心 2.4 版之前,Linux 核心不支援 POSIX Thread,但這裡說的不支援只限於核心模式,很早就有 [LinuxThreads](https://en.wikipedia.org/wiki/LinuxThreads) 這樣使用者層級的多執行緒機制,當然這是比 Linux 2.4 核心更早的故事。Linux 核心 2.4 版之後,對執行緒的支援就可在核心模式達成,對應的 NPTL 則以 `CLONE_THREAD` 為基礎來實作,可見上述的手冊資訊。 該如何建立一個執行緒呢?我們來看以下程式碼: ```cpp #include <pthread.h> #include <stdio.h> void *func(void *unused) { printf("sub thread\n"); return (void *)123; } int main(int argc, char **argv) { pthread_t t1; void *p; pthread_create(&t1, NULL, *func, NULL); pthread_join(t1, &p); printf("main thread:%d\n", (int)p); return 0; } ``` 關於執行緒,我們關注建立和摧毀的操作,用 strace 來追蹤: ![](https://i.imgur.com/tNZ8BFQ.png) 其中,clone 系統呼叫的 flags 參數的意思大致可表述如下: * 黃色: 指示都共享哪些資源、記憶體管理、檔案描述子 (fd)、或檔案系統等等; * 紅色: 實作 POSIX Thread 的語義,比如共享行程 PID、signal 傳遞等等; clone 之後,就建立一個執行緒。執行緒執行 func 之後便退出。問題是,執行緒是如何退出的呢? 對於普通的 C 程式,我們知道 main 函式會返回到 C Runtime (詳見: [你所不知道的 C 語言: 執行階段程式庫 (CRT)](https://hackmd.io/@sysprog/c-runtime) 的討論),後者在 main 函式返回後會呼叫 exit 以結束程式,而對於多執行緒的程式來說,在編譯程式碼的時候,就要連結到 libpthread (即透過 `-lpthread` 連結器參數),那麼類似 CRT 的操作,在多執行緒程式就由 libpthread 函式庫代勞。 大致的 `pthread_create` 如下: ```cpp void clone_func(Thread *thread) { ret = thread->fn(...); exit(ret); } int pthread_create(..., fn, ...) { thread = malloc(sizeof(&thread)); thread->fn = fn; ret = clone(clone_func, &thread); return ERR_NO(ret); } ``` 從上述 strace 的結果可見,執行緒退出使用 `exit` 系統呼叫,而主行程退出則使用 `exit_group` 系統呼叫,二者的區別更多的是 POSIX 行程和執行緒之間的操作,嚴格來說,`exit` 系統呼叫僅退出目前的 `task_struct`,而 `exit_group` 則是退出目前 `task_struct` 所在行程的所有 `task_struct`,對於多執行緒的程式來說,它當然就是退出所有的執行緒。但 clone 系統呼叫不僅實作多執行緒,它還可改善 fork 系統呼叫的使用效率。對照傳統 UNIX 風格的 fork 系統呼叫,Linux 的 clone 系統呼叫的對應描述如下: 1. 在執行新行程層面,clone 可僅僅 `CLONE_VM` 實作 LWP 來達成快速 exec,避免不必要的資源複製; 2. 在並行多處理層面,如上述,clone 的 `CLONE_` 搭配 `CLONE_THREAD` 可實作核心層級的 POSIX Thread; fork 的思想最終被 Linux 所繼承和發揚光大,一切又回歸到 Conway 在 1963 年提出的論文,並行多處理,終於在 Linux 的 clone 系統呼叫得到落實: * clone 可建立多執行緒,允許程式間並行執行; * clone 建立新行程,減少不必要的資源複製;