操作系統(tǒng) 課件 第4章 進(jìn)程線程調(diào)度

第4章進(jìn)程線程調(diào)度4.1進(jìn)程調(diào)度的基本概念4.2進(jìn)程調(diào)度算法的設(shè)計(jì)思路4.3經(jīng)典進(jìn)程調(diào)度算法4.4其他進(jìn)程調(diào)度算法4.5操作系統(tǒng)調(diào)度算法實(shí)例4.6多處理器調(diào)度算法4.7實(shí)時(shí)調(diào)度算法

4.8習(xí)題目錄CONTENTSPART4.1進(jìn)程調(diào)度的基本概念4.1進(jìn)程調(diào)度的基本概念<4

>進(jìn)程調(diào)度即處理機(jī)調(diào)度。進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對(duì)CPU的競爭，按照一定的調(diào)度算法，使某一就緒進(jìn)程獲得CPU的控制權(quán)，轉(zhuǎn)換成運(yùn)行狀態(tài)。進(jìn)程調(diào)度也叫低級(jí)調(diào)度進(jìn)程調(diào)度程序是操作系統(tǒng)的真正核心，它直接負(fù)責(zé)CPU的分配。系統(tǒng)中所有進(jìn)程都是在CPU上運(yùn)行的，進(jìn)程調(diào)度程序就是它們的切換開關(guān)。4.1.1進(jìn)程調(diào)度的主要功能<5

>①保存現(xiàn)場②挑選進(jìn)程③恢復(fù)現(xiàn)場4.1.2進(jìn)程調(diào)度的時(shí)機(jī)<6

>①創(chuàng)建進(jìn)程②任務(wù)完成③等待資源④中斷發(fā)生⑤運(yùn)行到時(shí)4.1.3兩級(jí)調(diào)度模型<7

>兩級(jí)調(diào)度簡化隊(duì)列圖4.1.4三級(jí)調(diào)度模型<8

>三級(jí)調(diào)度簡化隊(duì)列示意圖背景-2：北京大學(xué)圖書館PART4.2進(jìn)程調(diào)度算法的設(shè)計(jì)思路4.2.1調(diào)度策略的選擇<10

>①設(shè)計(jì)目標(biāo)②公平性③均衡性④統(tǒng)籌兼顧⑤優(yōu)先級(jí)⑥開銷4.2.2性能評(píng)價(jià)標(biāo)準(zhǔn)<11

>①CPU利用率②吞吐量③周轉(zhuǎn)時(shí)間④就緒等待時(shí)間⑤響應(yīng)時(shí)間背景-3：西門華表經(jīng)典進(jìn)程調(diào)度算法PART4.34.3.1先來先服務(wù)法<13

>先來先服務(wù)（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）法是最簡單的一種調(diào)度算法對(duì)于作業(yè)調(diào)度來說，每次調(diào)度從后備作業(yè)隊(duì)列中選擇隊(duì)頭的一個(gè)或幾個(gè)作業(yè)，把它們調(diào)入內(nèi)存，分配相應(yīng)的資源，創(chuàng)建進(jìn)程，然后把進(jìn)程放入就緒隊(duì)列對(duì)于進(jìn)程調(diào)度算法來說，即每次調(diào)度從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把CPU分給它，直至完成或者由于某些原因而阻塞，當(dāng)新一個(gè)進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，它的PCB就鏈入就緒隊(duì)列的末尾。每次進(jìn)程調(diào)度時(shí)就把隊(duì)頭進(jìn)程從該隊(duì)列中摘下，分給它CPU，使它運(yùn)行4.3.1先來先服務(wù)法<14

>設(shè)有三個(gè)作業(yè)，編號(hào)分別為1、2、3，且分別對(duì)應(yīng)一個(gè)進(jìn)程。各作業(yè)依次到達(dá)，相差一個(gè)時(shí)間單位。如圖所示為采用FCFS方式調(diào)度時(shí)這三個(gè)作業(yè)的執(zhí)行順序，其中，*表示作業(yè)到達(dá)的時(shí)間，實(shí)線表示作業(yè)執(zhí)行過程。根據(jù)圖，可算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間等。4.3.1先來先服務(wù)法<15

