嵌入式操作系統(tǒng)中的搶占式調(diào)度策略

關(guān)鍵詞：搶占式 多任務(wù) 中斷

引 言

　　通過逐行閱讀順序程序的源代碼，不難說出程序會(huì)向處理器提出什么樣的特定操作，并且也能說出這些操作的順序。實(shí)際上，如果能夠知道對(duì)一個(gè)順序程序的所有輸入，那就不僅能精確預(yù)測到處理器所執(zhí)行的一系列機(jī)器碼，還能計(jì)算出系統(tǒng)最終的輸出值或系統(tǒng)行為。這樣，無論這個(gè)程序運(yùn)行的速度快慢，都能夠得到一個(gè)唯一的結(jié)果。

　　然而，在現(xiàn)實(shí)中順序操作程序是很少見的。譬如，在嵌入式系統(tǒng)C程序中的main（）函數(shù)，盡管它看上去是順序的，但是這種看似順序執(zhí)行的程序最終會(huì)被系統(tǒng)的硬件中斷，在某個(gè)時(shí)刻所打斷。當(dāng)外圍設(shè)備中斷產(chǎn)生后，相應(yīng)的中斷服務(wù)程序會(huì)運(yùn)行，從而取代當(dāng)前main（）函數(shù)的執(zhí)行。這個(gè)過程就可以稱為搶占。

　　搶占意味著main（）函數(shù)將以比預(yù)期慢的速度執(zhí)行。這是因?yàn)樗鼒?zhí)行速度的快慢與系統(tǒng)中斷的數(shù)量、中斷程序的執(zhí)行時(shí)間以及用于保存和恢復(fù)處理器狀態(tài)的操作時(shí)間有著直接的關(guān)系。實(shí)質(zhì)上，大部分的處理器周期都被中斷服務(wù)程序給占用了。除非對(duì)中斷服務(wù)程序有時(shí)間的限制，否則，這些中斷自身并不會(huì)改變系統(tǒng)其它部分的輸出，它們只是減慢了程序的執(zhí)行。

　　由于絕大多數(shù)中斷服務(wù)程序處理來自于系統(tǒng)設(shè)備的中斷，這樣它們的執(zhí)行必將會(huì)帶來系統(tǒng)狀態(tài)的改變。這種狀態(tài)的改變最終會(huì)給后續(xù)指令主序列中的系統(tǒng)行為帶來變化，指令主序列則必須做出適當(dāng)?shù)姆磻?yīng)來避免狀態(tài)改變帶來的影響。此時(shí)，不但難以預(yù)測處理器將執(zhí)行的操作，同時(shí)也難以知道何時(shí)，并且以何種順序來執(zhí)行這些操作。

　　絕大多數(shù)處理器支持中斷的嵌套。一個(gè)打斷程序順序執(zhí)行的中斷服務(wù)程序可以被另一個(gè)更高優(yōu)先級(jí)的中斷服務(wù)程序所打斷。當(dāng)該高優(yōu)先級(jí)的中斷服務(wù)程序執(zhí)行完成后，最初的中斷可以在指令主序列之前得以繼續(xù)執(zhí)行。

　　當(dāng)每一個(gè)搶占過程發(fā)生時(shí)，處理器標(biāo)志位、當(dāng)前PC指針以及關(guān)鍵寄存器的內(nèi)容都應(yīng)該被保存起來（通常在RAM中），這稱為被搶占程序的上下文（context）。這些信息會(huì)在該程序進(jìn)入運(yùn)行態(tài)之前恢復(fù)到處理器中。在中斷事件產(chǎn)生時(shí)，大多數(shù)處理器會(huì)自動(dòng)保存這些值，剩下的就是必須執(zhí)行中斷服務(wù)程序的入口和出口代碼了。

1 偽并行

　　一個(gè)近似的技術(shù)就是使處理器像對(duì)待處理硬件事件一樣處理軟件事件。為了達(dá)到這個(gè)目的，需要將系統(tǒng)劃分為一系列獨(dú)立的事件來處理，即任務(wù)。搶占式調(diào)度方式使這個(gè)想法成為可能。該調(diào)度方式管理著系統(tǒng)軟件對(duì)處理器的使用，并且使系統(tǒng)能夠保證對(duì)時(shí)間要求嚴(yán)格的事件得以有效的執(zhí)行。

每個(gè)任務(wù)就是一個(gè)順序執(zhí)行的函數(shù)，并常常以一個(gè)無限循環(huán)作為結(jié)束。這樣，就好像任務(wù)獨(dú)占了處理器；同時(shí)，每個(gè)任務(wù)都被賦予特定的工作，如讀傳感器、掃描鍵盤、記錄一些數(shù)據(jù)或者刷新顯示等。每個(gè)任務(wù)都擁有一個(gè)相應(yīng)的優(yōu)先級(jí)，并在RAM中有屬于自己的堆?？臻g?？偟膩碚f，這一系列任務(wù)一起完成了整個(gè)系統(tǒng)所要完成的功能。

　　當(dāng)一個(gè)高優(yōu)先級(jí)任務(wù)搶占一個(gè)低優(yōu)先級(jí)任務(wù)時(shí)，調(diào)度器所做的操作與處理器處理中斷的操作一致。首先，將當(dāng)前運(yùn)行任務(wù)的上下文保存到內(nèi)存中某個(gè)地方，然后開始執(zhí)行新的任務(wù)。如果這個(gè)新任務(wù)在先前已經(jīng)運(yùn)行了，那它必有一個(gè)保存的上下文，那么，則需要恢復(fù)這些內(nèi)容使其繼續(xù)運(yùn)行。當(dāng)高優(yōu)先級(jí)任務(wù)執(zhí)行完后，調(diào)度器將保存其最終的上下文，并且恢復(fù)被搶占任務(wù)的運(yùn)行，就好像該低優(yōu)先級(jí)任務(wù)從沒被打斷過。

