分類(lèi)

可以按不同方式對(duì)實(shí)時(shí)調(diào)度算法加以分類(lèi)：
①根據(jù)實(shí)時(shí)任務(wù)性質(zhì)，可將實(shí)時(shí)調(diào)度的算法分為硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度算法；
②按調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。

1.非搶占式調(diào)度算法

(1）非搶占式輪轉(zhuǎn)調(diào)度算法：由一臺(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)度程序再選擇下一個(gè)隊(duì)首任務(wù)運(yùn)行。這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中。
(2) 非搶占式優(yōu)先調(diào)度算法：如果在系統(tǒng)中還含有少數(shù)具有一定要求的實(shí)時(shí)任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法，系統(tǒng)為這些任務(wù)賦予了較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后，便可去調(diào)度執(zhí)行隊(duì)首的高優(yōu)先進(jìn)程。這種調(diào)度算法在做了精心的處理后有可能使其響應(yīng)時(shí)間減少到數(shù)秒至數(shù)百毫秒，因而可用于有一定要求的實(shí)時(shí)控制系統(tǒng)中。

2.搶占式調(diào)度算法

可根據(jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法：
(1）基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法：在某實(shí)時(shí)任務(wù)到達(dá)后，如果它的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷發(fā)生時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先級(jí)任務(wù)。該算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十至幾毫秒，可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。
(2) 立即搶占（ Immediate Preemption ）的優(yōu)先級(jí)調(diào)度算法：在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便能立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。這種算法能獲得非常快的響應(yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。圖3-5中的（ a )、(b)、( c )、(d）分別示出了四種情況的調(diào)度時(shí)間。

---

最早截止時(shí)間優(yōu)先（Earliest Deadline First）算法

該算法是根據(jù)任務(wù)的截止時(shí)間確定任務(wù)的優(yōu)先級(jí)，任務(wù)的截止時(shí)間愈早，其優(yōu)先級(jí)愈高，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的隊(duì)首。調(diào)度程序在選擇任務(wù)時(shí)，總是選擇就緒隊(duì)中的第一個(gè)任務(wù)，為之分配處理機(jī)。最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度方式中，包可用于非搶占式調(diào)度方式中。

1．非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)

圖3-6示出了將該算法用于非搶占調(diào)度方式之例。該例中具有四個(gè)非周期任務(wù)，它們先后到達(dá)。系統(tǒng)先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、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í)行。

2.搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)

圖3-7示出了將該算法用于搶占調(diào)度方式之例。在該例中有兩個(gè)周期任務(wù)，任務(wù)A和任務(wù)B的周期時(shí)間分別為20ms和50ms，每個(gè)周期的處理時(shí)間分別為10ms和25ms。

圖3-7示出了將最早截止時(shí)間（最后期限）優(yōu)先算法用于搶占調(diào)度的示意圖。圖中的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、截止時(shí)間和執(zhí)行時(shí)間圖。其中任務(wù) A 的到達(dá)時(shí)間為0、20ms、40ms…，任務(wù) A 的最后期限為20ms、40ms、60ms…，任務(wù) B 的到達(dá)時(shí)間為0、50ms、100 ms ……，任務(wù) B 的最后期限為50ms、100 ms …。
為了說(shuō)明通常的優(yōu)先級(jí)調(diào)度不能適用于實(shí)時(shí)系統(tǒng)，該圖特增加了第二和第三行。在第二行中，假定任務(wù) A 具有較高的優(yōu)先級(jí)，所以在t＝0ms時(shí)，先調(diào)度 A₁ 執(zhí)行，在 A₁ 完成后(t=10 ms ）才調(diào)度 B₁ 執(zhí)行。在t＝20ms時(shí)，又重新調(diào)度 A ₂執(zhí)行，在t＝30ms時(shí)， A₂ 完成，又調(diào)度 B₁ 執(zhí)行。在 t =40ms時(shí)，又調(diào)度 A₃ 執(zhí)行，在t＝50ms時(shí)，雖然 A₃ 已完成，但 B₁ 已錯(cuò)過(guò)了它的最后期限。這說(shuō)明利用通常的優(yōu)先級(jí)調(diào)度已經(jīng)失敗。第三行與第二行類(lèi)似，只是假定任務(wù) B 具有較高的優(yōu)先級(jí)。
第四行是采用最早截止時(shí)間優(yōu)先算法的時(shí)間圖。在t＝0時(shí)， A₁ 和 B₁ 同時(shí)到達(dá)，由于 A₁ 的截止時(shí)間比 B₁ 早，故調(diào)度 A₁ 執(zhí)行。在 t =10時(shí)， A₁ 完成又調(diào)度 B₁ 執(zhí)行。在t＝20時(shí)， A₂ 到達(dá)，由于 A₂ 的截止時(shí)間比 B₁ 早， B₁ 被中斷而調(diào)度 A₂ 執(zhí)行。在t＝30時(shí)， A₂ 完成，又重新調(diào)度 B₁ 執(zhí)行。在t＝40時(shí)， A₃又到達(dá)，但 B₁ 的截止時(shí)間要比 A₃ 早，仍應(yīng)讓 B₁ 繼續(xù)執(zhí)行直到完成（t=45)，然后再調(diào)度 A₃ 執(zhí)行。在t＝55時(shí)， A₃ 完成又調(diào)度 B₂ 執(zhí)行。在該例中，利用最早截止時(shí)間優(yōu)先算法可以滿足系統(tǒng)的要求。

---

最低松弛度優(yōu)先LLF（Least Laxity First）算法

該算法在確定任務(wù)的優(yōu)先級(jí)時(shí)，根據(jù)的是任務(wù)的緊急（或松弛）程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間是100 ms ,因此調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度（松弛程度）為100 ms 。又如另一任務(wù)在400 ms 時(shí)必須完成，它本身需要運(yùn)行150ms，則其松弛程度為250ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在最前面，調(diào)度程序選擇隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。
該算法主要用于可搶占調(diào)度方式中。假如在一個(gè)實(shí)時(shí)系統(tǒng)中有兩個(gè)周期性實(shí)時(shí)任務(wù) A 和 B ，任務(wù) A 要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms，任務(wù) B 要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25 ms 。由此可知，任務(wù) A 和 B 每次必須完成的時(shí)間分別為： A₁、A₂ 、A₃、…和 B₁ 、B₂ 、B₃ …，見(jiàn)圖3-8。為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。

在剛開(kāi)始時(shí)（ t =0), A ₁必須在20ms時(shí)完成，而它本身運(yùn)行又需10ms，可算出 A 的松弛度為10ms。 B₁必須在50ms時(shí)完成，而它本身運(yùn)行就需25ms，可算出 B₁ 的松弛度為25 ms ，故調(diào)度程序應(yīng)先調(diào)度 A₁ 執(zhí)行。在＝10 ms 時(shí)， A₂ 的松弛度可按下式算出：
A₂的松弛度＝必須完成時(shí)間﹣其本身的運(yùn)行時(shí)間﹣當(dāng)前時(shí)間=40 ms -10 ms -10 ms =20 ms
類(lèi)似地，可算出 B₁ 的松弛度為15 ms ，故調(diào)度程序應(yīng)選擇 B₁ 運(yùn)行。在t₃=30ms時(shí)， A₂ 的松弛度已減為0即40-10-30)，而 B₁ 的松弛度為15ms（即50-5-30)，于是調(diào)度程序應(yīng)搶占 B₁ 的處理機(jī)而調(diào)度 A₂ 運(yùn)行。在t₄=40 ms 時(shí)， A₃的松弛度為10ms（即60-10-40)，而 B₁ 的松弛度僅為5ms（即50-5-40)，故又應(yīng)重新調(diào)度 B₁ 執(zhí)行。在 t₅ =45ms時(shí)， B₁ 執(zhí)行完成。而此時(shí) A₃ 的松弛度已減為5ms（即60-10-45)，而 B₂ 的松弛度為30ms（即100-25-45)，于是又應(yīng)調(diào)度 A₃執(zhí)行。在t₆＝55 ms 時(shí)，任務(wù) A 尚未進(jìn)入第4周期，而任務(wù) B 已進(jìn)入第2周期，故再調(diào)度 B₂ 執(zhí)行。在 t ₇=70ms時(shí)， A₄ 的松弛度已減至0ms（即80-10-70)，而B(niǎo)₂的松弛度為20ms（即100-10-70)，故此時(shí)調(diào)度程序又應(yīng)搶占 B₂ 的處理機(jī)而調(diào)度 A₄ 執(zhí)行。圖3-9示出了具有兩個(gè)周期性實(shí)時(shí)任務(wù)的調(diào)度情況。