>FCFS調(diào)度算法的性能如表所示。FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。因?yàn)槎套鳂I(yè)運(yùn)行時(shí)間很短，如果讓它等待較長時(shí)間才得到服務(wù)，它的帶權(quán)周轉(zhuǎn)時(shí)間就會(huì)很長。另外，F(xiàn)CFS調(diào)度算法對(duì)CPU繁忙型作業(yè)（指需要大量CPU時(shí)間進(jìn)行計(jì)算的作業(yè)）較有利，而不利于I/O繁忙型作業(yè)（指需要頻繁請(qǐng)求I/O的作業(yè)）。FCFS調(diào)度算法容易實(shí)現(xiàn)，但它的效率較低。作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間10240242412132427268.673232730289.33平均周轉(zhuǎn)時(shí)間=26平均帶權(quán)周轉(zhuǎn)時(shí)間=6.334.3.2時(shí)間片輪轉(zhuǎn)法<16

>時(shí)間片輪轉(zhuǎn)法（Round-Robin，RR）主要用于分時(shí)系統(tǒng)中的進(jìn)程調(diào)度。當(dāng)進(jìn)程用完分給它的時(shí)間片后，系統(tǒng)的計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序便停止該進(jìn)程的運(yùn)行，并把它放入就緒隊(duì)列的末尾；然后，把CPU分給就緒隊(duì)列的隊(duì)首進(jìn)程，同樣也讓它運(yùn)行一個(gè)時(shí)間片，如此往復(fù)4.3.2時(shí)間片輪轉(zhuǎn)法<17

>四個(gè)進(jìn)程運(yùn)行情況4.3.2時(shí)間片輪轉(zhuǎn)法<18

>時(shí)間片輪轉(zhuǎn)法（Round-Robin，RR）主要用于分時(shí)系統(tǒng)中的進(jìn)程調(diào)度。為實(shí)現(xiàn)輪轉(zhuǎn)調(diào)度，表RR法的性能指標(biāo)到達(dá)時(shí)間進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間時(shí)間片q=1

A012026262.17B05117173.4C03211113.67D06320203.33平均周轉(zhuǎn)時(shí)間=18.5平均帶權(quán)周轉(zhuǎn)時(shí)間=3.14時(shí)間片q=4A012026262.17B05420204C03811113.67D061122223.67平均周轉(zhuǎn)時(shí)間=19.75平均帶權(quán)周轉(zhuǎn)時(shí)間=3.384.3.2時(shí)間片輪轉(zhuǎn)法<19

>時(shí)間片的大小對(duì)輪轉(zhuǎn)法的性能有很大影響：如果時(shí)間片太長，每個(gè)進(jìn)程都在這段時(shí)間內(nèi)運(yùn)行完畢，那么時(shí)間片輪轉(zhuǎn)法就退化為先來先服務(wù)算法。很顯然，對(duì)用戶的響應(yīng)時(shí)間必然加長；如果時(shí)間片太短，CPU在進(jìn)程間的切換工作就非常頻繁，從而導(dǎo)致系統(tǒng)開銷增加4.3.2時(shí)間片輪轉(zhuǎn)法<20

>時(shí)間片的長短通常由以下四個(gè)因素來確定：①系統(tǒng)的響應(yīng)時(shí)間②就緒隊(duì)列進(jìn)程的數(shù)目③進(jìn)程的轉(zhuǎn)換時(shí)間④CPU運(yùn)行指令速度4.3.3優(yōu)先級(jí)法<21

>利用優(yōu)先級(jí)調(diào)度算法進(jìn)行進(jìn)程調(diào)度時(shí)，是從就緒隊(duì)列中選出優(yōu)先級(jí)最高的進(jìn)程，把CPU分給它使用。如果在就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)更高的進(jìn)程時(shí)，怎么辦：①非搶占式優(yōu)先級(jí)法②搶占式優(yōu)先級(jí)法4.3.3優(yōu)先級(jí)法<22

>內(nèi)部決定優(yōu)先級(jí)是利用某些可度量的量來定義一個(gè)進(jìn)程的優(yōu)先級(jí)外部優(yōu)先級(jí)是按操作系統(tǒng)以外的標(biāo)準(zhǔn)設(shè)置的4.3.3優(yōu)先級(jí)法<23

>兩種確定進(jìn)程優(yōu)先級(jí)的方式：①靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)就確定下來的，而且在進(jìn)程的整個(gè)運(yùn)行期間保持不變②動(dòng)態(tài)優(yōu)先級(jí)是隨著進(jìn)程的推進(jìn)而不斷改變的4.3.3優(yōu)先級(jí)法<24

