第九章 单处理器调度
在多道程序設(shè)計(jì)系統(tǒng)中，內(nèi)存中有多個(gè)進(jìn)程。每個(gè)進(jìn)程或者正在處理器上運(yùn)行，或者正在等待某些事件的發(fā)生，比如IO完成。處理器通過執(zhí)行某個(gè)進(jìn)程而保持忙狀態(tài)，而此時(shí)其他進(jìn)程處于等待狀態(tài)。
一、處理器調(diào)度的類型
處理器調(diào)度的目標(biāo)是以滿足系統(tǒng)目標(biāo)（如響應(yīng)時(shí)間、吞吐率、處理器小雷）的方式，把進(jìn)程分配到一個(gè)或多個(gè)處理器中執(zhí)行。
在許多系統(tǒng)中，這個(gè)調(diào)度活動(dòng)分成三個(gè)獨(dú)立功能：長(zhǎng)程、中程和短程調(diào)度。他們的名字表明在執(zhí)行這些功能時(shí)的相對(duì)時(shí)間比例。
創(chuàng)建新進(jìn)程時(shí)，執(zhí)行長(zhǎng)程調(diào)度，它決定是否把進(jìn)程添加到當(dāng)前活躍的進(jìn)程集合中。
中程調(diào)度是交換功能的一部分，它決定是否把進(jìn)程加到那些至少部分在內(nèi)存中并且可以被執(zhí)行的進(jìn)程集合中。
短程調(diào)度真正決定下一次執(zhí)行哪一個(gè)就緒進(jìn)程。
從根本上說，調(diào)度屬于隊(duì)列管理方面的問題，用來在排隊(duì)環(huán)境中減少延遲和優(yōu)化性能。
1 長(zhǎng)程調(diào)度
長(zhǎng)程調(diào)度決定哪一個(gè)程序可以進(jìn)入系統(tǒng)中處理，因此，它控制著系統(tǒng)的并發(fā)度。一旦允許進(jìn)入，一個(gè)作業(yè)或用戶程序就成為一個(gè)進(jìn)程，并被添加到供短程調(diào)度程序使用的隊(duì)列中等待調(diào)度。在某些系統(tǒng)中，一個(gè)新創(chuàng)建的進(jìn)程開始處于被換出狀態(tài)，在這種情況下，它被添加到供中程調(diào)度程序使用的隊(duì)列中等待調(diào)度。
在批處理系統(tǒng)或者操作系統(tǒng)的批處理部分中，新提交的作業(yè)被發(fā)送到磁盤，并保存在一個(gè)批處理隊(duì)列中。在長(zhǎng)程調(diào)度程序運(yùn)行的時(shí)候，從隊(duì)列中創(chuàng)建相應(yīng)的進(jìn)程。這里涉及兩個(gè)決策：調(diào)度程序必須決定什么時(shí)候操作系統(tǒng)能夠接納一個(gè)進(jìn)程或者多個(gè)進(jìn)程；同時(shí)，調(diào)度程序必須決定接受哪個(gè)作業(yè)或哪些作業(yè)，并將其轉(zhuǎn)變成進(jìn)程。
2 中程調(diào)度
中程調(diào)度時(shí)交換功能的一部分。在典型情況下，換入決定取決于管理系統(tǒng)并發(fā)度的需求。
3 短程調(diào)度
考慮執(zhí)行的頻繁程度，長(zhǎng)程調(diào)度程序執(zhí)行的頻率相對(duì)較低，并且僅僅是粗略地決定是否接受新進(jìn)程及接受哪一個(gè)。為進(jìn)行交換決定，中程調(diào)度程序執(zhí)行得略微頻繁一些。
短程調(diào)度程序，也稱為分派（dispatcher）程序，執(zhí)行的最頻繁，并且精確地決定下一次執(zhí)行哪一個(gè)進(jìn)程。
二、調(diào)度算法
1 短程調(diào)度準(zhǔn)則
短程調(diào)度的主要目標(biāo)是按照優(yōu)化系統(tǒng)一個(gè)或多個(gè)方面行為的方式來分配處理器時(shí)間。通常使用的準(zhǔn)則可以按兩個(gè)維度來分類：面向用戶的準(zhǔn)則與單個(gè)用戶或進(jìn)程感知到的系統(tǒng)行為相關(guān)；面向系統(tǒng)的準(zhǔn)則的重點(diǎn)是處理器使用效果和效率（比如吞吐量，也就是進(jìn)程的完成的速度）。
面向用戶的準(zhǔn)則：響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間（周轉(zhuǎn)時(shí)間 = 完成時(shí)間 - 到達(dá)時(shí)間）
面向系統(tǒng)的準(zhǔn)則：吞吐量、處理器利用率
設(shè)計(jì)一個(gè)調(diào)度策略涉及在互相競(jìng)爭(zhēng)的各種要求之間進(jìn)行折中，根據(jù)系統(tǒng)的本質(zhì)和使用情況，給各種要求設(shè)定相應(yīng)的權(quán)值。
2 優(yōu)先級(jí)的使用
在許多系統(tǒng)中，每個(gè)進(jìn)程都被指定一個(gè)優(yōu)先級(jí)，調(diào)度程序總是有些選擇具有較高優(yōu)先級(jí)的進(jìn)程。
3 選擇調(diào)度策略
選擇函數(shù)確定在就緒進(jìn)程中選擇哪一個(gè)進(jìn)程在下一次執(zhí)行。
決策模式說明選擇函數(shù)在被執(zhí)行的瞬間的處理方式，通常可分為以下兩類：
- 非搶占。在這種情況下，一旦進(jìn)程出于運(yùn)行狀態(tài)，它就不斷執(zhí)行直到終止，或者因?yàn)榈却齀O，或者因?yàn)檎?qǐng)求某些操作系統(tǒng)服務(wù)，而阻塞自己。
- 搶占。當(dāng)前正中運(yùn)行的進(jìn)程可能被操作系統(tǒng)中斷，并轉(zhuǎn)移到就緒態(tài)。關(guān)于搶占的決策可能是在一個(gè)新進(jìn)程到達(dá)時(shí)，或者在一個(gè)中斷發(fā)生后，把一個(gè)被阻塞的進(jìn)程職位就緒態(tài)時(shí)，或者出現(xiàn)基于周期性的時(shí)間中斷時(shí)。
與非搶占策略相比，搶占策略可能會(huì)導(dǎo)致較大的開銷，但是可能會(huì)對(duì)所有進(jìn)程提供較好的服務(wù)，因?yàn)樗鼈儽苊饬巳魏我粋€(gè)進(jìn)程獨(dú)占處理器太長(zhǎng)時(shí)間。此外，通過使用有效的進(jìn)程切換機(jī)制，以及提供較大的內(nèi)存，使得大部分程序都在內(nèi)存中，可使搶占的代價(jià)相對(duì)比較低。
- 周轉(zhuǎn)時(shí)間：就是駐留時(shí)間，或者這一項(xiàng)在系統(tǒng)中花費(fèi)的總時(shí)間。
- 歸一化周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間與服務(wù)時(shí)間的比率，該值表示一個(gè)進(jìn)程的相對(duì)延遲。
1）先來先服務(wù)（FCFS）：當(dāng)美國(guó)進(jìn)程就緒后，它就入就緒隊(duì)列。當(dāng)前正在運(yùn)行的進(jìn)程停止執(zhí)行時(shí)，選擇在就緒隊(duì)列中存在時(shí)間最長(zhǎng)的進(jìn)程運(yùn)行。
2）輪轉(zhuǎn)：一種簡(jiǎn)單的方法是采用使用基于時(shí)鐘的搶占策略，在這類方法中，最簡(jiǎn)單的是輪轉(zhuǎn)算法。以一個(gè)周期性間隔產(chǎn)生時(shí)鐘中斷，當(dāng)中斷發(fā)送時(shí)，當(dāng)前正在運(yùn)行的進(jìn)程被置于就緒隊(duì)列中，然后基于FCFS策略選擇下一個(gè)就緒作業(yè)運(yùn)行。這種技術(shù)也稱為時(shí)間片，因?yàn)槊總€(gè)進(jìn)程在被搶占前都給定一片時(shí)間。
3）最短進(jìn)程優(yōu)先：這是一個(gè)非搶占的策略，其原則是下一次選擇預(yù)計(jì)處理時(shí)間最短的進(jìn)程。因此，短進(jìn)程將會(huì)越過長(zhǎng)進(jìn)程，跳到隊(duì)列頭。
4）最短剩余時(shí)間：調(diào)度程序總是選擇預(yù)期剩余時(shí)間最短的進(jìn)程。當(dāng)一個(gè)新進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間，因此，只要新進(jìn)程就緒，調(diào)度程序就可能搶占當(dāng)前正在運(yùn)行的進(jìn)程。
5）最高響應(yīng)比優(yōu)先：響應(yīng)比=（等待處理器的時(shí)間+預(yù)計(jì)的服務(wù)時(shí)間）/預(yù)計(jì)的服務(wù)時(shí)間
6）反饋法：建立一組調(diào)度隊(duì)列，基于每個(gè)進(jìn)程的執(zhí)行歷史和其他一些準(zhǔn)則，把他們分配到各個(gè)隊(duì)列中。
4 公平共享調(diào)度
如果當(dāng)用戶的應(yīng)用程序或作業(yè)可以組成多個(gè)進(jìn)程（或線程），就會(huì)出現(xiàn)傳統(tǒng)的調(diào)度程序不認(rèn)識(shí)的進(jìn)程集合結(jié)構(gòu)。從用戶的角度看，他所關(guān)心的不是某個(gè)特定的進(jìn)程如何執(zhí)行，而是構(gòu)成應(yīng)用程序的一組進(jìn)程如何執(zhí)行。因此，基于進(jìn)程組的調(diào)度策略是非常具有吸引力的，該方法通常稱為公平共享調(diào)度。
術(shù)語“公平共享”表明了這類調(diào)度程序的基本原則。每個(gè)用戶被指定了某種類型的權(quán)值，該權(quán)值定義了該用戶對(duì)系統(tǒng)資源的共享，而且是作為在所有使用的資源中所占的比例來體現(xiàn)的。
5.進(jìn)程調(diào)度算法的實(shí)例
進(jìn)程調(diào)度方式有兩種：
非搶占方式
- 分配 CPU 后，進(jìn)程一直運(yùn)行到完成或異常終止
- 簡(jiǎn)單、系統(tǒng)開銷小
- 批處理系統(tǒng)
搶占方式
- 系統(tǒng)根據(jù)某種策略（搶占原則）收回正在運(yùn)行進(jìn)程的 CPU ，調(diào)度其它就緒進(jìn)程運(yùn)行
- 及時(shí)響應(yīng)各進(jìn)程的需求
- 分時(shí)/實(shí)時(shí)系統(tǒng)
搶占原則：
- 時(shí)間片原則（時(shí)間片用完）
- 優(yōu)先級(jí)原則（更高優(yōu)先級(jí)進(jìn)程就緒）
- 短進(jìn)程優(yōu)先原則（更短進(jìn)程就緒）
（1）先來先服務(wù)FCFS
FCFS 算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。（非搶占調(diào)度）
FCFS 的優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單。
FCFS 的缺點(diǎn)：沒有考慮進(jìn)程的優(yōu)先級(jí)，平均等待時(shí)間波動(dòng)較大，短進(jìn)程可能排在長(zhǎng)進(jìn)程后面，I/O 資源和 CPU 資源利用率低。
FCFS 有利于長(zhǎng)作業(yè)（進(jìn)程）
（2）時(shí)間片輪轉(zhuǎn)RR
RR 用于分時(shí)系統(tǒng)進(jìn)程調(diào)度，其步驟如下：
1.就緒進(jìn)程按照 FCFS 原則排成一個(gè)就緒隊(duì)列
2.調(diào)度隊(duì)首進(jìn)程，執(zhí)行一個(gè)時(shí)間片
3.在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷
4.調(diào)度程序暫停當(dāng)前進(jìn)程的執(zhí)行，并送就緒隊(duì)列尾
5.通過 CPU 現(xiàn)場(chǎng)切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程
這里的時(shí)間片 q = 1
RR 的優(yōu)點(diǎn)：就緒隊(duì)列中的所有進(jìn)程都會(huì)有機(jī)會(huì)獲得處理器運(yùn)行；可提高進(jìn)程并發(fā)性和資源利用率；縮短響應(yīng)時(shí)間。
RR 的缺點(diǎn)：時(shí)間片的長(zhǎng)度影響系統(tǒng)開銷和響應(yīng)時(shí)間。
時(shí)間片過短，則調(diào)度程序剝奪處理機(jī)的次數(shù)增多，增加進(jìn)程上下文交換次數(shù)，加重了系統(tǒng)開銷（時(shí)間片短，有利于短作業(yè)，不利于長(zhǎng)作業(yè)）；
時(shí)間片過長(zhǎng)，大到進(jìn)程能完成全部運(yùn)行作業(yè)所需的時(shí)間，那么時(shí)間片輪轉(zhuǎn)法就退化為 FCFS （長(zhǎng)時(shí)間片，無法滿足交互式用戶需求）。
最佳時(shí)間片，長(zhǎng)度略大于一次典型交互所需的時(shí)間（響應(yīng)時(shí)間= 進(jìn)程數(shù)目 × 時(shí)間片大小）
（3）最短進(jìn)程優(yōu)先SPN
SPN 算法從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，為之分配處理機(jī)，如果運(yùn)行時(shí)間相同，按 FCFS 調(diào)度。
SPN 算法有搶占方式和非搶占方式兩種：
最短進(jìn)程優(yōu)先SPN（非搶占）
最短剩余時(shí)間優(yōu)先SRT（搶占）
SPN 的優(yōu)點(diǎn)：能有效地降低平均等待時(shí)間，提高系統(tǒng)的吞吐量（平均周轉(zhuǎn)時(shí)間最短），有利于短作業(yè)。
SPN 的缺點(diǎn)：不利于長(zhǎng)作業(yè)當(dāng)短作業(yè)持續(xù)不斷到達(dá)時(shí)，長(zhǎng)作業(yè)可能被餓死。無法準(zhǔn)確估計(jì)作業(yè)的的確切執(zhí)行時(shí)間，不一定能真正做到短作業(yè)（進(jìn)程）優(yōu)先調(diào)度。
（4）最短剩余時(shí)間優(yōu)先SRT
SRT 是對(duì) SPN 的改進(jìn)，采用了搶占機(jī)制，根據(jù)就緒隊(duì)列里進(jìn)程剩余需要服務(wù)的時(shí)間來排隊(duì)。剩余時(shí)間越短的排在最前面。因?yàn)樾枰ビ涗涍M(jìn)程的剩余服務(wù)時(shí)間，所以增加了系統(tǒng)的開銷。
SRT 的優(yōu)點(diǎn)：比 SPN 的性能更好，短作業(yè)只要就緒就可以搶占正在執(zhí)行長(zhǎng)進(jìn)程的 CPU。
SRT 的缺點(diǎn)：增加了額外開銷，長(zhǎng)作業(yè)（進(jìn)程）可能會(huì)被餓死。
（5）最高相應(yīng)比優(yōu)先HRRN
為了防止長(zhǎng)作業(yè)（進(jìn)程）被餓死，選擇最高相應(yīng)比優(yōu)先算法。
響應(yīng)比 = 周轉(zhuǎn)時(shí)間 / 運(yùn)行時(shí)間 = （運(yùn)行時(shí)間 + 等待時(shí)間 ）/ 運(yùn)行時(shí)間 = 1 + 等待時(shí)間 / 運(yùn)行時(shí)間
HRRN 的優(yōu)點(diǎn)：對(duì)短作業(yè)有利（運(yùn)行時(shí)間越短優(yōu)先級(jí)越高），長(zhǎng)作業(yè)不會(huì)被餓死（運(yùn)行時(shí)間相同時(shí)，等待時(shí)間越長(zhǎng)優(yōu)先級(jí)越高）
HRRN 的缺點(diǎn)：增加了系統(tǒng)的開銷（每次重新調(diào)度需要估計(jì)運(yùn)行時(shí)間，并計(jì)算響應(yīng)比）
（6）反饋法
多級(jí)隊(duì)列調(diào)度：
根據(jù)進(jìn)程屬性設(shè)置多個(gè)就緒隊(duì)列，每個(gè)就緒隊(duì)列有各自的調(diào)度算法、優(yōu)先級(jí)或時(shí)間片長(zhǎng)度
前臺(tái)（或交互式）RR
后臺(tái)（或批處理）FCFS
隊(duì)列之間必須有調(diào)度
通常采用固定優(yōu)先級(jí)可搶占調(diào)度
另一種可能是在隊(duì)列之間劃分時(shí)間片。每個(gè)隊(duì)列都有一定的 CPU 時(shí)間
多級(jí)反饋隊(duì)列：
基于多級(jí)隊(duì)列調(diào)度（多個(gè)隊(duì)列，不同優(yōu)先級(jí)，不同時(shí)間片長(zhǎng)度，不同調(diào)度算法）
進(jìn)程可以在不同隊(duì)列間移動(dòng)
可搶占調(diào)度
最通用和最復(fù)雜的 CPU 調(diào)度算法
多級(jí)反饋隊(duì)列調(diào)度的優(yōu)點(diǎn)：
a.短進(jìn)程出現(xiàn)在優(yōu)先級(jí)高的隊(duì)列中，可提高系統(tǒng)吞吐量、縮短平均周轉(zhuǎn)時(shí)間
b.I/O 密集型進(jìn)程放在最高優(yōu)先級(jí)隊(duì)列，保證及時(shí) I/O 交互，提高 I/O 設(shè)備利用率、縮短響應(yīng)時(shí)間
c.不必事先估計(jì)進(jìn)程執(zhí)行時(shí)間，可以在進(jìn)程中動(dòng)態(tài)調(diào)節(jié)
6.多種調(diào)度算法的比較
三、傳統(tǒng)的UNIX調(diào)度
傳統(tǒng)的UNIX調(diào)度程序采用了多級(jí)反饋，而在每個(gè)優(yōu)先級(jí)隊(duì)列中采用了輪轉(zhuǎn)的方法。該系統(tǒng)使用1秒搶占方式，也就是說，如果一個(gè)正在運(yùn)行的進(jìn)程在1秒內(nèi)未被阻塞或者完成，它將被搶占。優(yōu)先級(jí)基于進(jìn)程類型和執(zhí)行歷史。
四 、小結(jié)
操作系統(tǒng)根據(jù)進(jìn)程的執(zhí)行對(duì)三種類型的調(diào)度方案作出選擇。長(zhǎng)程調(diào)度決定何時(shí)允許一個(gè)新進(jìn)程進(jìn)入系統(tǒng)。中程調(diào)度是交換功能的一部分，它決定何時(shí)把一個(gè)程序的部分或全部取進(jìn)內(nèi)存，使得該程序能夠被執(zhí)行。短程調(diào)度決定哪一個(gè)就緒進(jìn)程下一次被處理器執(zhí)行。本章集中討論與短程調(diào)度相關(guān)的問題。
在設(shè)計(jì)短程調(diào)度程序時(shí)使用了各種各樣的準(zhǔn)則。一些準(zhǔn)則與單個(gè)用戶察覺到的系統(tǒng)行為有關(guān)（面向用戶），而其他準(zhǔn)則查看系統(tǒng)在滿足所有用戶的需求時(shí)的總效率（面向系統(tǒng)）。一些準(zhǔn)則與性能的定量度量有關(guān)，另一些在本質(zhì)上是定性的。從用戶角度看，相應(yīng)時(shí)間通常是系統(tǒng)最重要的一個(gè)特性；從系統(tǒng)的角度看，吞吐量或處理器利用率是最重要的。
版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。
轉(zhuǎn)載于:https://www.cnblogs.com/yangquanhui/p/4937487.html
總結(jié)
以上是生活随笔為你收集整理的第九章 单处理器调度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： seasar 2
- 下一篇： 《Programming WPF》翻译