引言

隨著嵌入式實(shí)時(shí)操作系統(tǒng)應(yīng)用的不斷深入，多個(gè)實(shí)時(shí)任務(wù)并發(fā)執(zhí)行，再加上任務(wù)之間不停地動(dòng)態(tài)切換，這對(duì)任務(wù)調(diào)度算法提出了較高的要求。實(shí)時(shí)操作系統(tǒng)中各個(gè)任務(wù)的優(yōu)先級(jí)是不同的，而且經(jīng)常會(huì)遇到超負(fù)荷的情況.。在這種超載情況下，使任務(wù)集內(nèi)各任務(wù)滿(mǎn)足各自的時(shí)限，嵌入式操作系統(tǒng)必須保證在確定的時(shí)間內(nèi)對(duì)事件進(jìn)行處理，因此必須要有一個(gè)良好的任務(wù)調(diào)度算法。周期任務(wù)和非周期任務(wù)是實(shí)時(shí)嵌入式系統(tǒng)中的常見(jiàn)任務(wù)類(lèi)型，系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度策略主要包括時(shí)間驅(qū)動(dòng)調(diào)度策略、優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度策略。常見(jiàn)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法有最早截止期優(yōu)先調(diào)度算法和最小空閑時(shí)間優(yōu)先算法、單調(diào)速率調(diào)度算法和最大價(jià)值優(yōu)先算法等。

實(shí)時(shí)系統(tǒng)的任務(wù)按產(chǎn)生請(qǐng)求的頻率可分為周期性任務(wù)與非周期性任務(wù)：周期性任務(wù)按照固定的請(qǐng)求間隔持續(xù)地產(chǎn)生請(qǐng)求，不同的任務(wù)請(qǐng)求間隔不一定相同。 非周期性任務(wù)在任意一段時(shí)間間隔內(nèi)可能產(chǎn)生不定數(shù)量的請(qǐng)求。按任務(wù)優(yōu)先級(jí)分配方式可分為靜態(tài)優(yōu)先級(jí)任務(wù)和動(dòng)態(tài)優(yōu)先級(jí)任務(wù)。

1）固定優(yōu)先級(jí)調(diào)度算法

在實(shí)時(shí)調(diào)度算法中，固定優(yōu)先級(jí)調(diào)度算法事先根據(jù)任務(wù)的屬性，如任務(wù)的周期、截止期限等為系統(tǒng)中的所有任務(wù)靜態(tài)分配一個(gè)優(yōu)先級(jí)。當(dāng)任務(wù)的截止期限等于周期時(shí)，提出了RMS調(diào)度算法，它根據(jù)任務(wù)的執(zhí)行周期長(zhǎng)短的不同來(lái)決定優(yōu)先級(jí)，即任務(wù)的周期越小優(yōu)先級(jí)越高，任務(wù)的周期越大優(yōu)先級(jí)越低。以RMS為代表的固定優(yōu)先級(jí)調(diào)度算法，一方面不僅具有運(yùn)行時(shí)間開(kāi)銷(xiāo)小和易于實(shí)現(xiàn)的優(yōu)點(diǎn)，而且在系統(tǒng)超載情況下，仍然可以保證高優(yōu)先級(jí)的任務(wù)得到執(zhí)行；但另一方面卻是不能充分地利用系統(tǒng)資源。

2）動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法

在實(shí)時(shí)調(diào)度算法中，動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法根據(jù)任務(wù)資源需求的變化以及任務(wù)的屬性，如任務(wù)周期、截止期限等動(dòng)態(tài)地決定任務(wù)的優(yōu)先級(jí)。當(dāng)任務(wù)的截止期限等于周期時(shí)，提出了EDF調(diào)度算法，該算法根據(jù)就緒隊(duì)列中任務(wù)的截止期限分配優(yōu)先級(jí)，距離絕對(duì)截止期限的最近的任務(wù)具有最高的優(yōu)先級(jí)，即任務(wù)的絕對(duì)截止期限越小優(yōu)先級(jí)越高，任務(wù)的絕對(duì)截止期限越大優(yōu)先級(jí)越低。以EDF為代表的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，一方面可以充分地利用系統(tǒng)的資源；但是另一方面在系統(tǒng)負(fù)荷嚴(yán)重超載時(shí)，系統(tǒng)性能很不穩(wěn)定，導(dǎo)致大多數(shù)任務(wù)在截止期限到來(lái)之時(shí)仍無(wú)法滿(mǎn)足。

3）靜態(tài)優(yōu)先調(diào)度算法與動(dòng)態(tài)優(yōu)先調(diào)度算法的比較