>進(jìn)程運(yùn)行時(shí)間優(yōu)先數(shù)P1103P211P324P415P552一組進(jìn)程列表

采用優(yōu)先級(jí)法時(shí)五個(gè)進(jìn)程的執(zhí)行順序4.3.4短作業(yè)優(yōu)先法<25

>從作業(yè)的后備隊(duì)列中挑選那些需要運(yùn)行時(shí)間最短的作業(yè)放入內(nèi)存短作業(yè)優(yōu)先法能有效地降低作業(yè)的平均等待時(shí)間和提高系統(tǒng)的吞吐量算法對(duì)長作業(yè)很不利，并且不能保證緊迫性作業(yè)會(huì)被及時(shí)處理4.3.5最短剩余時(shí)間優(yōu)先法<26

>最短剩余時(shí)間優(yōu)先（ShortestRemainingTimeFirst,SRTF）法是短作業(yè)優(yōu)先法的變形，它采用搶占式策略4.3.6多級(jí)隊(duì)列法<27

>多級(jí)隊(duì)列（MultilevelQueue）調(diào)度算法是根據(jù)作業(yè)的某些特性，如占用內(nèi)存大小和作業(yè)類型等，永久性地把各個(gè)作業(yè)分別鏈入不同的隊(duì)列，每個(gè)隊(duì)列都有自己的調(diào)度算法，在各個(gè)隊(duì)列之間也要進(jìn)行調(diào)度，通常采用固定優(yōu)先級(jí)的搶占式調(diào)度4.3.7多級(jí)反饋隊(duì)列法<28

>多級(jí)反饋隊(duì)列（MultilevelFeedbackQueue）法是在多級(jí)隊(duì)列法的基礎(chǔ)上加進(jìn)“反饋”措施。其實(shí)現(xiàn)思想是：系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)優(yōu)先級(jí)，第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，以下各個(gè)隊(duì)列的優(yōu)先級(jí)逐個(gè)降低；各就緒隊(duì)列中進(jìn)程的運(yùn)行時(shí)間片不同，高優(yōu)先級(jí)隊(duì)列的時(shí)間片小，低優(yōu)先級(jí)隊(duì)列的時(shí)間片大，如從高到低依次加倍；新進(jìn)程進(jìn)入系統(tǒng)后，先放入第一隊(duì)列的末尾，各隊(duì)列按FCFS方式排隊(duì)；如某個(gè)進(jìn)程在相應(yīng)時(shí)間片內(nèi)沒有完成工作，則把它轉(zhuǎn)到下一級(jí)隊(duì)列的末尾；系統(tǒng)先運(yùn)行第一隊(duì)列中的進(jìn)程，第一隊(duì)列為空后，才運(yùn)行第二隊(duì)列中的進(jìn)程，依次類推。最后一個(gè)隊(duì)列（最低級(jí)）中的進(jìn)程采用時(shí)間片輪轉(zhuǎn)的方式進(jìn)行調(diào)度。多級(jí)反饋隊(duì)列法雖然比較復(fù)雜一些，但具有較好的性能，在UNIX系統(tǒng)，WindowsNT和OS/2中都采用了類似的調(diào)度算法。背景-4：未名湖PART4.4其他進(jìn)程調(diào)度算法4.4.1公平共享調(diào)度<30

>到此為止講述的所有調(diào)度算法都是把就緒進(jìn)程集合看做是單一的進(jìn)程池，從這個(gè)進(jìn)程池中選擇下一個(gè)要運(yùn)行的進(jìn)程。該池可以按優(yōu)先級(jí)劃分成幾個(gè)，但它們都是同構(gòu)的。但是，在多用戶系統(tǒng)中，如果單個(gè)用戶的應(yīng)用程序或作業(yè)可以組成多個(gè)進(jìn)程（或線程），就會(huì)出現(xiàn)傳統(tǒng)的調(diào)度器不認(rèn)識(shí)的進(jìn)程集合結(jié)構(gòu)。從用戶的角度看，他所關(guān)心的不是某個(gè)特定的進(jìn)程如何執(zhí)行，而是構(gòu)成應(yīng)用程序的一組進(jìn)程如何執(zhí)行。因此，基于進(jìn)程組的調(diào)度決策是非常具有吸引力的。該方法通常稱作公平共享調(diào)度（fair-sharescheduling）。此外，即使每個(gè)用戶用一個(gè)進(jìn)程表示，這個(gè)概念可以擴(kuò)展到用戶組。例如，在分時(shí)系統(tǒng)中，可能希望把某個(gè)部門的所有用戶看作是同一個(gè)組中的成員，然后進(jìn)行調(diào)度決策，并給每個(gè)組中的用戶提供類似的服務(wù)。因此，如果同一個(gè)部門中的大量用戶登錄到系統(tǒng)，則希望響應(yīng)時(shí)間效果的降低主要影響到該部門的成員，而不會(huì)影響其他部門的用戶。4.4.1公平共享調(diào)度<31

