[[315712]]

調(diào)度

當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)，會頻繁的有很多進(jìn)程或者線程來同時(shí)競爭 CPU 時(shí)間片。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會發(fā)生這種情況。如果只有一個(gè) CPU 可用，那么必須選擇接下來哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做 調(diào)度程序(scheduler) 的角色存在，它就是做這件事兒的，該程序使用的算法叫做 調(diào)度算法(scheduling algorithm) 。

盡管有一些不同，但許多適用于進(jìn)程調(diào)度的處理方法同樣也適用于線程調(diào)度。當(dāng)內(nèi)核管理線程的時(shí)候，調(diào)度通常會以線程級別發(fā)生，很少或者根本不會考慮線程屬于哪個(gè)進(jìn)程。下面我們會首先專注于進(jìn)程和線程的調(diào)度問題，然后會明確的介紹線程調(diào)度以及它產(chǎn)生的問題。

調(diào)度介紹

讓我們回到早期以磁帶上的卡片作為輸入的批處理系統(tǒng)的時(shí)代，那時(shí)候的調(diào)度算法非常簡單：依次運(yùn)行磁帶上的每一個(gè)作業(yè)。對于多道程序設(shè)計(jì)系統(tǒng)，會復(fù)雜一些，因?yàn)橥ǔ卸鄠€(gè)用戶在等待服務(wù)。一些大型機(jī)仍然將 批處理和 分時(shí)服務(wù)結(jié)合使用，需要調(diào)度程序決定下一個(gè)運(yùn)行的是一個(gè)批處理作業(yè)還是終端上的用戶。由于在這些機(jī)器中 CPU 是稀缺資源，所以好的調(diào)度程序可以在提高性能和用戶的滿意度方面取得很大的成果。

進(jìn)程行為

幾乎所有的進(jìn)程(磁盤或網(wǎng)絡(luò))I/O 請求和計(jì)算都是交替運(yùn)行的

如上圖所示，CPU 不停頓的運(yùn)行一段時(shí)間，然后發(fā)出一個(gè)系統(tǒng)調(diào)用等待 I/O 讀寫文件。完成系統(tǒng)調(diào)用后，CPU 又開始計(jì)算，直到它需要讀更多的數(shù)據(jù)或者寫入更多的數(shù)據(jù)為止。當(dāng)一個(gè)進(jìn)程等待外部設(shè)備完成工作而被阻塞時(shí)，才是 I/O 活動(dòng)。

上面 a 是 CPU 密集型進(jìn)程;b 是 I/O 密集型進(jìn)程進(jìn)程，a 因?yàn)樵谟?jì)算的時(shí)間上花費(fèi)時(shí)間更長，因此稱為計(jì)算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因?yàn)镮/O 發(fā)生頻率比較快因此稱為 I/O 密集型(I/O-bound)。計(jì)算密集型進(jìn)程有較長的 CPU 集中使用和較小頻度的 I/O 等待。I/O 密集型進(jìn)程有較短的 CPU 使用時(shí)間和較頻繁的 I/O 等待。注意到上面兩種進(jìn)程的區(qū)分關(guān)鍵在于 CPU 的時(shí)間占用而不是 I/O 的時(shí)間占用。I/O 密集型的原因是因?yàn)樗鼈儧]有在 I/O 之間花費(fèi)更多的計(jì)算、而不是 I/O 請求時(shí)間特別長。無論數(shù)據(jù)到達(dá)后需要花費(fèi)多少時(shí)間，它們都需要花費(fèi)相同的時(shí)間來發(fā)出讀取磁盤塊的硬件請求。

值得注意的是，隨著 CPU 的速度越來越快，更多的進(jìn)程傾向于 I/O 密集型。這種情況出現(xiàn)的原因是 CPU 速度的提升要遠(yuǎn)遠(yuǎn)高于硬盤。這種情況導(dǎo)致的結(jié)果是，未來對 I/O 密集型進(jìn)程的調(diào)度處理似乎更為重要。這里的基本思想是，如果需要運(yùn)行 I/O 密集型進(jìn)程，那么就應(yīng)該讓它盡快得到機(jī)會，以便發(fā)出磁盤請求并保持磁盤始終忙碌。

何時(shí)調(diào)度

第一個(gè)和調(diào)度有關(guān)的問題是何時(shí)進(jìn)行調(diào)度決策。存在著需要調(diào)度處理的各種情形。首先，在創(chuàng)建一個(gè)新進(jìn)程后，需要決定是運(yùn)行父進(jìn)程還是子進(jìn)程。因?yàn)槎叩倪M(jìn)程都處于就緒態(tài)下，這是正常的調(diào)度決策，可以任意選擇，也就是說，調(diào)度程序可以任意的選擇子進(jìn)程或父進(jìn)程開始運(yùn)行。

第二，在進(jìn)程退出時(shí)需要作出調(diào)度決定。因?yàn)榇诉M(jìn)程不再運(yùn)行(因?yàn)樗鼘⒉辉俅嬖?，因此必須從就緒進(jìn)程中選擇其他進(jìn)程運(yùn)行。如果沒有進(jìn)程處于就緒態(tài)，系統(tǒng)提供的空閑進(jìn)程通常會運(yùn)行

什么是空閑進(jìn)程

