【文章內(nèi)容簡介】 5 2．多級反饋隊列調(diào)度算法 ?在多級反饋隊列調(diào)度下，就緒隊列被分為若干個獨立子隊列。 ? 但進(jìn)程不是根據(jù)其性質(zhì)或類型固定地分屬于一個隊列，而是根據(jù)其使用CPU時間的長短來動態(tài)地決定進(jìn)程屬于哪級隊列。 2．多級反饋隊列調(diào)度算法 （ 1） * 首先系統(tǒng)中設(shè)置多個就緒隊列 * 每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一級隊列，時間片最小，隨著隊列級別的降低，時間片加大 * 各個隊列按照先進(jìn)先出調(diào)度算法，最后一級采用時間片輪轉(zhuǎn) （ 2） * 一個新進(jìn)程就緒后進(jìn)入第一級隊列 末尾 * 進(jìn)程由于等待而放棄 CPU后，進(jìn)入等待隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列 * 如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾，如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列， …… 2．多級反饋隊列調(diào)度算法 2．多級反饋隊列調(diào)度算法 （ 3） *系統(tǒng)從第一級調(diào)度， 僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運行；僅當(dāng)?shù)?1～ (i1)隊列均空時，才會調(diào)度第 i隊列中的進(jìn)程運行。 * 當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒時，可以搶占 CPU，被搶占進(jìn)程回到原來一級就緒隊列末尾。 2．多級反饋隊列調(diào)度算法 3．多級反饋隊列調(diào)度算法的性能 ?多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。 ?(1) 終端型作業(yè)用戶 。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè) (進(jìn)程 )在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。 (2) 短批處理作業(yè)用戶 。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一隊列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間。 (3) 長批處理作業(yè)用戶 。對于長作業(yè)，它將依次在第 1， 2， … ， n個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。 3．多級反饋隊列調(diào)度算法的性能 進(jìn)程調(diào)度的時機(jī) ?當(dāng)一個進(jìn)程運行完畢，或由于某種錯誤而終止運行 ?當(dāng)一個進(jìn)程在運行中處于等待狀態(tài)（等待 I/O） ?分時系統(tǒng)中時間片到 ?當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒（可搶占式） ?在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作（ P操作，阻塞原語，喚醒原語） 實 時 調(diào) 度 ? 實現(xiàn)實時調(diào)度的基本條件 1． 提供必要的信息 2．系統(tǒng)處理能力強(qiáng) 3．采用搶占式調(diào)度機(jī)制 4．具有快速切換機(jī)制 1．提供必要的信息 (1) 就緒時間。 (2) 開始截止時間和完成截止時間。 (3) 處理時間。 (4) 資源要求。 (5) 優(yōu)先級。 2．系統(tǒng)處理能力強(qiáng) 在實時系統(tǒng)中，若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實時任務(wù)不能得到及時處理。假定系統(tǒng)中有 m個周期性的硬實時任務(wù)，它們的處理時間可表示為 Ci，周期時間表示為 Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件： 11???mi iiPC2．系統(tǒng)處理能力強(qiáng) ?對于不能滿足實時性要求的解決方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須 增強(qiáng)其處理能力 ，以顯著地減少對每一個任務(wù)的處理時間；其二是 采用多處理機(jī)系統(tǒng) 。假定系統(tǒng)中的處理機(jī)數(shù)為 N，則應(yīng)將上述的限制條件改為： NPCmi ii ??? 13．采用搶占式調(diào)度機(jī)制 ?在含有硬實時任務(wù)的實時系統(tǒng)中，廣泛采用搶占機(jī)制。這樣便可滿足該硬實時任務(wù)對截止時間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。 ?對于一些小型實時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷。 4．具有快速切換機(jī)制 為保證要求較高的硬實時任務(wù)能及時運行 ，在實時系統(tǒng)中還應(yīng)具有快速切換機(jī)制 。 該機(jī)制應(yīng)具有如下兩方面的能力： ?(1) 對外部中斷的快速響應(yīng)能力。 ?(2) 快速的任務(wù)分派能力。 實時調(diào)度算法的分類 1． 非搶占式調(diào)度算法 1) 非搶占式輪轉(zhuǎn)調(diào)度算法 該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺計算機(jī)控制若干個相同的 (或類似的 )對象，為每一個被控對象建立一個實時任務(wù)，并將它們排成一個輪轉(zhuǎn)隊列。調(diào)度程序每次選擇隊列中的第一個任務(wù)投入運行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊列的末尾，等待下次調(diào)度運行，而調(diào)度程序再選擇下一個 (隊首 )任務(wù)運行。 1．非搶占式調(diào)度算法 ?2) 非搶占式優(yōu)先調(diào)度算法 ? 如果在實時系統(tǒng)中存在著要求較為嚴(yán)格(響應(yīng)時間為數(shù)百毫秒 )的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級。當(dāng)這些實時任務(wù)到達(dá)時，把它們安排在就緒隊列的隊首，等待當(dāng)前任務(wù)自我終止或運行完成后才能被調(diào)度執(zhí)行。 2．搶占式調(diào)度算法 在要求較嚴(yán)格的實時系統(tǒng)中 ， 應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法 。 可根據(jù)搶占發(fā)生時間的不同而進(jìn)一步分成以下兩種調(diào)度算法 。 1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 ?在某實時任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級高于當(dāng)前任務(wù)的優(yōu)先級，這時并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時鐘中斷到來時。 2．搶占式調(diào)度算法 ?2) 立即搶占的優(yōu)先權(quán)調(diào)度算法 ? 在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請求中斷的緊迫任務(wù)。這種算法能獲得非常快的響應(yīng)。 圖 實時進(jìn)程調(diào)度 時鐘 ?時鐘（ clock），又稱為定時器（ timer） (1) 時鐘負(fù)責(zé)提供一天的時間 (2) 防止一個進(jìn)程壟斷 CPU 時鐘既不是塊設(shè)備，也不是字符設(shè)備，但時鐘軟件通常也采用設(shè)備驅(qū)動程序的形式 1) 時鐘硬件 兩種類型： ?比較簡單的時鐘被連到 110V或 220V的電源線上，每個電壓周期產(chǎn)生一個中斷，頻率是 50Hz或60Hz ?另一種時鐘由三個部件構(gòu)成：晶體振蕩器、計數(shù)器和存儲寄存器 石英晶體產(chǎn)生的精確的周期信號，典型的范圍是 5到 100MHz 信號送到到計數(shù)器，使其遞減計數(shù)至 0。當(dāng)計數(shù)器變?yōu)?0時，產(chǎn)生一個 CPU中斷信號 ?可編程時鐘操作方式：在單脈沖方式（ oneshot mode）下，當(dāng)時鐘啟動時，它把存儲寄存器的值拷貝到計數(shù)器中，然后，晶體的每一個脈沖使計數(shù)器減 1。當(dāng)計數(shù)器為 0時，產(chǎn)生一個中斷，并停止工作，直到軟件再一次顯式啟動它。 ?在方波方式（ squarewave mode）下，當(dāng)計數(shù)器為 0并產(chǎn)生中斷時，存儲寄存器的值自動拷貝到計數(shù)器，這個過程不斷地重復(fù)下去。周期性的中斷稱為時鐘滴答（ clock tick ） ?可編程時鐘的優(yōu)點是其中斷頻率可由軟件控制。 2) 時鐘軟件 時鐘硬件所做的工作是每隔一定的時間間隔產(chǎn)生一個中斷。 涉及時間的其他所有工作都必須由軟件 時鐘驅(qū)動程序完成 3) 時鐘軟件功能 1．維護(hù)日期時間 2．防止進(jìn)程超時運行 3．對 CPU的使用情況記帳 4．處理用戶進(jìn)程提出的 ALARM系統(tǒng)調(diào)用 5．為系統(tǒng)本身各部分提供監(jiān)視定時器 6．繪制 CPU運行直方圖，完成監(jiān)視和統(tǒng)計信息收集 ?系統(tǒng)的其他部分也需要定時器稱為監(jiān)視定時器（ watchdog timer）。 常用的幾種實時調(diào)度算法 ?1．最早截止時間優(yōu)先即 EDF算法 ?該算法是根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。就緒隊列按各任務(wù)截止時間的早晚排序。調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊列中的第一個任務(wù)。該算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。 1．最早截止時間優(yōu)先算法 ? 1) 非搶占式調(diào)度方式用于非周期實時任務(wù) ? 有四個非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù) 1執(zhí)行，在任務(wù) 1執(zhí)行期間，任務(wù) 3又先后到達(dá)。由于任務(wù) 3的開始截止時間早于任務(wù) 2，故系統(tǒng)在任務(wù) 1后將調(diào)度任務(wù) 3執(zhí)行。在此期間又到達(dá)作業(yè) 4，其開始截止時間仍是早于任務(wù) 2的，故在任務(wù) 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù) 4執(zhí)行，最后才調(diào)度任務(wù) 2執(zhí)行。 1．最早截止時間優(yōu)先算法 圖 EDF算法用于非搶占調(diào)度方式 ? 2) 搶占式調(diào)度方式用于周期實時任務(wù) 有兩個周期性任務(wù)，任務(wù) A的周期時間為 20 ms，每個周期的處理時間為 10 ms；任務(wù) B的周期時間為 50 ms，每個周期的處理時間為 25 ms。圖中的第一行示出了兩個任務(wù)的到達(dá)時間、最后期限和執(zhí)行時間圖。 1．最早截止時間優(yōu)先算法 圖 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例 A1 B1 A2 B1 A3 B2 A4 B2 A5B1 A2 A3 B2 A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1 A2B2A3 A4 A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達(dá)時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A2 B1 A3 A4 A5 ， B2A5 ， B2A4A1( 錯過 )A2 B1 A3( 錯過 )A1 A2 B1( 錯過 )A3 A4 A5 ， B20 10 20 30 40 50 60 70 80 90 100 時間 t /ms使用完成最后期限最早和最后期限調(diào)度(A 有較高優(yōu)先級 )(B 有較高優(yōu)先級 )2．最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 該算法是根據(jù)任務(wù)緊急 (或松弛 )的程度，來確定任務(wù)的優(yōu)先級。 例如，一個任務(wù)在 200 ms時必須完成，而它本身所需的運行時間就有 100 ms，因此，調(diào)度程序必須在 100 ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度 (松弛程度 )為 100 ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列。 (LLF)算法 假如在一個實時系統(tǒng)中 ， 有兩個周期性實時任務(wù)A和 B， 任務(wù) A要求每 20 ms執(zhí)行一次 ， 執(zhí)行時間為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次 ， 執(zhí)行時間為 25 ms。 圖 A和 B任務(wù)每次必須完成的時間 在剛開始時 (t1=