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

陳 藝，徐寶磊

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

0 引言

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

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

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

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

1.1 進(jìn)程調(diào)度前的準(zhǔn)備工作包括：

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

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

（3）初始化一個(gè)空鏈表，建立掛起隊(duì)列；

（4）為每一個(gè)臨界資源建立一個(gè)阻塞隊(duì)列，并且初始化為先進(jìn)先出的空鏈表；

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

（6）建立包含標(biāo)識(shí)進(jìn)程狀態(tài)的進(jìn)程控制塊結(jié)構(gòu)；

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

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

（2）進(jìn)程進(jìn)入掛起隊(duì)列；

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）可運(yùn)行棧隊(duì)中增加一個(gè)新進(jìn)程時(shí)；

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

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

2.2 初始化方法

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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