U調(diào)度：

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

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

系統(tǒng)場景：

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

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

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

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

3. 當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)進(jìn)入阻塞態(tài)

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

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

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

調(diào)度過程：

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

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

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

例如：

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

• 此時(shí)上下文保存的具體步驟為：

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

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

直接開銷：

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

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

間接開銷：

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

調(diào)度算法：

• 以此為設(shè)計(jì)算法的出發(fā)點(diǎn)。

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

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

2. 周轉(zhuǎn)時(shí)間TT(Turnaround Time)：每個(gè)進(jìn)程從提出請求到運(yùn)行完成的時(shí)間

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

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

5. 等待時(shí)間(Waiting time)：每個(gè)進(jìn)程在就緒隊(duì)列(ready queue)中等待的時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

調(diào)度算法：

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

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

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

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

例子：

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

• FCFS算法：　　

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

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

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

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

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

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

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

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

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

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

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

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

例子：

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

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

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

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

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

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

• 設(shè)計(jì)思想：

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

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

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

• 缺點(diǎn)：每次都需計(jì)算R值開銷較大

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

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

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

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

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




• 時(shí)間片大小的確定：

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

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

• 太短 --小于典型的交互時(shí)間

1.進(jìn)程切換浪費(fèi)CPU時(shí)間

• 太短，那么大部分CPU時(shí)間將浪費(fèi)在調(diào)度上

• 優(yōu)缺點(diǎn)

1. 公平

2. 有利于交互式計(jì)算，響應(yīng)時(shí)間快

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

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

• 例如：

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

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

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

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

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

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

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

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

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

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

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

• 缺點(diǎn)：

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

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

• 例如：

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

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

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

• 設(shè)計(jì)思想：

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

• 總結(jié)：

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

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

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

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

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

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

windows調(diào)度算法：

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

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

• 實(shí)現(xiàn)：

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

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

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

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

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

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

• 時(shí)間配額

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

• 調(diào)度策略：

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

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

3.時(shí)間配額用完

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

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

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

• 解決方案：

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

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

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




• 針對饑餓線程：

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

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

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