>術(shù)語“公平共享”表明了這類調(diào)度器的基本原則。每個(gè)用戶被指定了某種類型的權(quán)值，該權(quán)值定義了該用戶對(duì)系統(tǒng)資源的共享，而且是作為在所有使用的資源中所占的比例來體現(xiàn)。特別地，每個(gè)用戶被分配了處理器的共享。這種方案或多或少以線性的方式操作，如果用戶A的權(quán)值是用戶B的2倍，那么從長期運(yùn)行的結(jié)果來看，用戶A可以完成的工作應(yīng)該是用戶B的2倍。公平共享調(diào)度器的目標(biāo)是監(jiān)視使用情況，對(duì)那些相對(duì)于公平共享的用戶占有較多資源的用戶，調(diào)度器分配以較少的資源，相對(duì)于公平共享的用戶占有較少資源的用戶，調(diào)度器分配以較多的資源。4.4.2保證調(diào)度<32

>

保證調(diào)度算法的目標(biāo)是保證每個(gè)進(jìn)程享用CPU的時(shí)間完全一樣，即如果系統(tǒng)里一共有n個(gè)進(jìn)程，則每個(gè)進(jìn)程占用CPU的時(shí)間為1/n。保障調(diào)度就是保障每個(gè)進(jìn)程使用1/n的CPU時(shí)間。保障就是肯定1/n的時(shí)間運(yùn)轉(zhuǎn)，而不是大概1/n時(shí)間運(yùn)轉(zhuǎn)。那么保障調(diào)度和輪轉(zhuǎn)調(diào)度是一樣嗎？時(shí)間片輪轉(zhuǎn)能不能達(dá)到1/n的效果？關(guān)鍵就是達(dá)到1/n不一定要靠輪轉(zhuǎn)。輪轉(zhuǎn)是能夠達(dá)到1/n的，但是保障調(diào)度不一定要輪轉(zhuǎn)。每次給的時(shí)間片不一定要一樣。4.4.3彩票調(diào)度

<33

>彩票調(diào)度算法是一種概率調(diào)度算法。你買過彩票就知道，你買的越多中獎(jiǎng)的概率越大。在該算法里，給每個(gè)進(jìn)程分發(fā)一定數(shù)量的彩票，而調(diào)度器則從所有彩票里隨機(jī)抽取一張彩票，持有該彩票的進(jìn)程就獲得CPU。這樣，如果想讓某個(gè)進(jìn)程獲得更多的CPU時(shí)間，我們可以給該進(jìn)程多發(fā)幾張彩票。彩票算法的優(yōu)越性是顯而易見的，通過給每個(gè)進(jìn)程至少一張彩票就可以防止饑餓，因?yàn)樵撨M(jìn)程獲得CPU的概率將大于0。背景-5：翻尾石魚PART4.5操作系統(tǒng)調(diào)度算法實(shí)例4.5.1BSD多級(jí)反饋隊(duì)列法<35

>BSDUNIX系統(tǒng)主要用于分時(shí)交互環(huán)境中，調(diào)度算法設(shè)計(jì)成為交互用戶提供好的響應(yīng)時(shí)間，同時(shí)保證低優(yōu)先級(jí)的后臺(tái)作業(yè)不會(huì)餓死。BSDUNIX系統(tǒng)采用了多級(jí)反饋隊(duì)列法，在每個(gè)優(yōu)先級(jí)隊(duì)列中采用了輪轉(zhuǎn)的方法

4.5.1BSD多級(jí)反饋隊(duì)列法<36

>