空閑進(jìn)程(system-supplied idle process) 是 Microsoft 公司 windows 操作系統(tǒng)帶有的系統(tǒng)進(jìn)程，該進(jìn)程是在各個(gè)處理器上運(yùn)行的單個(gè)線程，它唯一的任務(wù)是在系統(tǒng)沒有處理其他線程時(shí)占用處理器時(shí)間。System Idle Process 并不是一個(gè)真正的進(jìn)程，它是核心虛擬出來的，多任務(wù)操作系統(tǒng)都存在。在沒有可用的進(jìn)程時(shí)，系統(tǒng)處于空運(yùn)行狀態(tài)，此時(shí)就是System Idle Process 在正在運(yùn)行。你可以簡單的理解成，它代表的是 CPU 的空閑狀態(tài)，數(shù)值越大代表處理器越空閑，可以通過 Windows 任務(wù)管理器查看 Windows 中的 CPU 利用率

第三種情況是，當(dāng)進(jìn)程阻塞在 I/O 、信號量或其他原因時(shí)，必須選擇另外一個(gè)進(jìn)程來運(yùn)行。有時(shí)，阻塞的原因會成為選擇進(jìn)程運(yùn)行的關(guān)鍵因素。例如，如果 A 是一個(gè)重要進(jìn)程，并且它正在等待 B 退出關(guān)鍵區(qū)域，讓 B 退出關(guān)鍵區(qū)域從而使 A 得以運(yùn)行。但是調(diào)度程序一般不會對這種情況進(jìn)行考量。

第四點(diǎn)，當(dāng) I/O 中斷發(fā)生時(shí)，可以做出調(diào)度決策。如果中斷來自 I/O 設(shè)備，而 I/O 設(shè)備已經(jīng)完成了其工作，那么那些等待 I/O 的進(jìn)程現(xiàn)在可以繼續(xù)運(yùn)行。由調(diào)度程序來決定是否準(zhǔn)備運(yùn)行新的進(jìn)程還是重新運(yùn)行已經(jīng)中斷的進(jìn)程。

如果硬件時(shí)鐘以 50 或 60 Hz 或其他頻率提供周期性中斷，可以在每個(gè)時(shí)鐘中斷或第 k 個(gè)時(shí)鐘中斷處做出調(diào)度決策。根據(jù)如何處理時(shí)鐘中斷可以把調(diào)度算法可以分為兩類。非搶占式(nonpreemptive) 調(diào)度算法挑選一個(gè)進(jìn)程，讓該進(jìn)程運(yùn)行直到被阻塞(阻塞在 I/O 上或等待另一個(gè)進(jìn)程)，或者直到該進(jìn)程自動(dòng)釋放 CPU。即使該進(jìn)程運(yùn)行了若干個(gè)小時(shí)后，它也不會被強(qiáng)制掛起。這樣會在時(shí)鐘中斷發(fā)生時(shí)不會進(jìn)行調(diào)度。在處理完時(shí)鐘中斷后，如果沒有更高優(yōu)先級的進(jìn)程等待，則被中斷的進(jìn)程會繼續(xù)執(zhí)行。

另外一種情況是 搶占式 調(diào)度算法，它會選擇一個(gè)進(jìn)程，并使其在最大固定時(shí)間內(nèi)運(yùn)行。如果在時(shí)間間隔結(jié)束后仍在運(yùn)行，這個(gè)進(jìn)程會被掛起，調(diào)度程序會選擇其他進(jìn)程來運(yùn)行(前提是存在就緒進(jìn)程)。進(jìn)行搶占式調(diào)度需要在時(shí)間間隔結(jié)束時(shí)發(fā)生時(shí)鐘中斷，以將 CPU 的控制權(quán)交還給調(diào)度程序。如果沒有可用的時(shí)鐘，那么非搶占式就是唯一的選擇。

調(diào)度算法的分類

毫無疑問，不同的環(huán)境下需要不同的調(diào)度算法。之所以出現(xiàn)這種情況，是因?yàn)椴煌膽?yīng)用程序和不同的操作系統(tǒng)有不同的目標(biāo)。也就是說，在不同的系統(tǒng)中，調(diào)度程序的優(yōu)化也是不同的。這里有必要?jiǎng)澐殖鋈N環(huán)境

• 批處理(Batch)
• 交互式(Interactive)
• 實(shí)時(shí)(Real time)

批處理系統(tǒng)廣泛應(yīng)用于商業(yè)領(lǐng)域，比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計(jì)算、索賠處理和其他周期性作業(yè)。在批處理系統(tǒng)中，一般會選擇使用非搶占式算法或者周期性比較長的搶占式算法。這種方法可以減少線程切換因此能夠提升性能。

在交互式用戶環(huán)境中，為了避免一個(gè)進(jìn)程霸占 CPU 拒絕為其他進(jìn)程服務(wù)，所以需要搶占式算法。即使沒有進(jìn)程有意要一直運(yùn)行下去，但是，由于某個(gè)進(jìn)程出現(xiàn)錯(cuò)誤也有可能無限期的排斥其他所有進(jìn)程。為了避免這種情況，搶占式也是必須的。服務(wù)器也屬于此類別，因?yàn)樗鼈兺ǔ槎鄠€(gè)(遠(yuǎn)程)用戶提供服務(wù)，而這些用戶都非常著急。計(jì)算機(jī)用戶總是很忙。

