一文詳解操作系統進程管理

• 1. 什麼是進程
• 2. 進程模型
• 2.1 PCB
• 2.2 進程狀態
• 2.2.1 五狀態模型
• 2.2.2 七狀態模型
• 2.2.3 進程切換
• 2.3 進程組織
• 2.3.1 線性表
• 2.3.2 鏈表
• 2.3.3 索引
• 3. 線程
• 3.1 線程結構
• 3.2 線程狀態
• 4.進程調度
• 4.1 幾種調度方式
• 4.1.1 長程調度
• 4.1.2 中程調度
• 4.1.3 短程調度
• 4.2 進程調度算法
• 4.2.1 先來先服務
• 4.2.2 時間片輪轉調度
• 4.2.3 最短作業優先
• 4.2.4 最短剩餘時間優先
• 4.2.5 優先級調度
• 4.2.6 多級反饋隊列調度
• 5.進程間通信
• 5.1 共享內存
• 5.2 管道
• 5.3 信號
• 5.4 消息
• 5.5 信號量
• 6 總結
• 7. 參考資料

1. 什麼是進程

進程即正在運行的程序的一個實例。

當啟動一個程序，程序會從磁盤被讀取到內存，CPU 再從內存中讀取指令，對其解碼，然後執行指令（比如兩數相加，訪問內存，檢查條件，跳轉函數等）。完成這條指令後，CPU 繼續重複上述操作。這樣子就可以實現一個 CPU 可以對一個進程，以一對一的形式進行指令讀取與執行。

我們把操作系統做某件事，抽象成一種概念，稱之為一個任務。一個進程可以對應一個任務，也可以對應多個任務。

早期的計算機只有一個 CPU，多個任務需要運行怎麼辦？需要依次排隊等待，串行執行，一個任務執行完畢，才能執行下一個。這種方式存在著明顯的弊端，假設排在前面的 A 任務需要執行5小時，而排後面的B任務僅需要1分鐘，那麼 B 任務必須等待 A 任務5小時完成後，才能執行，這種方式顯得極其不靈活。

後來就有了多任務系統，在CPU同一時間只能處理一個任務的前提下，每個任務有一定的執行時長，比如任務A執行0.001s，切換到任務B執行0.05s，再切換到任務C執行0.01s...不斷循環。這種機制也就可以在一定程度上解決上述任務B需要長時間等待的問題。

由於 CPU 速度非常快，這種多個任務不斷切換，會給用戶一種任務並行執行的錯覺，這種也被稱為是偽並行調度。既然有偽並行，那麼也會有真並行。在現代計算機中，常見的CPU核數可以達到8核甚至更多，操作系統可將每一個核視為一個CPU，那麼8核CPU就可以真並行執行8個任務。還有更進一步的，即一個計算機內，有多個CPU。至於多個CPU與多核的區別，感興趣的讀者可以參考多核 CPU 和多個 CPU 有何區別？。

那麼我們繼續基於偽並行進一步探討。偽並行雖然可以解決上述任務等待的問題，但是依然還存在一系列未解之謎：
- 每個任務應該執行多長時間？
- 如何找到要執行的下一個任務？
- 有些任務涉及了資源操作，執行到一半，切換任務，那麼這些資源怎麼辦？
......

為了解決上面一系列謎題，我們需要一種模型對任務進行詳盡的描述記錄。一個進程可以對應一個任務，也可以對應多個任務，當前還未涉及多線程，我們可以在此先把進程和任務當作是一對一的關係（這並不是為了理解而創造出來的一種暫時錯誤的假設）。下面我們將進一步探討關於進程更詳細的內容，這些內容將有助於解釋上面的問題。

2. 進程模型

2.1 PCB

對於一個被執行的程序，操作系統會為該程序創建一個進程。進程作為一種抽象概念，可將其視為一個容器，該容器聚集了相關資源，包括地址空間，線程，打開的文件，保護許可等。而操作系統本身是一個程序，有一句經典的話 程序 = 算法 + 數據結構，因此對於單個進程，可以基於一種數據結構來表示它，這種數據結構稱之為進程控制塊(PCB)，有一些教材也將其稱為進程表。不同的操作系統，PCB中包含的信息存在差異，大體上都會包含這些信息（該圖來自《現代操作系統》）。