CPUj(i)：進(jìn)程j在區(qū)間i中處理器使用情況的度量Pj(i)：進(jìn)程j在區(qū)間i開始處的優(yōu)先級(jí)；值越小表示的優(yōu)先級(jí)最高Basej：進(jìn)程j的基本優(yōu)先級(jí)nicej：用戶可控制的調(diào)節(jié)因子4.5.1BSD多級(jí)反饋隊(duì)列法<37

>每秒都重新計(jì)算每個(gè)進(jìn)程的優(yōu)先級(jí)，并且進(jìn)行一次新的調(diào)度決策。給每個(gè)進(jìn)程賦予基本優(yōu)先級(jí)的目的是把所有的進(jìn)程劃分成固定的優(yōu)先級(jí)區(qū)。CPU和“nice”組件是被限制的，以防止進(jìn)程遷移出指定的區(qū)4.5.2UNIXSVR4調(diào)度<38

>UNIXSVR4中使用的調(diào)度算法是對(duì)早期UNIX系統(tǒng)所使用的調(diào)度算法的全面檢查。新算法被設(shè)計(jì)成給實(shí)時(shí)進(jìn)程最高的優(yōu)先權(quán)，給內(nèi)核模式的進(jìn)程次高的優(yōu)先權(quán)，給其他用戶模式的進(jìn)程（稱作分時(shí)進(jìn)程）最低的優(yōu)先權(quán)。SVR4中實(shí)現(xiàn)的兩個(gè)重要的修改為：1．增加了可搶占的靜態(tài)優(yōu)先級(jí)調(diào)度器，引進(jìn)了160種優(yōu)先級(jí)，并劃分到三個(gè)優(yōu)先級(jí)類中。2．插入了可搶占點(diǎn)。由于基本內(nèi)核是不能被搶占的，它只能劃分成許多個(gè)處理步驟，每一步都必須一直運(yùn)行到完成，中間不會(huì)被中斷。在處理步驟之間，有一個(gè)稱作可搶占點(diǎn)的安全位置，在這里，內(nèi)核可以安全地中斷處理，并調(diào)度一個(gè)新進(jìn)程。安全位置定義成一個(gè)代碼區(qū)域，在這里所有的內(nèi)核數(shù)據(jù)結(jié)構(gòu)或者是已經(jīng)更新且一致的，或者通過一個(gè)信號(hào)量被鎖定。4.5.2UNIXSVR4調(diào)度<39

>SVR4中定義了160個(gè)優(yōu)先級(jí)，每個(gè)進(jìn)程定義成屬于這三類優(yōu)先級(jí)中的一類，并被指定為具有該類中的一個(gè)優(yōu)先級(jí)。這三類優(yōu)先級(jí)為：●實(shí)時(shí)（159~100）：具有這些優(yōu)先級(jí)的進(jìn)程可以保證在任何內(nèi)核進(jìn)程或分時(shí)進(jìn)程之前被選擇運(yùn)行。此外，實(shí)時(shí)進(jìn)程可以使用可搶占點(diǎn)搶占內(nèi)核進(jìn)程和用戶進(jìn)程?！駜?nèi)核（99～66）：具有這些優(yōu)先級(jí)的進(jìn)程保證在任何分時(shí)進(jìn)程之前被選擇運(yùn)行，但必須服從實(shí)時(shí)進(jìn)程?！穹謺r(shí)（59～0）：最低優(yōu)先級(jí)的進(jìn)程，通常是除了實(shí)時(shí)應(yīng)用程序以外的用戶應(yīng)用程序。每個(gè)優(yōu)先級(jí)都關(guān)聯(lián)著一個(gè)調(diào)度隊(duì)列，在某一給定優(yōu)先級(jí)的進(jìn)程按循環(huán)方式執(zhí)行。有一個(gè)位映像向量dqactmap，它的每一位對(duì)應(yīng)于各個(gè)優(yōu)先級(jí)。4.5.2UNIXSVR4調(diào)度<40