在實(shí)時(shí)系統(tǒng)中，搶占有時(shí)是不需要的，因?yàn)檫M(jìn)程知道自己可能運(yùn)行不了很長時(shí)間，通常很快的做完自己的工作并阻塞。實(shí)時(shí)系統(tǒng)與交互式系統(tǒng)的差別是，實(shí)時(shí)系統(tǒng)只運(yùn)行那些用來推進(jìn)現(xiàn)有應(yīng)用的程序，而交互式系統(tǒng)是通用的，它可以運(yùn)行任意的非協(xié)作甚至是有惡意的程序。

調(diào)度算法的目標(biāo)

為了設(shè)計(jì)調(diào)度算法，有必要考慮一下什么是好的調(diào)度算法。有一些目標(biāo)取決于環(huán)境(批處理、交互式或者實(shí)時(shí))但大部分是適用于所有情況的，下面是一些需要考量的因素，我們會在下面一起討論。

所有系統(tǒng)

在所有的情況中，公平是很重要的。對一個(gè)進(jìn)程給予相較于其他等價(jià)的進(jìn)程更多的 CPU 時(shí)間片對其他進(jìn)程來說是不公平的。當(dāng)然，不同類型的進(jìn)程可以采用不同的處理方式。

與公平有關(guān)的是系統(tǒng)的強(qiáng)制執(zhí)行，什么意思呢?如果某公司的薪資發(fā)放系統(tǒng)計(jì)劃在本月的15號，那么碰上了疫情大家生活都很拮據(jù)，此時(shí)老板說要在14號晚上發(fā)放薪資，那么調(diào)度程序必須強(qiáng)制使進(jìn)程執(zhí)行 14 號晚上發(fā)放薪資的策略。

另一個(gè)共同的目標(biāo)是保持系統(tǒng)的所有部分盡可能的忙碌。如果 CPU 和所有的 I/O 設(shè)備能夠一直運(yùn)行，那么相對于讓某些部件空轉(zhuǎn)而言，每秒鐘就可以完成更多的工作。例如，在批處理系統(tǒng)中，調(diào)度程序控制哪個(gè)作業(yè)調(diào)入內(nèi)存運(yùn)行。在內(nèi)存中既有一些 CPU 密集型進(jìn)程又有一些 I/O 密集型進(jìn)程是一個(gè)比較好的想法，好于先調(diào)入和運(yùn)行所有的 CPU 密集型作業(yè)，然后在它們完成之后再調(diào)入和運(yùn)行所有 I/O 密集型作業(yè)的做法。使用后者這種方式會在 CPU 密集型進(jìn)程啟動(dòng)后，爭奪 CPU ，而磁盤卻在空轉(zhuǎn)，而當(dāng) I/O 密集型進(jìn)程啟動(dòng)后，它們又要為磁盤而競爭，CPU 卻又在空轉(zhuǎn)。。。。。。顯然，通過結(jié)合 I/O 密集型和 CPU 密集型，能夠使整個(gè)系統(tǒng)運(yùn)行更流暢，效率更高。

批處理系統(tǒng)

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

CPU 利用率(CPU utilization) 通常作為批處理系統(tǒng)上的指標(biāo)。即使如此， CPU 利用率也不是一個(gè)好的度量指標(biāo)，真正有價(jià)值的衡量指標(biāo)是系統(tǒng)每小時(shí)可以完成多少作業(yè)(吞吐量)，以及完成作業(yè)需要多長時(shí)間(周轉(zhuǎn)時(shí)間)。把 CPU 利用率作為度量指標(biāo)，就像是引擎每小時(shí)轉(zhuǎn)動(dòng)了多少次來比較汽車的性能一樣。而且知道 CPU 的利用率什么時(shí)候接近 100% 要比什么什么時(shí)候要求得到更多的計(jì)算能力要有用。

交互式系統(tǒng)

對于交互式系統(tǒng)，則有不同的指標(biāo)。最重要的是盡量減少響應(yīng)時(shí)間。這個(gè)時(shí)間說的是從執(zhí)行指令開始到得到結(jié)果的時(shí)間。再有后臺進(jìn)程運(yùn)行(例如，從網(wǎng)絡(luò)上讀取和保存 E-mail 文件)的個(gè)人計(jì)算機(jī)上，用戶請求啟動(dòng)一個(gè)程序或打開一個(gè)文件應(yīng)該優(yōu)先于后臺的工作。能夠讓所有的交互式請求首先運(yùn)行的就是一個(gè)好的服務(wù)。

一個(gè)相關(guān)的問題是 均衡性(proportionality)，用戶對做一件事情需要多長時(shí)間總是有一種固定(不過通常不正確)的看法。當(dāng)認(rèn)為一個(gè)請求很復(fù)雜需要較多時(shí)間時(shí)，用戶會認(rèn)為很正常并且可以接受，但是一個(gè)很簡單的程序卻花費(fèi)了很長的運(yùn)行時(shí)間，用戶就會很惱怒?？梢阅貌视『蛷?fù)印來舉出一個(gè)簡單的例子，彩印可能需要1分鐘的時(shí)間，但是用戶覺得復(fù)雜并且愿意等待一分鐘，相反，復(fù)印很簡單只需要 5 秒鐘，但是復(fù)印機(jī)花費(fèi) 1 分鐘卻沒有完成復(fù)印操作，用戶就會很焦躁。