---

優(yōu)先級(jí)倒置（priority inversion problem）

1.優(yōu)先級(jí)倒置的形成

當(dāng)前 OS 廣泛采用優(yōu)先級(jí)調(diào)度算法和搶占方式，然而在系統(tǒng)中存在著影響進(jìn)程運(yùn)行的資源而可能產(chǎn)生“優(yōu)先級(jí)倒置”的現(xiàn)象，即高優(yōu)先級(jí)進(jìn)程（或線程）被低優(yōu)先級(jí)進(jìn)程（或線程）廷遲或阻塞。我們通過(guò)一個(gè)例子來(lái)說(shuō)明該問(wèn)題。假如有三個(gè)完全獨(dú)立的進(jìn)程 P₁、P₂ 和 P₃ , P ₁的優(yōu)先級(jí)最高， P ₂次之， P ₃最低。 P₁ 和 P₃ 通過(guò)共享的一個(gè)臨界資源進(jìn)行交互。下面是一段代碼：

P1: ...P(mutex); CS-1; V(mutex);... P2: ...program2...; P3: ...P(mutex); CS-3; V(mutex);...

假如P₃最先執(zhí)行，在執(zhí)行了 P ( mutex ）操作后，進(jìn)入到臨界區(qū) CS -3。在時(shí)刻 a , P₂ 就緒，因?yàn)樗?P ₃的優(yōu)先級(jí)高， P₂ 搶占了 P₃ 的處理機(jī)而運(yùn)行，如圖3－10所示。在時(shí)刻 b , P₁ 就緒，因?yàn)樗直?P₂ 的優(yōu)先級(jí)高， P₁ 搶占了 P₂ 的處理機(jī)而運(yùn)行。在時(shí)刻 c , P₁ 執(zhí)行 P ( mutex )操作，試圖進(jìn)入臨界區(qū) CS -1，但因?yàn)橄鄳?yīng)的臨界資源已被 P₃ 占用，故 P₁ 將被阻塞。由 P ₂繼續(xù)運(yùn)行，直到時(shí)刻 d 運(yùn)行結(jié)束。然后由 P ₃接著運(yùn)行，到時(shí)刻 e 時(shí) P₃ 退出臨界區(qū)，并喚醒P₁。因?yàn)樗?P ₃的優(yōu)先級(jí)高，故它搶占了 P₃ 的處理機(jī)而運(yùn)行。
根據(jù)優(yōu)先級(jí)原則，高優(yōu)先級(jí)進(jìn)程應(yīng)當(dāng)能優(yōu)先執(zhí)行，但在此例中， P₁和 P₃ 共享著“臨界資源”，而出現(xiàn)了不合常理的現(xiàn)象，高優(yōu)先級(jí)進(jìn)程 P ₁因 P₃ 進(jìn)程被阻塞了，又因?yàn)檫M(jìn)程的存在而延長(zhǎng)了P₁被阻塞的時(shí)間，而且被延長(zhǎng)的時(shí)間是不可預(yù)知和無(wú)法限定的。由此所產(chǎn)生的“優(yōu)先級(jí)倒置”的現(xiàn)象是非常有害的，它不應(yīng)該出現(xiàn)在實(shí)時(shí)系統(tǒng)中。

