IT工程師數位筆記本

進程和線程究竟是什么東西？傳統網絡服務模型是如何工作的？協程和線程的關系和區別有哪些？IO過程在什么時間發生？

一、上下文切換技術

簡述

在進一步之前，讓我們先回顧一下各種上下文切換技術。

不過首先說明一點術語。當我們說“上下文”的時候，指的是程序在執行中的一個狀態。通常我們會用調用棧來表示這個狀態——棧記載了每個調用層級執行到哪里，還有執行時的環境情況等所有有關的信息。

當我們說“上下文切換”的時候，表達的是一種從一個上下文切換到另一個上下文執行的技術。而“調度”指的是決定哪個上下文可以獲得接下去的CPU時間的方法。

進程

進程是一種古老而典型的上下文系統，每個進程有獨立的地址空間，資源句柄，他們互相之間不發生干擾。

每個進程在內核中會有一個數據結構進行描述，我們稱其為進程描述符。這些描述符包含了系統管理進程所需的信息，并且放在一個叫做任務隊列的隊列里面。

很顯然，當新建進程時，我們需要分配新的進程描述符，并且分配新的地址空間(和父地址空間的映射保持一致，但是兩者同時進入COW狀態)。這些過程需要一定的開銷。

進程狀態

忽略去linux內核復雜的狀態轉移表，我們實際上可以把進程狀態歸結為三個最主要的狀態：就緒態，運行態，睡眠態。這就是任何一本系統書上都有的三態轉換圖。

就緒和執行可以互相轉換，基本這就是調度的過程。而當執行態程序需要等待某些條件(最典型就是IO)時，就會陷入睡眠態。而條件達成后，一般會自動進入就緒。

阻塞

當進程需要在某個文件句柄上做IO，這個fd又沒有數據給他的時候，就會發生阻塞。具體來說，就是記錄XX進程阻塞在了XX fd上，然后將進程標記為睡眠態，并調度出去。當fd上有數據時(例如對端發送的數據到達)，就會喚醒阻塞在fd上的進程。進程會隨后進入就緒隊列，等待合適的時間被調度。

阻塞后的喚醒也是一個很有意思的話題。當多個上下文阻塞在一個fd上(雖然不多見，但是后面可以看到一個例子)，而且fd就緒時，應該喚醒多少個上下文呢？傳統上應當喚醒所有上下文，因為如果僅喚醒一個，而這個上下文又不能消費所有數據時，就會使得其他上下文處于無謂的死鎖中。

但是有個著名的例子——accept，也是使用讀就緒來表示收到的。如果試圖用多個線程來accept會發生什么？當有新連接時，所有上下文都會就緒，但是只有第一個可以實際獲得fd，其他的被調度后又立刻阻塞。這就是驚群問題thundering herd problem。

現代linux內核已經解決了這個問題，方法驚人的簡單——accept方法加鎖。

(inet_connection_sock.c:inet_csk_wait_for_connect)

線程

線程是一種輕量進程，實際上在linux內核中，兩者幾乎沒有差別，除了一點——線程并不產生新的地址空間和資源描述符表，而是復用父進程的。
但是無論如何，線程的調度和進程一樣，必須陷入內核態。

二、傳統網絡服務模型

進程模型

為每個客戶分配一個進程。優點是業務隔離，在一個進程中出現的錯誤不至于影響整個系統，甚至其他進程。Oracle傳統上就是進程模型。缺點是進程的分配和釋放有非常高的成本。因此Oracle需要連接池來保持連接減少新建和釋放，同時盡量復用連接而不是隨意的新建連接。

線程模型

為每客戶分配一個線程。優點是更輕量，建立和釋放速度更快，而且多個上下文間的通訊速度非常快。缺點是一個線程出現問題容易將整個系統搞崩潰。

一個例子

py_http_fork_thread.py

在這個例子中，線程模式和進程模式可以輕易的互換。

如何工作的：

