UNIX 作業系統 fork/exec 系統呼叫的前世今生

--- title: UNIX 作業系統 fork/exec 系統呼叫的前世今生 image: https://i.imgur.com/xm1056l.png tags: LINUX KERNEL, LKI --- # UNIX 作業系統 fork/exec 系統呼叫的前世今生資料整理: [jserv](https://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](https://creativecommons.org/licenses/by-sa/4.0/) 本文不僅探究 UNIX 系統的 fork 和 exec 的淵源，並廣泛剖析 fork, exec, exit, wait 等系統呼叫間的緊密聯繫。此外，本文也討論 Linux 核心如何透過 clone 系統呼叫，對 UNIX 的 fork 系統呼叫進行創新詮釋，強調唯有洞悉歷史，才能洞見未來。 ![](https://hackmd.io/_uploads/HJBvf7h-c.png) > 出處: [forked!](https://turnoff.us/geek/forked/) ## 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 年前即存在。 > 可線上查閱 UNIX 第一版的技術手冊，[section 2](https://man.cat-v.org/unix-1st/) 即是系統呼叫 1960 年代中期，與阿波羅登月計劃齊頭並進的 [Project MAC](https://multicians.org/project-mac.html) 啟動，這是個由 DARPA 贊助的宏大計畫，旨在開發一個能夠支援多使用者、分時多工，並運作於多處理器 (multi-processor) 硬體環境的作業系統 —— [Multics ](https://web.mit.edu/multics-history/)。有意思的是，Project MAC 這麼龐大的計畫卻由麻省理工學院 (MIT) 領軍開發關鍵技術，並由 GE (美國通用電氣，也稱奇異公司) 提供硬體及 AT&T 旗下的 Bell Labs 開發軟體和技術支持 (受到反壟斷條款的處分，AT&T 不得涉及硬體銷售，但研發專利技術並授權他人不在此限，於是軟體技術就成為 Bell Labs 的施力點)，今日我們熟知的 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-" 形成鮮明對比，這類命名的幽默持續在泛 UNIX 的系統中出現。隨後 UNICS 正式更名為 UNIX，從此名聲大噪，深遠影響我們生活的各個層面。UNIX 最初使用組合語言開發，主要提供檔案系統服務。隨後，它被用 C 語言重寫，其中 [Research UNIX](https://en.wikipedia.org/wiki/Research_Unix) version 6（簡稱 V6）在貝爾實驗室所屬的 AT&T 對 UNIX 施加高昂授權費之前，V6 已被眾多學校和企業廣泛採用。在 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) (名詞)，這詞彙在中國簡體稱為「并发」。本文使用「並行」指 concurrent/concurrency。 $\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: 我們考慮以下流程圖: ```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](https://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 (及其家族) 超過 50 年，和 [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](https://pages.cs.wisc.edu/~remzi/OSTEP/)》，在其〈[The Abstraction: The Process](https://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](https://people.eecs.berkeley.edu/~brewer/cs262/unix.pdf)〉，由 Ken Thompson 和 Dennis Ritchie 在 1973 年 10 月 ACM [Symposium on Operating Systems Principles](https://www.sosp.org/) (SOSP) 中提出，稍後於 1974 年 7 月的 [Communications of the ACM](https://cacm.acm.org/) 發表，正是採用分時多工作為主題。 :::success 至於《[Operating Systems: Three Easy Pieces](https://pages.cs.wisc.edu/~remzi/OSTEP/)》(可簡稱為 OSTEP) 的 "Three Easy Pieces" 也有典故，是向已故物理學家費曼致敬，後者著有《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](https://en.wikipedia.org/wiki/John_Lions) 針對 V6 原始程式碼進行註解，集結成冊《[Lions' Commentary on UNIX 6th Edition, with Source Code](https://en.wikipedia.org/wiki/Lions%27_Commentary_on_UNIX_6th_Edition,_with_Source_Code)》(簡稱 Lions Book)，獲得廣泛流傳。該書對電腦科學的影響，猶如普羅米修斯將火種 (V6 的運作奧秘和程式碼) 帶到人類世界。因此，大部分論及 Unix 的材料是從 v6 講起，算是較為「現代」的版本，即便是[在 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](https://www.read.seas.harvard.edu/~kohler/class/aosref/ritchie84evolution.pdf)〉窺知樣貌。最初的 Unix 雖然是個分時系統 (Time-sharing System)，但裡頭只有二個 shell 行程，分別屬於二個終端機 ([terminal](https://en.wikipedia.org/wiki/Computer_terminal)，對應到 Linux 核心的 tty 子系統，對照閱讀〈[看漫畫學 Linux](https://hackmd.io/@sysprog/linux-comic)〉以得知其發展脈絡)，不難見其簡陋。 > 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"，之所以不叫 Version 0，是因為在 1971 年 11 月 [UNIX 手冊](https://www.bell-labs.com/usr/dmr/www/1stEdman.html)在 Bell Labs 發布以前，Unix 程式碼經歷大量變更，為避免討論的歧異，本文特別標示 Ken Unix 為最早期的 Unix 實作，儘管當時甚至不叫 Unix 這名稱。事實上，Ken Unix 用二個單元構成的區塊 (Process Control Block, PCB) 來容納所有行程，此處「區塊」僅為概念，因為 Ken Unix 用 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/)，內附場景重現的短片，甚至可藉由 [SimH](http://simh.trailing-edge.com/) 模擬器來執行，參見 [pdp7-unix](https://github.com/DoctorWkt/pdp7-unix) 我們現在考慮其中一個終端機的 shell 行程如何工作，問題馬上就浮現：「這個 shell 行程該如何執行別的程式」？如果說系統中最多只能容納二個行程，一個終端機只有一個行程的話，當該終端機的 shell 執行其他程式時他自己該怎麼辦？ :::warning 注意: 不要用現代的眼光去評價 1969 年的 Unix。按照現代的眼光，執行一個程式 (program，靜態存在於儲存媒介中) 必然要產生一個新的行程 (process，執行中的「程式」，自儲存媒介中載入)，顯然這在初版的 Unix 中並不適用。 ::: 答案是根本不用產生新的行程，直接將程式碼載入記憶體並「覆疊」(overlay) 掉 shell 所在的記憶體空間即可！當程式執行完後，再用 shell 的程式碼覆疊回去原本的記憶體空間。針對單獨的終端機，系統其實一直在執行下面的覆疊循環。以下摘自〈[The Evolution of the Unix Time-sharing System](https://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://hackmd.io/_uploads/rkWGjiBxn.png) 結合上圖和覆疊循環的第 3 步，你會發現該步驟就是 exec 的邏輯。若你熟悉 Linux 核心裡頭 `execve` 系統呼叫載入 ELF 執行檔的邏輯，你會發現對他們而言，這裡所謂的 bootstrap 其實是 [load_elf_binary 函式](https://elixir.bootlin.com/linux/v6.8.2/source/fs/binfmt_elf.c#L819)。然而，當時畢竟還沒有將這個邏輯封裝為 exec 系統呼叫，所以每一個行程都需要實作這些動作: * shell 需要執行程式時，執行磁碟 (disk) I/O 來載入程式覆疊掉自己 * 程式結束時，exit 讓磁碟 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) 到磁碟即可。很顯然，程式不能夠覆疊掉 shell 行程。解決方案是用「置換」(swap)。不只在 UNIX，「置換」和「覆疊」都曾在多款作業系統中，用來解決有限記憶體的多行程 (或「多任務」) 使用問題，不同點在於二者方向不同: * 覆疊：用不同的行程磁碟映像 (image) 覆疊目前行程的記憶體映像 * 置換：將行程的記憶體映像置換到磁碟，再載入別的行程的磁碟映像使用置換手法解決覆疊的問題，意味著要建立新的行程: * 在新的行程中執行程式 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 經費支持)，其分時多工系統稱為 [Berkeley Timesharing System](https://en.wikipedia.org/wiki/Berkeley_Timesharing_System)，Project Genie 的成果最終商業化為 [Scientific Data Systems](https://en.wikipedia.org/wiki/Scientific_Data_Systems) (SDS) 公司的 [SDS 940](https://en.wikipedia.org/wiki/SDS_940) 大型電腦裡頭的分時多工作業系統，而 Ken Thompson 在 UC Berkeley 進修時，一度投入 SDS 940 的開發。1969 年，SDS 被 Xerox 收購，SDS 940 則更名為 XDS，表示 "Xerox Data Systems"。 > 延伸閱讀: 《[The Computers Nobody Wanted: My Years at Xerox](https://worrydream.com/refs/Strassmann_2008_-_The_Computers_Nobody_Wanted,_My_Years_With_Xerox.pdf)》，該書第 22 頁的 "SDS was also a user of early versions of the UNIX operating system that was favored by defense firms." 描述不正確，SDS 創立時主要客戶就是軍方及其供應商，且 SDS 被 Xerox 收購時，Unix 尚未發展。不過該書談及 SDS 是早期採納積體電路和電晶體的公司，且積極擁抱新技術來滿足 NASA 一類客戶的需求，甚至在 1960 年代就實作支援虛擬記憶體的硬體，軟體的推進更是不遑多讓，Xerox 在收購 SDS 後，催生 Palo Alto Research Center (PARC)，許多關鍵電腦技術，像是電腦網路和圖形人機介面，就源於 PARC。 Berkeley Timesharing System 的 fork 並非盲目地複製行程，對 fork 的過程有精細的控制權，例如可決定要配置多大的記憶體空間、複製哪些必要的資源等等。顯然，Berkeley Timesharing System 的 fork 依循著 Conway 的多處理器並行邏輯而實作，可對照閱讀 1968 年發行的〈[SDS 940 Time-Sharing System Version 2.0 Technical Manual](https://bitsavers.org/pdf/sds/9xx/940/901116B_940_TimesharingTechMan_Aug68.pdf)〉第 11 頁 "Forking Structure"。 Unix 若想要實作複製行程，有 Berkeley Timesharing System 這個現成的典範可參考，但後者的 fork 對於 Unix 太過精細且複雜，而 Unix 顯然不需要有這麼精細的控制 —— Unix 僅想要讓 fork 出來的新行程被覆疊，而非顧及執行於多處理器上的並行邏輯。換句話說，Unix 只是借用 fork 的複製邏輯，最終作出不同的實作。於是，Unix 非常粗暴地實作 fork！ (就是完全複製親代行程而已) 而這仍是我們現在使用的 fork 系統呼叫。 ```c 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](https://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=<fork>] B [label="create task" style=filled] C [label="fork task"] D [label="copy resource" style=filled] E [label=<exec>] F [label="release resource" style=filled] G [label="reload resource" style=filled] H [label="fork ret" style=filled] I [label=<exit>] J [label="release resource" style=filled] K [label="new task"] L [label=<wait>] 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) 等人發表在 HotOS 2019 的研究 [A fork() in the road](https://www.microsoft.com/en-us/research/uploads/prod/2019/04/fork-hotos19-slides.pdf) 清晰地交代 fork 系統呼叫是如何一步一步走向今日複雜的面貌。 > [論文全文](https://www.microsoft.com/en-us/research/uploads/prod/2019/04/fork-hotos19.pdf) 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 位元虛擬定址空間 (即 512 GiB) 或 48 位元虛擬定址空間 (即 256 TiB)，其實就是避免分頁開銷過度增長。 > 參見: [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 語言函式的認知，建立行程的函式原型宣告應該要長這樣: ```c 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](https://man7.org/linux/man-pages/man2/clone.2.html) 系統呼叫嗎？用法如下: ```c #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()](https://man7.org/linux/man-pages/man2/clone.2.html) creates a new process, in a manner similar to [fork(2)](https://man7.org/linux/man-pages/man2/fork.2.html). > … > 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 呼叫結束後就什麼都有。也就是說，新行程繼承親代行程的一切！記住，一切都繼承自親代行程，連同程式碼也是。所以說，你想要設定新行程的優先權，你就必須在新行程中進行變更： ```c if (fork() == 0) { // 變更優先等級 nice(-3); } else { ... } ``` 而非這樣: ```c 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 位元的系統中這問題會更嚴重。多層次的分頁表主要解決稠密地址空間不必要的分頁表配置問題，本身無法節省記憶體。相反地，在稀疏地址空間，這樣做更會浪費記憶體空間。  參見下圖，我們構建一個稀疏的地址空間的多層分頁表。若僅有一層，只有葉節點需要佔據記憶體，多層分頁表則整棵樹都要佔據記憶體空間: ```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 帶來的記憶體開銷 > TODO: 探討 CoW 以下程式碼為例： ```c /* page-table-mm-usage.c */ #include <string.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/wait.h> #include <sys/types.h> #include <sys/mman.h> #define GIG (1ul << 30) #define NGIG 16 #define SIZE (NGIG * GIG) #define BUFFER_SIZE 512 unsigned int parser(char *buffer, const char *symbol) { if (strstr(buffer, symbol)) { char dump1[BUFFER_SIZE]; char dump2[BUFFER_SIZE]; unsigned int tmp; sscanf(buffer, "%s %u %s", dump1, &tmp, dump2); return tmp; } return 0; } void read_file(const char *prefix) { int pid = (int)getpid(); char file[BUFFER_SIZE] = { 0 }; char buffer[BUFFER_SIZE] = { 0 }; FILE *fp = NULL; unsigned int vmPTE = 0; sprintf(file, "/proc/%d/status", pid); fp = fopen(file, "r"); if (!fp) { perror("fopen"); exit(1); } while (fgets(buffer, BUFFER_SIZE, fp)) { buffer[BUFFER_SIZE - 1] = '\0'; vmPTE += parser(buffer, "VmPTE"); memset(buffer, '0', BUFFER_SIZE); } fclose(fp); printf("[%s] [PID %d] VmPTE:%u kB\n", prefix, pid, vmPTE); } void touch(char *p, int page_size) { /* Touch every page */ for (int i = 0; i < SIZE; i += page_size) p[i] = 0; } int main(void) { int pid, page_size = getpagesize(); char *p = NULL; p = mmap(NULL, SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (p == MAP_FAILED) { perror("mmap"); exit(1); } madvise(p, SIZE, MADV_NOHUGEPAGE); touch(p, page_size); pid = fork(); if (pid == 0) { sleep(4); read_file("Child"); if (execl("/bin/bash", "bash", "script.sh", NULL) < 0) perror("execl"); exit(0); } read_file("Parent"); waitpid(pid, NULL, 0); return 0; } ``` 測試用的腳本: (檔名 `script.sh`) ```shell #!/usr/bin/env bash echo -n "[exec] [PID $$] VmPTE:" awk '/VmPTE:/{ sum = $2 } END { printf "%u", sum }' /proc/$$/status echo " kB" ``` 執行程式後，得到類似以下輸出： ``` [Parent] [PID 3945868] VmPTE:4152 kB [Child] [PID 3945869] VmPTE:4152 kB [exec] [PID 3945869] VmPTE:52 kB ``` 因親代行程配置大量的記憶體，且在其後持續寫入，以確保此記憶體確實被配置，可從第一行輸出見到 PTE table 有顯著的記憶體開銷。隨後，親代行程呼叫 `fork`，子行程也因此複製親代行程的分頁表 (page table)，於是子行程的 PTE table 也與親代行程相同。當子行程呼叫 `exec` 以執行 `script.sh` 後，PTE table 的記憶體使用量減少。可見在 `exec` 前，親代行程都配置同樣的記憶體空間在分頁表，然而子行程根本不需要。若只是利用 fork + exec 執行一個記憶體開銷極小的程式，可能會因親代行程的稀疏 (sparse) 定址空間，導致在 fork 時配置大量的分頁表，進而導致非必要的記憶體開銷。上述實驗向我們闡明，在下面的條件被滿足的場景中，fork 呼叫光是分頁表的記憶體開銷相當巨大: * 親代行程地址空間是 sparse 或 large 的; * 子行程 exec 在親代行程之前複製親代行程的地址空間; 這些條件在大型伺服器的背景服務 (daemon) 中非常容易被滿足，例如 memcached 和 redis。若在記憶體吃緊之際誤用 fork，說不定會失敗，更嚴重甚至會觸發系統核心的 OOM ([out-of-memory](https://www.kernel.org/doc/gorman/html/understand/understand016.html))。往往 fork 出來的子行程僅進行一些非常簡單的工作，這類分頁表的開銷完全沒有必要。這個問題之所以沒成為普遍的問題，確實部份原因是，並非所有的親代行程都是稀疏地址空間，且恰好親代行程的記憶體剛好都不是 file-backed mapping 這樣可讓作業系統進行 lazy fork （不在 fork 系統呼叫時配置分頁表及 CoW，而是在 page fault 之際才進行）。但這並不能掩蓋問題本身，上面的例子不就建立這樣的場景嗎？此外，該議題不受重視還有個原因是，即便是稀疏地址空間的分頁表影響記憶體消耗，該消耗是稍縱即逝。一般而言，子行程會馬上呼叫 exec，對作業系統核心的影響彷彿是被針扎一下，稍後就無感。換言之，不是不想發現問題，而是過往的工具捕捉不到如此精細的事件，同樣的事情也發生在 Linux 核心中 CPU 排程器的負載平衡，詳見〈[The Linux Scheduler: a Decade of Wasted Cores](https://people.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](https://man7.org/linux/man-pages/man2/mmap.2.html) 即可。也許你把事情想簡單，下面程式碼可達到我們的要求嗎？ ```c for (i = 0; i < 100000000; i++) { data = mmap(NULL, ps - 1, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0); cnt++; } ``` 答案是不行！ Linux 核心的最佳化策略用漢語來說，就是「見縫插針」。如果你按照上面的邏輯呼叫 mmap，Linux 核心通常會把超級多個 mmap 區域 (即 `vm_area_struct` 物件) 合併成一個。可進行合併操作的前提很簡單，只要二個 `vm_area_struct` 物件的首尾連續即可。為了不讓核心進行這種合併，我們要保留 mmap 的 FIXED 參數。 ```c 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](https://man7.org/linux/man-pages/man1/slabtop.1.html) 觀察會更有趣。有時你若只看 `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，會發生死結！ ![](https://hackmd.io/_uploads/r1-sXX2bc.png) > 出處: [brothers conflict (at linux kernel)](https://turnoff.us/geek/brothers-conflict/) 根源是，**多個 `task_struct` 在操作同一個地址空間，但 fork 只參照呼叫者的狀態進行地址空間的複製!** 重現的程式碼很簡單： ```c #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("No deadlock\n"); } sleep(1000); return 0; } ``` 編譯並執行後，遲遲等不到 "No deadlock" 字串的出現。由於這是 fork 自己的問題，所以 POSIX Thread 引入特殊的函式來處理： ```c 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` 的操作。 ```c 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](https://man7.org/linux/man-pages/man2/vfork.2.html) 與 fork 具有相同呼叫方式，但僅能在特定情況使用。[vfork](https://man7.org/linux/man-pages/man2/vfork.2.html) 源於 3BSD，後者是首個支援虛擬記憶體的 UNIX。但 vfork 已在 2004 年的版本中被標為過時，並在後續版本中被 [posix_spawn](https://man7.org/linux/man-pages/man3/posix_spawn.3.html) 所取代。在發出一個 vfork 系統呼叫時，親代行程被暫停，直至子行程完成執行或被新的可執行映像取代（經由系統呼叫之 exec 家族中的一項）。子行程借用親代行程的 MMU 設定和記憶體頁面，在親代行程與子行程之間共享，不進行複製，尤其是缺乏 CoW 的行為。因此，若子行程在任何共享頁面中進行修改，不會建立新的頁面，且修改的頁面對親代行程同樣可見。 System V 在 Release 4 (SVR4) 之前，不支援 [vfork](https://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 的手冊頁面](https://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://hackmd.io/_uploads/SkSmoorx3.png) 在傳統 UNIX 系統或者類 UNIX 系統，則沒有 clone 這樣的系統呼叫。箇中原因可能是 UNIX 一開始就明確定義行程的實作，到後來，當 UNIX 不得不支持執行緒的時候，就要引入一個所謂輕量級行程 (LWP) 的概念，意思是可共享某些資源的行程，這以 Solaris 的 LWP 實作最為出名。在這些老牌 Unix 系統中，一開始過重的行程概念在引入多執行緒機制時造成阻礙。然而對於 Linux，為了支持執行緒而引入新的資料結構則完全沒有必要 —— Linux 核心內部沒有表示 LWP 的結構體。 Linux 核心在底層 task 設計及系統呼叫介面如此這般的設計，注定它實作 POSIX Thread 規範可相當容易，一個參數的指定即可達成: ![image](https://hackmd.io/_uploads/ryHbKV71C.png) 注意上述 `(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` 為基礎來實作，可見上述的手冊資訊。該如何建立一個執行緒呢？我們來看以下程式碼: ```c #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://hackmd.io/_uploads/S194iiBxn.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` 如下: ```c 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 建立新行程，減少不必要的資源複製; ## 待整理 * [A fork() in the road](https://www.microsoft.com/en-us/research/uploads/prod/2019/04/fork-hotos19.pdf), HotOS'19

Read more

Linux 核心設計: 中斷處理和現代架構考量

2024q1 第 4 週測驗題

2024q1 第 10 週測驗題

Linux 核心設計: 透過 eBPF 觀察作業系統行為