特定應用操作系統(tǒng)的實時調(diào)度算法研究.pdf

1、實時系統(tǒng)通常是指可實現(xiàn)計算機控制的嵌入式系統(tǒng)。它自出現(xiàn)一來一直穩(wěn)步發(fā)展，近幾年來更有著飛速地發(fā)展，應用于幾乎所有行業(yè)：從日常家電到一般工業(yè)、交通……直至航天航空等領域。對實時系統(tǒng)的研究涉及到實時編程語言及工具、實時通訊、實時任務調(diào)度、容錯技術及可靠性評估技術等眾多方面內(nèi)容，而在這些研究中，實時任務調(diào)度占據(jù)核心位置。 隨著硬件技術的發(fā)展和實際控制任務變得越來越復雜，實時系統(tǒng)已由無操作系統(tǒng)階段發(fā)展到帶有通用嵌入式操作系統(tǒng)(RTOS)

2、階段，出現(xiàn)了所謂的片上系統(tǒng)(SOC)。同時，嵌入式系統(tǒng)在應用層上的飛速發(fā)展，也促使嵌入式系統(tǒng)體系結構由靜態(tài)向動態(tài)，由通用向可定制的特定應用轉(zhuǎn)變，從而出現(xiàn)了基于特定應用的嵌入式操作系統(tǒng)(ASOS)。特定應用系統(tǒng)是一種片上系統(tǒng)，它實現(xiàn)了嵌入式與Internet網(wǎng)絡的真正結合，嵌入式操作系統(tǒng)與應用設備的無縫結合，代表著嵌入系統(tǒng)發(fā)展的一種趨勢。ASOS本身是一種實時操作系統(tǒng)但與一般意義上的RTOS存在區(qū)別： ■ASOS更強調(diào)面向應用的功

3、能專用性，如面向某一(組)應用的高可靠性的部分功能集，而并不像RTOS的系統(tǒng)通用性與系統(tǒng)資源可配置性； ■ASOS更強調(diào)面向應用的實時高性能，而并不像RTOS強調(diào)的系統(tǒng)整體效率； ■ASOS更強調(diào)系統(tǒng)結構的可伸縮性和可裁減性，一個極典型的例子是傳真機操作系統(tǒng)(OSforFAXMachine); ■ASOS更強調(diào)與Internet的連接，特別是無線接入接口。 ■ASOS追求更高的性價比。 ASOS與

4、RTOS間的差異反映在調(diào)度算法上主要表現(xiàn)為基于ASOS的調(diào)度算法應滿足以下三個基本要求：(1)任務調(diào)度開銷要盡量小。ASOS的實時高效性要求任務切換要盡量少。在RTOS算法研究中，往往忽略任務切換開銷，而在實際任務的調(diào)度中，任務的切換時間往往是不可忽略的，尤其是在復雜的多任務系統(tǒng)中，任務搶占頻繁，任務切換開銷相對較大，而再像RTOS的調(diào)度算法中忽略任務的切換開銷，將造成災難性后果。(2)任務調(diào)度的內(nèi)存需求不能太高。在經(jīng)典實時調(diào)度算法研究

5、中通常都沒有考慮到內(nèi)存容量的限制，即假設所需的內(nèi)存都能滿足要求。由于特定應用系統(tǒng)是一種片上系統(tǒng)，因此系統(tǒng)空間決定內(nèi)存配置不能太大，此外，對系統(tǒng)低成本的追求也決定各種配置不能太高，這就要求調(diào)度算法應考慮到存儲容量的限制。(3)算法應便于在實際開發(fā)中的應用?，F(xiàn)在，嵌入式處理器的運行速度越來越快，系統(tǒng)軟件及基于其上的應用軟件也越來越復雜，因此在軟件開發(fā)上，許多特定應用系統(tǒng)引進了實時系統(tǒng)的面向?qū)ο笤O計技術(ROOM)和統(tǒng)一建模語言(UML)，這

6、些高級技術的引進也決定了面向特定應用系統(tǒng)的調(diào)度算法不同于通用嵌入系統(tǒng)的調(diào)度算法。 雖然ASOS的概念提出已有幾年了，但是針對ASOS的調(diào)度算法研究還是一個較新的領域，有著現(xiàn)實的需求。本文根據(jù)ASOS算法要求，提出了單處理器的專門基于片上ASOS系統(tǒng)的靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級調(diào)度算法。 對于處理器利用率要求不十分高的ASOS系統(tǒng)，本文首先給出了靜態(tài)優(yōu)先級下的改進可搶占閾調(diào)度算法(IPTS)。它合并了單調(diào)截止時限算法(DMS)

7、與搶占閾算法(PTS)，是基于DMS算法上的一種改進算法。當每一個任務的搶占閾與按DMS算法分配的初始優(yōu)先級相等時，IPTS算法就退化成完全可搶占的DMS算法；當每個任務的搶占閾都等于最高優(yōu)先級時，它就變成了不可搶占調(diào)度算法。文章還給出了IPTS算法下的有效線程、最優(yōu)線程和堆棧需求最小線程的分配方法。由于線程內(nèi)的任務互不可搶占，又最優(yōu)線程方法是最少的線程分配方法，所以最優(yōu)線程能最大限度地降低了任務間的搶占次數(shù)，有效滿足了ASOS任務調(diào)度

8、的高效實時性要求。堆棧需求最小線程分配方法給了系統(tǒng)對堆棧內(nèi)存需要最小情況下的線程分配方法。此外，線程的引進可以使IPTS算法與ROOM等技術較容易地結合在一起，便于復雜軟件的開發(fā)。 對處理器要求較高的系統(tǒng)，文章給出了動態(tài)優(yōu)先級搶占閾調(diào)度算法(DPTS)，在理論上它可以達到100％的處理器利用率。DPTS算法是建立在動態(tài)優(yōu)先級調(diào)度算法一一EDF算法上的搶占閾調(diào)度算法。在DPTS算法下每個任務被賦予三個優(yōu)先級：初始優(yōu)先級、搶占水準和

9、搶占閾。當搶占水準與搶占閾相等時，DPTS算法退化成可搶占的EDF算法，當搶占閾等于最高搶占水準時，DPTS算法變成完全不可搶占調(diào)度算法。文中同樣給出的DPTS算法下的有效線程、最優(yōu)化線程和堆棧需求最小線程分配方法。在文章最后還給出了優(yōu)化的DPTS算法，它將靜態(tài)不變的搶占閾按運行時的實際情況而加以改變，可以更有效地降低任務間的切換開銷。 對ASOS的調(diào)度算法研究是一個開放的課題，需要研究的內(nèi)容及深度都需要加寬加深，希望通過本人的