1. 父進程監聽服務端口
2. 在有新連接建立的時候，父進程執行fork，產生一個子進程副本
3. 如果子進程需要的話，可以exec(例如CGI)
4. 父進程執行(理論上應當先執行子進程，因為exec執行的快可以避免COW)到accept后，發生阻塞
5. 上下文調度，內核調度器選擇下一個上下文，如無意外，應當就是剛剛派生的子進程
6. 子進程進程進入讀取處理狀態，阻塞在read調用上，所有上下文均進入睡眠態
7. 隨著SYN或者數據報文到來，CPU會喚醒對應fd上阻塞的上下文(wait_queue)，切換到就緒態，并加入調度隊列
8. 上下文繼續執行到下一個阻塞調用，或者因為時間片耗盡被掛起

評價

• 同步模型，編寫自然，每個上下文可以當作其他上下文不存在一樣的操作，每次讀取數據可以當作必然能讀取到。
• 進程模型自然的隔離了連接。即使程序復雜且易崩潰，也只影響一個連接而不是在整個系統。
• 生成和釋放開銷很大(效率測試的進程fork和線程模式開銷測試)，需要考慮復用。
• 進程模式的多客戶通訊比較麻煩，尤其在共享大量數據的時候。

性能

thread模式，虛擬機：

1: 909.27 2: 3778.38 3: 4815.37 4: 5000.04 10: 4998.16 50: 4881.93 100: 4603.24 200: 3445.12 500: 1778.26 (出現錯誤)

fork模式，虛擬機：

1: 384.14 2: 435.67 3: 435.17 4: 437.54 10: 383.11 50: 364.03 100: 320.51 (出現錯誤)

thread模式，物理機：

1: 6942.78 2: 6891.23 3: 6584.38 4: 6517.23 10: 6178.50 50: 4926.91 100: 2377.77

注意在python中，雖然有GIL，但是一個線程陷入到網絡IO的時候，GIL是解鎖的。因此從調用開始到調用結束，減去CPU切換到其他上下文的時間，是可以多線程的。現象是，在此種狀況下可以觀測到短暫的python CPU用量超過100%。

如果執行多個上下文，可以充分利用這段時間。所觀測到的結果就是，只能單核的python，在小范圍內，其隨著并發數上升，性能居然會跟著上升。如果將這個過程轉移到一臺物理機上執行，那么基本不能得出這樣的結論。這主要是因為虛擬機上內核陷入的開銷更高。

三、C10K 問題

描述

當同時連接數在10K左右時，傳統模型就不再適用。實際上在效率測試報告的線程切換開銷一節可以看到，超過1K后性能就差的一塌糊涂了。

進程模型的問題：

在C10K的時候，啟動和關閉這么多進程是不可接受的開銷。事實上單純的進程fork模型在C1K時就應當拋棄了。

Apache的prefork模型，是使用預先分配(pre)的進程池。這些進程是被復用的。但即便是復用，本文所描述的很多問題仍不可避免。

線程模式的問題

從任何測試都可以表明，線程模式比進程模式更耐久一些，性能更好。但是在面對C10K還是力不從心的。問題是，線程模式的問題出在哪里呢？

內存？

有些人可能認為線程模型的失敗首先在于內存。如果你這么認為，一定是因為你查閱了非常老的資料，并且沒仔細思考過。

你可能看到資料說，一個線程棧會消耗8M內存(linux默認值，ulimit可以看到)，512個線程棧就會消耗4G內存，而10K個線程就是80G。所以首先要考慮調整棧深度，并考慮爆棧問題。

聽起來很有道理，問題是——linux的棧是通過缺頁來分配內存的(How does stack allocation work in Linux?)，不是所有棧地址空間都分配了內存。因此，8M是最大消耗，實際的內存消耗只會略大于實際需要的內存(內部損耗，每個在4k以內)。但是內存一旦被分配，就很難回收(除非線程結束)，這是線程模式的缺陷。

這個問題提出的前提是，32位下地址空間有限。雖然10K個線程不一定會耗盡內存，但是512個線程一定會耗盡地址空間。然而這個問題對于目前已經成為主流的64位系統來說根本不存在。

