一篇文章帶你「重新認識」執行緒上下文切換怎麼玩兒

• 2020 年 2 月 26 日
• 筆記

點擊藍色「Java建設者」關注我喲

加個「星標」，一起走向人生巔峰！

這是Java建設者第68篇原創文章

調度

當一個電腦是多道程式設計系統時，會頻繁的有很多進程或者執行緒來同時競爭 CPU 時間片。當兩個或兩個以上的進程/執行緒處於就緒狀態時，就會發生這種情況。如果只有一個 CPU 可用，那麼必須選擇接下來哪個進程/執行緒可以運行。作業系統中有一個叫做 調度程式(scheduler) 的角色存在，它就是做這件事兒的，該程式使用的演算法叫做 調度演算法(scheduling algorithm) 。

儘管有一些不同，但許多適用於進程調度的處理方法同樣也適用於執行緒調度。當內核管理執行緒的時候，調度通常會以執行緒級別發生，很少或者根本不會考慮執行緒屬於哪個進程。下面我們會首先專註於進程和執行緒的調度問題，然後會明確的介紹執行緒調度以及它產生的問題。

調度介紹

讓我們回到早期以磁帶上的卡片作為輸入的批處理系統的時代，那時候的調度演算法非常簡單：依次運行磁帶上的每一個作業。對於多道程式設計系統，會複雜一些，因為通常會有多個用戶在等待服務。一些大型機仍然將 批處理和 分時服務結合使用，需要調度程式決定下一個運行的是一個批處理作業還是終端上的用戶。由於在這些機器中 CPU 是稀缺資源，所以好的調度程式可以在提高性能和用戶的滿意度方面取得很大的成果。

進程行為

幾乎所有的進程（磁碟或網路）I/O 請求和計算都是交替運行的

如上圖所示，CPU 不停頓的運行一段時間，然後發出一個系統調用等待 I/O 讀寫文件。完成系統調用後，CPU 又開始計算，直到它需要讀更多的數據或者寫入更多的數據為止。當一個進程等待外部設備完成工作而被阻塞時，才是 I/O 活動。

上面 a 是 CPU 密集型進程；b 是 I/O 密集型進程進程，a 因為在計算的時間上花費時間更長，因此稱為計算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因為I/O 發生頻率比較快因此稱為 I/O 密集型(I/O-bound)。計算密集型進程有較長的 CPU 集中使用和較小頻度的 I/O 等待。I/O 密集型進程有較短的 CPU 使用時間和較頻繁的 I/O 等待。注意到上面兩種進程的區分關鍵在於 CPU 的時間佔用而不是 I/O 的時間佔用。I/O 密集型的原因是因為它們沒有在 I/O 之間花費更多的計算、而不是 I/O 請求時間特別長。無論數據到達後需要花費多少時間，它們都需要花費相同的時間來發出讀取磁碟塊的硬體請求。

值得注意的是，隨著 CPU 的速度越來越快，更多的進程傾向於 I/O 密集型。這種情況出現的原因是 CPU 速度的提升要遠遠高於硬碟。這種情況導致的結果是，未來對 I/O 密集型進程的調度處理似乎更為重要。這裡的基本思想是，如果需要運行 I/O 密集型進程，那麼就應該讓它儘快得到機會，以便發出磁碟請求並保持磁碟始終忙碌。

何時調度

第一個和調度有關的問題是何時進行調度決策。存在著需要調度處理的各種情形。首先，在創建一個新進程後，需要決定是運行父進程還是子進程。因為二者的進程都處於就緒態下，這是正常的調度決策，可以任意選擇，也就是說，調度程式可以任意的選擇子進程或父進程開始運行。

第二，在進程退出時需要作出調度決定。因為此進程不再運行（因為它將不再存在），因此必須從就緒進程中選擇其他進程運行。如果沒有進程處於就緒態，系統提供的空閑進程通常會運行

什麼是空閑進程

