現代操作系統 - 進程與線程及其調度

進程#

new: 進程剛被創建但還沒有完成初始化
ready: 進程可以被調度執行
running: 進程正在 CPU 上執行
blocked: 被阻塞，需要等待外部事件完成
terminated: 執行完成，不會再被調度

進程地址空間
核心代碼及數據
核心棧
用戶棧
⬇️
共享庫，只讀 (如 libc)
⬆️
用戶堆
數據段 (全局變量)
代碼段

Linux 使用 fork 從當前進程中創建一個新的子進程：對於父進程 fork 返回子進程的 PID; 對於子進程 fork 返回 0 執行 fork 時子進程會複製父進程 PCB(Process Control Block) 中的數據，比如打開的文件描述符表，但是兩進程 FD 表中指向的文件數據結構是相同的 (相當於只複製了指針) 導致兩進程共享一份打開文件的指針，在讀取文件時受到共享偏移量的影響，讀取的數據並不一致。

子進程複製父進程數據

通過 fork 可以得到一個和父進程幾乎相同的子進程在 Linux 下還可以通過 exec 系列接口在當前進程中執行新的程序。使用 execve 後操作系統會執行以下操作:

根據指定的可執行文件路徑將數據段和代碼段載入地址空間
重新初始化堆和棧並進行 地址空間隨機化 改變堆棧起始地址
將 PC 寄存器設置到可執行文件代碼段的入口

Linux 的第一個進程是 init 進程，所有進程都是通過 fork 創建的，每個進程會記錄自己的父子進程，由此所有進程形成了一棵進程樹。父進程可以通過 wait 監控子進程的退出並檢查其狀態，比如是否異常退出。如果父進程沒有執行或者還沒來得及執行 wait 調用子進程就已經退出，此時子進程的資源並不會被完全回收 Linux 下稱這種進程為 zombie 進程。

Linux 核心定義了 進程組 process group 的概念，即由多個進程組成的集合，應用進程可以用過 killpg 向一個進程組發送信號，此信號會發送到組內的所有進程。多個進程組的集合構成 會話 session 會話將進程組分為前台進程組和後台進程組，前台進程組一般用於接受 控制終端 controlling terminal 進程的輸入 (比如標準輸入或者信號等)。會話和進程組主要用於 Shell 環境的進程管理。

線程#

線程是進程內可以獨立執行的單元，同一進程內的所有線程共享同一份地址空間，但是擁有不同的運行上下文：比如寄存器狀態和棧。多線程應用的地址空間分布如下:

有多個線程的進程地址空間
核心代碼及數據
核心棧 1
核心棧 2
核心棧 2
...
用戶棧 1
用戶棧 2
用戶棧 3
...
共享庫，只讀 (如 libc)
⬆️
用戶堆
數據段 (全局變量)
代碼段

操作系統內線程分為用戶態線程和核心線程，用戶態線程如果要進行系統調用需要進入到核心線程中去執行，所以需要為每個用戶態線程分配對應的核心線程。分配方式有多種:

多對一：多個用戶線程對應一個核心線程，缺點是同時只能有一個用戶線程進入核心
一對一：每個用戶線程對應一個核心線程，缺點是核心線程的數量會隨著用戶進程的增多而增多
多對多：將 N 個用戶線程對應 M 個核心線程 (N> M) 需要核心對映射關係做管理和調度

每個線程有一個 Thread Control Block TCB 數據結構用於保存線程的上下文信息。

用戶態線程可以創建特殊的 Thread Local Storage TLS 線程局部存儲變量，多個線程可以使用同一個 TLS 變量，但是每個線程讀寫的都只是本線程內的數據拷貝。如下伪代码:

__thread int count; // 聲明一個 TLS 變量

thread1.set(&count, 1); // 線程1寫 count
thread2.set(&count, 2); // 線程2寫 count
thread1.get(&count) == 1; // 線程1讀 count 的結果是 1
thread1.get(&count) == 2; // 線程2讀 count 的結果是 2

在 x86-64 架構中，當一個線程被調度時 libpthread 會將該線程的 TLS 起始地址寫入到 FS 段寄存器內，線程訪問 TLS 變量時會使用 FS 寄存器中的地址加上變量偏移量進行訪問，即實際上多線程讀寫各自的 TLS 變量時使用的地址是不同的。

