---

前言

先來看看一則小故事

我們寫好的一行行程式碼，為了讓其工作起來，我們還得把它送進城（進程）里，那既然進了城裡，那肯定不能胡作非為了。

城裡人有城裡人的規矩，城中有個專門管轄你們的城管（作業系統），人家讓你休息就休息，讓你工作就工作，畢竟攤位不多，每個人都要佔這個攤位來工作，城裡要工作的人多著去了。

所以城管為了公平起見，它使用一種策略（調度）方式，給每個人一個固定的工作時間（時間片），時間到了就會通知你去休息而換另外一個人上場工作。

另外，在休息時候你也不能偷懶，要記住工作到哪了，不然下次到你工作了，你忘記工作到哪了，那還怎麼繼續？

有的人，可能還進入了縣城（執行緒）工作，這裡相對輕鬆一些，在休息的時候，要記住的東西相對較少，而且還能共享城裡的資源。

「哎喲，難道本文內容是進程和執行緒？」

可以，聰明的你猜出來了，也不枉費我瞎編亂造的故事了。

進程和執行緒對於寫程式碼的我們，真的天天見、日日見了，但見的多不代表你就熟悉它們，比如簡單問你一句，你知道它們的工作原理和區別嗎？

不知道沒關係，今天就要跟大家討論作業系統的進程和執行緒。

提綱

---

正文

進程

我們編寫的程式碼只是一個存儲在硬碟的靜態文件，通過編譯後就會生成二進位可執行文件，當我們運行這個可執行文件後，它會被裝載到記憶體中，接著 CPU 會執行程式中的每一條指令，那麼這個運行中的程式，就被稱為「進程」。

現在我們考慮有一個會讀取硬碟文件數據的程式被執行了，那麼當運行到讀取文件的指令時，就會去從硬碟讀取數據，但是硬碟的讀寫速度是非常慢的，那麼在這個時候，如果 CPU 傻傻的等硬碟返回數據的話，那 CPU 的利用率是非常低的。

做個類比，你去煮開水時，你會傻傻的等水壺燒開嗎？很明顯，小孩也不會傻等。我們可以在水壺燒開之前去做其他事情。當水壺燒開了，我們自然就會聽到「嘀嘀嘀」的聲音，於是再把燒開的水倒入到水杯里就好了。

所以，當進程要從硬碟讀取數據時，CPU 不需要阻塞等待數據的返回，而是去執行另外的進程。當硬碟數據返回時，CPU 會收到個中斷，於是 CPU 再繼續運行這個進程。

進程 1 與進程 2 切換

這種多個程式、交替執行的思想，就有 CPU 管理多個進程的初步想法。

對於一個支援多進程的系統，CPU 會從一個進程快速切換至另一個進程，其間每個進程各運行幾十或幾百個毫秒。

雖然單核的 CPU 在某一個瞬間，只能運行一個進程。但在 1 秒鐘期間，它可能會運行多個進程，這樣就產生並行的錯覺，實際上這是並發。

並發和並行有什麼區別？

一圖勝千言。

並發與並行

進程與程式的關係的類比

到了晚飯時間，一對小情侶肚子都咕咕叫了，於是男生見機行事，就想給女生做晚飯，所以他就在網上找了辣子雞的菜譜，接著買了一些雞肉、辣椒、香料等材料，然後邊看邊學邊做這道菜。

突然，女生說她想喝可樂，那麼男生只好把做菜的事情暫停一下，並在手機菜譜標記做到哪一個步驟，把狀態資訊記錄了下來。

然後男生聽從女生的指令，跑去下樓買了一瓶冰可樂後，又回到廚房繼續做菜。

這體現了，CPU 可以從一個進程（做菜）切換到另外一個進程（買可樂），在切換前必須要記錄當前進程中運行的狀態資訊，以備下次切換回來的時候可以恢復執行。

所以，可以發現進程有著「運行 – 暫停 – 運行」的活動規律。

進程的狀態

在上面，我們知道了進程有著「運行 – 暫停 – 運行」的活動規律。一般說來，一個進程並不是自始至終連續不停地運行的，它與並發執行中的其他進程的執行是相互制約的。

它有時處於運行狀態，有時又由於某種原因而暫停運行處於等待狀態，當使它暫停的原因消失後，它又進入準備運行狀態。

所以，在一個進程的活動期間至少具備三種基本狀態，即運行狀態、就緒狀態、阻塞狀態。

進程的三種基本狀態

上圖中各個狀態的意義：

• 運行狀態（Runing）：該時刻進程佔用 CPU；
• 就緒狀態（Ready）：可運行，但因為其他進程正在運行而暫停停止；
• 阻塞狀態（Blocked）：該進程正在等待某一事件發生（如等待輸入/輸出操作的完成）而暫時停止運行，這時，即使給它CPU控制權，它也無法運行；

當然，進程另外兩個基本狀態：

• 創建狀態（new）：進程正在被創建時的狀態；
• 結束狀態（Exit）：進程正在從系統中消失時的狀態；

於是，一個完整的進程狀態的變遷如下圖：

進程五種狀態的變遷

