操作系統(tǒng) 課件 第4章 進程線程調度

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

4.8習題目錄CONTENTSPART4.1進程調度的基本概念4.1進程調度的基本概念<4

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

>①保存現場②挑選進程③恢復現場4.1.2進程調度的時機<6

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

>兩級調度簡化隊列圖4.1.4三級調度模型<8

>三級調度簡化隊列示意圖背景-2：北京大學圖書館PART4.2進程調度算法的設計思路4.2.1調度策略的選擇<10

>①設計目標②公平性③均衡性④統(tǒng)籌兼顧⑤優(yōu)先級⑥開銷4.2.2性能評價標準<11

>①CPU利用率②吞吐量③周轉時間④就緒等待時間⑤響應時間背景-3：西門華表經典進程調度算法PART4.34.3.1先來先服務法<13

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

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

>FCFS調度算法的性能如表所示。FCFS算法比較有利于長作業(yè)（進程），而不利于短作業(yè)（進程）。因為短作業(yè)運行時間很短，如果讓它等待較長時間才得到服務，它的帶權周轉時間就會很長。另外，FCFS調度算法對CPU繁忙型作業(yè)（指需要大量CPU時間進行計算的作業(yè)）較有利，而不利于I/O繁忙型作業(yè)（指需要頻繁請求I/O的作業(yè)）。FCFS調度算法容易實現，但它的效率較低。作業(yè)到達時間運行時間開始時間完成時間周轉時間帶權周轉時間10240242412132427268.673232730289.33平均周轉時間=26平均帶權周轉時間=6.334.3.2時間片輪轉法<16

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

>四個進程運行情況4.3.2時間片輪轉法<18

>時間片輪轉法（Round-Robin，RR）主要用于分時系統(tǒng)中的進程調度。為實現輪轉調度，表RR法的性能指標到達時間進程名到達時間運行時間開始時間完成時間周轉時間帶權周轉時間時間片q=1

A012026262.17B05117173.4C03211113.67D06320203.33平均周轉時間=18.5平均帶權周轉時間=3.14時間片q=4A012026262.17B05420204C03811113.67D061122223.67平均周轉時間=19.75平均帶權周轉時間=3.384.3.2時間片輪轉法<19

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

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

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

>內部決定優(yōu)先級是利用某些可度量的量來定義一個進程的優(yōu)先級外部優(yōu)先級是按操作系統(tǒng)以外的標準設置的4.3.3優(yōu)先級法<23

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

>進程運行時間優(yōu)先數P1103P211P324P415P552一組進程列表

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

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

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

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

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

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

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

>

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

<33

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

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

4.5.1BSD多級反饋隊列法<36

>

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

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

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

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

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

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

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

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

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

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

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

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

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

>●把進程分配到處理器●在單個處理器上使用多道程序設計●一個進程的實際分派4.6.2設計問題<51

>●無約束并行性●

粗粒度和非常粗粒度并行性●中等粒度并行性●細粒度的并行性4.6.2設計問題<52

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

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

>1、如何能為應用提供最好的平均性能2、選擇哪一個進程運行4.6.3進程調度<55

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

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

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

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

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

>（1）一個系統(tǒng)是否執(zhí)行可調度性分析（2）如果執(zhí)行，它是靜態(tài)的還是動態(tài)的（3）分析結果自身是否根據在運行時分派的任務產生一個調度或計劃4.7.1實時調度方法<62

>●靜態(tài)表驅動法●靜態(tài)優(yōu)先級驅動搶占法●基于動態(tài)規(guī)劃調度法●動態(tài)盡力調度法4.7.1實時調度方法<63

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

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

>大多數當代實時操作系統(tǒng)的設計目標是盡可能快速地啟動實時任務，因此強調快速中斷處理和任務分派。事實上，在評估實時操作系統(tǒng)時，并沒有一個特別有用的度量4.7.2限期調度<66

>●就緒時間●啟動最后期限●完成最后期限●處理時間●資源需求●優(yōu)先級●子任務結構4.7.2限期調度<67

>當考慮到最后期限時，實時調度功能可以分成許多維：下一次調度哪個任務以及允許哪種類型的搶占另一個重要的設計問題是搶占4.7.3速率單調調度<68

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

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

>一個更加嚴重的情況被稱之為無界限優(yōu)先級逆轉（Unboundedp