第十八講處理器調(diào)度算法(下)

教學目的讓學生掌握常用的實時調(diào)度算法讓學生掌握常用的多處理器調(diào)度算法教學重點單比率調(diào)度算法、限期調(diào)度算法、最少裕度調(diào)度算法多處理機調(diào)度算法的設(shè)計要點負載共享調(diào)度算法，群調(diào)度算法教學難點多處理機調(diào)度算法的設(shè)計要點2.8處理器調(diào)度算法（下）2.8處理器調(diào)度算法2.8.1低級調(diào)度的功能和類型2.8.2作業(yè)調(diào)度和低級調(diào)度算法2.8.3實時調(diào)度算法2.8.4多處理機調(diào)度算法

2.8.3

實時調(diào)度算法

實時系統(tǒng)是那些時間因素非常關(guān)鍵的系統(tǒng)。實時系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應即使正確，也和沒有響應一樣糟糕。硬實時系統(tǒng)和軟實時系統(tǒng)實時系統(tǒng)通常分為硬實時系統(tǒng)和軟實時系統(tǒng)。前者意味著存在必須滿足的時間限制；后者意味著偶爾超過時間限制時可以容忍的。

周期性和非周期性事件實時系統(tǒng)響應的事件可劃分為周期性事件和非周期性事件。例如，m個周期性事件，事件i的周期為Pi，每個事件需要Ci秒的CPU時間來處理，則只有滿足以下條件：

C1/P1+C2/P2+…+Cm/Pm≤1

時，才可能處理所有的負載。滿足該條件的實時系統(tǒng)稱作任務可調(diào)度的。

實時調(diào)度算法(1)

1）單比率調(diào)度算法基本思想：為每個進程分配一個與事件發(fā)生頻率成正比的優(yōu)先數(shù)。例如，周期為20ms的進程優(yōu)先數(shù)為50，周期為100ms的進程優(yōu)先數(shù)為10，運行時調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進程，并采取搶占式分配策略。實時調(diào)度算法(2)

2）限期調(diào)度算法

基本思想：當一個事件發(fā)生時，對應的進程就按照截止期限被加入就緒進程隊列。對于一個周期性事件，其截止期限即為事件下一次發(fā)生的時間。該調(diào)度算法首先運行隊首進程，即截止時間最近的那個進程。實時調(diào)度算法(3)

3）最少裕度法

基本思想：首先計算各個進程的富裕時間，即裕度（laxity），然后選擇裕度最少的進程執(zhí)行。裕度=截止時間-(就緒時間+計算時間)2.8.4

多處理器調(diào)度

1多處理機調(diào)度的設(shè)計要點

1)如何為進程分配處理機

2)在單個處理機上是否使用多道程序設(shè)計技術(shù)

3)如何實際指派進程如何為進程分配處理機CPU1CPU2CPU3...CPUn就緒隊列1就緒隊列2就緒隊列3...就緒隊列n靜態(tài)分配法CPU1CPU2CPU3...CPUn就緒隊列...動態(tài)分配法一個程序的多個線程同時在多個處理機上運行（性能佳）在單個處理機上運行單個程序，讓其線程多道運行在單個處理機上是否使用多道程序設(shè)計技術(shù)不再采用復雜的調(diào)度算法，而采用簡單的優(yōu)先數(shù)法或FCFS算法如何實際指派進程多處理器調(diào)度算法(1)1）負載共享調(diào)度算法

基本思想：進程并不指派到特定處理機上，系統(tǒng)維護全局性進程就緒隊列，當處理機空閑時，就選擇進程的一個線程去運行。優(yōu)點：負載均衡，不須集中調(diào)度缺點：就緒隊列必須被互斥訪問，被剝奪線程很難在原處理機上運行，一個進程的所有線程未必能同時獲得處理機多處理器調(diào)度算法(2)2）群調(diào)度算法

基本思想：一群相關(guān)線程基于一對一的原則，被同時調(diào)度到一組處理機上運行。它具有的優(yōu)點：

?當緊密相關(guān)的進程同時執(zhí)行時，同步造成的等待將減少，進程切換也相應減少，系統(tǒng)性能得到提高。

?由于一次性同時調(diào)度一組處理器，調(diào)度的代價也將減少。

群調(diào)度的例子

統(tǒng)一劃分進程1進程2空閑空閑空閑浪費時間37.5%浪費時間15%空閑空閑空閑50%50%80%20%例：4個處理機，2個進程，進程1有4個線程，進程2有1個線程。

加權(quán)劃分進程1進程2多處理器調(diào)度算法(3)

3）處理器專派調(diào)度算法基本思想：給同屬一個進程的一組線程，同時分派到一組處理機上運行，每個線程獲得一個處理機，且它專用于處理這個線程，直到進程運行結(jié)束，這是群調(diào)度的一種極端形式。采用這一算法，處理器將不適用多道程序設(shè)計，即該應用的一個線程阻塞后，線程對應的處理器不會被調(diào)度給其他線程，而處于空閑狀態(tài)。多處理器調(diào)度算法(4)

4）動態(tài)調(diào)度算法(1)

基本思想：由操作系統(tǒng)和應用進程共同完成調(diào)度。操作系統(tǒng)負責在應用進程之間劃分處理器。應用進程在分配給它的處理器上執(zhí)行可運行線程的子集，哪一些線程應該執(zhí)行，哪一些線程應該掛起完全是應用進程自己的事。多處理器調(diào)度算法(5)

動態(tài)調(diào)度算法(2)

?

如果有空閑處理器，滿足要求。否則，對新到達進程，從當前分配了一個以上處理器的進程中收回一個，并把它分