實(shí)時(shí)系統(tǒng)

實(shí)時(shí)系統(tǒng)則有著和交互式系統(tǒng)不同的考量因素，因此也就有不同的調(diào)度目標(biāo)。實(shí)時(shí)系統(tǒng)的特點(diǎn)是必須滿足最后的截止時(shí)間。例如，如果計(jì)算機(jī)控制著以固定速率產(chǎn)生數(shù)據(jù)的設(shè)備，未能按時(shí)運(yùn)行的話可能會導(dǎo)致數(shù)據(jù)丟失。因此，實(shí)時(shí)系統(tǒng)中最重要的需求是滿足所有(或大多數(shù))時(shí)間期限。

在一些實(shí)事系統(tǒng)中，特別是涉及到多媒體的，可預(yù)測性很重要。偶爾不能滿足最后的截止時(shí)間不重要，但是如果音頻多媒體運(yùn)行不穩(wěn)定，聲音質(zhì)量會持續(xù)惡化。視頻也會造成問題，但是耳朵要比眼睛敏感很多。為了避免這些問題，進(jìn)程調(diào)度必須能夠高度可預(yù)測的而且是有規(guī)律的。

批處理中的調(diào)度

現(xiàn)在讓我們把目光從一般性的調(diào)度轉(zhuǎn)換為特定的調(diào)度算法。下面我們會探討在批處理中的調(diào)度。

先來先服務(wù)

很像是先到先得。。?？赡茏詈唵蔚姆菗屨际秸{(diào)度算法的設(shè)計(jì)就是 先來先服務(wù)(first-come,first-serverd)。使用此算法，將按照請求順序?yàn)檫M(jìn)程分配 CPU。最基本的，會有一個(gè)就緒進(jìn)程的等待隊(duì)列。當(dāng)?shù)谝粋€(gè)任務(wù)從外部進(jìn)入系統(tǒng)時(shí)，將會立即啟動(dòng)并允許運(yùn)行任意長的時(shí)間。它不會因?yàn)檫\(yùn)行時(shí)間太長而中斷。當(dāng)其他作業(yè)進(jìn)入時(shí)，它們排到就緒隊(duì)列尾部。當(dāng)正在運(yùn)行的進(jìn)程阻塞，處于等待隊(duì)列的第一個(gè)進(jìn)程就開始運(yùn)行。當(dāng)一個(gè)阻塞的進(jìn)程重新處于就緒態(tài)時(shí)，它會像一個(gè)新到達(dá)的任務(wù)，會排在隊(duì)列的末尾，即排在所有進(jìn)程最后。

這個(gè)算法的強(qiáng)大之處在于易于理解和編程，在這個(gè)算法中，一個(gè)單鏈表記錄了所有就緒進(jìn)程。要選取一個(gè)進(jìn)程運(yùn)行，只要從該隊(duì)列的頭部移走一個(gè)進(jìn)程即可;要添加一個(gè)新的作業(yè)或者阻塞一個(gè)進(jìn)程，只要把這個(gè)作業(yè)或進(jìn)程附加在隊(duì)列的末尾即可。這是很簡單的一種實(shí)現(xiàn)。

不過，先來先服務(wù)也是有缺點(diǎn)的，那就是沒有優(yōu)先級的關(guān)系，試想一下，如果有 100 個(gè) I/O 進(jìn)程正在排隊(duì)，第 101 個(gè)是一個(gè) CPU 密集型進(jìn)程，那豈不是需要等 100 個(gè) I/O 進(jìn)程運(yùn)行完畢才會等到一個(gè) CPU 密集型進(jìn)程運(yùn)行，這在實(shí)際情況下根本不可能，所以需要優(yōu)先級或者搶占式進(jìn)程的出現(xiàn)來優(yōu)先選擇重要的進(jìn)程運(yùn)行。

最短作業(yè)優(yōu)先

批處理中，第二種調(diào)度算法是 最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知。例如，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測處理 1000 個(gè)索賠的一批作業(yè)需要多長時(shí)間。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

如上圖 a 所示，這里有 4 個(gè)作業(yè) A、B、C、D ，運(yùn)行時(shí)間分別為 8、4、4、4 分鐘。若按圖中的次序運(yùn)行，則 A 的周轉(zhuǎn)時(shí)間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時(shí)間內(nèi)為 14 分鐘。

現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運(yùn)行 4 個(gè)作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時(shí)間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的?？紤]有 4 個(gè)作業(yè)的情況，其運(yùn)行時(shí)間分別為 a、b、c、d。第一個(gè)作業(yè)在時(shí)間 a 結(jié)束，第二個(gè)在時(shí)間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時(shí)間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時(shí)間了。

需要注意的是，在所有的進(jìn)程都可以運(yùn)行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。

最短剩余時(shí)間優(yōu)先

