多種處理器調(diào)度過程及調(diào)度算法

U調(diào)度：

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

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

系統(tǒng)場景：

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

調(diào)度時機：

進程正常終止 或 由于某種錯誤而終止

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

當一個進程從運行態(tài)進入阻塞態(tài)

當一個進程從運行態(tài)變?yōu)榫途w態(tài)

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

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

調(diào)度過程：

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

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

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

例如：

進程A下CPU，進程B上CPU

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

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

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

直接開銷：

1.保存和恢復寄存器

2.切換進程地址空間

間接開銷：

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

調(diào)度算法：

?

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

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

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

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

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

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

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

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

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

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

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

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

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

?

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

?

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

進程搶占與非搶占：

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

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

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

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

?

?

CPU密集型：需要大量的CPU時間來進行計算

?

?

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

調(diào)度算法：

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

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

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

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

例子：

三個進程按順序就緒：P1、P2、P3，進程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）：

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

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

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

例子：

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

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

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

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

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

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

設(shè)計思想：

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

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

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

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

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

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

目標：改善短進程的平均響應時間

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

?

?
?

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

?

時間片大小的確定：

?

?

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

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

?

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

1.進程切換浪費CPU時間

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

優(yōu)缺點

公平

有利于交互式計算，響應時間快

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

RR對不同大小的進程是有利的，但是對于相同大小的進程反而不利

例如：

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

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

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

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

缺點：

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

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

例如：

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

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

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

設(shè)計思想：

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

總結(jié)：

?

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

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

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

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

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

4. 考慮負載均衡問題

windows調(diào)度算法：

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

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

實現(xiàn)：

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

引發(fā)線程調(diào)度的條件： 1.一個線程的優(yōu)先級改變了 2.一個線程改變（增加了CPU）了它的親和(Affinity)處理機集合(將線程局限于幾個CPU之間運行，這幾個CPU就叫親和處理機集合，當其他處理機空閑該線程也不能被執(zhí)行) 3.線程正常終止 或 由于某種錯誤而終止 4.新線程創(chuàng)建 或 一個等待線程變成就緒 5.當一個線程從運行態(tài)進入阻塞態(tài) 6.當一個線程從運行態(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.搶占，當線程被搶占時，它被放回相應優(yōu)先級的就緒隊列的隊首

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

3.時間配額用完

假設(shè)線程A的時間配額用完 1.A的優(yōu)先級沒有降低 　?、偃绻犃兄杏衅渌途w線程，選擇下一個線程執(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)吞吐量、響應時間等整體特征？

?

解決方案：

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

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

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

?

針對饑餓線程：

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

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

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

審核編輯：湯梓紅