空閑進程(system-supplied idle process) 是 Microsoft 公司 windows 作業系統帶有的系統進程，該進程是在各個處理器上運行的單個執行緒，它唯一的任務是在系統沒有處理其他執行緒時佔用處理器時間。System Idle Process 並不是一個真正的進程，它是核心虛擬出來的，多任務作業系統都存在。在沒有可用的進程時，系統處於空運行狀態，此時就是System Idle Process 在正在運行。你可以簡單的理解成，它代表的是 CPU 的空閑狀態，數值越大代表處理器越空閑，可以通過 Windows 任務管理器查看 Windows 中的 CPU 利用率

第三種情況是，當進程阻塞在 I/O 、訊號量或其他原因時，必須選擇另外一個進程來運行。有時，阻塞的原因會成為選擇進程運行的關鍵因素。例如，如果 A 是一個重要進程，並且它正在等待 B 退出關鍵區域，讓 B 退出關鍵區域從而使 A 得以運行。但是調度程式一般不會對這種情況進行考量。

第四點，當 I/O 中斷髮生時，可以做出調度決策。如果中斷來自 I/O 設備，而 I/O 設備已經完成了其工作，那麼那些等待 I/O 的進程現在可以繼續運行。由調度程式來決定是否準備運行新的進程還是重新運行已經中斷的進程。

如果硬體時鐘以 50 或 60 Hz 或其他頻率提供周期性中斷，可以在每個時鐘中斷或第 k 個時鐘中斷處做出調度決策。根據如何處理時鐘中斷可以把調度演算法可以分為兩類。非搶佔式(nonpreemptive) 調度演算法挑選一個進程，讓該進程運行直到被阻塞（阻塞在 I/O 上或等待另一個進程），或者直到該進程自動釋放 CPU。即使該進程運行了若干個小時後，它也不會被強制掛起。這樣會在時鐘中斷髮生時不會進行調度。在處理完時鐘中斷後，如果沒有更高優先順序的進程等待，則被中斷的進程會繼續執行。

另外一種情況是 搶佔式 調度演算法，它會選擇一個進程，並使其在最大固定時間內運行。如果在時間間隔結束後仍在運行，這個進程會被掛起，調度程式會選擇其他進程來運行（前提是存在就緒進程）。進行搶佔式調度需要在時間間隔結束時發生時鐘中斷，以將 CPU 的控制權交還給調度程式。如果沒有可用的時鐘，那麼非搶佔式就是唯一的選擇。

調度演算法的分類

毫無疑問，不同的環境下需要不同的調度演算法。之所以出現這種情況，是因為不同的應用程式和不同的作業系統有不同的目標。也就是說，在不同的系統中，調度程式的優化也是不同的。這裡有必要劃分出三種環境

• 批處理(Batch)
• 互動式(Interactive)
• 實時(Real time)

批處理系統廣泛應用於商業領域，比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計算、索賠處理和其他周期性作業。在批處理系統中，一般會選擇使用非搶佔式演算法或者周期性比較長的搶佔式演算法。這種方法可以減少執行緒切換因此能夠提升性能。

在互動式用戶環境中，為了避免一個進程霸佔 CPU 拒絕為其他進程服務，所以需要搶佔式演算法。即使沒有進程有意要一直運行下去，但是，由於某個進程出現錯誤也有可能無限期的排斥其他所有進程。為了避免這種情況，搶佔式也是必須的。伺服器也屬於此類別，因為它們通常為多個（遠程）用戶提供服務，而這些用戶都非常著急。電腦用戶總是很忙。

在實時系統中，搶佔有時是不需要的，因為進程知道自己可能運行不了很長時間，通常很快的做完自己的工作並阻塞。實時系統與互動式系統的差別是，實時系統只運行那些用來推進現有應用的程式，而互動式系統是通用的，它可以運行任意的非協作甚至是有惡意的程式。

調度演算法的目標

為了設計調度演算法，有必要考慮一下什麼是好的調度演算法。有一些目標取決於環境（批處理、互動式或者實時）但大部分是適用於所有情況的，下面是一些需要考量的因素，我們會在下面一起討論。

所有系統

在所有的情況中，公平是很重要的。對一個進程給予相較於其他等價的進程更多的 CPU 時間片對其他進程來說是不公平的。當然，不同類型的進程可以採用不同的處理方式。