內核陷入開銷？

所謂內核陷入開銷，就是指CPU從非特權轉向特權，并且做輸入檢查的一些開銷。這些開銷在不同的系統上差異很大。

線程模型主要通過陷入切換上下文，因此陷入開銷大聽起來有點道理。實際上，這也是不成立的。線程在什么時候發生陷入切換？正常情況下，應當是IO阻塞的時候。同樣的IO量，難道其他模型就不需要陷入了么？只是非阻塞模型有很大可能直接返回，并不發生上下文切換而已。

效率測試報告的基礎調用開銷一節，證實了當代操作系統上內核陷入開銷是非常驚人的小的(10個時鐘周期這個量級)。

線程模型的問題在于切換成本高

熟悉linux內核的應該知道，近代linux調度器經過幾個階段的發展。

1. linux2.4的調度器
2. O(1)調度器
3. CFS

實際上直到O(1)，調度器的調度復雜度才和隊列長度無關。在此之前，過多的線程會使得開銷隨著線程數增長(不保證線性)。

O(1)調度器看起來似乎是完全不隨著線程的影響。但是這個調度器有顯著的缺點——難于理解和維護，并且在一些情況下會導致交互式程序響應緩慢。
CFS使用紅黑樹管理就緒隊列。每次調度，上下文狀態轉換，都會查詢或者變更紅黑樹。紅黑樹的開銷大約是O(logm)，其中m大約為活躍上下文數(準確的說是同優先級上下文數)，大約和活躍的客戶數相當。

因此，每當線程試圖讀寫網絡，并遇到阻塞時，都會發生O(logm)級別的開銷。而且每次收到報文，喚醒阻塞在fd上的上下文時，同樣要付出O(logm)級別的開銷。

分析

O(logm)的開銷看似并不大，但是卻是一個無法接受的開銷。因為IO阻塞是一個經常發生的事情。每次IO阻塞，都會發生開銷。而且決定活躍線程數的是用戶，這不是我們可控制的。更糟糕的是，當性能下降，響應速度下降時。同樣的用戶數下，活躍上下文會上升(因為響應變慢了)。這會進一步拉低性能。

問題的關鍵在于，http服務并不需要對每個用戶完全公平，偶爾某個用戶的響應時間大大的延長了是可以接受的。在這種情況下，使用紅黑樹去組織待處理fd列表（其實是上下文列表），并且反復計算和調度，是無謂的開銷。

四、多路復用

簡述

要突破C10K問題，必須減少系統內活躍上下文數(其實未必，例如換一個調度器，例如使用RT的SCHED_RR)，因此就要求一個上下文同時處理多個鏈接。而要做到這點，就必須在每次系統調用讀取或寫入數據時立刻返回。否則上下文持續阻塞在調用上，如何能夠復用？這要求fd處于非阻塞狀態，或者數據就緒。

上文所說的所有IO操作，其實都特指了他的阻塞版本。所謂阻塞，就是上下文在IO調用上等待直到有合適的數據為止。這種模式給人一種“只要讀取數據就必定能讀到”的感覺。而非阻塞調用，就是上下文立刻返回。如果有數據，帶回數據。如果沒有數據，帶回錯誤(EAGAIN)。因此，“雖然發生錯誤，但是不代表出錯”。

但是即使有了非阻塞模式，依然繞不過就緒通知問題。如果沒有合適的就緒通知技術，我們只能在多個fd中盲目的重試，直到碰巧讀到一個就緒的fd為止。這個效率之差可想而知。

在就緒通知技術上，有兩種大的模式——就緒事件通知和異步IO。其差別簡要來說有兩點。就緒通知維護一個狀態，由用戶讀取。而異步IO由系統調用用戶的回調函數。就緒通知在數據就緒時就生效，而異步IO直到數據IO完成才發生回調。

