陳 藝,徐寶磊
(四川文理學(xué)院 教務(wù)處,四川 達(dá)州635000)
在嵌入式實(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]
模型所述進(jìn)程調(diào)度的方法包括進(jìn)程調(diào)度前系統(tǒng)環(huán)境的準(zhǔn)備和進(jìn)程調(diào)度的策略:
(1)設(shè)置進(jìn)程的類(lèi)型、狀態(tài);進(jìn)程分為關(guān)鍵實(shí)時(shí)進(jìn)程(sched_RTkey)、普通實(shí)時(shí)進(jìn)程(sched_RTcom)、普通進(jìn)程(sched_common)三種類(lèi)型,分別有就緒、阻塞、執(zhí)行三種狀態(tài),采用就緒隊(duì)列嵌套、局部分時(shí)調(diào)度的方式;[4]就緒進(jìn)程按照優(yōu)先級(jí)高低排列成一個(gè)隊(duì)列,相同優(yōu)先級(jí)進(jìn)程(sched_RTcom類(lèi)型進(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)行排序的有序鏈表,用于類(lèi)型為sched_RTcom的進(jìn)程;
(6)建立包含標(biāo)識(shí)進(jìn)程狀態(tài)的進(jìn)程控制塊結(jié)構(gòu);
(1)創(chuàng)建進(jìn)程,指定進(jìn)程的類(lèi)型、優(yōu)先級(jí);
(2)進(jìn)程進(jìn)入掛起隊(duì)列;
(3)當(dāng)進(jìn)程被激活,根據(jù)進(jìn)程的類(lèi)型、優(yōu)先級(jí),將其掛到相應(yīng)的就緒棧隊(duì);
(4)查找就緒棧隊(duì),獲取當(dāng)前就緒的具備最高優(yōu)先級(jí)條件的進(jìn)程,如果是sched_RTcom類(lèi)型的進(jìn)程,還要查找所在子隊(duì)列中時(shí)間片最大的進(jìn)程;[6]
(5)根據(jù)所獲得的最高優(yōu)先級(jí)的進(jìn)程(或者時(shí)間片最大的進(jìn)程)控制模塊內(nèi)容確定進(jìn)程類(lèi)型,并將其掛到相應(yīng)的棧隊(duì).
系統(tǒng)進(jìn)程狀態(tài)及其轉(zhuǎn)換簡(jiǎn)單描述如圖1.將進(jìn)程的類(lèi)型分為關(guān)鍵實(shí)時(shí)進(jìn)程(sched_RTkey)、普通實(shí)時(shí)進(jìn)程(sched_RTcom)、普通進(jìn)程(sched_common)三種類(lèi)型:
關(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)先滿足該類(lèi)型進(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ū)⑼V蛊溥\(yùn)行并自動(dòng)將其放置于可運(yùn)行棧隊(duì)的末尾進(jìn)行等待下一次時(shí)間片的使用.
sched_common是面向普通非實(shí)時(shí)進(jìn)程的時(shí)間片輪轉(zhuǎn)類(lèi)型.
圖1 系統(tǒng)進(jìn)程狀態(tài)轉(zhuǎn)換圖
此調(diào)度策略以?xún)?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í).
(1)取出8個(gè)優(yōu)先級(jí)為普通實(shí)時(shí)進(jìn)程(sched_RTcom)專(zhuān)用,如圖2所示,設(shè)立時(shí)間片,在各自?xún)?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)程專(zhuān)用的任務(wù)).
進(jìn)程創(chuàng)建后,在棧隊(duì)中顯示為處于掛起狀態(tài),該進(jìn)程的類(lèi)型、優(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類(lèi)型,則直接將其取出,并與當(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專(zhuān)用進(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類(lèi)型進(jìn)程,則按照步驟3按時(shí)間片輪轉(zhuǎn)調(diào)度,否則轉(zhuǎn)入步驟2;[10]
圖3 系統(tǒng)的調(diào)度函數(shù)示意圖
本方法主要通過(guò)增加進(jìn)程的類(lèi)型,在就緒隊(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.
四川文理學(xué)院學(xué)報(bào)2014年2期