再來詳細說明一下進程的狀態變遷：

• NULL -> 創建狀態：一個新進程被創建時的第一個狀態；
• 創建狀態 -> 就緒狀態：當進程被創建完成並初始化後，一切就緒準備運行時，變為就緒狀態，這個過程是很快的；
• 就緒態 -> 運行狀態：處於就緒狀態的進程被作業系統的進程調度器選中後，就分配給 CPU 正式運行該進程；
• 運行狀態 -> 結束狀態：當進程已經運行完成或出錯時，會被作業系統作結束狀態處理；
• 運行狀態 -> 就緒狀態：處於運行狀態的進程在運行過程中，由於分配給它的運行時間片用完，作業系統會把該進程變為就緒態，接著從就緒態選中另外一個進程運行；
• 運行狀態 -> 阻塞狀態：當進程請求某個事件且必須等待時，例如請求 I/O 事件；
• 阻塞狀態 -> 就緒狀態：當進程要等待的事件完成時，它從阻塞狀態變到就緒狀態；

如果有大量處於阻塞狀態的進程，進程可能會佔用著物理記憶體空間，顯然不是我們所希望的，畢竟物理記憶體空間是有限的，被阻塞狀態的進程佔用著物理記憶體就一種浪費物理記憶體的行為。

所以，在虛擬記憶體管理的作業系統中，通常會把阻塞狀態的進程的物理記憶體空間換出到硬碟，等需要再次運行的時候，再從硬碟換入到物理記憶體。

虛擬記憶體管理-換入換出

那麼，就需要一個新的狀態，來描述進程沒有佔用實際的物理記憶體空間的情況，這個狀態就是掛起狀態。這跟阻塞狀態是不一樣，阻塞狀態是等待某個事件的返回。

另外，掛起狀態可以分為兩種：

• 阻塞掛起狀態：進程在外存（硬碟）並等待某個事件的出現；
• 就緒掛起狀態：進程在外存（硬碟），但只要進入記憶體，即刻立刻運行；

這兩種掛起狀態加上前面的五種狀態，就變成了七種狀態變遷（留給我的顏色不多了），見如下圖：

七種狀態變遷

導致進程掛起的原因不只是因為進程所使用的記憶體空間不在物理記憶體，還包括如下情況：

• 通過 sleep 讓進程間歇性掛起，其工作原理是設置一個定時器，到期後喚醒進程。
• 用戶希望掛起一個程式的執行，比如在 Linux 中用 Ctrl+Z 掛起進程；

進程的控制結構

在作業系統中，是用進程式控制制塊（process control block，PCB）數據結構來描述進程的。

那 PCB 是什麼呢？打開知乎搜索你就會發現這個東西並不是那麼簡單。

知乎搜 PCB 的提示

打住打住，我們是個正經的人，怎麼會去看那些問題呢？是吧，回來回來。

PCB 是進程存在的唯一標識，這意味著一個進程的存在，必然會有一個 PCB，如果進程消失了，那麼 PCB 也會隨之消失。

PCB 具體包含什麼資訊呢？

進程描述資訊：

• 進程標識符：標識各個進程，每個進程都有一個並且唯一的標識符；
• 用戶標識符：進程歸屬的用戶，用戶標識符主要為共享和保護服務；

進程式控制制和管理資訊：

• 進程當前狀態，如 new、ready、running、waiting 或 blocked 等；
• 進程優先順序：進程搶佔 CPU 時的優先順序；

資源分配清單：

• 有關記憶體地址空間或虛擬地址空間的資訊，所打開文件的列表和所使用的 I/O 設備資訊。

CPU 相關資訊：

• CPU 中各個暫存器的值，當進程被切換時，CPU 的狀態資訊都會被保存在相應的 PCB 中，以便進程重新執行時，能從斷點處繼續執行。

可見，PCB 包含資訊還是比較多的。

每個 PCB 是如何組織的呢？

通常是通過鏈表的方式進行組織，把具有相同狀態的進程鏈在一起，組成各種隊列。比如：

• 將所有處於就緒狀態的進程鏈在一起，稱為就緒隊列；
• 把所有因等待某事件而處於等待狀態的進程鏈在一起就組成各種阻塞隊列；
• 另外，對於運行隊列在單核 CPU 系統中則只有一個運行指針了，因為單核 CPU 在某個時間，只能運行一個程式。

那麼，就緒隊列和阻塞隊列鏈表的組織形式如下圖：

就緒隊列和阻塞隊列

除了鏈接的組織方式，還有索引方式，它的工作原理：將同一狀態的進程組織在一個索引表中，索引表項指向相應的 PCB，不同狀態對應不同的索引表。

一般會選擇鏈表，因為可能面臨進程創建，銷毀等調度導致進程狀態發生變化，所以鏈表能夠更加靈活的插入和刪除。

進程的控制

我們熟知了進程的狀態變遷和進程的數據結構 PCB 後，再來看看進程的創建、終止、阻塞、喚醒的過程，這些過程也就是進程的控制。

01 創建進程