linux下的主流方案一直是就緒通知，其內核態異步IO方案甚至沒有被封裝到glibc里去。圍繞就緒通知，linux總共提出過三種解決方案。我們繞過select和poll方案，看看epoll方案的特性。

另外提一點。有趣的是，當使用了epoll后(更準確說只有在LT模式下)，fd是否為非阻塞其實已經不重要了。因為epoll保證每次去讀取的時候都能讀到數據，因此不會阻塞在調用上。

epoll

用戶可以新建一個epoll文件句柄，并且將其他fd和這個"epoll fd"關聯。此后可以通過epoll fd讀取到所有就緒的文件句柄。

epoll有兩大模式，ET和LT。LT模式下，每次讀取就緒句柄都會讀取出完整的就緒句柄。而ET模式下，只給出上次到這次調用間新就緒的句柄。換個說法，如果ET模式下某次讀取出了一個句柄，這個句柄從未被讀取完過——也就是從沒有從就緒變為未就緒。那么這個句柄就永遠不會被新的調用返回，哪怕上面其實充滿了數據——因為句柄無法經歷從非就緒變為就緒的過程。

類似CFS，epoll也使用了紅黑樹——不過是用于組織加入epoll的所有fd。epoll的就緒列表使用的是雙向隊列。這方便系統將某個fd加入隊列中，或者從隊列中解除。

要進一步了解epoll的具體實現，可以參考這篇linux下poll和epoll內核源碼剖析。

性能

如果使用非阻塞函數，就不存在阻塞IO導致上下文切換了，而是變為時間片耗盡被搶占（大部分情況下如此），因此讀寫的額外開銷被消除。而epoll的常規操作，都是O(1)量級的。而epoll wait的復制動作，則和當前需要返回的fd數有關(在LT模式下幾乎就等同于上面的m，而ET模式下則會大大減少)。

但是epoll存在一點細節問題。epoll fd的管理使用紅黑樹，因此在加入和刪除時需要O(logn)復雜度(n為總連接數)，而且關聯操作還必須每個fd調用一次。因此在大連接量下頻繁建立和關閉連接仍然有一定性能問題(超短連接)。不過關聯操作調用畢竟比較少。如果確實是超短連接，tcp連接和釋放開銷就很難接受了，所以對總體性能影響不大。

固有缺陷

原理上說，epoll實現了一個wait_queue的回調函數，因此原理上可以監聽任何能夠激活wait_queue的對象。但是epoll的最大問題是無法用于普通文件，因為普通文件始終是就緒的——雖然在讀取的時候不是這樣。

這導致基于epoll的各種方案，一旦讀到普通文件上下文仍然會阻塞。golang為了解決這個問題，在每次調用syscall的時候，會獨立的啟動一個線程，在獨立的線程中進行調用。因此golang在IO普通文件的時候網絡不會阻塞。

五、事件通知機制下的幾種程序設計模型

簡述

使用通知機制的一大缺憾就是，用戶進行IO操作后會陷入茫然——IO沒有完成，所以當前上下文不能繼續執行。但是由于復用線程的要求，當前線程還需要接著執行。所以，在如何進行異步編程上，又分化出數種方案。

用戶態調度

首先需要知道的一點就是，異步編程大多數情況下都伴隨著用戶態調度問題——即使不使用上下文技術。

因為系統不會自動根據fd的阻塞狀況來喚醒合適的上下文了，所以這個工作必須由其他人——一般就是某種框架——來完成。

你可以想像一個fd映射到對象的大map表，當我們從epoll中得知某個fd就緒后，需要喚醒某種對象，讓他處理fd對應的數據。

當然，實際情況會更加復雜一些。原則上所有不占用CPU時間的等待都需要中斷執行，陷入睡眠，并且交由某種機構管理，等待合適的機會被喚醒。例如sleep，或是文件IO，還有lock。更精確的說，所有在內核里面涉及到wait_queue的，在框架里面都需要做這種機制——也就是把內核的調度和等待搬到用戶態來。