　　經(jīng)過這樣劃分，每個(gè)任務(wù)函數(shù)可以被寫成獨(dú)占處理器的形式。在實(shí)際應(yīng)用中，往往大多數(shù)系統(tǒng)中只有一個(gè)處理器。所以在某個(gè)特定時(shí)刻應(yīng)該只有一個(gè)任務(wù)或中斷在執(zhí)行。當(dāng)沒有中斷發(fā)生時(shí)，調(diào)度器會(huì)根據(jù)就緒任務(wù)的優(yōu)先級(jí)來決定任務(wù)的運(yùn)行次序。

　　圖1顯示了兩個(gè)不同優(yōu)先級(jí)任務(wù)和一個(gè)中斷服務(wù)程序的執(zhí)行情況。首先，中斷服務(wù)程序搶占低優(yōu)先級(jí)的任務(wù)進(jìn)入運(yùn)行態(tài)，但是該中斷服務(wù)程序使一個(gè)更高優(yōu)先級(jí)的任務(wù)進(jìn)入就緒態(tài)。所以在中斷服務(wù)程序執(zhí)行完成后，調(diào)度器選擇該高優(yōu)先級(jí)任務(wù)進(jìn)入運(yùn)行，這樣就推遲了恢復(fù)執(zhí)行被搶占任務(wù)的操作。需要注意的是，處理器總是認(rèn)為系統(tǒng)中低優(yōu)先級(jí)的中斷比高優(yōu)先級(jí)的任務(wù)更重要。

2 任務(wù)控制

　　 有關(guān)每個(gè)任務(wù)的信息，如任務(wù)起始地址（在C中就是函數(shù)名的地址）、任務(wù)優(yōu)先級(jí)和任務(wù)執(zhí)行需要的堆棧空間，都必須提供給調(diào)度器。系統(tǒng)調(diào)用正是利用這些信息來建立一個(gè)新的任務(wù)。盡管在不同的操作系統(tǒng)中，這些信息會(huì)有所不同，但它們的作用是一樣的。

　　在任務(wù)函數(shù)的實(shí)現(xiàn)體中，可能會(huì)調(diào)用與軟件事件或定時(shí)事件相關(guān)的系統(tǒng)函數(shù)。許多任務(wù)會(huì)等待一個(gè)特定類型的事件并對(duì)之作出響應(yīng)。如一些可能產(chǎn)生一個(gè)軟件事件；另一些可能做一個(gè)100ns的等待，然后再進(jìn)行重復(fù)。

　　軟件事件和超時(shí)事件可以由其它任務(wù)或中斷服務(wù)程序來產(chǎn)生。對(duì)于后者，可以參看圖1。圖1顯示了一個(gè)中斷服務(wù)程序產(chǎn)生了一個(gè)高優(yōu)先級(jí)任務(wù)正在等待的事件（從而喚醒該任務(wù)）。當(dāng)然，可能該中斷服務(wù)程序只是執(zhí)行了一個(gè)時(shí)鐘中斷，而該高優(yōu)先級(jí)任務(wù)只是等待計(jì)數(shù)器到達(dá)某一個(gè)數(shù)值。由于新的軟件事件的到來，該高優(yōu)先級(jí)任務(wù)將在下一次任務(wù)調(diào)度后投入運(yùn)行。

　　可以采用不同方式，甚至隨機(jī)地為任務(wù)設(shè)置優(yōu)先級(jí)。然而，單調(diào)執(zhí)行率算法（RAM）為我們提供了一個(gè)理想的方法來保證關(guān)鍵任務(wù)的時(shí)間期限總能得到滿足。

3 權(quán) 衡

　　在使用搶占式調(diào)度策略的系統(tǒng)中，內(nèi)存消耗主要包含系統(tǒng)調(diào)用函數(shù)額外的ROM和任務(wù)堆棧使用的RAM。另一個(gè)代價(jià)就是CPU時(shí)間的損耗。例如，調(diào)度策略會(huì)消耗處理器的時(shí)鐘周期；上下文切換和時(shí)鐘節(jié)拍會(huì)消耗相當(dāng)一部分的CPU時(shí)間，特別是它們頻繁發(fā)生的情況下。

　　當(dāng)任務(wù)共享諸如全局變量、數(shù)據(jù)結(jié)構(gòu)或外設(shè)控制以及狀態(tài)寄存器等系統(tǒng)資源時(shí)，此時(shí)一個(gè)稱為互斥的系統(tǒng)機(jī)制被用來避免對(duì)這些共享資源競爭?；コ鈾C(jī)制是一個(gè)避免資源競爭的有效方法；但同時(shí)它會(huì)帶來一個(gè)新的問題――優(yōu)先級(jí)反轉(zhuǎn)。

　　在一些應(yīng)用中，將系統(tǒng)分成一個(gè)個(gè)獨(dú)立任務(wù)來設(shè)計(jì)，并使用搶占式的調(diào)度策略。這將簡化系統(tǒng)設(shè)計(jì)，但這種方法的利弊是需要權(quán)衡的。我們只有充分考慮這些權(quán)衡條件，才能對(duì)該方法是否適合我們的應(yīng)用做出正確的判斷。