作業系統允許一個進程創建另一個進程，而且允許子進程繼承父進程所擁有的資源，當子進程被終止時，其在父進程處繼承的資源應當還給父進程。同時，終止父進程時同時也會終止其所有的子進程。

創建進程的過程如下：

• 為新進程分配一個唯一的進程標識號，並申請一個空白的 PCB，PCB 是有限的，若申請失敗則創建失敗；
• 為進程分配資源，此處如果資源不足，進程就會進入等待狀態，以等待資源；
• 初始化 PCB；
• 如果進程的調度隊列能夠接納新進程，那就將進程插入到就緒隊列，等待被調度運行；

02 終止進程

進程可以有 3 種終止方式：正常結束、異常結束以及外界干預（訊號 kill 掉）。

終止進程的過程如下：

• 查找需要終止的進程的 PCB；
• 如果處於執行狀態，則立即終止該進程的執行，然後將 CPU 資源分配給其他進程；
• 如果其還有子進程，則應將其所有子進程終止；
• 將該進程所擁有的全部資源都歸還給父進程或作業系統；
• 將其從 PCB 所在隊列中刪除；

03 阻塞進程

當進程需要等待某一事件完成時，它可以調用阻塞語句把自己阻塞等待。而一旦被阻塞等待，它只能由另一個進程喚醒。

阻塞進程的過程如下：

• 找到將要被阻塞進程標識號對應的 PCB；
• 如果該進程為運行狀態，則保護其現場，將其狀態轉為阻塞狀態，停止運行；
• 將該 PCB 插入的阻塞隊列中去；

04 喚醒進程

進程由「運行」轉變為「阻塞」狀態是由於進程必須等待某一事件的完成，所以處於阻塞狀態的進程是絕對不可能叫醒自己的。

如果某進程正在等待 I/O 事件，需由別的進程發消息給它，則只有當該進程所期待的事件出現時，才由發現者進程用喚醒語句叫醒它。

喚醒進程的過程如下：

• 在該事件的阻塞隊列中找到相應進程的 PCB；
• 將其從阻塞隊列中移出，並置其狀態為就緒狀態；
• 把該 PCB 插入到就緒隊列中，等待調度程式調度；

進程的阻塞和喚醒是一對功能相反的語句，如果某個進程調用了阻塞語句，則必有一個與之對應的喚醒語句。

進程的上下文切換

各個進程之間是共享 CPU 資源的，在不同的時候進程之間需要切換，讓不同的進程可以在 CPU 執行，那麼這個一個進程切換到另一個進程運行，稱為進程的上下文切換。

在詳細說進程上下文切換前，我們先來看看 CPU 上下文切換

大多數作業系統都是多任務，通常支援大於 CPU 數量的任務同時運行。實際上，這些任務並不是同時運行的，只是因為系統在很短的時間內，讓各個任務分別在 CPU 運行，於是就造成同時運行的錯覺。

任務是交給 CPU 運行的，那麼在每個任務運行前，CPU 需要知道任務從哪裡載入，又從哪裡開始運行。

所以，作業系統需要事先幫 CPU 設置好 CPU 暫存器和程式計數器。

CPU 暫存器是 CPU 內部一個容量小，但是速度極快的記憶體（快取）。我舉個例子，暫存器像是你的口袋，記憶體像你的書包，硬碟則是你家裡的柜子，如果你的東西存放到口袋，那肯定是比你從書包或家裡柜子取出來要快的多。

再來，程式計數器則是用來存儲 CPU 正在執行的指令位置、或者即將執行的下一條指令位置。

所以說，CPU 暫存器和程式計數是 CPU 在運行任何任務前，所必須依賴的環境，這些環境就叫做 CPU 上下文。

既然知道了什麼是 CPU 上下文，那理解 CPU 上下文切換就不難了。

CPU 上下文切換就是先把前一個任務的 CPU 上下文（CPU 暫存器和程式計數器）保存起來，然後載入新任務的上下文到這些暫存器和程式計數器，最後再跳轉到程式計數器所指的新位置，運行新任務。

系統內核會存儲保持下來的上下文資訊，當此任務再次被分配給 CPU 運行時，CPU 會重新載入這些上下文，這樣就能保證任務原來的狀態不受影響，讓任務看起來還是連續運行。

上面說到所謂的「任務」，主要包含進程、執行緒和中斷。所以，可以根據任務的不同，把 CPU 上下文切換分成：進程上下文切換、執行緒上下文切換和中斷上下文切換。

進程的上下文切換到底是切換什麼呢？

進程是由內核管理和調度的，所以進程的切換隻能發生在內核態。

所以，進程的上下文切換不僅包含了虛擬記憶體、棧、全局變數等用戶空間的資源，還包括了內核堆棧、暫存器等內核空間的資源。

通常，會把交換的資訊保存在進程的 PCB，當要運行另外一個進程的時候，我們需要從這個進程的 PCB 取出上下文，然後恢復到 CPU 中，這使得這個進程可以繼續執行，如下圖所示：

進程上下文切換

大家需要注意，進程的上下文開銷是很關鍵的，我們希望它的開銷越小越好，這樣可以使得進程可以把更多時間花費在執行程式上，而不是耗費在上下文切換。