與公平有關的是系統的強制執行，什麼意思呢？如果某公司的薪資發放系統計劃在本月的15號，那麼碰上了疫情大家生活都很拮据，此時老闆說要在14號晚上發放薪資，那麼調度程式必須強制使進程執行 14 號晚上發放薪資的策略。

另一個共同的目標是保持系統的所有部分儘可能的忙碌。如果 CPU 和所有的 I/O 設備能夠一直運行，那麼相對於讓某些部件空轉而言，每秒鐘就可以完成更多的工作。例如，在批處理系統中，調度程式控制哪個作業調入記憶體運行。在記憶體中既有一些 CPU 密集型進程又有一些 I/O 密集型進程是一個比較好的想法，好於先調入和運行所有的 CPU 密集型作業，然後在它們完成之後再調入和運行所有 I/O 密集型作業的做法。使用後者這種方式會在 CPU 密集型進程啟動後，爭奪 CPU ，而磁碟卻在空轉，而當 I/O 密集型進程啟動後，它們又要為磁碟而競爭，CPU 卻又在空轉。。。。。。顯然，通過結合 I/O 密集型和 CPU 密集型，能夠使整個系統運行更流暢，效率更高。

批處理系統

通常有三個指標來衡量系統工作狀態：吞吐量、周轉時間和 CPU 利用率，吞吐量(throughout) 是系統每小時完成的作業數量。綜合考慮，每小時完成 50 個工作要比每小時完成 40 個工作好。周轉時間(Turnaround time) 是一種平均時間，它指的是從一個批處理提交開始直到作業完成時刻為止平均時間。該數據度量了用戶要得到輸出所需的平均等待時間。周轉時間越小越好。

CPU 利用率(CPU utilization) 通常作為批處理系統上的指標。即使如此， CPU 利用率也不是一個好的度量指標，真正有價值的衡量指標是系統每小時可以完成多少作業（吞吐量），以及完成作業需要多長時間（周轉時間）。把 CPU 利用率作為度量指標，就像是引擎每小時轉動了多少次來比較汽車的性能一樣。而且知道 CPU 的利用率什麼時候接近 100% 要比什麼什麼時候要求得到更多的計算能力要有用。

互動式系統

對於互動式系統，則有不同的指標。最重要的是盡量減少響應時間。這個時間說的是從執行指令開始到得到結果的時間。再有後台進程運行（例如，從網路上讀取和保存 E-mail 文件）的個人電腦上，用戶請求啟動一個程式或打開一個文件應該優先於後台的工作。能夠讓所有的互動式請求首先運行的就是一個好的服務。

一個相關的問題是 均衡性(proportionality)，用戶對做一件事情需要多長時間總是有一種固定（不過通常不正確）的看法。當認為一個請求很複雜需要較多時間時，用戶會認為很正常並且可以接受，但是一個很簡單的程式卻花費了很長的運行時間，用戶就會很惱怒。可以拿彩印和複印來舉出一個簡單的例子，彩印可能需要1分鐘的時間，但是用戶覺得複雜並且願意等待一分鐘，相反，複印很簡單只需要 5 秒鐘，但是複印機花費 1 分鐘卻沒有完成複印操作，用戶就會很焦躁。

實時系統

實時系統則有著和互動式系統不同的考量因素，因此也就有不同的調度目標。實時系統的特點是必須滿足最後的截止時間。例如，如果電腦控制著以固定速率產生數據的設備，未能按時運行的話可能會導致數據丟失。因此，實時系統中最重要的需求是滿足所有（或大多數）時間期限。

在一些實事系統中，特別是涉及到多媒體的，可預測性很重要。偶爾不能滿足最後的截止時間不重要，但是如果音頻多媒體運行不穩定，聲音品質會持續惡化。影片也會造成問題，但是耳朵要比眼睛敏感很多。為了避免這些問題，進程調度必須能夠高度可預測的而且是有規律的。

批處理中的調度

現在讓我們把目光從一般性的調度轉換為特定的調度演算法。下面我們會探討在批處理中的調度。

