一種實時系統(tǒng)進程調(diào)度方法探究

陳 藝，徐寶磊

（四川文理學(xué)院 教務(wù)處，四川 達州635000）

0 引言

在嵌入式實時系統(tǒng)中，最核心的部分是進程調(diào)度，它起著至關(guān)重要的作用，保障了整個系統(tǒng)的實時性.進程調(diào)度效率的高低直接關(guān)系到實時系統(tǒng)的效率和性能，優(yōu)秀的進程調(diào)度方法既可以保證關(guān)鍵進程得到實時運行，又不至于讓普通進程盲等.［1］實時操作系統(tǒng)主要通過中斷和任務(wù)方式來響應(yīng)處理外部事件.任務(wù)的優(yōu)先級反映了外部事件的重要程度，在μC／OS-Ⅱ進程調(diào)度模型中，主要基于靜態(tài)優(yōu)先級的調(diào)度策略，使得系統(tǒng)缺乏實時性和靈活性.使用可搶占方式的調(diào)度策略，可以保證高優(yōu)先級的外部事件能得到及時響應(yīng)，高性能實時系統(tǒng)需要在外部事件復(fù)雜頻發(fā)的環(huán)境中，及時響應(yīng)并有效處理重要的高優(yōu)先級的突發(fā)事件，保證系統(tǒng)具有穩(wěn)定的、高效的大吞吐量處理事件能力.［2］進程調(diào)度的時機與引起進程調(diào)度的原因尤為重要，它是進程調(diào)度設(shè)計的前提和基礎(chǔ).

多數(shù)開源的、基于優(yōu)先級可搶占式多進程實時系統(tǒng)，通過任務(wù)控制塊（TCB）和任務(wù)棧實現(xiàn)對任務(wù)的管理、調(diào)度和切換，多用于家電等小型系統(tǒng)中.在μC／OS-Ⅱ?qū)崟r系統(tǒng)中，其本身的調(diào)度策略無法滿足，由于每個優(yōu)先級只容納一個進程，所有任務(wù)的優(yōu)先級各不相同，即使就緒棧隊中有多個任務(wù)等待處理，也只能是優(yōu)先級最高的進程才能得到執(zhí)行，這樣使得進程調(diào)度存在一定的局限性，當(dāng)最高優(yōu)先級的進程需要次優(yōu)先級進程的運行結(jié)果時就需要有多個進程交替運行.［3］

1 實現(xiàn)原理及方法

模型所述進程調(diào)度的方法包括進程調(diào)度前系統(tǒng)環(huán)境的準備和進程調(diào)度的策略：

1.1 進程調(diào)度前的準備工作包括：

（1）設(shè)置進程的類型、狀態(tài)；進程分為關(guān)鍵實時進程（sched＿RTkey）、普通實時進程（sched＿RTcom）、普通進程（sched＿common）三種類型，分別有就緒、阻塞、執(zhí)行三種狀態(tài)，采用就緒隊列嵌套、局部分時調(diào)度的方式；［4］就緒進程按照優(yōu)先級高低排列成一個隊列，相同優(yōu)先級進程（sched＿RTcom類型進程）按照時間片大小排列成一個子隊列；

（2）建立就緒隊列，該發(fā)明假定系統(tǒng)中共64個優(yōu)先級數(shù)，其中0-7保留為系統(tǒng)優(yōu)先級，8-31為sched＿RTkey實時進程優(yōu)先級，32-39為sched＿RTcom采用時間片輪轉(zhuǎn)實時進程優(yōu)先級，其余為普通進程優(yōu)先級（sched＿common）；［5］

（3）初始化一個空鏈表，建立掛起隊列；

（4）為每一個臨界資源建立一個阻塞隊列，并且初始化為先進先出的空鏈表；

（5）建立時間片等待隊列，根據(jù)進程被延遲的時間進行排序的有序鏈表，用于類型為sched＿RTcom的進程；

（6）建立包含標識進程狀態(tài)的進程控制塊結(jié)構(gòu)；