發生進程上下文切換有哪些場景？

• 為了保證所有進程可以得到公平調度，CPU 時間被劃分為一段段的時間片，這些時間片再被輪流分配給各個進程。這樣，當某個進程的時間片耗盡了，進程就從運行狀態變為就緒狀態，系統從就緒隊列選擇另外一個進程運行；
• 進程在系統資源不足（比如記憶體不足）時，要等到資源滿足後才可以運行，這個時候進程也會被掛起，並由系統調度其他進程運行；
• 當進程通過睡眠函數 sleep 這樣的方法將自己主動掛起時，自然也會重新調度；
• 當有優先順序更高的進程運行時，為了保證高優先順序進程的運行，當前進程會被掛起，由高優先順序進程來運行；
• 發生硬體中斷時，CPU 上的進程會被中斷掛起，轉而執行內核中的中斷服務程式；

以上，就是發生進程上下文切換的常見場景了。

---

執行緒

在早期的作業系統中都是以進程作為獨立運行的基本單位，直到後面，電腦科學家們又提出了更小的能獨立運行的基本單位，也就是執行緒。

為什麼使用執行緒？

我們舉個例子，假設你要編寫一個影片播放器軟體，那麼該軟體功能的核心模組有三個：

• 從影片文件當中讀取數據；
• 對讀取的數據進行解壓縮；
• 把解壓縮後的影片數據播放出來；

對於單進程的實現方式，我想大家都會是以下這個方式：

單進程實現方式

對於單進程的這種方式，存在以下問題：

• 播放出來的畫面和聲音會不連貫，因為當 CPU 能力不夠強的時候，Read 的時候可能進程就等在這了，這樣就會導致等半天才進行數據解壓和播放；
• 各個函數之間不是並發執行，影響資源的使用效率；

那改進成多進程的方式：

多進程實現方式

對於多進程的這種方式，依然會存在問題：

• 進程之間如何通訊，共享數據？
• 維護進程的系統開銷較大，如創建進程時，分配資源、建立 PCB；終止進程時，回收資源、撤銷 PCB；進程切換時，保存當前進程的狀態資訊；

那到底如何解決呢？需要有一種新的實體，滿足以下特性：

• 實體之間可以並發運行；
• 實體之間共享相同的地址空間；

這個新的實體，就是執行緒( Thread )，執行緒之間可以並發運行且共享相同的地址空間。

什麼是執行緒？

執行緒是進程當中的一條執行流程。

同一個進程內多個執行緒之間可以共享程式碼段、數據段、打開的文件等資源，但每個執行緒都有獨立一套的暫存器和棧，這樣可以確保執行緒的控制流是相對獨立的。

多執行緒

執行緒的優缺點？

執行緒的優點：

• 一個進程中可以同時存在多個執行緒；
• 各個執行緒之間可以並發執行；
• 各個執行緒之間可以共享地址空間和文件等資源；

執行緒的缺點：

• 當進程中的一個執行緒奔潰時，會導致其所屬進程的所有執行緒奔潰。

舉個例子，對於遊戲的用戶設計，則不應該使用多執行緒的方式，否則一個用戶掛了，會影響其他同個進程的執行緒。

執行緒與進程的比較

執行緒與進程的比較如下：

• 進程是資源（包括記憶體、打開的文件等）分配的單位，執行緒是 CPU 調度的單位；
• 進程擁有一個完整的資源平台，而執行緒只獨享必不可少的資源，如暫存器和棧；
• 執行緒同樣具有就緒、阻塞、執行三種基本狀態，同樣具有狀態之間的轉換關係；
• 執行緒能減少並發執行的時間和空間開銷；

對於，執行緒相比進程能減少開銷，體現在：

• 執行緒的創建時間比進程快，因為進程在創建的過程中，還需要資源管理資訊，比如記憶體管理資訊、文件管理資訊，而執行緒在創建的過程中，不會涉及這些資源管理資訊，而是共享它們；
• 執行緒的終止時間比進程快，因為執行緒釋放的資源相比進程少很多；
• 同一個進程內的執行緒切換比進程切換快，因為執行緒具有相同的地址空間（虛擬記憶體共享），這意味著同一個進程的執行緒都具有同一個頁表，那麼在切換的時候不需要切換頁表。而對於進程之間的切換，切換的時候要把頁表給切換掉，而頁表的切換過程開銷是比較大的；
• 由於同一進程的各執行緒間共享記憶體和文件資源，那麼在執行緒之間數據傳遞的時候，就不需要經過內核了，這就使得執行緒之間的數據交互效率更高了；

所以，執行緒比進程不管是時間效率，還是空間效率都要高。

執行緒的上下文切換

在前面我們知道了，執行緒與進程最大的區別在於：執行緒是調度的基本單位，而進程則是資源擁有的基本單位。

所以，所謂作業系統的任務調度，實際上的調度對象是執行緒，而進程只是給執行緒提供了虛擬記憶體、全局變數等資源。

對於執行緒和進程，我們可以這麼理解：