先來先服務

很像是先到先得。。。可能最簡單的非搶佔式調度演算法的設計就是 先來先服務(first-come,first-serverd)。使用此演算法，將按照請求順序為進程分配 CPU。最基本的，會有一個就緒進程的等待隊列。當第一個任務從外部進入系統時，將會立即啟動並允許運行任意長的時間。它不會因為運行時間太長而中斷。當其他作業進入時，它們排到就緒隊列尾部。當正在運行的進程阻塞，處於等待隊列的第一個進程就開始運行。當一個阻塞的進程重新處於就緒態時，它會像一個新到達的任務，會排在隊列的末尾，即排在所有進程最後。

這個演算法的強大之處在於易於理解和編程，在這個演算法中，一個單鏈表記錄了所有就緒進程。要選取一個進程運行，只要從該隊列的頭部移走一個進程即可；要添加一個新的作業或者阻塞一個進程，只要把這個作業或進程附加在隊列的末尾即可。這是很簡單的一種實現。

不過，先來先服務也是有缺點的，那就是沒有優先順序的關係，試想一下，如果有 100 個 I/O 進程正在排隊，第 101 個是一個 CPU 密集型進程，那豈不是需要等 100 個 I/O 進程運行完畢才會等到一個 CPU 密集型進程運行，這在實際情況下根本不可能，所以需要優先順序或者搶佔式進程的出現來優先選擇重要的進程運行。

最短作業優先

批處理中，第二種調度演算法是 最短作業優先(Shortest Job First)，我們假設運行時間已知。例如，一家保險公司，因為每天要做類似的工作，所以人們可以相當精確地預測處理 1000 個索賠的一批作業需要多長時間。當輸入隊列中有若干個同等重要的作業被啟動時，調度程式應使用最短優先作業演算法

如上圖 a 所示，這裡有 4 個作業 A、B、C、D ，運行時間分別為 8、4、4、4 分鐘。若按圖中的次序運行，則 A 的周轉時間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時間內為 14 分鐘。

現在考慮使用最短作業優先演算法運行 4 個作業，如上圖 b 所示，目前的周轉時間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業優先是最優的。考慮有 4 個作業的情況，其運行時間分別為 a、b、c、d。第一個作業在時間 a 結束，第二個在時間 a + b 結束，以此類推。平均周轉時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應該是最短優先作業，其次是 b，然後是 c ，最後是 d 它就只能影響自己的周轉時間了。

需要注意的是，在所有的進程都可以運行的情況下，最短作業優先的演算法才是最優的。

最短剩餘時間優先

最短作業優先的搶佔式版本被稱作為 最短剩餘時間優先(Shortest Remaining Time Next) 演算法。使用這個演算法，調度程式總是選擇剩餘運行時間最短的那個進程運行。當一個新作業到達時，其整個時間同當前進程的剩餘時間做比較。如果新的進程比當前運行進程需要更少的時間，當前進程就被掛起，而運行新的進程。這種方式能夠使短期作業獲得良好的服務。

互動式系統中的調度

互動式系統中在個人電腦、伺服器和其他系統中都是很常用的，所以有必要來探討一下互動式調度

輪詢調度

一種最古老、最簡單、最公平並且最廣泛使用的演算法就是 輪詢演算法(round-robin)。每個進程都會被分配一個時間段，稱為時間片(quantum)，在這個時間片內允許進程運行。如果時間片結束時進程還在運行的話，則搶佔一個 CPU 並將其分配給另一個進程。如果進程在時間片結束前阻塞或結束，則 CPU 立即進行切換。輪詢演算法比較容易實現。調度程式所做的就是維護一個可運行進程的列表，就像下圖中的 a，當一個進程用完時間片後就被移到隊列的末尾，就像下圖的 b。