2.2 進程狀態

那麼什麼原因會導致進程會被創建，從而生成PCB呢？常見的有以下幾種
1. 系統初始化
2. 用戶通過系統提供的API創建新進程
3. 批處理作業初始化 (什麼是批處理作業)
4. 由現有進程派生子進程

一個進程，因為某種原因被創建了，那麼它可以按照以下步驟進行一系列的初始化
1. 給新進程分配一個進程ID
2. 分配內存空間
3. 初始化PCB
4. 進入就緒隊列

2.2.1 五狀態模型

如圖，進入就緒隊列，其狀態就會變為就緒態。各個狀態之間的關係描述如下：

就緒 -> 運行：當操作系統內存在著調度程序，當需要運行一個新進程時，調度程序選擇一個就緒態的進程，讓其進入運行態。

運行 -> 就緒：運行態的進程，會佔有CPU（參照一開始的餅狀圖）。每個進程會被分配一定的執行時間，當時間結束後，重新回到就緒態。

運行 -> 阻塞：進程請求調用系統的某些服務，但是操作系統沒法立即給它（比如這種服務可能要耗時初始化，比如I/O資源需要等待），那麼它就會進入阻塞態。

阻塞 -> 就緒：當等待結束了，就由阻塞態進入就緒態。

運行 -> 終止：當進程表示自己已經完成了，它會被操作系統終止。

這便是對於單個進程，經典的五狀態模型。當存在多個進程時，由於同一時間只能有一個進程在執行，那麼如何去管理這一系列的處於阻塞態和就緒態的進程呢？一般來說，會使用就緒隊列，和阻塞隊列，讓處於阻塞態和就緒態的進程進入隊列，排隊執行。下圖是一個單一阻塞隊列模型。

基於此，還可以擴展出多個就緒隊列，每個優先級對應一個隊列，這樣子操作系統在選擇要調度哪一個進程時，可以有更大的靈活性。下面將進一步探討隊列與進程之間如何組織管理。也可以有多條阻塞隊列，每一個事件對應一個阻塞隊列，當事件發生時，該隊列所有進程都進入就緒態。

2.2.2 七狀態模型

上面所講的進程狀態存在一個前提：每個進程都必須完全載入內存。一旦排隊的進程多了，對於有限的內存空間將會是極大的考驗。為了解決內存佔用問題，可以將一部分內存中的進程交換到磁盤中，這些被交換到磁盤的進程，會進入掛起狀態，進一步還可細分為就緒/掛起，阻塞/掛起。對於單個進程的狀態轉換如下圖。

整體上對於掛起隊列的轉換關係，如下圖。

關於圖中的幾種調度，將會在下面第4章進一步描述。

2.2.3 進程切換

當一個正在運行中的進程被中斷，操作系統指定另一個就緒態的進程進入運行態，這個過程就是進程切換，也可以叫上下文切換。

該切換過程一般涉及以下步驟：
1.保存處理器上下文環境：將CPU程序計數器和寄存器的值保存到當前進程的私有堆棧裡
2.更新當前進程的PCB（包括狀態更變）
3.將當前進程移到就緒隊列或者阻塞隊列
4.根據調度算法，選擇就緒隊列中一個合適的新進程，將其更改為運行態
5.更新內存管理的數據結構
6.新進程內對堆棧所保存的上下文信息載入到CPU的寄存器和程序計數器，佔有CPU

2.3 進程組織

每一個PCB表示一個進程，多個進程同時存在時，需要一定的方式將這些PCB組織起來，便於操作系統訪問。常見的組織方式有如下3種。

2.3.1 線性表

所有的PCB存放於一張線性表中，每次查找時需要遍歷線性表。比較適用於進程數量不多的情況，如果有幾百上千個進程，每次操作都進行遍歷，那將是十分耗時的。

2.3.2 鏈表

上面提到的就緒隊列和阻塞隊列，他們可以以鏈表的形式組織。從圖中可以看出就緒隊列指向PCB1，PCB1右邊的數字“2”表示鏈表指向的下一個節點PCB2。依此類推，PBC以如下鏈表形式串聯起來。

<code>執行指針 -> PCB4
就緒隊列指針 -> PCB1 -> PCB2 -> PCB3 -> PCB5
阻塞隊列指針 -> PCB7 -> PCB8 -> PCB6/<code>

