多種處理器調度過程及調度算法

U調度：

即按照一定的的調度算法從就緒隊列中選擇進程，把CPU使用權交給被選中進程。

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

系統場景：

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

調度時機：

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

新進程創建 或 一個等待進程變成就緒

當一個進程從運行態進入阻塞態

當一個進程從運行態變為就緒態

前兩種是CPU上有進程，后兩種是CPU上沒有進程執行時發生調度

總之往往是內核對中斷/異常/系統調用處理后返回到用戶態時發生調度。

調度過程：

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

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

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

例如：

進程A下CPU，進程B上CPU

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

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

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

直接開銷：

1.保存和恢復寄存器

2.切換進程地址空間

間接開銷：

cache失效，緩沖區的緩存失效，TLB失效

調度算法：

?

以此為設計算法的出發點。

調度算法衡量指標：

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

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

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

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

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

調度算法要點：

進程優先數與優先級并不成正相關:基本上優先數越小優先級越大

進程優先級可以分成靜態和動態的：

1.靜態優先級：進程創建時指定，運行過程中不再改變 2.動態優先級：進程創建時指定了一個優先級，運行過程中可以動態變化

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

根據不同的優先級就設計不同就緒隊列的組織方式：

?

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

?

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

進程搶占與非搶占：

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

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

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

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

?

?

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

?

?

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

調度算法：

批處理的調度算法：

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

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

優缺點：公平，易實現，但是對于運行時間長的進程后面的短進程不利

例子：

三個進程按順序就緒：P1、P2、P3，進程P1執行需要24s，P2和P3各需要3s

FCFS算法：　　

?
?

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

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

平均周轉時間：（24+27+30）/ 3 = 27s

但是不同的順序狀態會影響周轉時間

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

?

?

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

周轉時間TT：P1:30；P2:3；P3:6；

平均周轉時間：13s

?

短作業優先（Shortest Job First）：

思想：具有最短完成時間的進程優先執行（非搶占式）

最短剩余時間優先（Shortest Remaining Time Next）：

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

例子：

對于非搶占式短作業優先：

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

對于搶占式短作業優先：

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

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

最高相應優先比（Highest Response Ratio Next）

設計思想：

調度時，首先計算每個進程的響應比R之后，總是選擇 R 最高的進程執行

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

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

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

交互式系統的調度算法：

時間片輪轉調度：

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

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

?

?
?

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

?

時間片大小的確定：

?

?

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

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

?

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

1.進程切換浪費CPU時間

太短，那么大部分CPU時間將浪費在調度上

優缺點

公平

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

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

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

例如：

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

如果使用時間片輪轉（RR）算法的平均周轉時間？

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

A周轉時間為199ms B周轉時間為200ms 平均周轉時間為199.5ms

使用先來先服務（FCFS）算法呢？

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

虛擬輪轉調度算法：

?

?

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

最高優先級調度算法：

設計思想：選擇優先級最高的進程投入運行

通常：系統進程優先級 高于 用戶進程 　　 前臺進程優先級 高于 后臺進程 　　　操作系統更偏好 I/O型進程

缺點：

會產生饑餓現象，低優先級在大量高優先級進程中始終得不到運行，而且會出現優先級反轉問題：

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

例如：

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

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

多級反饋隊列調度算法：

設計思想：

1.設置多個就緒隊列，第一級隊列優先級最高 2.給不同就緒隊列中的進程分配長度不同的時間片，第一級隊列時間片最??；隨著隊列優先級別的降低，時間片增大(為了平衡優先級和時間片的關系) 3.當第一級隊列為空時，在第二級隊列調度，以此類推 4.各級隊列按照時間片輪轉方式 進行調度 5.當一個新創建進程就緒后，進入第一級隊列 6.進程用完時間片而放棄CPU，進入下一級就緒隊列（該進程優先級降低，CPU密集型進程吃虧） 7.由于阻塞而放棄CPU的進程進入相應的等待隊列，一旦等待的事件發生，該進程回到原來一級就緒隊列(隊首/隊尾，要考慮，上CPU后時間片是原來剩余的還是全新的也要考慮)

總結：

?

多處理器調度算法：

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

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

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

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

4. 考慮負載均衡問題

windows調度算法：

調度單位是線程

設計思想：采用基于動態優先級的、搶占式調度，結合時間配額的調整

實現：

1.就緒線程按優先級進入相應隊列 2. 系統總是選擇優先級最高的就緒線程運行 3. 同一優先級的各線程按時間片輪轉進行調度 4. 多CPU系統中允許多個線程并行運行

引發線程調度的條件： 1.一個線程的優先級改變了 2.一個線程改變（增加了CPU）了它的親和(Affinity)處理機集合(將線程局限于幾個CPU之間運行，這幾個CPU就叫親和處理機集合，當其他處理機空閑該線程也不能被執行) 3.線程正常終止 或 由于某種錯誤而終止 4.新線程創建 或 一個等待線程變成就緒 5.當一個線程從運行態進入阻塞態 6.當一個線程從運行態變為就緒態

windows線程優先級：

①實時優先級：不改變其優先級

②可變優先級：其優先級可以在一定范圍內升高或降低

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

時間配額

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

調度策略：

1.主動切換，一旦某線程從運行態轉到阻塞態，OS就從同優先級就緒隊列中選擇一個線程上CPU 2.搶占，當線程被搶占時，它被放回相應優先級的就緒隊列的隊首

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

3.時間配額用完

假設線程A的時間配額用完 1.A的優先級沒有降低 　?、偃绻犃兄杏衅渌途w線程，選擇下一個線程執行，A回到原來就緒隊列末尾 　?、谌绻犃兄袥]有其他就緒線程，系統給線程A分配一個新的時間配額，讓它繼續運行

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

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

?

解決方案：

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

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

以上5種現象會導致OS將線程優先級提高.

?

針對饑餓線程：

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

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

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

審核編輯：湯梓紅