時間片輪詢調度中唯一有意思的一點就是時間片的長度。從一個進程切換到另一個進程需要一定的時間進行管理處理，包括保存暫存器的值和記憶體映射、更新不同的表格和列表、清除和重新調入記憶體高速快取等。這種切換稱作 進程間切換(process switch) 和 上下文切換(context switch)。如果進程間的切換時間需要 1ms，其中包括記憶體映射、清除和重新調入高速快取等，再假設時間片設為 4 ms，那麼 CPU 在做完 4 ms 有用的工作之後，CPU 將花費 1 ms 來進行進程間的切換。因此，CPU 的時間片會浪費 20% 的時間在管理開銷上。耗費巨大。

為了提高 CPU 的效率，我們把時間片設置為 100 ms。現在時間的浪費只有 1%。但是考慮會發現下面的情況，如果在一個非常短的時間內到達 50 個請求，並且對 CPU 有不同的需求，此時會發生什麼？50 個進程都被放在可運行進程列表中。如果 CP畫U 是空閑的，第一個進程會立即開始執行，第二個直到 100 ms 以後才會啟動，以此類推。不幸的是最後一個進程需要等待 5 秒才能獲得執行機會。大部分用戶都會覺得對於一個簡短的指令運行 5 秒是很慢的。如果隊列末尾的某些請求只需要幾秒鐘的運行時間的話，這種設計就非常糟糕了。

另外一個因素是如果時間片設置長度要大於 CPU 使用長度，那麼搶佔就不會經常發生。相反，在時間片用完之前，大多數進程都已經阻塞了，那麼就會引起進程間的切換。消除搶佔可提高性能，因為進程切換僅在邏輯上必要時才發生，即流程阻塞且無法繼續時才發生。

結論可以表述如下：將上下文切換時間設置得太短會導致過多的進程切換並降低 CPU 效率，但設置時間太長會導致一個短請求很長時間得不到響應。最好的切換時間是在 20 – 50 毫秒之間設置。

優先順序調度

輪詢調度假設了所有的進程是同等重要的。但事實情況可能不是這樣。例如，在一所大學中的等級制度，首先是院長，然後是教授、秘書、後勤人員，最後是學生。這種將外部情況考慮在內就實現了優先順序調度(priority scheduling)

它的基本思想很明確，每個進程都被賦予一個優先順序，優先順序高的進程優先運行。

但是也不意味著高優先順序的進程能夠永遠一直運行下去，調度程式會在每個時鐘中斷期間降低當前運行進程的優先順序。如果此操作導致其優先順序降低到下一個最高進程的優先順序以下，則會發生進程切換。或者，可以為每個進程分配允許運行的最大時間間隔。當時間間隔用完後，下一個高優先順序的進程會得到運行的機會。

可以靜態或者動態的為進程分配優先順序。在一台軍用電腦上，可以把將軍所啟動的進程設為優先順序 100，上校為 90 ，少校為 80，上尉為 70，中尉為 60，以此類推。UNIX 有一條命令為 nice ，它允許用戶為了照顧他人而自願降低自己進程的優先順序，但是一般沒人用。

優先順序也可以由系統動態分配，用於實現某種目的。例如，有些進程為 I/O 密集型，其多數時間用來等待 I/O 結束。當這樣的進程需要 CPU 時，應立即分配 CPU，用來啟動下一個 I/O 請求，這樣就可以在另一個進程進行計算的同時執行 I/O 操作。這類 I/O 密集型進程長時間的等待 CPU 只會造成它長時間佔用記憶體。使 I/O 密集型進程獲得較好的服務的一種簡單演算法是，將其優先順序設為 1/f，f 為該進程在上一時間片中所佔的部分。一個在 50 ms 的時間片中只使用 1 ms 的進程將獲得優先順序 50 ，而在阻塞之前用掉 25 ms 的進程將具有優先順序 2，而使用掉全部時間片的進程將得到優先順序 1。

可以很方便的將一組進程按優先順序分成若干類，並且在各個類之間採用優先順序調度，而在各類進程的內部採用輪轉調度。下面展示了一個四個優先順序類的系統

它的調度演算法主要描述如下：上面存在優先順序為 4 類的可運行進程，首先會按照輪轉法為每個進程運行一個時間片，此時不理會較低優先順序的進程。若第 4 類進程為空，則按照輪詢的方式運行第三類進程。若第 4 類和第 3 類進程都為空，則按照輪轉法運行第 2 類進程。如果不對優先順序進行調整，則低優先順序的進程很容易產生飢餓現象。