最短作業(yè)優(yōu)先的搶占式版本被稱作為 最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next) 算法。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行。當(dāng)一個(gè)新作業(yè)到達(dá)時(shí)，其整個(gè)時(shí)間同當(dāng)前進(jìn)程的剩余時(shí)間做比較。如果新的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程需要更少的時(shí)間，當(dāng)前進(jìn)程就被掛起，而運(yùn)行新的進(jìn)程。這種方式能夠使短期作業(yè)獲得良好的服務(wù)。

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個(gè)人計(jì)算機(jī)、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調(diào)度

輪詢調(diào)度

一種最古老、最簡單、最公平并且最廣泛使用的算法就是 輪詢算法(round-robin)。每個(gè)進(jìn)程都會被分配一個(gè)時(shí)間段，稱為時(shí)間片(quantum)，在這個(gè)時(shí)間片內(nèi)允許進(jìn)程運(yùn)行。如果時(shí)間片結(jié)束時(shí)進(jìn)程還在運(yùn)行的話，則搶占一個(gè) CPU 并將其分配給另一個(gè)進(jìn)程。如果進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換。輪詢算法比較容易實(shí)現(xiàn)。調(diào)度程序所做的就是維護(hù)一個(gè)可運(yùn)行進(jìn)程的列表，就像下圖中的 a，當(dāng)一個(gè)進(jìn)程用完時(shí)間片后就被移到隊(duì)列的末尾，就像下圖的 b。

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

為了提高 CPU 的效率，我們把時(shí)間片設(shè)置為 100 ms?，F(xiàn)在時(shí)間的浪費(fèi)只有 1%。但是考慮會發(fā)現(xiàn)下面的情況，如果在一個(gè)非常短的時(shí)間內(nèi)到達(dá) 50 個(gè)請求，并且對 CPU 有不同的需求，此時(shí)會發(fā)生什么?50 個(gè)進(jìn)程都被放在可運(yùn)行進(jìn)程列表中。如果 CP畫U 是空閑的，第一個(gè)進(jìn)程會立即開始執(zhí)行，第二個(gè)直到 100 ms 以后才會啟動(dòng)，以此類推。不幸的是最后一個(gè)進(jìn)程需要等待 5 秒才能獲得執(zhí)行機(jī)會。大部分用戶都會覺得對于一個(gè)簡短的指令運(yùn)行 5 秒是很慢的。如果隊(duì)列末尾的某些請求只需要幾秒鐘的運(yùn)行時(shí)間的話，這種設(shè)計(jì)就非常糟糕了。

另外一個(gè)因素是如果時(shí)間片設(shè)置長度要大于 CPU 使用長度，那么搶占就不會經(jīng)常發(fā)生。相反，在時(shí)間片用完之前，大多數(shù)進(jìn)程都已經(jīng)阻塞了，那么就會引起進(jìn)程間的切換。消除搶占可提高性能，因?yàn)檫M(jìn)程切換僅在邏輯上必要時(shí)才發(fā)生，即流程阻塞且無法繼續(xù)時(shí)才發(fā)生。

結(jié)論可以表述如下：將上下文切換時(shí)間設(shè)置得太短會導(dǎo)致過多的進(jìn)程切換并降低 CPU 效率，但設(shè)置時(shí)間太長會導(dǎo)致一個(gè)短請求很長時(shí)間得不到響應(yīng)。最好的切換時(shí)間是在 20 - 50 毫秒之間設(shè)置。

優(yōu)先級調(diào)度

輪詢調(diào)度假設(shè)了所有的進(jìn)程是同等重要的。但事實(shí)情況可能不是這樣。例如，在一所大學(xué)中的等級制度，首先是院長，然后是教授、秘書、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級調(diào)度(priority scheduling)

它的基本思想很明確，每個(gè)進(jìn)程都被賦予一個(gè)優(yōu)先級，優(yōu)先級高的進(jìn)程優(yōu)先運(yùn)行。

但是也不意味著高優(yōu)先級的進(jìn)程能夠永遠(yuǎn)一直運(yùn)行下去，調(diào)度程序會在每個(gè)時(shí)鐘中斷期間降低當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級。如果此操作導(dǎo)致其優(yōu)先級降低到下一個(gè)最高進(jìn)程的優(yōu)先級以下，則會發(fā)生進(jìn)程切換。或者，可以為每個(gè)進(jìn)程分配允許運(yùn)行的最大時(shí)間間隔。當(dāng)時(shí)間間隔用完后，下一個(gè)高優(yōu)先級的進(jìn)程會得到運(yùn)行的機(jī)會。

可以靜態(tài)或者動(dòng)態(tài)的為進(jìn)程分配優(yōu)先級。在一臺軍用計(jì)算機(jī)上，可以把將軍所啟動(dòng)的進(jìn)程設(shè)為優(yōu)先級 100，上校為 90 ，少校為 80，上尉為 70，中尉為 60，以此類推。UNIX 有一條命令為 nice ，它允許用戶為了照顧他人而自愿降低自己進(jìn)程的優(yōu)先級，但是一般沒人用。