2.優(yōu)先級(jí)倒置的解決辦法

一種簡(jiǎn)單的解決方法是規(guī)定：假如進(jìn)程 P₃在進(jìn)入臨界區(qū)后 P₃所占用的處理機(jī)就不允許被搶占。由圖3-10可以看出， P₂ 即使優(yōu)先級(jí)高于 P ₃也不能執(zhí)行。于是 P ₃就有可能會(huì)較快地退出臨界區(qū)，不會(huì)出現(xiàn)上述情況。如果系統(tǒng)中的臨界區(qū)都較短且不多，該方法是可行的。反之，如果 P₃ 臨界區(qū)非常長(zhǎng)，則高優(yōu)先級(jí)進(jìn)程 P₁ 仍會(huì)等待很長(zhǎng)的時(shí)間，其效果是無(wú)法令人満意的。
一個(gè)比較實(shí)用的方法是建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上的。該方法規(guī)定，當(dāng)高優(yōu)先級(jí)進(jìn)程 P₁要進(jìn)入臨界區(qū)，去使用臨界資源 R ，如果已有一個(gè)低優(yōu)先級(jí)進(jìn)程 P ₃正在使用該資源，此時(shí)一方面 P₁ 被阻塞，另一方面由 P₃ 繼承 P₁ 的優(yōu)先級(jí)，并一直保持到 P ₃退出臨界區(qū)。這樣做的目的在于不讓比 P₃ 優(yōu)先級(jí)稍高，但比 P₁優(yōu)先級(jí)低的進(jìn)程如 P₂ 進(jìn)程插進(jìn)來(lái)，導(dǎo)致延緩 P₃ 退出臨界區(qū)。圖3-11示出了采用動(dòng)態(tài)優(yōu)先級(jí)繼承方法后， P ₁、 P₂、P₃ 三個(gè)進(jìn)程的運(yùn)行情況。由圖可以看出，在時(shí)刻 c , P₁ 被阻塞，但由于 P₃ 已繼承了 P₁ 的優(yōu)先級(jí)，它比 P₂ 優(yōu)先級(jí)高，這樣就避免了 P₂ 的插入，使 P₃ 在時(shí)刻 d 進(jìn)入臨界區(qū)。該方法已在一些操作系統(tǒng)中得到應(yīng)用，而在實(shí)時(shí)操作系統(tǒng)中是必須的。

總結(jié)

以上是生活随笔為你收集整理的os 实时调度算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。