多級隊列

最早使用優先順序調度的系統是 CTSS(Compatible TimeSharing System)。CTSS 是一種兼容分時系統，它有一個問題就是進程切換太慢，其原因是 IBM 7094 記憶體只能放進一個進程。

IBM 是哥倫比亞大學電腦中心在 1964 – 1968 年的電腦

CTSS 在每次切換前都需要將當前進程換出到磁碟，並從磁碟上讀入一個新進程。CTSS 的設計者很快就認識到，為 CPU 密集型進程設置較長的時間片比頻繁地分給他們很短的時間要更有效（減少交換次數）。另一方面，如前所述，長時間片的進程又會影響到響應時間，解決辦法是設置優先順序類。屬於最高優先順序的進程運行一個時間片，次高優先順序進程運行 2 個時間片，再下面一級運行 4 個時間片，以此類推。當一個進程用完分配的時間片後，它被移到下一類。

最短進程優先

對於批處理系統而言，由於最短作業優先常常伴隨著最短響應時間，所以如果能夠把它用於互動式進程，那將是非常好的。在某種程度上，的確可以做到這一點。互動式進程通常遵循下列模式：等待命令、執行命令、等待命令、執行命令。。。如果我們把每個命令的執行都看作一個分離的作業，那麼我們可以通過首先運行最短的作業來使響應時間最短。這裡唯一的問題是如何從當前可運行進程中找出最短的那一個進程。

一種方式是根據進程過去的行為進行推測，並執行估計運行時間最短的那一個。假設每個終端上每條命令的預估運行時間為 T0，現在假設測量到其下一次運行時間為 T1，可以用兩個值的加權來改進估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是儘快忘掉老的運行時間，還是在一段長時間內始終記住它們。當 a = 1/2 時，可以得到下面這個序列

可以看到，在三輪過後，T0 在新的估計值中所佔比重下降至 1/8。

有時把這種通過當前測量值和先前估計值進行加權平均從而得到下一個估計值的技術稱作 老化(aging)。這種方法會使用很多預測值基於當前值的情況。

保證調度

一種完全不同的調度方法是對用戶做出明確的性能保證。一種實際而且容易實現的保證是：若用戶工作時有 n 個用戶登錄，則每個用戶將獲得 CPU 處理能力的 1/n。類似地，在一個有 n 個進程運行的單用戶系統中，若所有的進程都等價，則每個進程將獲得 1/n 的 CPU 時間。

彩票調度

對用戶進行承諾並在隨後兌現承諾是一件好事，不過很難實現。但是存在著一種簡單的方式，有一種既可以給出預測結果而又有一種比較簡單的實現方式的演算法，就是 彩票調度(lottery scheduling)演算法。

其基本思想是為進程提供各種系統資源（例如 CPU 時間）的彩票。當做出一個調度決策的時候，就隨機抽出一張彩票，擁有彩票的進程將獲得該資源。在應用到 CPU 調度時，系統可以每秒持有 50 次抽獎，每個中獎者將獲得比如 20 毫秒的 CPU 時間作為獎勵。

George Orwell 關於 所有的進程是平等的，但是某些進程能夠更平等一些。一些重要的進程可以給它們額外的彩票，以便增加他們贏得的機會。如果出售了 100 張彩票，而且有一個進程持有了它們中的 20 張，它就會有 20% 的機會去贏得彩票中獎。在長時間的運行中，它就會獲得 20% 的CPU。相反，對於優先順序調度程式，很難說明擁有優先順序 40 究竟是什麼意思，這裡的規則很清楚，擁有彩票 f 份額的進程大約得到系統資源的 f 份額。

如果希望進程之間協作的話可以交換它們之間的票據。例如，客戶端進程給伺服器進程發送了一條消息後阻塞，客戶端進程可能會把自己所有的票據都交給伺服器，來增加下一次伺服器運行的機會。當服務完成後，它會把彩票還給客戶端讓其有機會再次運行。事實上，如果沒有客戶機，伺服器也根本不需要彩票。

