U調(diào)度：

即按照一定的的調(diào)度算法從就緒隊列中選擇進(jìn)程，把CPU使用權(quán)交給被選中進(jìn)程。

如果沒有就緒隊列中沒有進(jìn)程，系統(tǒng)會安排一個系統(tǒng)空閑進(jìn)程（即什么也不做）或idle進(jìn)程，目的就是讓CPU不空閑

系統(tǒng)場景：

N（N>=1）個進(jìn)程處于就緒隊列中，M（M>=1）個CPU給哪個進(jìn)程分配哪個CPU？怎么分配？（調(diào)度算法），什么時候分配？（調(diào)度時機(jī)），怎么讓進(jìn)程上CPU？（調(diào)度過程，涉及到上下文的保存）

調(diào)度時機(jī)：

進(jìn)程正常終止 或 由于某種錯誤而終止

新進(jìn)程創(chuàng)建 或 一個等待進(jìn)程變成就緒

當(dāng)一個進(jìn)程從運行態(tài)進(jìn)入阻塞態(tài)

當(dāng)一個進(jìn)程從運行態(tài)變?yōu)榫途w態(tài)

前兩種是CPU上有進(jìn)程，后兩種是CPU上沒有進(jìn)程執(zhí)行時發(fā)生調(diào)度

總之往往是內(nèi)核對中斷/異常/系統(tǒng)調(diào)用處理后返回到用戶態(tài)時發(fā)生調(diào)度。

調(diào)度過程：

進(jìn)程切換：是指一個進(jìn)程讓出處理器，由另一個進(jìn)程占用處理器的過程

進(jìn)程切換主要包括兩部分工作： 1.切換全局頁目錄以加載一個新的地址空間 2.切換內(nèi)核棧（因為進(jìn)程地址空間發(fā)生變化）和硬件上下文，其中硬件上下文包括了內(nèi)核執(zhí)行新進(jìn)程需要的全部信息，如CPU相關(guān)寄存器

總之切換過程包括了對原來運行進(jìn)程各種狀態(tài)的保存和對新的進(jìn)程各種狀態(tài)的恢復(fù)

例如：

進(jìn)程A下CPU，進(jìn)程B上CPU

此時上下文保存的具體步驟為：

1.保存進(jìn)程A的上下文環(huán)境（程序計數(shù)器、程序狀態(tài)字、其他寄存器……） 2.用新狀態(tài)和其他相關(guān)信息更新進(jìn)程A的PCB 3.把進(jìn)程A移至合適的隊列（就緒、阻塞……） 4.將進(jìn)程B的狀態(tài)設(shè)置為運行態(tài) 5.從進(jìn)程B的PCB中恢復(fù)上下文（程序計數(shù)器 、程序狀態(tài)字、其他寄存器……）

但是頻繁進(jìn)程切換就會涉及到上下文切換的開銷：

直接開銷：

1.保存和恢復(fù)寄存器

2.切換進(jìn)程地址空間

間接開銷：

cache失效，緩沖區(qū)的緩存失效，TLB失效

調(diào)度算法：

?

以此為設(shè)計算法的出發(fā)點。

調(diào)度算法衡量指標(biāo)：

吞吐量 Throughput: 每單位時間完成的進(jìn)程數(shù)目

周轉(zhuǎn)時間TT(Turnaround Time)：每個進(jìn)程從提出請求到運行完成的時間

響應(yīng)時間RT(Response Time)：從提出請求到第一次回應(yīng)的時間

CPU 利用率(CPU Utilization)：CPU做有效工作的時間比例

等待時間(Waiting time)：每個進(jìn)程在就緒隊列(ready queue)中等待的時間

調(diào)度算法要點：

進(jìn)程優(yōu)先數(shù)與優(yōu)先級并不成正相關(guān):基本上優(yōu)先數(shù)越小優(yōu)先級越大

進(jìn)程優(yōu)先級可以分成靜態(tài)和動態(tài)的：

1.靜態(tài)優(yōu)先級：進(jìn)程創(chuàng)建時指定，運行過程中不再改變 2.動態(tài)優(yōu)先級：進(jìn)程創(chuàng)建時指定了一個優(yōu)先級，運行過程中可以動態(tài)變化