在 Linux 下線程的創建，退出等操作都是通過調用 libpthread 接口實現:

pthread_create: 在當前進程內創建一個線程，運行指定的函數，底層通過 clone 調用實現
pthread_exit: 結束當前線程，函數執行結束時會隱式調用，可以通過主動調用設置返回值
pthread_yield: 主動暫停當前線程，讓出資源，等待下一次調度，但是線程仍處於 ready 狀態
pthread_join: 等待指定的線程結束並獲取其返回值
pthread_cond_wait: 等待一個指定的條件變量，用於多線程同步

調度概念#

調度的指標#

吞吐量：單位時間內處理的任務數量
周轉時間：任務從開始執行到結束執行的耗時
響應時間：交互式任務的請求響應耗時
實時性：實時任務的完成度 (某些任務需要在指定 deadline 前完成)
能耗
資源利用率
公平性
調度器本身的開銷

長期，中期與短期調度#

長期調度#

長期調度主要控制系統中可以被調度的任務總量，比如短時間內大量的進程被創建，長期調度不會立即將所有進程都轉移到 ready 狀態 (對於實時性要求較高的交互式任務例外), 否則會造成任務數量劇增調度開銷增大。另外長期調度會根據當前系統的 CPU 和 I/O 使用情況適當平衡可以被調度的進程，避免同時有大量的 I/O 任務或 CPU 任務造成劇烈的資源競爭和利用率不足。總的來說長期調度通過決定是否將一個任務納入調度來控制總量，降低短期調度的壓力。

短期調度#

短期調度執行具體的調度決策，將任務的狀態在 blocked/ready/running 之間轉換。比如:

處於 running 狀態的進程如果執行時間超過預估的時間片會被調度搶占，轉換為 ready 狀態等待下一次調度
任務執行或等待 I/O 時會被轉換為 blocked 狀態等到 I/O 事件就緒時轉換為 ready 狀態
軟 / 硬件 (比如時鐘) 中斷，系統調用等會中斷任務的執行

中期調度#

中期調度是換頁機制的一部分，主要是控制系統中可運行和正在運行任務的內存使用，避免使用量超出內存資源總量。實際運行過程中，如果系統中的任務已經佔用了大量的內存，中期調度會選取某些任務 (比如頻繁觸發缺頁異常的任務) 將其掛起 suspend 而後換頁機制會傾向於將被掛起的進程內存換出到磁碟以緩解系統的內存壓力。被掛起的任務也無法被短期調度使用，進一步降低短期調度的壓力。

總體調度示意圖:

操作系統進程調度

調度機制#

優先級調度#

時間片輪轉：每個任務執行指定時間片的時間，然後切換到下一個任務。這種調度策略會導致平均的周轉時間變長 (比如系統中一共就兩個任務，時間片輪轉會耗費大量的時間在兩個任務的切換上)。而且需要平衡時間片的大小：如果太小，調度和狀態轉換的開銷會很大；如果太大會造成某些任務延遲過高。

考慮到交互式任務的實時性需求，可以為每個進程指定一個優先級，高優先級的任務 (比如交互式任務或者實時任務) 會先被調度器執行。

實際運行時一般會有多個具有高優先級的任務，因此可以使用 多級隊列 的方式將所有任務分配到不同的優先級，依舊是高優先級任務先執行，但是同一優先級內的多個任務會放在一個隊列中通過時間片輪轉或者其他策略進行調度。此種策略可能會造成低優先級的任務長時間無法執行。

在多級隊列的基礎上，還可以根據任務的運行情況，動態調整優先級，稱為 多級反饋隊列 Multi-Level Feedback Queue 此種方式傾向於將將短任務 (比如 I/O 密集型和交互式這種在 CPU 上運行時間較短的任務) 設置更高的優先級，以獲取更好的平均周轉時間。

動態調整優先級策略：在任務運行之初 MLFQ 會將新任務設置較高的優先級 (便於交互和實時任務), 在每個優先級上 MLFQ 會設置一個最長運行時間 (任務多次運行的總時間) 如果任務在此隊列上的運行時間超過此時間則 MLFQ 會認為此任務是一個較長的任務，將其調整至下一級隊列，多次運行後該任務會根據執行時間情況被調整到一個合適的優先級。