優(yōu)先級也可以由系統(tǒng)動(dòng)態(tài)分配，用于實(shí)現(xiàn)某種目的。例如，有些進(jìn)程為 I/O 密集型，其多數(shù)時(shí)間用來等待 I/O 結(jié)束。當(dāng)這樣的進(jìn)程需要 CPU 時(shí)，應(yīng)立即分配 CPU，用來啟動(dòng)下一個(gè) I/O 請求，這樣就可以在另一個(gè)進(jìn)程進(jìn)行計(jì)算的同時(shí)執(zhí)行 I/O 操作。這類 I/O 密集型進(jìn)程長時(shí)間的等待 CPU 只會造成它長時(shí)間占用內(nèi)存。使 I/O 密集型進(jìn)程獲得較好的服務(wù)的一種簡單算法是，將其優(yōu)先級設(shè)為 1/f，f 為該進(jìn)程在上一時(shí)間片中所占的部分。一個(gè)在 50 ms 的時(shí)間片中只使用 1 ms 的進(jìn)程將獲得優(yōu)先級 50 ，而在阻塞之前用掉 25 ms 的進(jìn)程將具有優(yōu)先級 2，而使用掉全部時(shí)間片的進(jìn)程將得到優(yōu)先級 1。

可以很方便的將一組進(jìn)程按優(yōu)先級分成若干類，并且在各個(gè)類之間采用優(yōu)先級調(diào)度，而在各類進(jìn)程的內(nèi)部采用輪轉(zhuǎn)調(diào)度。下面展示了一個(gè)四個(gè)優(yōu)先級類的系統(tǒng)

它的調(diào)度算法主要描述如下：上面存在優(yōu)先級為 4 類的可運(yùn)行進(jìn)程，首先會按照輪轉(zhuǎn)法為每個(gè)進(jìn)程運(yùn)行一個(gè)時(shí)間片，此時(shí)不理會較低優(yōu)先級的進(jìn)程。若第 4 類進(jìn)程為空，則按照輪詢的方式運(yùn)行第三類進(jìn)程。若第 4 類和第 3 類進(jìn)程都為空，則按照輪轉(zhuǎn)法運(yùn)行第 2 類進(jìn)程。如果不對優(yōu)先級進(jìn)行調(diào)整，則低優(yōu)先級的進(jìn)程很容易產(chǎn)生饑餓現(xiàn)象。

多級隊(duì)列

最早使用優(yōu)先級調(diào)度的系統(tǒng)是 CTSS(Compatible TimeSharing System)。CTSS 是一種兼容分時(shí)系統(tǒng)，它有一個(gè)問題就是進(jìn)程切換太慢，其原因是 IBM 7094 內(nèi)存只能放進(jìn)一個(gè)進(jìn)程。

IBM 是哥倫比亞大學(xué)計(jì)算機(jī)中心在 1964 - 1968 年的計(jì)算機(jī)

[[315718]]

CTSS 在每次切換前都需要將當(dāng)前進(jìn)程換出到磁盤，并從磁盤上讀入一個(gè)新進(jìn)程。CTSS 的設(shè)計(jì)者很快就認(rèn)識到，為 CPU 密集型進(jìn)程設(shè)置較長的時(shí)間片比頻繁地分給他們很短的時(shí)間要更有效(減少交換次數(shù))。另一方面，如前所述，長時(shí)間片的進(jìn)程又會影響到響應(yīng)時(shí)間，解決辦法是設(shè)置優(yōu)先級類。屬于最高優(yōu)先級的進(jìn)程運(yùn)行一個(gè)時(shí)間片，次高優(yōu)先級進(jìn)程運(yùn)行 2 個(gè)時(shí)間片，再下面一級運(yùn)行 4 個(gè)時(shí)間片，以此類推。當(dāng)一個(gè)進(jìn)程用完分配的時(shí)間片后，它被移到下一類。

最短進(jìn)程優(yōu)先

對于批處理系統(tǒng)而言，由于最短作業(yè)優(yōu)先常常伴隨著最短響應(yīng)時(shí)間，所以如果能夠把它用于交互式進(jìn)程，那將是非常好的。在某種程度上，的確可以做到這一點(diǎn)。交互式進(jìn)程通常遵循下列模式：等待命令、執(zhí)行命令、等待命令、執(zhí)行命令。。。如果我們把每個(gè)命令的執(zhí)行都看作一個(gè)分離的作業(yè)，那么我們可以通過首先運(yùn)行最短的作業(yè)來使響應(yīng)時(shí)間最短。這里唯一的問題是如何從當(dāng)前可運(yùn)行進(jìn)程中找出最短的那一個(gè)進(jìn)程。

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

可以看到，在三輪過后，T0 在新的估計(jì)值中所占比重下降至 1/8。

有時(shí)把這種通過當(dāng)前測量值和先前估計(jì)值進(jìn)行加權(quán)平均從而得到下一個(gè)估計(jì)值的技術(shù)稱作 老化(aging)。這種方法會使用很多預(yù)測值基于當(dāng)前值的情況。

保證調(diào)度

一種完全不同的調(diào)度方法是對用戶做出明確的性能保證。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n。類似地，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間。

彩票調(diào)度

對用戶進(jìn)行承諾并在隨后兌現(xiàn)承諾是一件好事，不過很難實(shí)現(xiàn)。但是存在著一種簡單的方式，有一種既可以給出預(yù)測結(jié)果而又有一種比較簡單的實(shí)現(xiàn)方式的算法，就是 彩票調(diào)度(lottery scheduling)算法。

其基本思想是為進(jìn)程提供各種系統(tǒng)資源(例如 CPU 時(shí)間)的彩票。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得該資源。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)。