>如果某個(gè)優(yōu)先級(jí)上的隊(duì)列不為空，則相應(yīng)的位被置為1。當(dāng)一個(gè)正在運(yùn)行的進(jìn)程由于阻塞、時(shí)間片到期或搶占等原因離開運(yùn)行狀態(tài)時(shí)，調(diào)度器檢查dqactmap，并從優(yōu)先級(jí)最高的非空隊(duì)列中調(diào)度一個(gè)就緒進(jìn)程。此外，當(dāng)?shù)竭_(dá)一個(gè)定義的可搶占點(diǎn)時(shí)，內(nèi)核檢查一個(gè)稱作kprunrun的標(biāo)記，如果它被置位，則表明至少有一個(gè)實(shí)時(shí)進(jìn)程處于就緒狀態(tài)，如果當(dāng)前進(jìn)程的優(yōu)先級(jí)低于優(yōu)先級(jí)最高的實(shí)時(shí)就緒進(jìn)程，則內(nèi)核搶占當(dāng)前進(jìn)程。在分時(shí)類中，進(jìn)程的優(yōu)先級(jí)是可變的。每當(dāng)一個(gè)進(jìn)程用完它的時(shí)間片時(shí)，調(diào)度器降低它的優(yōu)先級(jí)；如果一個(gè)進(jìn)程在一個(gè)事件或資源上阻塞時(shí)，則調(diào)度器提高它的優(yōu)先級(jí)。分配給分時(shí)進(jìn)程的時(shí)間量取決于它的優(yōu)先級(jí)，其范圍從給優(yōu)先級(jí)0分配的100ms到給優(yōu)先級(jí)59分配的50ms。每個(gè)實(shí)時(shí)進(jìn)程都有一個(gè)固定的優(yōu)先級(jí)和固定的時(shí)間量。4.5.3Linux搶占式調(diào)度<41

>Linux系統(tǒng)中的進(jìn)程，既可以在用戶態(tài)下運(yùn)行，又可以在核心態(tài)下運(yùn)行。而核心態(tài)的權(quán)限高于用戶態(tài)的權(quán)限。進(jìn)程每次執(zhí)行系統(tǒng)調(diào)用時(shí)，其運(yùn)行方式就會(huì)發(fā)生變化，從用戶態(tài)切換到核心態(tài)4.5.3Linux搶占式調(diào)度<42

>1．調(diào)度方式Linux系統(tǒng)的調(diào)度方式基本上采用“搶占式優(yōu)先級(jí)”方式Linux系統(tǒng)中的調(diào)度基本上繼承了UNIX系統(tǒng)的以優(yōu)先級(jí)為基礎(chǔ)的調(diào)度4.5.3Linux搶占式調(diào)度<43

>2．調(diào)度策略Linux系統(tǒng)針對(duì)不同類別的進(jìn)程提供了三種不同的調(diào)度策略，即SCHED_FIFO,SCHED_RR及SCHED_OTHER4.5.3Linux搶占式調(diào)度<44

>3．調(diào)度時(shí)機(jī)①當(dāng)前進(jìn)程調(diào)用系統(tǒng)調(diào)用nanosleep()或者pause()，使自己進(jìn)入睡眠狀態(tài)，主動(dòng)讓出一段時(shí)間的CPU的使用權(quán)②進(jìn)程終止，永久地放棄對(duì)CPU的使用③在時(shí)鐘中斷處理程序執(zhí)行過程中，發(fā)現(xiàn)當(dāng)前進(jìn)程連續(xù)運(yùn)行的時(shí)間過長④當(dāng)喚醒一個(gè)睡眠進(jìn)程時(shí)，發(fā)現(xiàn)被喚醒的進(jìn)程比當(dāng)前進(jìn)程更有資格運(yùn)行⑤一個(gè)進(jìn)程通過執(zhí)行系統(tǒng)調(diào)用來改變調(diào)度策略或者降低自身的優(yōu)先級(jí)（如nice命令），從而引起立即調(diào)度4.5.3Linux搶占式調(diào)度<45

>4．調(diào)度算法首先查找所有在就緒隊(duì)列中的進(jìn)程，從中選出優(yōu)先級(jí)最高且在內(nèi)存的一個(gè)進(jìn)程。如果隊(duì)列中有實(shí)時(shí)進(jìn)程，則實(shí)時(shí)進(jìn)程將優(yōu)先運(yùn)行。如果最需要運(yùn)行的進(jìn)程不是當(dāng)前進(jìn)程，則當(dāng)前進(jìn)程就被掛起，并且保存它的現(xiàn)場——所涉及的一切機(jī)器狀態(tài)，包括程序計(jì)數(shù)器和CPU寄存器等，然后為選中的進(jìn)程恢復(fù)運(yùn)行現(xiàn)場。4.5.4Windows調(diào)度<46

