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