當然，其實也有反過來的方案——就是把程序扔到內核里面去。其中最著名的實例大概是微軟的http服務器了。

這個所謂的“可喚醒可中斷對象”，用的最多的就是協程。

協程

協程是一種編程組件，可以在不陷入內核的情況進行上下文切換。如此一來，我們就可以把協程上下文對象關聯到fd，讓fd就緒后協程恢復執行。
當然，由于當前地址空間和資源描述符的切換無論如何需要內核完成，因此協程所能調度的，只有在同一進程中的不同上下文而已。

如何做到

這是如何做到的呢？

我們在內核里實行上下文切換的時候，其實是將當前所有寄存器保存到內存中，然后從另一塊內存中載入另一組已經被保存的寄存器。對于圖靈機來說，當前狀態寄存器意味著機器狀態——也就是整個上下文。其余內容，包括棧上內存，堆上對象，都是直接或者間接的通過寄存器來訪問的。

但是請仔細想想，寄存器更換這種事情，似乎不需要進入內核態么。事實上我們在用戶態切換的時候，就是用了類似方案。

C coroutine的實現，基本大多是保存現場和恢復之類的過程。python則是保存當前thread的top frame(greenlet)。

但是非常悲劇的，純用戶態方案(setjmp/longjmp)在多數系統上執行的效率很高，但是并不是為了協程而設計的。setjmp并沒有拷貝整個棧(大多數的coroutine方案也不應該這么做)，而是只保存了寄存器狀態。這導致新的寄存器狀態和老寄存器狀態共享了同一個棧，從而在執行時互相破壞。而完整的coroutine方案應當在特定時刻新建一個棧。

而比較好的方案(makecontext/swapcontext)則需要進入內核(sigprocmask)，這導致整個調用的性能非常低。

協程與線程的關系

首先我們可以明確，協程不能調度其他進程中的上下文。而后，每個協程要獲得CPU，都必須在線程中執行。因此，協程所能利用的CPU數量，和用于處理協程的線程數量直接相關。

作為推論，在單個線程中執行的協程，可以視為單線程應用。這些協程，在未執行到特定位置(基本就是阻塞操作)前，是不會被搶占，也不會和其他CPU上的上下文發生同步問題的。因此，一段協程代碼，中間沒有可能導致阻塞的調用，執行在單個線程中。那么這段內容可以被視為同步的。

我們經常可以看到某些協程應用，一啟動就是數個進程。這并不是跨進程調度協程。一般來說，這是將一大群fd分給多個進程，每個進程自己再做fd-協程對應調度。

基于就緒通知的協程框架

1. 首先需要包裝read/write，在發生read的時候檢查返回。如果是EAGAIN，那么將當前協程標記為阻塞在對應fd上，然后執行調度函數。
2. 調度函數需要執行epoll(或者從上次的返回結果緩存中取數據，減少內核陷入次數)，從中讀取一個就緒的fd。如果沒有，上下文應當被阻塞到至少有一個fd就緒。
3. 查找這個fd對應的協程上下文對象，并調度過去。
4. 當某個協程被調度到時，他多半應當在調度器返回的路上——也就是read/write讀不到數據的時候。因此應當再重試讀取，失敗的話返回1。
5. 如果讀取到數據了，直接返回。

這樣，異步的數據讀寫動作，在我們的想像中就可以變為同步的。而我們知道同步模型會極大降低我們的編程負擔。

CPS模型

其實這個模型有個更流行的名字——回調模型。之所以扯上CPS這么高大上的玩意，主要是里面涉及不少有趣的話題。

首先是回調模型的大致過程。在IO調用的時候，同時傳入一個函數，作為返回函數。當IO結束時，調用傳入的函數來處理下面的流程。這個模型聽起來挺簡單的。

然后是CPS。用一句話來描述這個模型——他把一切操作都當作了IO，無論干什么，結果要通過回調函數來返回。從這個角度來說，IO回調模型只能被視作CPS的一個特例。

例如，我們需要計算1+2*3，在cps里面就需要這么寫：

