引言

隨著嵌入式實(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ù)滿足各自的時(shí)限，嵌入式操作系統(tǒng)必須保證在確定的時(shí)間內(nèi)對(duì)事件進(jìn)行處理，因此必須要有一個(gè)良好的任務(wù)調(diào)度算法。周期任務(wù)和非周期任務(wù)是實(shí)時(shí)嵌入式系統(tǒng)中的常見任務(wù)類型，系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度策略主要包括時(shí)間驅(qū)動(dòng)調(diào)度策略、優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度策略。常見的動(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)短的不同來決定優(yōu)先級(jí)，即任務(wù)的周期越小優(yōu)先級(jí)越高，任務(wù)的周期越大優(yōu)先級(jí)越低。以RMS為代表的固定優(yōu)先級(jí)調(diào)度算法，一方面不僅具有運(yùn)行時(shí)間開銷小和易于實(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ù)在截止期限到來之時(shí)仍無法滿足。

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)行的過程中，調(diào)度表中的信息不再發(fā)生任何變化。該類調(diào)度算法假定系統(tǒng)實(shí)時(shí)任務(wù)的屬性是提前已知的并且在執(zhí)行過程中很少發(fā)生變化，特別適合于對(duì)那種確定問題的求解，具有較好的可預(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í)間是相同的。也就是說，在每次進(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è)周期開始之前完成 CPU 執(zhí)行。
首先，P1 開始，并在時(shí)間 20 完成 CPU 執(zhí)行，從而滿足第一個(gè)截止期限。P2 在這點(diǎn)開始運(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í)行，也滿足第一個(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í)的算法來調(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í)刻的差值來確定的差值越小證明任務(wù)的截止期越早，與其他差值大的任務(wù)相比優(yōu)先級(jí)就越高，越需優(yōu)先執(zhí)行避免錯(cuò)過任務(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)開銷較大，且任務(wù)調(diào)度過程中無法對(duì)系統(tǒng)負(fù)載情況進(jìn)行量化判斷，無法應(yīng)對(duì)系統(tǒng)高負(fù)載情況下的任務(wù)調(diào)度問題。EDF算法在調(diào)度過程中存在任務(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)度器都是從那些已就緒但還沒有完全處理完畢的任務(wù)中選擇最早截止時(shí)間的任務(wù)，并將執(zhí)行該任務(wù)所需的資源分配給它。在有新任務(wù)到來時(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間的開始，若有任務(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í)行的緩急程度來給任務(wù)分配優(yōu)先級(jí)。任務(wù)所剩的空閑時(shí)間越少，就越需要盡快執(zhí)行。最小空閑時(shí)間優(yōu)先調(diào)度算法改進(jìn)了EDF算法的性能，算法中任務(wù)優(yōu)先級(jí)由任務(wù)空閑時(shí)間片數(shù)值來決定， 即任務(wù)截止時(shí)間與剩余執(zhí)行時(shí)間之差，空閑時(shí)間片數(shù)值越小，任務(wù)優(yōu)先執(zhí)行的級(jí)別越高，LSF調(diào)度算法通過緊急任務(wù)優(yōu)先執(zhí)行策略一定程度上解決了EDF算法存在的問題，但調(diào)度算法存在任務(wù)調(diào)度頻繁搶占問題，增加了系統(tǒng)的開銷同時(shí)也降低了實(shí)時(shí)系統(tǒng)的性能。