• 當進程只有一個執行緒時，可以認為進程就等於執行緒；
• 當進程擁有多個執行緒時，這些執行緒會共享相同的虛擬記憶體和全局變數等資源，這些資源在上下文切換時是不需要修改的；

另外，執行緒也有自己的私有數據，比如棧和暫存器等，這些在上下文切換時也是需要保存的。

執行緒上下文切換的是什麼？

這還得看執行緒是不是屬於同一個進程：

• 當兩個執行緒不是屬於同一個進程，則切換的過程就跟進程上下文切換一樣；
• 當兩個執行緒是屬於同一個進程，因為虛擬記憶體是共享的，所以在切換時，虛擬記憶體這些資源就保持不動，只需要切換執行緒的私有數據、暫存器等不共享的數據；

所以，執行緒的上下文切換相比進程，開銷要小很多。

執行緒的實現

主要有三種執行緒的實現方式：

• 用戶執行緒（User Thread）：在用戶空間實現的執行緒，不是由內核管理的執行緒，是由用戶態的執行緒庫來完成執行緒的管理；
• 內核執行緒（Kernel Thread）：在內核中實現的執行緒，是由內核管理的執行緒；
• 輕量級進程（LightWeight Process）：在內核中來支援用戶執行緒；

那麼，這還需要考慮一個問題，用戶執行緒和內核執行緒的對應關係。

首先，第一種關係是多對一的關係，也就是多個用戶執行緒對應同一個內核執行緒：

多對一

第二種是一對一的關係，也就是一個用戶執行緒對應一個內核執行緒：

一對一

第三種是多對多的關係，也就是多個用戶執行緒對應到多個內核執行緒：

多對多

用戶執行緒如何理解？存在什麼優勢和缺陷？

用戶執行緒是基於用戶態的執行緒管理庫來實現的，那麼執行緒控制塊（Thread Control Block, TCB） 也是在庫裡面來實現的，對於作業系統而言是看不到這個 TCB 的，它只能看到整個進程的 PCB。

所以，用戶執行緒的整個執行緒管理和調度，作業系統是不直接參与的，而是由用戶級執行緒庫函數來完成執行緒的管理，包括執行緒的創建、終止、同步和調度等。

用戶級執行緒的模型，也就類似前面提到的多對一的關係，即多個用戶執行緒對應同一個內核執行緒，如下圖所示：

用戶級執行緒模型

用戶執行緒的優點：

• 每個進程都需要有它私有的執行緒控制塊（TCB）列表，用來跟蹤記錄它各個執行緒狀態資訊（PC、棧指針、暫存器），TCB 由用戶級執行緒庫函數來維護，可用於不支援執行緒技術的作業系統；
• 用戶執行緒的切換也是由執行緒庫函數來完成的，無需用戶態與內核態的切換，所以速度特別快；

用戶執行緒的缺點：

• 由於作業系統不參與執行緒的調度，如果一個執行緒發起了系統調用而阻塞，那進程所包含的用戶執行緒都不能執行了。
• 當一個執行緒開始運行後，除非它主動地交出 CPU 的使用權，否則它所在的進程當中的其他執行緒無法運行，因為用戶態的執行緒沒法打斷當前運行中的執行緒，它沒有這個特權，只有作業系統才有，但是用戶執行緒不是由作業系統管理的。
• 由於時間片分配給進程，故與其他進程比，在多執行緒執行時，每個執行緒得到的時間片較少，執行會比較慢；

以上，就是用戶執行緒的優缺點了。

那內核執行緒如何理解？存在什麼優勢和缺陷？

內核執行緒是由作業系統管理的，執行緒對應的 TCB 自然是放在作業系統里的，這樣執行緒的創建、終止和管理都是由作業系統負責。

內核執行緒的模型，也就類似前面提到的一對一的關係，即一個用戶執行緒對應一個內核執行緒，如下圖所示：

內核執行緒模型

內核執行緒的優點：

• 在一個進程當中，如果某個內核執行緒發起系統調用而被阻塞，並不會影響其他內核執行緒的運行；
• 分配給執行緒，多執行緒的進程獲得更多的 CPU 運行時間；

內核執行緒的缺點：

• 在支援內核執行緒的作業系統中，由內核來維護進程和執行緒的上下問資訊，如 PCB 和 TCB；
• 執行緒的創建、終止和切換都是通過系統調用的方式來進行，因此對於系統來說，系統開銷比較大；

以上，就是內核線的優缺點了。

最後的輕量級進程如何理解？

輕量級進程（Light-weight process，LWP）是內核支援的用戶執行緒，一個進程可有一個或多個 LWP，每個 LWP 是跟內核執行緒一對一映射的，也就是 LWP 都是由一個內核執行緒支援。

另外，LWP 只能由內核管理並像普通進程一樣被調度，Linux 內核是支援 LWP 的典型例子。

在大多數系統中，LWP與普通進程的區別也在於它只有一個最小的執行上下文和調度程式所需的統計資訊。一般來說，一個進程代表程式的一個實例，而 LWP 代表程式的執行執行緒，因為一個執行執行緒不像進程那樣需要那麼多狀態資訊，所以 LWP 也不帶有這樣的資訊。