優點：非常直觀，進程調度查找起來方便。

缺點：查找的時候需要從鏈表的頭部開始進行遍歷。如果進程狀態發生變化，那麼鏈表中進程節點的指針指向需要發生變動。

2.3.3 索引

優點：基於鏈表的方式進行進一步的優化，通過索引查找進程，可以將查找的時間複雜度由O(n)優化到O(1)。如果進程狀態發生變化，只需要操作索引表，相比於操作整個鏈表更便捷。

缺點：建立了索引表，需要額外的內存空間。相當於是利用空間去換取時間。

3. 線程

3.1 線程結構

基於前面所描述，進程包含了兩大特點：
1. 資源所有權：進程是一個容器，聚集了內存，I/O 設備，文件等資源，擁有這些資源的控制或所有權。
2. 調度/執行：具有執行狀態（運行，就緒，阻塞等），可被操作系統的調度程序所調度。

早期的操作系統中，一般一個進程內只有一個線程，即為單線程進程模型。如下圖，其中所包含的用戶棧和內核棧，用於管理調度和返回的行為。當進程不運行的時候，CPU的寄存器中的內容將被保存起來，以便於下一次運行該進程時，恢復當時的狀態。

那麼為什麼需要多線程？

1. 許多應用同時發生著多種活動，其中一些活動會被阻塞，將進程進一步分解為多個線程，可以更靈活地處理各種類型的活動。
2. 線程更加輕量級，創建和終止速度更快，且線程之間切換的速度會比進程切換更快。
3. 對於一些 I/O 密集型任務，多個線程允許這些並排執行，加快整體的速度。對於CPU密集型任務多線程沒這個優勢，因為本質上CPU同一時間只做一件事（什麼是CPU密集型、I/O密集型？）。
4. 線程間通信的效率會高於進程間通信。一般進程間通信需要內核介入，而同一進程內的線程間共享該進程的內存和文件，不需要調用內核就可以實現通信。

上圖為多線程進程模型，其中線程控制塊，也被稱為TCB（Thread Control Block）。

對於進程來說，進程 = 線程+資源。

我們一開始提及過，操作系統底層存在調度程序，調度程序可調度任務，而單線程進程，每個進程可以對應一個任務。現在，對於多線程的進程，每一個線程最終對於調度程序來說，都是一個任務，如下圖（Linux系統）。因此也有一種流行的說法“線程是CPU調度的基本單位”

3.2 線程狀態

和進程狀態模型類似，線程的狀態也有新建，運行，就緒，阻塞，終止。與進程狀態相似，終止線程時將進入終止狀態。但是區別於進程的是當一個進程被終止了，其內部的所有線程都會被終止。由於線程之間的並行關係，同一進程內，一個線程被阻塞了，不會影響到其他線程。

4.進程調度

處理器調度，按照相對時間長短，可以分為長程調度，中程調度，短程調度。（常見調度還有I/O調度，但不屬於處理器調度）。幾種調度和進程的狀態轉換關係如下圖

4.1 幾種調度方式

4.1.1 長程調度

長程調度又稱為高級調度，作業調度。
它控制系統的併發度，決定著哪一個批處理作業或者用戶程序可以進入系統中處理，一旦運行進入，批處理作業或者用戶程序就會變成進程，進入就緒隊列。

4.1.2 中程調度

中程調度又稱交換調度，中級調度。
核心思想是將進程從內存或CPU競爭中移出，之後進程能重新被調入內存，通過這種方式可控制內存中進程數量。如圖中，從就緒隊列中掛起的進程進入就緒掛起隊列，從阻塞隊列中掛起的進程進入阻塞掛起隊列。就緒掛起隊列中的進程激活，則進入就緒隊列。

4.1.3 短程調度

短程調度又稱為低級調度，大部分時候講的進程調度都是特指短程調度，短程調度將就緒隊列中的進程調度到CPU中執行。其中按照一定策略將CPU分配給一個就緒狀態的進程，分為搶佔式調度和非搶佔式調度。

非搶佔式調度：
非搶佔式調度，就是挑選一個進程，將CPU分配給它，該進程一直運行到終止或者因為等待事件進入阻塞狀態(圖中紅字標註)。顯然這種調度方式存在一個硬傷：正在運行的進程如果需要運行很長時間，那麼排在它後面的進程，只能一直等，直到它結束或阻塞。