mul(lambda x: add(pprint.pprint, x, 1), 2, 3)

其中mul和add在python里面如下定義：

add = lambda f, *nums: f(sum(nums))
mul = lambda f, *nums: f(reduce(lambda x,y: x*y, nums))

而且由于python沒有TCO，所以這樣的寫法會產生非常多的frame。

但是要正確理解這個模型，你需要仔細思考一下以下幾個問題：

1. 函數的調用過程為什么必須是一個棧？
2. IO過程在什么時間發生？調用發生時，還是回調時？
3. 回調函數從哪里調用？如果當時利用工具去看上下文的話，調用棧是什么樣子的？

函數組件和返回值

不知道你是否思考過為什么函數調用層級(上下文棧)會被表述為一個棧——是否有什么必要性，必須將函數調用的過程定義為一個棧呢？

原因就是返回值和同步順序。對于大部分函數，我們需要得到函數計算的返回值。而要得到返回值，調用者就必須阻塞直到被調用者返回為止。因此調用者的執行狀態就必須被保存，等到被調用者返回后繼續——從這點來說，調用其實是最樸素的上下文切換手段。而對于少部分無需返回的函數，我們又往往需要他的順序外部效應——例如干掉了某個進程，開了一個燈，或者僅僅是在環境變量里面添加了一項內容。而順序外部效應同樣需要等待被調用者返回以表明這個外部效應已經發生。

那么，如果我們不需要返回值也不需要順序的外部效應呢？例如啟動一個背景程序將數據發送到對端，無需保證發送成功的情況下。或者是開始一個數據抓取行為，無需保證抓取的成功。

通常這種需求我們就湊合著用一個同步調用混過去了——反正問題也不嚴重。但是對于阻塞相當嚴重的情況而言，很多人還是會考慮到將這個行為做成異步過程。目前最流行的異步調用分解工具就是mq——不僅異步，而且分布。當然，還有一個更簡單的非分布方案——開一個coroutine。

而CPS則是另一個方向——函數的返回值可以不返回調用者，而是返回給第三者。

IO 過程在什么時間發生

其實這個問題的核心在于——整個回調模型是基于多路復用的還是基于異步IO的？

原則上兩者都可以。你可以監聽fd就緒，也可以監聽IO完成。當然，即使監聽IO完成，也不代表使用了內核態異步接口。很可能只是用epoll封裝的而已。

回調函數的上下文環境

這個問題則需要和上面提到的“用戶態調度框架”結合起來說。IO回調注冊的實質是將回調函數綁定到某個fd上——就如同將coroutine綁定上去那樣。只是coroutine允許你順序的執行，而callback則會切碎函數。當然，大部分實現中，使用callback也有好處——coroutine的最小切換開銷也在50ns，而call本身則只有2ns。

狀態機模型

狀態機模型是一個更難于理解和編程的模型，其本質是每次重入。

想像你是一個周期失憶的病人(就像“一周的朋友”那樣)。那么你如何才能完成一項需要跨越周期的工作呢？例如刺繡，種植作物，或者——交一個男朋友。

當然，類比到失憶病人的例子上必須有一點限制。正常的生活技能，還有一些常識性的東西必須不能在周期失憶范圍內。例如重新學習認字什么的可沒人受的了。

答案就是——做筆記。每次重復失憶后，你需要閱讀自己的筆記，觀察上次做到哪個步驟，下一個步驟是什么。這需要將一個工作分解為很多步驟，在每個步驟內“重入”直到步驟完成，轉移到下一個狀態。

同理，在狀態機模型解法里，每次執行都需要推演合適的狀態，直到工作完成。這個模型已經很少用到了，因為相比回調函數來說，狀態機模型更難理解和使用，性能差異也不大。

最后順帶一提，交一個男友的方案和其他幾個略有不同，主要靠顏好高冷反差萌，一般人就不要嘗試挑戰了。。。當然一般人也不會一周失憶一次，畢竟生活不是韓劇也不是日本動漫。。。