在 LWP 之上也是可以使用用戶執行緒的，那麼 LWP 與用戶執行緒的對應關係就有三種：

• 1 : 1，即一個 LWP 對應 一個用戶執行緒；
• N : 1，即一個 LWP 對應多個用戶執行緒；
• N : N，即多個 LMP 對應多個用戶執行緒；

接下來針對上面這三種對應關係說明它們優缺點。先下圖的 LWP 模型：

LWP 模型

1 : 1 模式

一個執行緒對應到一個 LWP 再對應到一個內核執行緒，如上圖的進程 4，屬於此模型。

• 優點：實現並行，當一個 LWP 阻塞，不會影響其他 LWP；
• 缺點：每一個用戶執行緒，就產生一個內核執行緒，創建執行緒的開銷較大。

N : 1 模式

多個用戶執行緒對應一個 LWP 再對應一個內核執行緒，如上圖的進程 2，執行緒管理是在用戶空間完成的，此模式中用戶的執行緒對作業系統不可見。

• 優點：用戶執行緒要開幾個都沒問題，且上下文切換髮生用戶空間，切換的效率較高；
• 缺點：一個用戶執行緒如果阻塞了，則整個進程都將會阻塞，另外在多核 CPU 中，是沒辦法充分利用 CPU 的。

M : N 模式

根據前面的兩個模型混搭一起，就形成 M:N 模型，該模型提供了兩級控制，首先多個用戶執行緒對應到多個 LWP，LWP 再一一對應到內核執行緒，如上圖的進程 3。

• 優點：綜合了前兩種優點，大部分的執行緒上下文發生在用戶空間，且多個執行緒又可以充分利用多核 CPU 的資源。

組合模式

如上圖的進程 5，此進程結合 1:1 模型和 M:N 模型。開發人員可以針對不同的應用特點調節內核執行緒的數目來達到物理並行性和邏輯並行性的最佳方案。

---

調度

進程都希望自己能夠佔用 CPU 進行工作，那麼這涉及到前面說過的進程上下文切換。

一旦作業系統把進程切換到運行狀態，也就意味著該進程佔用著 CPU 在執行，但是當作業系統把進程切換到其他狀態時，那就不能在 CPU 中執行了，於是作業系統會選擇下一個要運行的進程。

選擇一個進程運行這一功能是在作業系統中完成的，通常稱為調度程式（scheduler）。

那到底什麼時候調度進程，或以什麼原則來調度進程呢？

調度時機

在進程的生命周期中，當進程從一個運行狀態到另外一狀態變化的時候，其實會觸發一次調度。

比如，以下狀態的變化都會觸發作業系統的調度：

• 從就緒態 -> 運行態：當進程被創建時，會進入到就緒隊列，作業系統會從就緒隊列選擇一個進程運行；
• 從運行態 -> 阻塞態：當進程發生 I/O 事件而阻塞時，作業系統必須另外一個進程運行；
• 從運行態 -> 結束態：當進程退出結束後，作業系統得從就緒隊列選擇另外一個進程運行；

因為，這些狀態變化的時候，作業系統需要考慮是否要讓新的進程給 CPU 運行，或者是否讓當前進程從 CPU 上退出來而換另一個進程運行。

另外，如果硬體時鐘提供某個頻率的周期性中斷，那麼可以根據如何處理時鐘中斷
，把調度演算法分為兩類：

• 非搶佔式調度演算法挑選一個進程，然後讓該進程運行直到被阻塞，或者直到該進程退出，才會調用另外一個進程，也就是說不會理時鐘中斷這個事情。
• 搶佔式調度演算法挑選一個進程，然後讓該進程只運行某段時間，如果在該時段結束時，該進程仍然在運行時，則會把它掛起，接著調度程式從就緒隊列挑選另外一個進程。這種搶佔式調度處理，需要在時間間隔的末端發生時鐘中斷，以便把 CPU 控制返回給調度程式進行調度，也就是常說的時間片機制。

調度原則

原則一：如果運行的程式，發生了 I/O 事件的請求，那 CPU 使用率必然會很低，因為此時進程在阻塞等待硬碟的數據返回。這樣的過程，勢必會造成 CPU 突然的空閑。所以，為了提高 CPU 利用率，在這種發送 I/O 事件致使 CPU 空閑的情況下，調度程式需要從就緒隊列中選擇一個進程來運行。

原則二：有的程式執行某個任務花費的時間會比較長，如果這個程式一直佔用著 CPU，會造成系統吞吐量（CPU 在單位時間內完成的進程數量）的降低。所以，要提高系統的吞吐率，調度程式要權衡長任務和短任務進程的運行完成數量。

原則三：從進程開始到結束的過程中，實際上是包含兩個時間，分別是進程運行時間和進程等待時間，這兩個時間總和就稱為周轉時間。進程的周轉時間越小越好，如果進程的等待時間很長而運行時間很短，那周轉時間就很長，這不是我們所期望的，調度程式應該避免這種情況發生。

原則四：處於就緒隊列的進程，也不能等太久，當然希望這個等待的時間越短越好，這樣可以使得進程更快的在 CPU 中執行。所以，就緒隊列中進程的等待時間也是調度程式所需要考慮的原則。