如：等待時間較長的進(jìn)程可提升其優(yōu)先級（windows中對饑餓線程的做法）

根據(jù)不同的優(yōu)先級就設(shè)計不同就緒隊列的組織方式：

?

就緒隊列從上到下優(yōu)先級（靜態(tài)，從創(chuàng)建就分配好了進(jìn)入對應(yīng)的就緒隊列中）逐漸降低，每次操作系統(tǒng)從就緒隊列1中選擇進(jìn)程上CPU，若隊列1位空則選擇下一級隊列中進(jìn)程，以此類推。

?

從上到下進(jìn)程優(yōu)先級也是逐漸降低，但是進(jìn)程一創(chuàng)建就進(jìn)入高優(yōu)先級的就緒隊列1，但是隨著進(jìn)程不斷地用完分配給它的時間片，他的優(yōu)先級會動態(tài)地降低（Unix BSD系統(tǒng)）

進(jìn)程搶占與非搶占：

可搶占式Preemptive（可剝奪式） 當(dāng)有比正在運行的進(jìn)程優(yōu)先級更高的進(jìn)程就緒時，系統(tǒng)可強(qiáng)行剝奪正在運行進(jìn)程的CPU，提供給具有更高優(yōu)先級的進(jìn)程使用

不可搶占式Non-preemptive（不可剝奪式 ） 某一進(jìn)程被調(diào)度運行后，除非由于它自身終止，否則一直運行下去

I/O密集型與CPU密集型：

I/O密集型：進(jìn)程大量時間都是用在等待I/O設(shè)備上

?

?

CPU密集型：需要大量的CPU時間來進(jìn)行計算

?

?

時間片：分配給調(diào)度上CPU的進(jìn)程，確定了允許該進(jìn)程運行的時間長度

調(diào)度算法：

批處理的調(diào)度算法：

先來先服務(wù)(First Come First Serve):

思想：按照進(jìn)程就緒的先后順序使用CPU（非搶占式）

優(yōu)缺點：公平，易實現(xiàn)，但是對于運行時間長的進(jìn)程后面的短進(jìn)程不利

例子：

三個進(jìn)程按順序就緒：P1、P2、P3，進(jìn)程P1執(zhí)行需要24s，P2和P3各需要3s

FCFS算法：　　

?
?

吞吐量：3 jobs/ 30s = 0.1 jobs/s

周轉(zhuǎn)時間TT（從提交到運行完成時間）：P1:24；P2:27；P3:30

平均周轉(zhuǎn)時間：（24+27+30）/ 3 = 27s

但是不同的順序狀態(tài)會影響周轉(zhuǎn)時間

按照P2,P3,P1就緒的話：

?

?

吞吐量：3 jobs/ 30s = 0.1 jobs/s

周轉(zhuǎn)時間TT：P1:30；P2:3；P3:6；

平均周轉(zhuǎn)時間：13s

?

短作業(yè)優(yōu)先（Shortest Job First）：

思想：具有最短完成時間的進(jìn)程優(yōu)先執(zhí)行（非搶占式）

最短剩余時間優(yōu)先（Shortest Remaining Time Next）：

思想：（SJF搶占版）當(dāng)一個新就緒的進(jìn)程比當(dāng)前運行進(jìn)程具有更短的完成時間時，新就緒進(jìn)程會搶占CPU執(zhí)行

例子：

對于非搶占式短作業(yè)優(yōu)先：

首先0時刻，P1先進(jìn)入，所以P1先執(zhí)行，之后P2,P3,P4都會進(jìn)入，但由于不是搶占式，所以就在就緒隊列中等待，之后P1執(zhí)行完成，從就緒隊列中選擇運行時間短的P3上CPU執(zhí)行，之后又按到達(dá)先后，選擇P2,P4執(zhí)行

對于搶占式短作業(yè)優(yōu)先：