1.2 當(dāng)進程運行的環(huán)境初始化以后，按照以下步驟執(zhí)行進程調(diào)度

（1）創(chuàng)建進程，指定進程的類型、優(yōu)先級；

（2）進程進入掛起隊列；

（3）當(dāng)進程被激活，根據(jù)進程的類型、優(yōu)先級，將其掛到相應(yīng)的就緒棧隊；

（4）查找就緒棧隊，獲取當(dāng)前就緒的具備最高優(yōu)先級條件的進程，如果是sched＿RTcom類型的進程，還要查找所在子隊列中時間片最大的進程；［6］

（5）根據(jù)所獲得的最高優(yōu)先級的進程（或者時間片最大的進程）控制模塊內(nèi)容確定進程類型，并將其掛到相應(yīng)的棧隊.

2 本方法的模型構(gòu)建及詳細實施方案

2.1 確定進程的狀態(tài)模型

系統(tǒng)進程狀態(tài)及其轉(zhuǎn)換簡單描述如圖1.將進程的類型分為關(guān)鍵實時進程（sched＿RTkey）、普通實時進程（sched＿RTcom）、普通進程（sched＿common）三種類型：

關(guān)鍵實時進程（sched＿RTkey）適用于運行所需時間比較短、對響應(yīng)時間要求比較高的實時任務(wù)，在該策略中，各實時任務(wù)按其先來先服務(wù)的原則依次獲得CPU使用權(quán).在進程運行過程中，除了因等待某個事件主動放棄CPU優(yōu)先使用權(quán)或者出現(xiàn)更高優(yōu)先級的進程而剝奪其CPU優(yōu)先使用權(quán)之外，將優(yōu)先滿足該類型進程的CPU的使用量，直至其完成.

普通實時進程（sched＿RTcom）適用于運行時間較長且對響應(yīng)時間要求較高的實時任務(wù).采用該策略時，該棧隊中的進程按時間片輪流合理使用CPU.當(dāng)棧隊中一個進程的時間片應(yīng)用結(jié)束后，進程調(diào)度程序?qū)⑼Ｖ蛊溥\行并自動將其放置于可運行棧隊的末尾進行等待下一次時間片的使用.

sched＿common是面向普通非實時進程的時間片輪轉(zhuǎn)類型.

圖1 系統(tǒng)進程狀態(tài)轉(zhuǎn)換圖

此調(diào)度策略以優(yōu)先級優(yōu)先調(diào)度為主、按照時間片輪轉(zhuǎn)為輔助，并根據(jù)每個進程的運行狀態(tài)進行一定的優(yōu)化使得進程調(diào)度可以公平有效而又不損失響應(yīng)時間，有效降低系統(tǒng)的時間復(fù)雜度.［7］

在實時系統(tǒng)進程調(diào)度中，主要存在下面四種進程調(diào)度時機：

（1）在進程狀態(tài)轉(zhuǎn)換時刻，進程終止或睡眠時；

（2）可運行棧隊中增加一個新進程時；

（3）內(nèi)核處理完中斷后，由中斷返回時；

（4）預(yù)定設(shè)置的時間片到時.

2.2 初始化方法

（1）取出8個優(yōu)先級為普通實時進程（sched＿RTcom）專用，如圖2所示，設(shè)立時間片，在各自優(yōu)先級進程組中采用時間片輪轉(zhuǎn)方式；

圖2 整個系統(tǒng)的就緒隊列

（2）在TCB控制塊中增加一項counter作為其任務(wù)進程調(diào)度的權(quán)值（時間片）；

（3）在進程調(diào)度函數(shù)和初始化函數(shù)中取得當(dāng)前最高優(yōu)先級；

（4）在時鐘中斷處理函數(shù)中，將當(dāng)前運行任務(wù)的counter減1（如果該任務(wù)屬于實時時間片輪轉(zhuǎn)進程專用的任務(wù)）.

2.3 進程調(diào)度的步驟