搶佔式調度：
搶佔式調度就是允許進程執行到一半時，將進程停下，CPU分配給其它進程。

4.2 進程調度算法

常見的進程調度算法有：

• 先來先服服務
• 時間片輪轉
• 最短作業優先
• 最短剩餘時間優先
• 優先級調度
• 多級反饋隊列調度

由於篇幅有限，每一種調度算法本文只做精要的介紹，想更進一步瞭解，可以根據最後的參考資料。

4.2.1 先來先服務

先來先服務（First Come First Serverd, FCFS）。先進就緒隊列，則先被調度，先來先服務是最簡單的調度算法。

先來先服務存在上面談論過的問題：當前面任務耗費很長時間執行，那麼後面的任務即使只需要執行很短的時間，也必須一直等待。屬於非搶佔式

4.2.2 時間片輪轉調度

時間片輪轉調度，即上面第一章所描述的方式。
每一個進程會被分配一個時間片，表示允許該進程在這個時間段運行，如果時間結束了，進程還沒運行完畢，那麼會通過搶佔式調度，將CPU分配給其他進程，該進程回到就緒隊列。這是一種最簡單最公平的調度算法，但是有可能會存在問題。由於進程的切換，需要耗費時間，如果時間片太短，頻繁進行切換，會影響效率。如果進程時間片太長，有可能導致排後面的進程等待太長時間。因此時間片的長度，需要有大致合理的數值。（《現代操作系統》的觀點是建議時間片長度在20ms~50ms）。

4.2.3 最短作業優先

最短作業優先（Shortest Job First, SJF），顧名思義即進程按照作業時間長短排隊，作業時間段的排前面先執行，如 下圖。

4.2.4 最短剩餘時間優先

最短剩餘時間優先（Shortest Remaining Time Next），從就緒隊列中選擇剩餘時間最短的進程進行調度。該算法可以理解最短作業優先和時間片輪轉的結合。如果沒有時間片，那麼最短剩餘時間其實就是最短作業時間，因為每個進程都是從頭執行到尾。

4.2.5 優先級調度

假設就緒隊列中有如下進程

進程執行時間優先級P151P223P332

按照優先級調度，執行順序為p1->p3->p2。如果多個進程優先級相同，則按照先來先服務的方式依次執行。

優先級調度可以進一步細分為搶佔式和非搶佔式。

非搶佔式：和上面提及的非搶佔式類似，一旦該進程佔有CPU就將一直執行到結束或者阻塞。

搶佔式：進程執行期間，一旦有更高優先級的進程進入就緒隊列，那麼該進程就會被暫停，重回就緒隊列，讓更高優先級的進程執行。但是為了防止最高優先級進程一直執行，每個進程依然有自己的時間片，每次時間片結束後，會根據一定規則降低該進程優先級，避免某些最高優先級長作業進程一直佔用CPU。

4.2.6 多級反饋隊列調度

多級反饋隊列調度基於時間片輪轉和優先級調度，設置多個就緒隊列，賦予每個就緒隊列優先級，優先級越高的隊列進程的時間片越短。如下圖，第1級就緒隊列優先級最高，進程的時間片長度最短，第2級就緒隊列次之，以此類推。

當有新的進程創建時，先進入第1級就緒隊列，時間片結束之前就運行完畢，則終止，否則進入第2級隊列等待下一次調度。在n級隊列之前，進程按照先到先服務規則依次調度，到了第n級隊列（最後一級）採用時間片輪轉調度。僅當第1級隊列為空時，才調度第2級隊列的進程，如果第i級隊列的進程正在運行，此時有一個更高優先級的進程進入，則會停下第i級的進程，讓它回到第i級隊列尾部，轉而執行更高優先級的進程，即滿足優先級調度算法的原則。

5.進程間通信

進程間通信目的一般有共享數據，數據傳輸，消息通知，進程控制等。以 Unix/Linux 為例，介紹幾種重要的進程間通信方式：共享內存，管道，消息，共享內存，信號量，信號

5.1 共享內存

多個進程可以讀寫同一塊內存區域，是效率最高的進程間通信方式。