由於低優先級的任務一般是長任務，所以低優先級隊列的時間片也會比較長，高優先級隊列同理時間片會比較短。

公平共享調度#

除了提升調度指標以外，某些情況下還需要實現對資源的公平調度。比如用戶 A 和用戶 B 花費同樣的價格共享一台機器但是用戶 A 運行了三個進程而用戶 B 只運行了一個進程，此時系統需要保證用戶 A 和用戶 B 各自都能占用 50% 的資源，即 CPU 的時間片。

彩票調度#

彩票調度為每個任務分配一定份額的彩票，每次調度時抽取一個中獎號碼，根據此中獎號碼選取需要執行的任務，類似於帶權重的隨機，伪代码如下:

loop:
    R = random(0, total_tickets)
    for sum = 0; task in task_list; {
        sum += task->tickets
        if sum > R {
            schedule(task)
            goto loop
        }
    }

通過此種方式為每個用戶分配相同的彩票額即可保證 CPU 時間的公平分配。但實際的分配情況依賴隨機，在調度次數較少的情況下由於隨機數據不平均可能會導致短期的分配不平均。

步幅調度#

步幅調度通過設置步幅確定性的為任務分配公平的時間，消除彩票調度的隨機性影響。

假設兩個任務 A 和 B 應分配的資源比例是 6:5 則步幅調度使用其反比作為其步幅，即 A 和 B 的步幅為 5 和 6 步幅調度會設置一個固定的時間片，每次選取當前已走距離最小的任務執行一次，並將其走過的距離加上對應的步幅。由於步幅不同，兩任務最終執行的時間片數量比會是 6:5 即達到穩定公平分配的目的。伪码如下:

loop:
    task = queue.pop_min()
    schedule(task)
    task.pass += task.stride
    queue.push(task)
    goto loop

多核調度#

在多核場景下由於系統可以同時運行多個任務，調度器需要決定同一時間有哪些任務可以進行，這些任務分別在哪個核心上運行。還需要考慮在同一核心上，如果調度不同任務，頻繁切換造成的性能損耗 (頁表切換，寄存器存取等)

協同調度#

對於某些任務間有關聯的場景，比如有請求 - 響應關係的兩個任務，如果不能同時運行即 A 發送消息時 B 並沒有在運行那這個消息要等到下次 B 被調度時才能收到，且 B 在被調度運行時 A 可能又會被調度出去返回的消息沒辦法立即接收，這樣每次發送請求和返回響應都會由於調度產生至少一個時間片的延遲，降低程序的運行效率。對於此類場景，需要使用協同調度：每次調度一組任務並行執行，這樣可以將具有关聯關係 (需要同時運行) 的任務可以分配到同一組內並行執行，而具有依賴關係的任務 (某個任務必須等待另外一個任務執行完) 需要分配到不同的組，避免空等造成 CPU 資源浪費。

協同調度一般用於並行計算，即將一個大的任務切分成多個子任務在多核心上並行執行加快計算。但是在更為普遍的場景下，使用協同調度可能會由於組內任務的相互等待 (注意：協同調度是以組為單位而非任務) 造成 CPU 資源的浪費。

協同調度的一個經典策略是群組調度，基本思想是將所有任務分成不同的組，將關聯任務分配至同一組，並且以組為單位，調度任務在多個核心上運行。比如現在有 4 個 CPU 核心和三組任務 A/B/C 每個組內分別有 4/3/2 個任務，則調度情況如下:

Core 0	Core 1	Core 2	Core 3
A0	A1	A2	A3
B0	B1	B2	C1
C2	A0	A1	A2

兩級調度#

多核心場景下，考慮任務在不同核心間的切換開銷，可以將某個任務固定到一個核心上進行調度和執行。即新任務首先通過一個全局調度器分配到某個核心上，每個核心再通過單核調度策略執行分配給自己的任務，在系統運行過程中，全局調度器也會根據每個核心的負載情況，平衡任務在不同核心間的分配。這種調度方式稱為兩級調度。

處理器親和性#

某些操作系統在自己運行的調度器之上，為用戶進程提供了處理器親和性相關的調用接口，可以讓應用進程自己控制 CPU 核心使用情況，比如 Linux 提供了 sched_setaffinity 接口可以讓用戶進程控制自己只能在某些核心上執行。