原則五：對於滑鼠、鍵盤這種互動式比較強的應用，我們當然希望它的響應時間越快越好，否則就會影響用戶體驗了。所以，對於互動式比較強的應用，響應時間也是調度程式需要考慮的原則。

五種調度原則

針對上面的五種調度原則，總結成如下：

• CPU 利用率：調度程式應確保 CPU 是始終匆忙的狀態，這可提高 CPU 的利用率；
• 系統吞吐量：吞吐量表示的是單位時間內 CPU 完成進程的數量，長作業的進程會佔用較長的 CPU 資源，因此會降低吞吐量，相反，短作業的進程會提升系統吞吐量；
• 周轉時間：周轉時間是進程運行和阻塞時間總和，一個進程的周轉時間越小越好；
• 等待時間：這個等待時間不是阻塞狀態的時間，而是進程處於就緒隊列的時間，等待的時間越長，用戶越不滿意；
• 響應時間：用戶提交請求到系統第一次產生響應所花費的時間，在互動式系統中，響應時間是衡量調度演算法好壞的主要標準。

說白了，這麼多調度原則，目的就是要使得進程要「快」。

調度演算法

不同的調度演算法適用的場景也是不同的。

接下來，說說在單核 CPU 系統中常見的調度演算法。

01 先來先服務調度演算法

最簡單的一個調度演算法，就是非搶佔式的先來先服務（First Come First Severd, FCFS）演算法了。

FCFS 調度演算法

顧名思義，先來後到，每次從就緒隊列選擇最先進入隊列的進程，然後一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那麼後面的短作業等待的時間就會很長，不利於短作業。

FCFS 對長作業有利，適用於 CPU 繁忙型作業的系統，而不適用於 I/O 繁忙型作業的系統。

02 最短作業優先調度演算法

最短作業優先（Shortest Job First, SJF）調度演算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助於提高系統的吞吐量。

SJF 調度演算法

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那麼就會使得長作業不斷的往後推，周轉時間變長，致使長作業長期不會被運行。

03 高響應比優先調度演算法

前面的「先來先服務調度演算法」和「最短作業優先調度演算法」都沒有很好的權衡短作業和長作業。

那麼，高響應比優先
（Highest Response Ratio Next, HRRN）調度演算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先順序」，然後把「響應比優先順序」最高的進程投入運行，「響應比優先順序」的計算公式：

從上面的公式，可以發現：

• 如果兩個進程的「等待時間」相同時，「要求的服務時間」越短，「響應比」就越高，這樣短作業的進程容易被選中運行；
• 如果兩個進程「要求的服務時間」相同時，「等待時間」越長，「響應比」就越高，這就兼顧到了長作業進程，因為進程的響應比可以隨時間等待的增加而提高，當其等待時間足夠長時，其響應比便可以升到很高，從而獲得運行的機會；

04 時間片輪轉調度演算法

最古老、最簡單、最公平且使用最廣的演算法就是時間片輪轉（Round Robin, RR）調度演算法。
。

RR 調度演算法

每個進程被分配一個時間段，稱為時間片（Quantum），即允許該進程在該時間段中運行。

• 如果時間片用完，進程還在運行，那麼將會把此進程從 CPU 釋放出來，並把 CPU 分配另外一個進程；
• 如果該進程在時間片結束前阻塞或結束，則 CPU 立即進行切換；

另外，時間片的長度就是一個很關鍵的點：

• 如果時間片設得太短會導致過多的進程上下文切換，降低了 CPU 效率；
• 如果設得太長又可能引起對短作業進程的響應時間變長。將

通常時間片設為 20ms~50ms 通常是一個比較合理的折中值。

05 最高優先順序調度演算法

前面的「時間片輪轉演算法」做了個假設，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對於多用戶電腦系統就有不同的看法了，它們希望調度是有優先順序的，即希望調度程式能從就緒隊列中選擇最高優先順序的進程進行運行，這稱為最高優先順序（Highest Priority First，HPF）調度演算法。

進程的優先順序可以分為，靜態優先順序或動態優先順序：

• 靜態優先順序：創建進程時候，就已經確定了優先順序了，然後整個運行時間優先順序都不會變化；
• 動態優先順序：根據進程的動態變化調整優先順序，比如如果進程運行時間增加，則降低其優先順序，如果進程等待時間（就緒隊列的等待時間）增加，則升高其優先順序，也就是隨著時間的推移增加等待進程的優先順序。

該演算法也有兩種處理優先順序高的方法，非搶佔式和搶佔式：

• 非搶佔式：當就緒隊列中出現優先順序高的進程，運行完當前進程，再選擇優先順序高的進程。
• 搶佔式：當就緒隊列中出現優先順序高的進程，當前進程掛起，調度優先順序高的進程運行。

但是依然有缺點，可能會導致低優先順序的進程永遠不會運行。

06 多級回饋隊列調度演算法

多級回饋隊列（Multilevel Feedback Queue）調度演算法是「時間片輪轉演算法」和「最高優先順序演算法」的綜合和發展。