首先0時刻，P1進(jìn)入，所以P1先執(zhí)行，但是到了2時刻時，就緒隊列中進(jìn)來P2，它的完成時間為4小于P1完成時間的5，所以CPU被搶占，P2執(zhí)行，但是到了4時刻時，P3進(jìn)入就緒隊列，P3完成時間1小于P2完成時間2，所以CPU被搶占，P3執(zhí)行，之后P4進(jìn)入就緒隊列，此時P3也執(zhí)行完畢，從就緒隊列中選擇完成時間最短的上CPU，選擇P2，剩余2運行時間，等到P2執(zhí)行完時，P4完成時間4小于P1完成時間5，所以P4上CPU，之后P5上CPU

優(yōu)缺點 1.最短的平均周轉(zhuǎn)時間 2.但是當(dāng)短任務(wù)很多時，可能使長的任務(wù)長時間得不到運行最終產(chǎn)生 “饑餓”現(xiàn)象 (starvation)

最高相應(yīng)優(yōu)先比（Highest Response Ratio Next）

設(shè)計思想：

調(diào)度時，首先計算每個進(jìn)程的響應(yīng)比R之后，總是選擇 R 最高的進(jìn)程執(zhí)行

響應(yīng)比R = 周轉(zhuǎn)時間 / 處理時間 =（處理時間 + 等待時間）/ 處理時間 = 1 +（等待時間 / 處理時間）PS：處理時間（完成所需時間），等待時間（在就緒隊列中等待的時間）

隨著等待時間的增加，R會增大從而有更大機(jī)會上CPU

缺點：每次都需計算R值開銷較大

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

時間片輪轉(zhuǎn)調(diào)度：

目標(biāo)：改善短進(jìn)程的平均響應(yīng)時間

解決問題的思路 1.周期性切換 2.每個進(jìn)程分配一個時間片 3.時間片用完產(chǎn)生時鐘中斷從而達(dá)到輪換

?

?
?

當(dāng)B進(jìn)程用完時間片后（此時B進(jìn)程可能還沒有完全執(zhí)行完），B進(jìn)程從運行態(tài)到就緒態(tài)，并將對應(yīng)的PCB插到就緒狀態(tài)隊列隊尾位置

?

時間片大小的確定：

?

?

太長 --大于典型的交互時間 1.降級為先來先服務(wù)算法 2.延長短進(jìn)程的響應(yīng)時間

若太長，那么每個進(jìn)程就完全被執(zhí)行完成，接著換下一個進(jìn)程，這就退化成了FCFS算法，同時因為降為FCFS導(dǎo)致短進(jìn)程若排在長進(jìn)程之后，其響應(yīng)時間將增長。

?

太短 --小于典型的交互時間

1.進(jìn)程切換浪費CPU時間

太短，那么大部分CPU時間將浪費在調(diào)度上

優(yōu)缺點

公平

有利于交互式計算，響應(yīng)時間快

由于進(jìn)程切換，時間片輪轉(zhuǎn)算法要花費較高的開銷

RR對不同大小的進(jìn)程是有利的，但是對于相同大小的進(jìn)程反而不利

例如：

1.兩個進(jìn)程A、B，運行時間均為100ms （1）時間片大小為1ms （2）上下文切換不耗時

如果使用時間片輪轉(zhuǎn)（RR）算法的平均周轉(zhuǎn)時間？

ABABABAB…… …… …… ……A(199)B(200)

A周轉(zhuǎn)時間為199ms B周轉(zhuǎn)時間為200ms 平均周轉(zhuǎn)時間為199.5ms

使用先來先服務(wù)（FCFS）算法呢？

A周轉(zhuǎn)時間為100ms，B周轉(zhuǎn)時間為等待A完成100 + 自己運行時間100 = 200ms，平均周轉(zhuǎn)時間為150ms

虛擬輪轉(zhuǎn)調(diào)度算法：

?

?

對于I/O密集型進(jìn)程來講，可能它在CPU上運行的時間很短，基本上都在等待I/O操作，這可能讓分配給該進(jìn)程的時間片都沒有用完，該進(jìn)程就進(jìn)入就緒隊列中，這就對I/O密集型進(jìn)程不合理。所以就增加一個輔助隊列和多個I/O事件所對應(yīng)的隊列。I/O密集型進(jìn)程用完時間片后就進(jìn)入對應(yīng)I/O隊列中，然后由I/O隊列添加到輔助隊列中，CPU先從輔助隊列中選取進(jìn)程上CPU，因為這些進(jìn)程只占用CPU很少時間，再從就緒隊列中挑取其他進(jìn)程。