George Orwell 關(guān)于 所有的進(jìn)程是平等的，但是某些進(jìn)程能夠更平等一些。一些重要的進(jìn)程可以給它們額外的彩票，以便增加他們贏得的機(jī)會。如果出售了 100 張彩票，而且有一個(gè)進(jìn)程持有了它們中的 20 張，它就會有 20% 的機(jī)會去贏得彩票中獎(jiǎng)。在長時(shí)間的運(yùn)行中，它就會獲得 20% 的CPU。相反，對于優(yōu)先級調(diào)度程序，很難說明擁有優(yōu)先級 40 究竟是什么意思，這里的規(guī)則很清楚，擁有彩票 f 份額的進(jìn)程大約得到系統(tǒng)資源的 f 份額。

如果希望進(jìn)程之間協(xié)作的話可以交換它們之間的票據(jù)。例如，客戶端進(jìn)程給服務(wù)器進(jìn)程發(fā)送了一條消息后阻塞，客戶端進(jìn)程可能會把自己所有的票據(jù)都交給服務(wù)器，來增加下一次服務(wù)器運(yùn)行的機(jī)會。當(dāng)服務(wù)完成后，它會把彩票還給客戶端讓其有機(jī)會再次運(yùn)行。事實(shí)上，如果沒有客戶機(jī)，服務(wù)器也根本不需要彩票。

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

公平分享調(diào)度

到目前為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身，而不用考慮該進(jìn)程的擁有者是誰。結(jié)果是，如果用戶 1 啟動(dòng)了 9 個(gè)進(jìn)程，而用戶 2 啟動(dòng)了一個(gè)進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時(shí)間，而用戶 2 將之得到 10 % 的 CPU 時(shí)間。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個(gè)用戶都會分配一些CPU 時(shí)間，而調(diào)度程序會選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個(gè)用戶每個(gè)都會有 50% 的 CPU 時(shí)間片保證，那么無論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額。

實(shí)時(shí)系統(tǒng)中的調(diào)度

實(shí)時(shí)系統(tǒng)(real-time) 是一個(gè)時(shí)間扮演了重要作用的系統(tǒng)。典型的，一種或多種外部物理設(shè)備發(fā)給計(jì)算機(jī)一個(gè)服務(wù)請求，而計(jì)算機(jī)必須在一個(gè)確定的時(shí)間范圍內(nèi)恰當(dāng)?shù)淖龀龇磻?yīng)。例如，在 CD 播放器中的計(jì)算機(jī)會獲得從驅(qū)動(dòng)器過來的位流，然后必須在非常短的時(shí)間內(nèi)將位流轉(zhuǎn)換為音樂播放出來。如果計(jì)算時(shí)間過長，那么音樂就會聽起來有異常。再比如說醫(yī)院特別護(hù)理部門的病人監(jiān)護(hù)裝置、飛機(jī)中的自動(dòng)駕駛系統(tǒng)、列車中的煙霧警告裝置等，在這些例子中，正確但是卻緩慢的響應(yīng)要比沒有響應(yīng)甚至還糟糕。

實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time) 和 軟實(shí)時(shí)(soft real time) 系統(tǒng)，前者意味著必須要滿足絕對的截止時(shí)間;后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍。在這兩種情形中，實(shí)時(shí)都是通過把程序劃分為一組進(jìn)程而實(shí)現(xiàn)的，其中每個(gè)進(jìn)程的行為是可預(yù)測和提前可知的。這些進(jìn)程一般壽命較短，并且極快的運(yùn)行完成。在檢測到一個(gè)外部信號時(shí)，調(diào)度程序的任務(wù)就是按照滿足所有截止時(shí)間的要求調(diào)度進(jìn)程。

實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或 非周期性(發(fā)生時(shí)間不可預(yù)知)事件。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間，可能甚至無法處理所有事件。例如，如果有 m 個(gè)周期事件，事件 i 以周期 Pi 發(fā)生，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是

只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的，這意味著它實(shí)際上能夠被實(shí)現(xiàn)。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間。

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

實(shí)時(shí)系統(tǒng)的調(diào)度算法可以是靜態(tài)的或動(dòng)態(tài)的。前者在系統(tǒng)開始運(yùn)行之前做出調(diào)度決策;后者在運(yùn)行過程中進(jìn)行調(diào)度決策。只有在可以提前掌握所完成的工作以及必須滿足的截止時(shí)間等信息時(shí)，靜態(tài)調(diào)度才能工作，而動(dòng)態(tài)調(diào)度不需要這些限制。

調(diào)度策略和機(jī)制

到目前為止，我們隱含的假設(shè)系統(tǒng)中所有進(jìn)程屬于不同的分組用戶并且進(jìn)程間存在相互競爭 CPU 的情況。通常情況下確實(shí)如此，但有時(shí)也會發(fā)生一個(gè)進(jìn)程會有很多子進(jìn)程并在其控制下運(yùn)行的情況。例如，一個(gè)數(shù)據(jù)庫管理系統(tǒng)進(jìn)程會有很多子進(jìn)程。每一個(gè)子進(jìn)程可能處理不同的請求，或者每個(gè)子進(jìn)程實(shí)現(xiàn)不同的功能(如請求分析、磁盤訪問等)。主進(jìn)程完全可能掌握哪一個(gè)子進(jìn)程最重要(或最緊迫)，而哪一個(gè)最不重要。但是，以上討論的調(diào)度算法中沒有一個(gè)算法從用戶進(jìn)程接收有關(guān)的調(diào)度決策信息，這就導(dǎo)致了調(diào)度程序很少能夠做出最優(yōu)的選擇。