靜態(tài)調(diào)度是指系統(tǒng)脫機(jī)地進(jìn)行調(diào)度可行性分析后生成一個(gè)可調(diào)度表，在運(yùn)行的過(guò)程中，調(diào)度表中的信息不再發(fā)生任何變化。該類(lèi)調(diào)度算法假定系統(tǒng)實(shí)時(shí)任務(wù)的屬性是提前已知的并且在執(zhí)行過(guò)程中很少發(fā)生變化，特別適合于對(duì)那種確定問(wèn)題的求解，具有較好的可預(yù)測(cè)性。

單調(diào)速率調(diào)度算法(Rate Monotonic Algorithm, RM)

單調(diào)速率調(diào)度算法是一種被廣泛使用的調(diào)度算法, 并且已被證明是一種最佳的靜態(tài)優(yōu)先級(jí)算法。單調(diào)速率調(diào)度（RMS）算法是C.L.Liu和J.W.Layland在1973年引入提出的一種基于周期和多任務(wù)的靜態(tài)優(yōu)先級(jí)可搶占調(diào)度算法。RMS是針對(duì)周期任務(wù)的優(yōu)先級(jí)調(diào)度算法，當(dāng)任務(wù)的截止時(shí)間等于其周期時(shí)，RMS算法已被證明是靜態(tài)最優(yōu)的調(diào)度算法。

當(dāng)較低優(yōu)先級(jí)的進(jìn)程正在運(yùn)行并且較高優(yōu)先級(jí)的進(jìn)程可以運(yùn)行時(shí)，較高優(yōu)先級(jí)進(jìn)程將會(huì)搶占低優(yōu)先級(jí)。在進(jìn)入系統(tǒng)時(shí)，每個(gè)周期性任務(wù)會(huì)分配一個(gè)優(yōu)先級(jí)，它與其周期成反比，即周期越短，優(yōu)先級(jí)越高；周期越長(zhǎng)，優(yōu)先級(jí)越低。這種策略背后的理由是：更頻繁地需要 CPU 的任務(wù)應(yīng)分配更高的優(yōu)先級(jí)。此外，單調(diào)速率調(diào)度假定：對(duì)于每次 CPU 執(zhí)行，周期性進(jìn)程的處理時(shí)間是相同的。也就是說(shuō)，在每次進(jìn)程獲取 CPU 時(shí)，它的 CPU 執(zhí)行長(zhǎng)度是相同的。

假設(shè)有兩個(gè)進(jìn)程 P1 和 P2。P1 和 P2 的周期分別為 50 和 100，即 ρ1 = 50 和 ρ2= 100。P1 和 P2 的處理時(shí)間分別為 t1 = 20 和 t2 = 35。每個(gè)進(jìn)程的截止期限要求，它在下一個(gè)周期開(kāi)始之前完成 CPU 執(zhí)行。
首先，P1 開(kāi)始，并在時(shí)間 20 完成 CPU 執(zhí)行，從而滿(mǎn)足第一個(gè)截止期限。P2 在這點(diǎn)開(kāi)始運(yùn)行，并運(yùn)行直到時(shí)間 50。此時(shí)，它被 P1 搶占，盡管它的 CPU 執(zhí)行仍有 5ms 的時(shí)間。P1 在時(shí)間 70 完成 CPU 執(zhí)行，在這點(diǎn)調(diào)度器恢復(fù) P2。P1 在時(shí)間 75 完成 CPU 執(zhí)行，也滿(mǎn)足第一個(gè)截止期限。然后，系統(tǒng)一直空閑直到時(shí)間 100，這時(shí)，P1 再次被調(diào)度。
單調(diào)速率調(diào)度可認(rèn)為是最優(yōu)的，因?yàn)槿绻唤M進(jìn)程不能由此算法調(diào)度，它不能由任何其他分配靜態(tài)優(yōu)先級(jí)的算法來(lái)調(diào)度。

最早截止時(shí)間優(yōu)先(Earliest DeadlineFirst, EDF)