顧名思義：

• 「多級」表示有多個隊列，每個隊列優先順序從高到低，同時優先順序越高時間片越短。
• 「回饋」表示如果有新的進程加入優先順序高的隊列時，立刻停止當前正在運行的進程，轉而去運行優先順序高的隊列；

多級回饋隊列

來看看，它是如何工作的：

• 設置了多個隊列，賦予每個隊列不同的優先順序，每個隊列優先順序從高到低，同時優先順序越高時間片越短；
• 新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，以此類推，直至完成；
• 當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程運行。如果進程運行時，有新進程進入較高優先順序的隊列，則停止當前運行的進程並將其移入到原隊列末尾，接著讓較高優先順序的進程運行；

可以發現，對於短作業可能可以在第一級隊列很快被處理完。對於長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也會更長了，所以該演算法很好的兼顧了長短作業，同時有較好的響應時間。

看的迷迷糊糊？那我拿去銀行辦業務的例子，把上面的調度演算法串起來，你還不懂，你錘我！

辦理業務的客戶相當於進程，銀行窗口工作人員相當於 CPU。

現在，假設這個銀行只有一個窗口（單核 CPU ），那麼工作人員一次只能處理一個業務。

銀行辦業務

那麼最簡單的處理方式，就是先來的先處理，後面來的就乖乖排隊，這就是先來先服務（FCFS）調度演算法。但是萬一先來的這位老哥是來貸款的，這一談就好幾個小時，一直佔用著窗口，這樣後面的人只能幹等，或許後面的人只是想簡單的取個錢，幾分鐘就能搞定，卻因為前面老哥辦長業務而要等幾個小時，你說氣不氣人？

先來先服務

有客戶抱怨了，那我們就要改進，我們乾脆優先給那些幾分鐘就能搞定的人辦理業務，這就是短作業優先（SJF）調度演算法。聽起來不錯，但是依然還是有個極端情況，萬一辦理短業務的人非常的多，這會導致長業務的人一直得不到服務，萬一這個長業務是個大客戶，那不就撿了芝麻丟了西瓜

最短作業優先

那就公平起見，現在窗口工作人員規定，每個人我只處理 10 分鐘。如果 10 分鐘之內處理完，就馬上換下一個人。如果沒處理完，依然換下一個人，但是客戶自己得記住辦理到哪個步驟了。這個也就是時間片輪轉（RR）調度演算法。但是如果時間片設置過短，那麼就會造成大量的上下文切換，增大了系統開銷。如果時間片過長，相當於退化成退化成 FCFS 演算法了。

時間片輪轉

既然公平也可能存在問題，那銀行就對客戶分等級，分為普通客戶、VIP 客戶、SVIP 客戶。只要高優先順序的客戶一來，就第一時間處理這個客戶，這就是最高優先順序（HPF）調度演算法。但依然也會有極端的問題，萬一當天來的全是高級客戶，那普通客戶不是沒有被服務的機會，不把普通客戶當人是嗎？那我們把優先順序改成動態的，如果客戶辦理業務時間增加，則降低其優先順序，如果客戶等待時間增加，則升高其優先順序。

最高優先順序（靜態）

那有沒有兼顧到公平和效率的方式呢？這裡介紹一種演算法，考慮的還算充分的，多級回饋隊列（MFQ）調度演算法，它是時間片輪轉演算法和優先順序演算法的綜合和發展。它的工作方式：

多級回饋隊列

• 銀行設置了多個排隊（就緒）隊列，每個隊列都有不同的優先順序，各個隊列優先順序從高到低，同時每個隊列執行時間片的長度也不同，優先順序越高的時間片越短。
• 新客戶（進程）來了，先進入第一級隊列的末尾，按先來先服務原則排隊等待被叫號（運行）。如果時間片用完客戶的業務還沒辦理完成，則讓客戶進入到下一級隊列的末尾，以此類推，直至客戶業務辦理完成。
• 當第一級隊列沒人排隊時，就會叫號二級隊列的客戶。如果客戶辦理業務過程中，有新的客戶加入到較高優先順序的隊列，那麼此時辦理中的客戶需要停止辦理，回到原隊列的末尾等待再次叫號，因為要把窗口讓給剛進入較高優先順序隊列的客戶。

可以發現，對於要辦理短業務的客戶來說，可以很快的輪到並解決。對於要辦理長業務的客戶，一下子解決不了，就可以放到下一個隊列，雖然等待的時間稍微變長了，但是輪到自己的辦理時間也變長了，也可以接受，不會造成極端的現象，可以說是綜合上面幾種演算法的優點。

---

好文推薦

真棒！ 20 張圖揭開記憶體管理的迷霧，瞬間豁然開朗

---

嘮叨嘮叨

其實，關於進程和執行緒的部分，小林周末就已經寫好了。

但是，寫到調度演算法的時候，我就懵逼了，在想用什麼方式能更通俗易懂的表達這些晦澀難懂的演算法，這一小結花了我非常多時間。唉，菜就是菜，小林我也不找借口了。。。

小林是專為大家圖解的工具人，Goodbye，我們下次見！