由於多個進程都可以讀寫內存，所以需要一定的同步機制來保證數據讀寫安全問題，關於這種機制，需要花費較大篇幅，這裡讀者可根據文章末尾提供的參考資料查看，筆者後續也會再另起一篇專門介紹。

5.2 管道

首先簡單介紹一下什麼是生產者/消費者問題。一個或多個生產者，生產一些數據，將其放置到共享緩衝區中，由消費者從緩衝區中取走數據。同一個緩衝區同一時間內只允許生產者或者消費者一方訪問，不能同時訪問。當緩衝區滿了，生產者不再向其中添加數據，當緩衝區空了，消費者不再向其讀取數據。

管道就是基於生產者/消費者模型來實現通信的，最基本的管道通信由一端的讀進程，管道，還有另一端的寫進程構成，通信的介質是共享文件，也稱為管道文件。管道可以分為匿名管道和命名管道，此處主要介紹命名管道。管道有一個特點：數據一旦被讀取了，就從管道中刪除，以釋放空間便於寫入更多數據。如下圖

如果需要實現雙端通信，則需要兩個管道，如下圖。

這裡有一個注意點：第二個圖是半雙工通信，即雖然通信可以雙向，但是同一時間只能單向傳輸。管道可以理解為一種共享存儲（是磁盤存儲而不是內存存儲）的優化方式，保證同一緩衝區的數據，只能一端寫入，一端讀取，無法多端同時進行寫操作。

5.3 信號

信號一般用於一些異常情況下的進程間通信，是一種異步通信，它的數據結構一般就是一個數字，比如Unix就提供瞭如下信號（摘自《操作系統精髓與設計原理》第6版 6.7.5章節）

01SIGHUB阻塞：內核認為進程正在做無用工作時發送給該進程02SIGINT中斷03SIGQUIT停止：由用戶發送，引發進程停止併產生信息轉存

進程需要為信號設置相應的監聽處理，當收到特定信號時，執行相應的操作，類似很多編程語言裡的通知機制。

5.4 消息

消息可以作為兩個不相關進程傳遞數據的方式，至少由一對原語構成

<code>send(destination,message)
receive(source,message)/<code>

什麼是原語：由若干條指令構成的程序段，用以執行特定的操作。消息通信可以分為直接通信和間接通信。

直接通信：發送進程直接發消息發給接收進程，把消息掛在接收進程的消息隊列中，接收進程從消息隊列中獲取消息，是一種一對一的通信關係。

間接通信：消息不直接發送給接收者，而是發送到一個共享數據結構，該結構是一種消息隊列，也稱為信箱。這種方式相對於直接通信更加靈活，可以一對一，一對多，多對一，多對多。

通過消息格式中指定的id來確保進程的識別，如下是一種常見的消息數據格式（來自《操作系統精髓與設計原理》5.5.3）

消息在消息隊列中，按照先進先出的原則。如果有消息比較緊急，發送者可以指定消息的類型，接收者在查詢消息隊列時，可以根據消息類型讀取，不一定完全按照先進先出順序。

消息相對於管道，有如下區別：

• 在傳輸中，管道基於字節流，消息基於格式文本。
• 介質上管道是文件，消息是內存
• 管道只能按照先進先出的順序，消息不一定，它可以根據消息類型選擇性接收處理，更加靈活。

5.5 信號量

信號量本質是一個計數器，當多進程共享內存時，用於保護共享內存，確保共享內存在同一時刻只有一個進程獨享。

信號量需要初始化為某個值，當有進程對共享內存進行訪問時，信號量減1，如果信號量值不為負數，則訪問共享內存。當此時其新進程也要訪問共享內存時，再次將信號量減一，如果信號量的值為負數，則新進程阻塞等待。

6. 總結

進程是操作系統最重要的概念之一，有比較多的細節點可以介紹，每一點還可以橫向縱向再展開。筆者翻閱了大部分主流操作系統的書中關於進程管理的章節，總結出了本篇入門介紹，其中用戶進程，內核進程，調度算法評價指標，進程和內存管理等內容這裡受限於篇幅沒有討論。同步，併發，鎖這幾部分相對複雜且重要的內容打算後面另起章節單獨描述。感謝閱讀，如有疏漏或錯誤，還請指正 。

轉載自 YinTokey：一篇快速入門操作系統的進程管理