可以把彩票理解為 buff，這個 buff 有 15% 的幾率能讓你產生 速度之靴 的效果。

公平分享調度

到目前為止，我們假設被調度的都是各個進程自身，而不用考慮該進程的擁有者是誰。結果是，如果用戶 1 啟動了 9 個進程，而用戶 2 啟動了一個進程，使用輪轉或相同優先順序調度演算法，那麼用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

為了阻止這種情況的出現，一些系統在調度前會把進程的擁有者考慮在內。在這種模型下，每個用戶都會分配一些CPU 時間，而調度程式會選擇進程並強制執行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證，那麼無論一個用戶有多少個進程，都將獲得相同的 CPU 份額。

實時系統中的調度

實時系統(real-time) 是一個時間扮演了重要作用的系統。典型的，一種或多種外部物理設備發給電腦一個服務請求，而電腦必須在一個確定的時間範圍內恰當的做出反應。例如，在 CD 播放器中的電腦會獲得從驅動器過來的位流，然後必須在非常短的時間內將位流轉換為音樂播放出來。如果計算時間過長，那麼音樂就會聽起來有異常。再比如說醫院特別護理部門的病人監護裝置、飛機中的自動駕駛系統、列車中的煙霧警告裝置等，在這些例子中，正確但是卻緩慢的響應要比沒有響應甚至還糟糕。

實時系統可以分為兩類，硬實時(hard real time) 和 軟實時(soft real time) 系統，前者意味著必須要滿足絕對的截止時間；後者的含義是雖然不希望偶爾錯失截止時間，但是可以容忍。在這兩種情形中，實時都是通過把程式劃分為一組進程而實現的，其中每個進程的行為是可預測和提前可知的。這些進程一般壽命較短，並且極快的運行完成。在檢測到一個外部訊號時，調度程式的任務就是按照滿足所有截止時間的要求調度進程。

實時系統中的事件可以按照響應方式進一步分類為周期性(以規則的時間間隔發生)事件或 非周期性(發生時間不可預知)事件。一個系統可能要響應多個周期性事件流，根據每個事件處理所需的時間，可能甚至無法處理所有事件。例如，如果有 m 個周期事件，事件 i 以周期 Pi 發生，並需要 Ci 秒 CPU 時間處理一個事件，那麼可以處理負載的條件是

只有滿足這個條件的實時系統稱為可調度的，這意味著它實際上能夠被實現。一個不滿足此檢驗標準的進程不能被調度，因為這些進程共同需要的 CPU 時間總和大於 CPU 能提供的時間。

舉一個例子，考慮一個有三個周期性事件的軟實時系統，其周期分別是 100 ms、200 m 和 500 ms。如果這些事件分別需要 50 ms、30 ms 和 100 ms 的 CPU 時間，那麼該系統是可調度的，因為 0.5 + 0.15 + 0.2 < 1。如果此時有第四個事件加入，其周期為 1 秒，那麼此時這個事件如果不超過 150 ms，那麼仍然是可以調度的。忽略上下文切換的時間。

實時系統的調度演算法可以是靜態的或動態的。前者在系統開始運行之前做出調度決策；後者在運行過程中進行調度決策。只有在可以提前掌握所完成的工作以及必須滿足的截止時間等資訊時，靜態調度才能工作，而動態調度不需要這些限制。

調度策略和機制

到目前為止，我們隱含的假設系統中所有進程屬於不同的分組用戶並且進程間存在相互競爭 CPU 的情況。通常情況下確實如此，但有時也會發生一個進程會有很多子進程並在其控制下運行的情況。例如，一個資料庫管理系統進程會有很多子進程。每一個子進程可能處理不同的請求，或者每個子進程實現不同的功能（如請求分析、磁碟訪問等）。主進程完全可能掌握哪一個子進程最重要（或最緊迫），而哪一個最不重要。但是，以上討論的調度演算法中沒有一個演算法從用戶進程接收有關的調度決策資訊，這就導致了調度程式很少能夠做出最優的選擇。