解決問題的辦法是將 調(diào)度機(jī)制(scheduling mechanism) 和 調(diào)度策略(scheduling policy) 分開，這是長期一貫的原則。這也就意味著調(diào)度算法在某種方式下被參數(shù)化了，但是參數(shù)可以被用戶進(jìn)程填寫。讓我們首先考慮數(shù)據(jù)庫的例子。假設(shè)內(nèi)核使用優(yōu)先級調(diào)度算法，并提供了一條可供進(jìn)程設(shè)置優(yōu)先級的系統(tǒng)調(diào)用。這樣，盡管父進(jìn)程本身并不參與調(diào)度，但它可以控制如何調(diào)度子進(jìn)程的細(xì)節(jié)。調(diào)度機(jī)制位于內(nèi)核，而調(diào)度策略由用戶進(jìn)程決定，調(diào)度策略和機(jī)制分離是一種關(guān)鍵性思路。

線程調(diào)度

當(dāng)若干進(jìn)程都有多個(gè)線程時(shí)，就存在兩個(gè)層次的并行：進(jìn)程和線程。在這樣的系統(tǒng)中調(diào)度處理有本質(zhì)的差別，這取決于所支持的是用戶級線程還是內(nèi)核級線程(或兩者都支持)。

首先考慮用戶級線程，由于內(nèi)核并不知道有線程存在，所以內(nèi)核還是和以前一樣地操作，選取一個(gè)進(jìn)程，假設(shè)為 A，并給予 A 以時(shí)間片控制。A 中的線程調(diào)度程序決定哪個(gè)線程運(yùn)行。假設(shè)為 A1。由于多道線程并不存在時(shí)鐘中斷，所以這個(gè)線程可以按其意愿任意運(yùn)行多長時(shí)間。如果該線程用完了進(jìn)程的全部時(shí)間片，內(nèi)核就會選擇另一個(gè)進(jìn)程繼續(xù)運(yùn)行。

在進(jìn)程 A 終于又一次運(yùn)行時(shí)，線程 A1 會接著運(yùn)行。該線程會繼續(xù)耗費(fèi) A 進(jìn)程的所有時(shí)間，直到它完成工作。不過，線程運(yùn)行不會影響到其他進(jìn)程。其他進(jìn)程會得到調(diào)度程序所分配的合適份額，不會考慮進(jìn)程 A 內(nèi)部發(fā)生的事情。

現(xiàn)在考慮 A 線程每次 CPU 計(jì)算的工作比較少的情況，例如：在 50 ms 的時(shí)間片中有 5 ms 的計(jì)算工作。于是，每個(gè)線程運(yùn)行一會兒，然后把 CPU 交回給線程調(diào)度程序。這樣在內(nèi)核切換到進(jìn)程 B 之前，就會有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。 如下所示

運(yùn)行時(shí)系統(tǒng)使用的調(diào)度算法可以是上面介紹算法的任意一種。從實(shí)用方面考慮，輪轉(zhuǎn)調(diào)度和優(yōu)先級調(diào)度更為常用。唯一的局限是，缺乏一個(gè)時(shí)鐘中斷運(yùn)行過長的線程。但由于線程之間的合作關(guān)系，這通常也不是問題。

現(xiàn)在考慮使用內(nèi)核線程的情況，內(nèi)核選擇一個(gè)特定的線程運(yùn)行。它不用考慮線程屬于哪個(gè)進(jìn)程，不過如果有必要的話，也可以這么做。對被選擇的線程賦予一個(gè)時(shí)間片，而且如果超過了時(shí)間片，就會強(qiáng)制掛起該線程。一個(gè)線程在 50 ms 的時(shí)間片內(nèi)，5 ms 之后被阻塞，在 30 ms 的時(shí)間片中，線程的順序會是 A1,B1,A2,B2,A3,B3。如下圖所示

用戶級線程和內(nèi)核級線程之間的主要差別在于性能。用戶級線程的切換需要少量的機(jī)器指令(想象一下Java程序的線程切換)，而內(nèi)核線程需要完整的上下文切換，修改內(nèi)存映像，使高速緩存失效，這會導(dǎo)致了若干數(shù)量級的延遲。另一方面，在使用內(nèi)核級線程時(shí)，一旦線程阻塞在 I/O 上就不需要在用戶級線程中那樣將整個(gè)進(jìn)程掛起。

從進(jìn)程 A 的一個(gè)線程切換到進(jìn)程 B 的一個(gè)線程，其消耗要遠(yuǎn)高于運(yùn)行進(jìn)程 A 的兩個(gè)線程(涉及修改內(nèi)存映像，修改高速緩存)，內(nèi)核對這種切換的消耗是了解到，可以通過這些信息作出決定。

后記

提出一個(gè)《機(jī)械工業(yè)出版社》的翻譯勘誤，不知道能不能看到，先提了再說，很不嚴(yán)謹(jǐn)。