進程創(chuàng)建后，在棧隊中顯示為處于掛起狀態(tài)，該進程的類型、優(yōu)先級也就隨之確定，進程進入掛起棧隊.［8］如果進程被激活，則進入就緒狀態(tài)，如圖3所示，進程依據(jù)其優(yōu)先級掛入就緒棧隊的相應(yīng)位置.

判斷當(dāng)前就緒棧隊中優(yōu)先級最高的進程，如果不屬于sched＿RTcom類型，則直接將其取出，并與當(dāng)前運行的進程進行優(yōu)先級對比，若高于當(dāng)前進程的優(yōu)先級，則執(zhí)行運行環(huán)境切換，直接運行；否則轉(zhuǎn)入第3步；

如果屬于sched＿RTcom進程中的8個進程級別之一，則順序完成所有就緒的sched＿RTcom專用進程組，掛到相同優(yōu)先級下的時間片輪轉(zhuǎn)組.［9］并且比較當(dāng)前進程的優(yōu)先級，如果相同則按照時間片輪轉(zhuǎn)調(diào)度，并且轉(zhuǎn)入第4步；否則按優(yōu)先級調(diào)度，轉(zhuǎn)入第5步；

計算時間片counter的值，取出時間片量最大的進程運行，遇到時間片大小相同的進程，則取出優(yōu)先級大的進程運行.如果在遍歷中發(fā)現(xiàn)所有的sched＿RTcom進程組時間片都已經(jīng)用完，則再將他們賦予一定的初值，并取出優(yōu)先級最大的進程投入到CPU運行；

按優(yōu)先級調(diào)度，高優(yōu)先級進程直接搶占低優(yōu)先級進程，如果屬于sched＿RTcom類型進程，則按照步驟3按時間片輪轉(zhuǎn)調(diào)度，否則轉(zhuǎn)入步驟2；［10］

圖3 系統(tǒng)的調(diào)度函數(shù)示意圖

3 結(jié)束語

本方法主要通過增加進程的類型，在就緒隊列中使用嵌套子隊列，與現(xiàn)有進程調(diào)度方法相比有著很好的靈活性，適用于各種復(fù)雜的環(huán)境，在保證實時性的前提下，采用局部時間片輪轉(zhuǎn)，兼顧公平.

［1］張曉芳，劉云生.一種支持時態(tài)數(shù)據(jù)的實時數(shù)據(jù)模型［J］.計算機科學(xué)，2006（2）：118-120.

［2］夏家莉.嵌入式實時數(shù)據(jù)庫系統(tǒng)中無沖突并發(fā)控制協(xié)議CCCP［J］.計算機研究與發(fā)展，2004（11）：1936-1940.

［3］Raghu Ramakrishnan，Johannes Gehrke.數(shù)據(jù)庫管理系統(tǒng)原理與設(shè)計［M］.北京：清華大學(xué)出版社，2007：389-420.

［4］謝西庭.嵌入式主動實時數(shù)據(jù)庫ARTs-EDB事務(wù)處理的設(shè)計［D］.武漢：華中科技大學(xué)碩士學(xué)位論文，2004：28-45.

［5］Kam-Yiu Lam.Evaluationofconcurrencycontrolstrategiesformixedsoftreal-timedatabasesystems［C］.UMBC，Maryland：Information Systems，2005.

［6］張 濤.嵌入式實時數(shù)據(jù)庫關(guān)鍵技術(shù)研究與實現(xiàn)［D］.成都：電子科技大學(xué)碩士學(xué)位論文，2005：67-80.

［7］明日科技.SQL Server 2005開發(fā)技術(shù)大全［M］.北京：人民郵電出版社，2007：239-276.

［8］劉云生.實時數(shù)據(jù)庫系統(tǒng)［J］.計算機科學(xué)，1994（3）：42-46.

［9］劉云生，夏家莉.基于功能替代的實時事務(wù)調(diào)度［J］.計算機學(xué)報，2003（2）：250-256.

［10］周東球，杜殿林，左 信.先進控制軟件系統(tǒng)實時數(shù)據(jù)庫的設(shè)計［J］.微計算機信息，2003（10）：23-24.