>Windows實(shí)現(xiàn)了可搶占式調(diào)度器，它具有靈活的優(yōu)先級(jí)系統(tǒng)，在每一級(jí)上都包括了輪轉(zhuǎn)調(diào)度方法，在某些級(jí)上，優(yōu)先級(jí)可以基于它們當(dāng)前的線程活動(dòng)而動(dòng)態(tài)變化Windows中的優(yōu)先級(jí)被組織成兩段：實(shí)時(shí)和可變4.5.4Windows調(diào)度<47

>在實(shí)時(shí)優(yōu)先級(jí)類中，所有線程具有固定的優(yōu)先級(jí)，并且它們的優(yōu)先級(jí)永遠(yuǎn)不會(huì)改變，某一給定優(yōu)先級(jí)的所有活動(dòng)線程在一個(gè)輪轉(zhuǎn)隊(duì)列中在可變優(yōu)先級(jí)類中，一個(gè)線程的優(yōu)先級(jí)在開始時(shí)是最初指定的值，但在它的生命周期中可能會(huì)發(fā)生變化，上升或者下降背景-1：北京大學(xué)西門PART4.6多處理器調(diào)度算法4.6多處理器調(diào)度算法<49

>●松耦合、分布式多處理器、集群●專門功能的處理器●緊耦合多處理4.6.1粒度<50

>●把進(jìn)程分配到處理器●在單個(gè)處理器上使用多道程序設(shè)計(jì)●一個(gè)進(jìn)程的實(shí)際分派4.6.2設(shè)計(jì)問題<51

>●無約束并行性●

粗粒度和非常粗粒度并行性●中等粒度并行性●細(xì)粒度的并行性4.6.2設(shè)計(jì)問題<52

>靜態(tài)分配的缺點(diǎn)是一個(gè)處理器可能處于空閑狀態(tài)調(diào)度進(jìn)程的開銷與它被調(diào)度到哪個(gè)處理器無關(guān)4.6.2設(shè)計(jì)問題<53

>不論是否給進(jìn)程分配專用的處理器，都需要通過某種方法把進(jìn)程分配給處理器這種方法有兩個(gè)缺點(diǎn)：（1）主處理器的失敗導(dǎo)致整個(gè)系統(tǒng)失敗（2）主處理器可能成為性能瓶頸4.6.2設(shè)計(jì)問題<54

>1、如何能為應(yīng)用提供最好的平均性能2、選擇哪一個(gè)進(jìn)程運(yùn)行4.6.3進(jìn)程調(diào)度<55

>在大多數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進(jìn)程并不是被指定到一個(gè)專門的處理器。不是所有處理器只有一個(gè)隊(duì)列，或者使用某種類型的優(yōu)先級(jí)方案，而是有多條基于優(yōu)先級(jí)的隊(duì)列，并且都送進(jìn)相同的處理器池中。在任何情況下，都可以把系統(tǒng)看作是多服務(wù)器排隊(duì)結(jié)構(gòu)4.6.4線程調(diào)度<56

>在單處理器中，線程可以用作輔助構(gòu)造程序，并在處理過程中重疊執(zhí)行I/O。由于在進(jìn)行線程切換時(shí)的性能損失遠(yuǎn)遠(yuǎn)小于進(jìn)程切換的開銷，因此可以用很少的代價(jià)實(shí)現(xiàn)這些優(yōu)點(diǎn)在多處理器系統(tǒng)中，線程的全部能力得到了更好的展現(xiàn)。在這個(gè)環(huán)境中，線程可以用于開發(fā)應(yīng)用程序中真正的并行性4.6.4線程調(diào)度<57

>●加載共享●組調(diào)度●專用處理器分配●動(dòng)態(tài)調(diào)度4.6.4線程調(diào)度<58

>●負(fù)載均勻●不需要集中調(diào)度器●可以使用基于優(yōu)先級(jí)的方案●先來先服務(wù)●最少線程數(shù)優(yōu)先●可搶占的最少線程數(shù)優(yōu)先4.6.4線程調(diào)度<59