最早截止時(shí)間優(yōu)先EDF算法是非常著名的實(shí)時(shí)調(diào)度算法之一。EDF調(diào)度算法是單處理器環(huán)境下調(diào)度性能最優(yōu)的一種動(dòng)態(tài)調(diào)度系統(tǒng)任務(wù)的算法。EDF調(diào)度算法的優(yōu)先級(jí)是以所調(diào)度任務(wù)的截止期與當(dāng)前時(shí)刻的差值來(lái)確定的差值越小證明任務(wù)的截止期越早，與其他差值大的任務(wù)相比優(yōu)先級(jí)就越高，越需優(yōu)先執(zhí)行避免錯(cuò)過(guò)任務(wù)截止期而導(dǎo)致任務(wù)夭折。因此，采用EDF調(diào)度算法可以保證當(dāng)前離截止期最近的任務(wù)獲得系統(tǒng)資源和控制權(quán)，優(yōu)先進(jìn)行調(diào)度。EDF調(diào)度算法最大的優(yōu)點(diǎn)是大幅度提升處理器的利用率，采用EDF調(diào)度算法進(jìn)行調(diào)度時(shí)，處理器的利用率可以達(dá)到最大值。 但EDF調(diào)度算法在進(jìn)行任務(wù)調(diào)度時(shí)系統(tǒng)開(kāi)銷(xiāo)較大，且任務(wù)調(diào)度過(guò)程中無(wú)法對(duì)系統(tǒng)負(fù)載情況進(jìn)行量化判斷，無(wú)法應(yīng)對(duì)系統(tǒng)高負(fù)載情況下的任務(wù)調(diào)度問(wèn)題。EDF算法在調(diào)度過(guò)程中存在任務(wù)錯(cuò)失截止期的情況，進(jìn)而影響其他等待調(diào)度任務(wù)的正常調(diào)度，致后續(xù)多個(gè)任務(wù)錯(cuò)失截止期而夭折。在系統(tǒng)超負(fù)載的情況下調(diào)度算法會(huì)導(dǎo)致系統(tǒng)任務(wù)調(diào)度的成功率大幅度降低，影響嵌入式系統(tǒng)的實(shí)時(shí)調(diào)度性能。

在每一個(gè)新的就緒狀態(tài)，調(diào)度器都是從那些已就緒但還沒(méi)有完全處理完畢的任務(wù)中選擇最早截止時(shí)間的任務(wù)，并將執(zhí)行該任務(wù)所需的資源分配給它。在有新任務(wù)到來(lái)時(shí)，調(diào)度器必須立即計(jì)算EDF，排出新的定序，即正在運(yùn)行的任務(wù)被剝奪，并且按照新任務(wù)的截止時(shí)間決定是否調(diào)度該新任務(wù)。如果新任務(wù)的最后期限早于被中斷的當(dāng)前任務(wù)，就立即處理新任務(wù)。按照EDF算法，被中斷任務(wù)的處理將在稍后繼續(xù)進(jìn)行。該算法的思想是從兩個(gè)任務(wù)中選擇截至?xí)r間最早的任務(wù)，把它暫作為當(dāng)前處理任務(wù)，再判斷該任務(wù)是否在當(dāng)前周期內(nèi)，若不在當(dāng)前周期內(nèi)，就讓另一任務(wù)暫作當(dāng)前處理任務(wù)，若該任務(wù)也不在當(dāng)前周期內(nèi)，就讓CPU空跑到最靠近的下一個(gè)截至?xí)r間的開(kāi)始，若有任務(wù)在該周期內(nèi)，就判斷該任務(wù)的剩余時(shí)間是否小于當(dāng)前截至?xí)r間與當(dāng)前時(shí)間的差,若小于，則讓該任務(wù)運(yùn)行到結(jié)束。否則，就讓該任務(wù)運(yùn)行到該周期的截止時(shí)間，就立即搶回處理器，再判斷緊接著的最早截至?xí)r間，并把處理器給它,做法同上，如此反復(fù)執(zhí)行。

最小空閑時(shí)間優(yōu)先算法(Least Slack First，LSF)

最小空閑時(shí)間優(yōu)先LSF算法結(jié)合任務(wù)執(zhí)行的緩急程度來(lái)給任務(wù)分配優(yōu)先級(jí)。任務(wù)所剩的空閑時(shí)間越少，就越需要盡快執(zhí)行。最小空閑時(shí)間優(yōu)先調(diào)度算法改進(jìn)了EDF算法的性能，算法中任務(wù)優(yōu)先級(jí)由任務(wù)空閑時(shí)間片數(shù)值來(lái)決定， 即任務(wù)截止時(shí)間與剩余執(zhí)行時(shí)間之差，空閑時(shí)間片數(shù)值越小，任務(wù)優(yōu)先執(zhí)行的級(jí)別越高，LSF調(diào)度算法通過(guò)緊急任務(wù)優(yōu)先執(zhí)行策略一定程度上解決了EDF算法存在的問(wèn)題，但調(diào)度算法存在任務(wù)調(diào)度頻繁搶占問(wèn)題，增加了系統(tǒng)的開(kāi)銷(xiāo)同時(shí)也降低了實(shí)時(shí)系統(tǒng)的性能。