最高優(yōu)先級調(diào)度算法：

設(shè)計思想：選擇優(yōu)先級最高的進(jìn)程投入運行

通常：系統(tǒng)進(jìn)程優(yōu)先級 高于 用戶進(jìn)程 　　 前臺進(jìn)程優(yōu)先級 高于 后臺進(jìn)程 　　　操作系統(tǒng)更偏好 I/O型進(jìn)程

缺點：

會產(chǎn)生饑餓現(xiàn)象，低優(yōu)先級在大量高優(yōu)先級進(jìn)程中始終得不到運行，而且會出現(xiàn)優(yōu)先級反轉(zhuǎn)問題：

一個低優(yōu)先級進(jìn)程持有一個高優(yōu)先級進(jìn)程所需要的資源，使得高優(yōu)先級進(jìn)程等待低優(yōu)先級進(jìn)程運行

例如：

設(shè)H是高優(yōu)先級進(jìn)程，L是低優(yōu)先級進(jìn)程， M是中優(yōu)先級進(jìn)程（CPU密集型） 場景：L進(jìn)入臨界區(qū)執(zhí)行，之后被H搶占； 　　　H也要進(jìn)入臨界區(qū)，失敗，因為所需資源被低優(yōu)先級占有，從而被阻塞； 　　　M上CPU執(zhí)行，L因優(yōu)先級較低無法執(zhí)行，所以H也無法執(zhí)行

解決方案 1.設(shè)置優(yōu)先級上限(進(jìn)入臨界區(qū)進(jìn)程優(yōu)先級為最高) 2.優(yōu)先級繼承（如果某個低優(yōu)先級進(jìn)程限制了高優(yōu)先級進(jìn)程，那么該低優(yōu)先級將繼承高優(yōu)先級） 3.使用中斷禁止（進(jìn)入臨界區(qū)后禁止因為優(yōu)先級高低而產(chǎn)生中斷）

多級反饋隊列調(diào)度算法：

設(shè)計思想：

1.設(shè)置多個就緒隊列，第一級隊列優(yōu)先級最高 2.給不同就緒隊列中的進(jìn)程分配長度不同的時間片，第一級隊列時間片最小；隨著隊列優(yōu)先級別的降低，時間片增大(為了平衡優(yōu)先級和時間片的關(guān)系) 3.當(dāng)?shù)谝患夑犃袨榭諘r，在第二級隊列調(diào)度，以此類推 4.各級隊列按照時間片輪轉(zhuǎn)方式 進(jìn)行調(diào)度 5.當(dāng)一個新創(chuàng)建進(jìn)程就緒后，進(jìn)入第一級隊列 6.進(jìn)程用完時間片而放棄CPU，進(jìn)入下一級就緒隊列（該進(jìn)程優(yōu)先級降低，CPU密集型進(jìn)程吃虧） 7.由于阻塞而放棄CPU的進(jìn)程進(jìn)入相應(yīng)的等待隊列，一旦等待的事件發(fā)生，該進(jìn)程回到原來一級就緒隊列(隊首/隊尾，要考慮，上CPU后時間片是原來剩余的還是全新的也要考慮)

總結(jié)：

?

多處理器調(diào)度算法：

1.要決定選擇哪一個進(jìn)程執(zhí)行，還需要決定在哪一個CPU上執(zhí)行

2.要考慮進(jìn)程在多個CPU之間遷移時的開銷（ 高速緩存失效、TLB失效）

3.盡可能使進(jìn)程總是在同一個CPU上執(zhí)行

如果每個進(jìn)程可以調(diào)度到所有CPU上，假如進(jìn)程上次在CPU1上執(zhí)行，本次被調(diào)度到CPU2，則會增加高速緩存失效、TLB失效；如果每個進(jìn)程盡量調(diào)度到指定的CPU上，各種失效就會減少

4. 考慮負(fù)載均衡問題

windows調(diào)度算法：

調(diào)度單位是線程

設(shè)計思想：采用基于動態(tài)優(yōu)先級的、搶占式調(diào)度，結(jié)合時間配額的調(diào)整