解決問題的辦法是將 調度機制(scheduling mechanism) 和 調度策略(scheduling policy) 分開，這是長期一貫的原則。這也就意味著調度演算法在某種方式下被參數化了，但是參數可以被用戶進程填寫。讓我們首先考慮資料庫的例子。假設內核使用優先順序調度演算法，並提供了一條可供進程設置優先順序的系統調用。這樣，儘管父進程本身並不參與調度，但它可以控制如何調度子進程的細節。調度機制位於內核，而調度策略由用戶進程決定，調度策略和機制分離是一種關鍵性思路。

執行緒調度

當若干進程都有多個執行緒時，就存在兩個層次的並行：進程和執行緒。在這樣的系統中調度處理有本質的差別，這取決於所支援的是用戶級執行緒還是內核級執行緒（或兩者都支援）。

首先考慮用戶級執行緒，由於內核並不知道有執行緒存在，所以內核還是和以前一樣地操作，選取一個進程，假設為 A，並給予 A 以時間片控制。A 中的執行緒調度程式決定哪個執行緒運行。假設為 A1。由於多道執行緒並不存在時鐘中斷，所以這個執行緒可以按其意願任意運行多長時間。如果該執行緒用完了進程的全部時間片，內核就會選擇另一個進程繼續運行。

在進程 A 終於又一次運行時，執行緒 A1 會接著運行。該執行緒會繼續耗費 A 進程的所有時間，直到它完成工作。不過，執行緒運行不會影響到其他進程。其他進程會得到調度程式所分配的合適份額，不會考慮進程 A 內部發生的事情。

現在考慮 A 執行緒每次 CPU 計算的工作比較少的情況，例如：在 50 ms 的時間片中有 5 ms 的計算工作。於是，每個執行緒運行一會兒，然後把 CPU 交回給執行緒調度程式。這樣在內核切換到進程 B 之前，就會有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。 如下所示

運行時系統使用的調度演算法可以是上面介紹演算法的任意一種。從實用方面考慮，輪轉調度和優先順序調度更為常用。唯一的局限是，缺乏一個時鐘中斷運行過長的執行緒。但由於執行緒之間的合作關係，這通常也不是問題。

現在考慮使用內核執行緒的情況，內核選擇一個特定的執行緒運行。它不用考慮執行緒屬於哪個進程，不過如果有必要的話，也可以這麼做。對被選擇的執行緒賦予一個時間片，而且如果超過了時間片，就會強制掛起該執行緒。一個執行緒在 50 ms 的時間片內，5 ms 之後被阻塞，在 30 ms 的時間片中，執行緒的順序會是 A1,B1,A2,B2,A3,B3。如下圖所示

用戶級執行緒和內核級執行緒之間的主要差別在於性能。用戶級執行緒的切換需要少量的機器指令（想像一下Java程式的執行緒切換），而內核執行緒需要完整的上下文切換，修改記憶體映像，使高速快取失效，這會導致了若干數量級的延遲。另一方面，在使用內核級執行緒時，一旦執行緒阻塞在 I/O 上就不需要在用戶級執行緒中那樣將整個進程掛起。

從進程 A 的一個執行緒切換到進程 B 的一個執行緒，其消耗要遠高於運行進程 A 的兩個執行緒（涉及修改記憶體映像，修改高速快取），內核對這種切換的消耗是了解到，可以通過這些資訊作出決定。

後記

提出一個《機械工業出版社》的翻譯勘誤，不知道能不能看到，先提了再說，很不嚴謹。

文章參考：

《現代作業系統》

《Modern Operating System》forth edition

https://www.encyclopedia.com/computing/news-wires-white-papers-and-books/interactive-systems

https://j00ru.vexillium.org/syscalls/nt/32/

https://www.bottomupcs.com/process_hierarchy.xhtml

https://en.wikipedia.org/wiki/Runtime_system

https://en.wikipedia.org/wiki/Execution_model

https://zhidao.baidu.com/question/113227654.html

https://baike.baidu.com/item/等待隊列/9223804?fr=aladdin

http://www.columbia.edu/cu/computinghistory/7094.html