>加載共享有以下缺點(diǎn)：●中心隊(duì)列占據(jù)了必須互斥訪問的存儲(chǔ)器區(qū)域●被搶占的線程可能不在同一個(gè)處理器上恢復(fù)執(zhí)行●如果一個(gè)程序的線程間需要高度的合作，所涉及的進(jìn)程切換就會(huì)嚴(yán)重影響性能。背景-1：北京大學(xué)西門PART4.7實(shí)時(shí)調(diào)度算法4.7.1實(shí)時(shí)調(diào)度方法<61

>（1）一個(gè)系統(tǒng)是否執(zhí)行可調(diào)度性分析（2）如果執(zhí)行，它是靜態(tài)的還是動(dòng)態(tài)的（3）分析結(jié)果自身是否根據(jù)在運(yùn)行時(shí)分派的任務(wù)產(chǎn)生一個(gè)調(diào)度或計(jì)劃4.7.1實(shí)時(shí)調(diào)度方法<62

>●靜態(tài)表驅(qū)動(dòng)法●靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶占法●基于動(dòng)態(tài)規(guī)劃調(diào)度法●動(dòng)態(tài)盡力調(diào)度法4.7.1實(shí)時(shí)調(diào)度方法<63

>靜態(tài)表驅(qū)動(dòng)調(diào)度適用于周期性的任務(wù)靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶占調(diào)度與大多數(shù)非實(shí)時(shí)多道程序系統(tǒng)中的優(yōu)先級(jí)驅(qū)動(dòng)的搶占式調(diào)度所用的機(jī)制相同4.7.1實(shí)時(shí)調(diào)度方法<64

>基于動(dòng)態(tài)規(guī)劃調(diào)度，在一個(gè)任務(wù)已到達(dá)但未執(zhí)行時(shí)，試圖創(chuàng)建一個(gè)包含前面被調(diào)度任務(wù)和新到達(dá)任務(wù)的調(diào)度如果新到達(dá)的任務(wù)可以按這種方式調(diào)度：滿足它的最后期限，但是當(dāng)前被調(diào)度的任務(wù)也不會(huì)錯(cuò)過它的最后期限，則修訂這個(gè)調(diào)度以適應(yīng)新任務(wù)4.7.2限期調(diào)度<65

>大多數(shù)當(dāng)代實(shí)時(shí)操作系統(tǒng)的設(shè)計(jì)目標(biāo)是盡可能快速地啟動(dòng)實(shí)時(shí)任務(wù)，因此強(qiáng)調(diào)快速中斷處理和任務(wù)分派。事實(shí)上，在評(píng)估實(shí)時(shí)操作系統(tǒng)時(shí)，并沒有一個(gè)特別有用的度量4.7.2限期調(diào)度<66

>●就緒時(shí)間●啟動(dòng)最后期限●完成最后期限●處理時(shí)間●資源需求●優(yōu)先級(jí)●子任務(wù)結(jié)構(gòu)4.7.2限期調(diào)度<67

>當(dāng)考慮到最后期限時(shí)，實(shí)時(shí)調(diào)度功能可以分成許多維：下一次調(diào)度哪個(gè)任務(wù)以及允許哪種類型的搶占另一個(gè)重要的設(shè)計(jì)問題是搶占4.7.3速率單調(diào)調(diào)度<68

>為周期性任務(wù)解決多任務(wù)調(diào)度沖突的一個(gè)非常好的方法是速率單調(diào)調(diào)度RMS優(yōu)先級(jí)最高的任務(wù)是周期最短的任務(wù)，優(yōu)先級(jí)次高的任務(wù)是周期次短的任務(wù)，依次類推。當(dāng)有多個(gè)任務(wù)可供執(zhí)行時(shí)，周期最短的任務(wù)首先得到服務(wù)4.7.4優(yōu)先級(jí)逆轉(zhuǎn)<69

>優(yōu)先級(jí)逆轉(zhuǎn)（priorityinversion）在任何基于優(yōu)先級(jí)的可搶占的調(diào)度方案中都能發(fā)生的一種現(xiàn)象，但是它與實(shí)時(shí)調(diào)度的上下文關(guān)聯(lián)特別大在任何優(yōu)先級(jí)調(diào)度方案中，系統(tǒng)應(yīng)該不停地執(zhí)行具有最高優(yōu)先級(jí)的任務(wù)4.7.4優(yōu)先級(jí)逆轉(zhuǎn)<70

>一個(gè)更加嚴(yán)重的情況被稱之為無界限優(yōu)先級(jí)逆轉(zhuǎn)（Unboundedp