實現(xiàn)：

1.就緒線程按優(yōu)先級進(jìn)入相應(yīng)隊列 2. 系統(tǒng)總是選擇優(yōu)先級最高的就緒線程運行 3. 同一優(yōu)先級的各線程按時間片輪轉(zhuǎn)進(jìn)行調(diào)度 4. 多CPU系統(tǒng)中允許多個線程并行運行

引發(fā)線程調(diào)度的條件： 1.一個線程的優(yōu)先級改變了 2.一個線程改變（增加了CPU）了它的親和(Affinity)處理機(jī)集合(將線程局限于幾個CPU之間運行，這幾個CPU就叫親和處理機(jī)集合，當(dāng)其他處理機(jī)空閑該線程也不能被執(zhí)行) 3.線程正常終止 或 由于某種錯誤而終止 4.新線程創(chuàng)建 或 一個等待線程變成就緒 5.當(dāng)一個線程從運行態(tài)進(jìn)入阻塞態(tài) 6.當(dāng)一個線程從運行態(tài)變?yōu)榫途w態(tài)

windows線程優(yōu)先級：

①實時優(yōu)先級：不改變其優(yōu)先級

②可變優(yōu)先級：其優(yōu)先級可以在一定范圍內(nèi)升高或降低

③系統(tǒng)線程，其中有個零號線程定期用來把空閑頁面清零

時間配額

1.時間配額不是一個時間長度值，而一個稱為配額單位(quantum unit)的整數(shù) 2.一個線程用完了自己的時間配額時，如果沒有其他相同優(yōu)先級的線程，Windows將重新給該線程分配一個新的時間配額，讓它繼續(xù)運行

調(diào)度策略：

1.主動切換，一旦某線程從運行態(tài)轉(zhuǎn)到阻塞態(tài)，OS就從同優(yōu)先級就緒隊列中選擇一個線程上CPU 2.搶占，當(dāng)線程被搶占時，它被放回相應(yīng)優(yōu)先級的就緒隊列的隊首

①處于實時優(yōu)先級的線程在被搶占時，時間配額被重置為一個完整的時間配額 ②處于可變優(yōu)先級的線程在被搶占時，時間配額不變，重新得到CPU后將運行剩余的時間配額

3.時間配額用完

假設(shè)線程A的時間配額用完 1.A的優(yōu)先級沒有降低 　　①如果隊列中有其他就緒線程，選擇下一個線程執(zhí)行，A回到原來就緒隊列末尾 　?、谌绻犃兄袥]有其他就緒線程，系統(tǒng)給線程A分配一個新的時間配額，讓它繼續(xù)運行

2.A的優(yōu)先級降低了（降低可能是之前A優(yōu)先級被提高了），Windows 將選擇一個更高優(yōu)先級的線程

Windows的調(diào)度策略注意的問題 1.如何體現(xiàn)對某類線程具有傾向性？ 2.如何解決由于調(diào)度策略中潛在的不公平性而帶來饑餓現(xiàn)象？ 3.如何改善系統(tǒng)吞吐量、響應(yīng)時間等整體特征？

?

解決方案：

　　1.提升優(yōu)先級,給線程分配一個很大的時間配額

1.I/O操作完成 2.信號量或事件等待結(jié)束 3.前臺進(jìn)程中的線程完成一個等待操作 4.由于窗口活動而喚醒窗口線程 5.線程處于就緒態(tài)超過了一定的時間還沒有運行—— “饑餓”現(xiàn)象

以上5種現(xiàn)象會導(dǎo)致OS將線程優(yōu)先級提高.

?

針對饑餓線程：

系統(tǒng)線程“平衡集管理器(balance set manager)” 每秒鐘掃描一次就緒隊列，發(fā)現(xiàn)是否存在等待時間超過300個時鐘中斷間隔的線程

平衡集管理器將這些線程的優(yōu)先級提升到15（最高），并分配給它一個長度為正常值4倍的時間配額

當(dāng)被提升的線程用完它的時間配額后，立即衰減到它原來的基本優(yōu)先級（維護(hù)平衡）

審核編輯：湯梓紅