在計(jì)算機(jī)系統(tǒng)中，可能同時(shí)有數(shù)百個(gè)批處理作業(yè)存放在磁盤(pán)的作業(yè)隊(duì)列中，或者有數(shù)百個(gè)終端與主機(jī)相連接。如何從這些作業(yè)中挑選作業(yè)進(jìn)入主存運(yùn)行、如何在進(jìn)程之間分配處理器時(shí)間，無(wú)疑是操作系統(tǒng)資源管理中的一個(gè)重要問(wèn)題。這一涉及處理機(jī)分配的問(wèn)題，稱之為處理機(jī)調(diào)度。
1、處理機(jī)調(diào)度的層次
處理機(jī)調(diào)度分為三個(gè)級(jí)別：
- 高級(jí)調(diào)度：又稱為作業(yè)調(diào)度，他按照系統(tǒng)的預(yù)定調(diào)度策略決定把后背隊(duì)列作業(yè)中的那些作業(yè)調(diào)入主存，并為之創(chuàng)建進(jìn)程、啟動(dòng)他們運(yùn)行，它發(fā)生在新進(jìn)程的創(chuàng)建過(guò)程中，決定了一個(gè)進(jìn)程能否被創(chuàng)建，或者創(chuàng)建后是否被指為就緒狀態(tài)。
- 中級(jí)調(diào)度：又稱為平衡負(fù)載調(diào)度，它決定了主存儲(chǔ)器中所能夠容納的進(jìn)程數(shù)，這些進(jìn)程允許參與競(jìng)爭(zhēng)處理器資源。而暫時(shí)不能運(yùn)行的進(jìn)程，則被調(diào)出主存，掛起；它根據(jù)當(dāng)前系統(tǒng)的負(fù)荷情況決定停留在主內(nèi)存中進(jìn)程數(shù)。
-
低級(jí)調(diào)度：又稱為進(jìn)程調(diào)度，按照某種原則決定就緒隊(duì)列中的那些進(jìn)程可以獲得處理器，并將處理機(jī)讓出給它進(jìn)行工作；
image.png
2、調(diào)度算法
2.1、選取原則
- 資源利用率--使得CPU或者其他資源的利用率盡可能的高且能夠并行工作
- 響應(yīng)時(shí)間--使交互式用戶的響應(yīng)時(shí)間盡可能的小，或者盡快處理實(shí)時(shí)任務(wù)
- 周轉(zhuǎn)時(shí)間---批處理用戶從作業(yè)提交給系統(tǒng)開(kāi)始到作業(yè)完成獲得結(jié)果為止的這段時(shí)間間隔稱作業(yè)周轉(zhuǎn)時(shí)間，應(yīng)該使作業(yè)周轉(zhuǎn)時(shí)間或作業(yè)平均周轉(zhuǎn)時(shí)間盡可能短。
- 吞吐量---使得單位時(shí)間處理的作業(yè)數(shù)盡可能多。
- 公平性---確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的 CPU份額或其他資源份額。
批處理系統(tǒng)的調(diào)度性能主要用作業(yè)周轉(zhuǎn)時(shí)間和作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間來(lái)衡量。如果作業(yè)i提交給系統(tǒng)的時(shí)刻是ts，完成時(shí)刻是tf，則其周轉(zhuǎn)時(shí)間為：
ti=tf-ts
即作業(yè)在系統(tǒng)中的等待時(shí)間和運(yùn)行時(shí)間之和
從操作系統(tǒng)來(lái)說(shuō)，為提高系統(tǒng)的性能，讓若干用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最?。?br> 平均作業(yè)周轉(zhuǎn)時(shí)間 T=（Σti）/n
如果作業(yè) i 的周轉(zhuǎn)時(shí)間為 ti，所需運(yùn)行時(shí)間為 tk，則稱 wi=ti/tk 為該作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間。因?yàn)椋瑃i 是等待時(shí)間與運(yùn)行時(shí)間之和，故帶權(quán)周轉(zhuǎn)時(shí)間總大于 1。
平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間 W = (Σwi) / n
通常，用平均作業(yè)周轉(zhuǎn)時(shí)間來(lái)衡量對(duì)同一作業(yè)流施行不同作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能；用平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間來(lái)衡量對(duì)不同作業(yè)流施行同一作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能。這兩個(gè)數(shù)值均越小越好。
3、批處理作業(yè)的管理與調(diào)度
多道批處理操作系統(tǒng)采用脫機(jī)控制方式，它具體獨(dú)立的作業(yè)管理模塊，為了有效管理作業(yè)，為每一個(gè)作業(yè)建立作業(yè)控制塊。每個(gè)作業(yè)的生命周期內(nèi)都順序的處于以下四個(gè)狀態(tài)：
- 輸入狀態(tài)：此時(shí)作業(yè)的信息正在從輸入設(shè)備上預(yù)輸入
- 后備狀態(tài)：此時(shí)作業(yè)預(yù)輸入結(jié)束但尚未被選中執(zhí)行
- 執(zhí)行狀態(tài)：作業(yè)已經(jīng)被選中并構(gòu)成進(jìn)程去，競(jìng)爭(zhēng)處理器資源以獲取運(yùn)行
- 完成狀態(tài)：作業(yè)以及運(yùn)行結(jié)束，正在等待緩輸出
多道批處理操作系統(tǒng)的處理機(jī)調(diào)度，至少包括作業(yè)調(diào)度和進(jìn)程調(diào)度。
3.1、 批處理作業(yè)的調(diào)度方法
對(duì)成批進(jìn)入系統(tǒng)的用戶作業(yè)，按一定的策略選取若干個(gè)作業(yè)使它們可以去獲得處理器運(yùn)行，這項(xiàng)工作稱為作業(yè)調(diào)度。
3.1.1、 先來(lái)先服務(wù)算法（FCFS ） ：
此種方法，按照作業(yè)進(jìn)入系統(tǒng)的先后順序來(lái)挑選作業(yè)，考慮了作業(yè)等待時(shí)間，而未考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短。此種不利于短作業(yè)而優(yōu)化了長(zhǎng)作業(yè)。
例如：下面三個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：
作業(yè)名 所需 CPU 時(shí)間
作業(yè)1 28
作業(yè)2 9
作業(yè)3 3
假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，現(xiàn)采用 FCFS 算法進(jìn)行:
平均作業(yè)周轉(zhuǎn)時(shí)間： T=(28+(28+9)+(28+9+3))/3=35
3.1.2、 最短作業(yè)優(yōu)先算法（SJF） ：
此種方法已進(jìn)入系統(tǒng)的作業(yè)所提出運(yùn)算的計(jì)算時(shí)間為標(biāo)準(zhǔn)，選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。它忽略了作業(yè)等待時(shí)間，且估算作業(yè)時(shí)間并不容易；
例如：下面四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：
作業(yè)名 所需 CPU 時(shí)間
作業(yè)1 9
作業(yè)2 4
作業(yè)3 10
作業(yè)4 8
假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，現(xiàn)采用 SJF 算法進(jìn)行: 此時(shí)作業(yè)調(diào)度順序?yàn)椋?2--4--1--3
平均作業(yè)周轉(zhuǎn)時(shí)間： T=(4+(4+8)+(4+8+9)+(4+8+9+10))/4=17
平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間：W=（4/4+（4+8）/8+（4+8+9）/9+（4+8+9+10）/10）/4=1.98
而采用FCFS調(diào)度算法：
平均作業(yè)周轉(zhuǎn)時(shí)間： T=(9+13+23+31)/4=19
平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間：W=（9/9+13/4+23/10+31/8）/4=2.51
對(duì)比可以看出，SJF算法較FCFS調(diào)度算法，性能較好；
3.1.3、 響應(yīng)比最高者有限算法（HRN） ：
前面兩者的調(diào)度算法都比較片面，而HRN算法使兩者的折衷算法。
響應(yīng)比=已等待時(shí)間/估計(jì)計(jì)算時(shí)間
限顯然，計(jì)算時(shí)間短的作業(yè)容易得到較高的響應(yīng)比，此算法優(yōu)待短作業(yè)
例如：下面四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：
作業(yè)名 所需 CPU 時(shí)間 到達(dá)時(shí)間
作業(yè)1 20 0
作業(yè)2 15 5
作業(yè)3 5 10
作業(yè)4 10 15
假設(shè)系統(tǒng)中沒(méi)有別的作業(yè)，現(xiàn)對(duì)實(shí)施SJF調(diào)度算法，此時(shí)作業(yè)調(diào)度順序?yàn)椋?--3--4--2
平均作業(yè)周轉(zhuǎn)時(shí)間： T=(20+15+20+45)/4=25
平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間：W=(20/20+15/5+25/10+45/15)/4=2.25
如果對(duì)它們施行 FCFS 調(diào)度算法，
平均作業(yè)周轉(zhuǎn)時(shí)間 T = (20+30+30+35)/4 = 38.75
平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間 W = (20/20+30/15+30/5+35/10)/4 = 3.13
采用HRN算法：
- 開(kāi)始只有作業(yè)1，作業(yè)1被選中，執(zhí)行時(shí)間20
- 作業(yè)1執(zhí)行完畢后，響應(yīng)比依次為15/15，10/5，5/10,作業(yè)3被選中，執(zhí)行時(shí)間為5
- 作業(yè) 3 執(zhí)行完畢后，響應(yīng)比依次為 20/15、10/10，作業(yè) 2 被選中，執(zhí)行時(shí)間 15；
- 作業(yè) 2 執(zhí)行完畢后，作業(yè) 4 被選中，執(zhí)行時(shí)間 10；
平均作業(yè)周轉(zhuǎn)時(shí)間 T = (20+15+35+35)/4 = 26.25
平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間 W = (20/20+15/5+35/15+35/10)/4 = 2.42
3.1.4、 優(yōu)先數(shù)法 ：
根據(jù)確定的優(yōu)先數(shù)來(lái)選取作業(yè)，每次總選擇優(yōu)先級(jí)高的作業(yè)。
3.1.5、分類調(diào)度算法
分類調(diào)度算法按照一定的原則將作業(yè)劃分為若干類，以達(dá)到均衡使用操作系統(tǒng)的資源和兼顧大小作業(yè)的目的。分類原則包括作業(yè)計(jì)算時(shí)間、對(duì)內(nèi)存的需求、對(duì)外圍設(shè)備的需求等。作業(yè)調(diào)度時(shí)還可以為每類作業(yè)設(shè)置優(yōu)先級(jí)，從而照顧到同類作業(yè)中的輕
重緩急。
4、進(jìn)程調(diào)度
進(jìn)程調(diào)度又稱為低級(jí)調(diào)度，其負(fù)責(zé)將處理器分配給進(jìn)程 。
- 記錄進(jìn)程的狀態(tài)
- 記錄某個(gè)進(jìn)程什么時(shí)候獲取處理器，以及占用多長(zhǎng)時(shí)間
- 把處理器分配給進(jìn)程
- 收回處理器
4.1、進(jìn)程調(diào)度算法
先來(lái)先服務(wù)算法
時(shí)間片輪轉(zhuǎn)算法：又稱為時(shí)間片調(diào)度。具體做法是調(diào)度程序每次把 CPU 分配給就緒隊(duì)列首進(jìn)程使用一個(gè)時(shí)間片，例100ms，就緒隊(duì)列中的每個(gè)進(jìn)程輪流地運(yùn)行一個(gè)這樣的時(shí)間片。當(dāng)這個(gè)時(shí)間片結(jié)束時(shí)，就強(qiáng)迫一個(gè)進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪調(diào)度。實(shí)現(xiàn)這種調(diào)度要使用一個(gè)間隔時(shí)鐘，例如，當(dāng)一個(gè)進(jìn)程開(kāi)始運(yùn)行時(shí)，就將時(shí)間片的值置入間隔時(shí)鐘內(nèi)，當(dāng)發(fā)生間隔時(shí)鐘中斷時(shí)，就表明該進(jìn)程連續(xù)運(yùn)行的時(shí)間已超過(guò)一個(gè)規(guī)定的時(shí)間片。此時(shí)，中斷處理程序就通知處理器調(diào)度進(jìn)行處理器的轉(zhuǎn)換工作。這種調(diào)度策略可以防止那些很少使用外圍設(shè)備的進(jìn)程過(guò)長(zhǎng)的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒(méi)有機(jī)會(huì)去啟動(dòng)外圍設(shè)備。
優(yōu)先權(quán)調(diào)度，每個(gè)進(jìn)程給出一個(gè)優(yōu)先數(shù)，調(diào)度每次選擇就緒進(jìn)程中優(yōu)先數(shù)最大者，讓它占用處理器運(yùn)行。
-
多級(jí)反饋隊(duì)列調(diào)度，又稱之為反饋循環(huán)隊(duì)列。其主要思想是將就緒進(jìn)程分為兩級(jí)或多級(jí)，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，較高優(yōu)先級(jí)的隊(duì)列一般分配給較短的時(shí)間片。處理器調(diào)度每次先從高級(jí)的就緒進(jìn)程隊(duì)列中選取可占有處理器的進(jìn)程，只有在選不到時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選取image.png
保證調(diào)度算法，一種完全不同的調(diào)度算法是向用戶做出明確的性能保證，然后去實(shí)現(xiàn)它。為了實(shí)現(xiàn)所作的保證，系統(tǒng)必須跟蹤各個(gè)進(jìn)程自創(chuàng)建以來(lái)已經(jīng)使用了多少 CPU 時(shí)間。然后它計(jì)算各個(gè)進(jìn)程應(yīng)獲得的 CPU 時(shí)間，即自創(chuàng)建以來(lái)的時(shí)間除以 n。由于各個(gè)進(jìn)程實(shí)際獲得的 CPU 時(shí)間已知，所以很容易計(jì)算出實(shí)際獲得的 CPU 時(shí)間和應(yīng)獲得的CPU 時(shí)間之比，于是調(diào)度將轉(zhuǎn)向比率最低的進(jìn)程。
彩票調(diào)度算法，為進(jìn)程發(fā)放針對(duì)系統(tǒng)各種資源（如 CPU 時(shí)間）的彩票。當(dāng)調(diào)度程序需要做出決策時(shí)，隨機(jī)選擇一張彩票，持有該彩票的進(jìn)程將獲得系統(tǒng)資源。對(duì)于 CPU調(diào)度，系統(tǒng)可能每秒鐘抽 50 次彩票，每次中獎(jiǎng)?wù)呖梢垣@得 20ms 的運(yùn)行時(shí)間。
4.2、 分時(shí)調(diào)度
實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。通常分為硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。前這意味著存在必須滿足的時(shí)間限制，后則意味著偶爾超過(guò)時(shí)間限制可以容忍的。
5、多處理器的調(diào)度算法
大量的實(shí)驗(yàn)數(shù)據(jù)證明，隨著處理器數(shù)目的增多，復(fù)雜進(jìn)程調(diào)度算法的有效性卻逐步下降。因此在大多數(shù)采取動(dòng)態(tài)分配策略的多處理器系統(tǒng)中，進(jìn)程調(diào)度算法往往采用最簡(jiǎn)單的先來(lái)先服務(wù)算法或優(yōu)先數(shù)算法，就緒進(jìn)程組成一個(gè)隊(duì)列或多個(gè)按照優(yōu)先數(shù)排列的隊(duì)列。
多處理器調(diào)度算法主要研究線程調(diào)度算法
5.1、均分負(fù)載調(diào)度算法
均分負(fù)載（load sharing）調(diào)度算法的基本思想是：進(jìn)程并不分配給一個(gè)處理器，系統(tǒng)維護(hù)一個(gè)就緒線程隊(duì)列，當(dāng)一個(gè)處理器空閑時(shí)，就選擇一個(gè)就緒線程占有處理器運(yùn)行。這一算法有如下優(yōu)點(diǎn)：
- 把負(fù)載均分到所有的可用處理器上，保證了處理器效率的提高。
- 不需要一個(gè)集中的調(diào)度程序，一旦一個(gè)處理器空閑，操作系統(tǒng)的調(diào)度程序就可以運(yùn)行在該處理器上以選擇下一個(gè)運(yùn)行的線程。
- 運(yùn)行線程的選擇可以采用各種可行的策略（雷同與前面介紹的各種進(jìn)程調(diào)度算法）。
這一算法也有一些不足：
- 就緒線程隊(duì)列必須被互斥訪問(wèn)，當(dāng)系統(tǒng)包括很多處理器，并且同時(shí)有多個(gè)處理器同時(shí)挑選運(yùn)行線程時(shí)，它將成為性能的瓶頸。
- 被搶占的線程很難在同一個(gè)處理器上恢復(fù)運(yùn)行，因此當(dāng)處理器帶有高速緩存時(shí)，恢復(fù)高速緩存的信息會(huì)帶來(lái)性能的下降。
- 如果所有的線程都被放在一個(gè)公共的線程池中的話，所有的線程獲得處理器的機(jī)會(huì)是相同的。如果一個(gè)程序的線程希望獲得較高的優(yōu)先級(jí)，進(jìn)程切換將導(dǎo)致性能的折衷。
5.2、群調(diào)度
群調(diào)度（gang scheduling）算法的基本思想是：把一組相關(guān)的線程在同一時(shí)間一次性調(diào)度到一組處理器上運(yùn)行
