基于移動中間件抽象層調(diào)度策略研究

黃錦濤,何加銘,陳 平,賈德祥

(寧波大學(xué)通信技術(shù)研究所,浙江寧波315211)

0 引 言

移動終端上數(shù)據(jù)業(yè)務(wù)越來越豐富,應(yīng)用環(huán)境越來越復(fù)雜,很多新型應(yīng)用(如聯(lián)網(wǎng)游戲)需要實(shí)時(shí)系統(tǒng)支持,為滿足應(yīng)用實(shí)時(shí)性要求,在基于移動終端中間件抽象層上完善調(diào)度策略。系統(tǒng)實(shí)時(shí)性具體表現(xiàn)為處理器的響應(yīng)時(shí)間和吞吐率。響應(yīng)時(shí)間指運(yùn)行程序所需要的所有時(shí)間的總和(一個任務(wù)從開始到結(jié)束所需的時(shí)間);吞吐率指單位時(shí)間內(nèi)能運(yùn)行的任務(wù)數(shù)。那么縮短響應(yīng)時(shí)間通常也就意味著提高吞吐率。提高實(shí)時(shí)性的途徑有：軟件級并行;處理器級并行;線程級并行;指令級并行;執(zhí)行級并行[1]。線程是程序中的一條執(zhí)行分支,或者說,線程是可以同時(shí)運(yùn)行的函數(shù)。線程有以下特點(diǎn)：(1)共享父進(jìn)程的所有資源;(2)通過系統(tǒng)調(diào)度或者同步變量傳送消息;(3)切換時(shí)只涉及寄存器和局部變量,開銷很小;(4)注意線程同步問題,防止死機(jī)現(xiàn)象[2]。線程分時(shí)共享處理器資源,大量線程切換帶來的開銷仍然相當(dāng)可觀,所以需要一種低開銷的多任務(wù)調(diào)度模型。不同操作系統(tǒng)的線程運(yùn)行機(jī)制有很大不同,本目標(biāo)系統(tǒng)提供了兩類調(diào)度策略：位圖(Bitmap)調(diào)度和多級(MLQ)調(diào)度。

1 位圖調(diào)度策略

位圖調(diào)度策略是一種基于靜態(tài)優(yōu)先級的搶占式調(diào)度策略。被調(diào)度的線程擁有唯一不變的優(yōu)先級,每一時(shí)刻運(yùn)行的是就緒隊(duì)列中優(yōu)先級最高的線程。該調(diào)度策略以時(shí)鐘中斷作為基本調(diào)度時(shí)機(jī),當(dāng)優(yōu)先級更高的線程進(jìn)入就緒態(tài)時(shí)就立刻搶占正在運(yùn)行的低優(yōu)先級線程[3]。主要數(shù)據(jù)結(jié)構(gòu)如下：

(1)位圖表。位圖調(diào)度策略可支持256種不同的優(yōu)先級,用32位無符號整型數(shù)(針對支持32位整型數(shù)的體系結(jié)構(gòu))數(shù)組rdy_queue將256個優(yōu)先級分成8組,數(shù)組每個成員的每一位代表一個優(yōu)先級,按照從最高有效位至最低有效位優(yōu)先級逐次降低,當(dāng)某位為l時(shí)表示該優(yōu)先級線程進(jìn)入就緒態(tài)。線程開始的優(yōu)先級為基本優(yōu)先級,線程的當(dāng)前優(yōu)先級可在1到32的范圍內(nèi)動態(tài)改變。在以下情況會提升線程當(dāng)前優(yōu)先級：I/O操作完成;信號量或事件等待結(jié)束;前臺進(jìn)程中的線程完成一個等待操作;線程處于就緒狀態(tài)一定時(shí)間,但沒能進(jìn)入運(yùn)行狀態(tài)。位圖表用來方便查找系統(tǒng)最高優(yōu)先級線程;

(2)就緒隊(duì)列。Bitmap_thread_rdy數(shù)組用來存儲進(jìn)入就緒態(tài)的線程對象的指針。當(dāng)位圖表中某組中任何一個優(yōu)先級進(jìn)入就緒狀態(tài)(被置1)時(shí),就緒隊(duì)列中對應(yīng)的元素就記錄了該線程的指針如圖1所示。

圖1 位圖表與就緒隊(duì)列

這樣,通過就緒隊(duì)列與位圖表就可以得到線程的優(yōu)先級。當(dāng)位圖調(diào)度器進(jìn)行調(diào)度時(shí)只需要依次查找rdy_queue中置1的最高位,即可找到最先級線程。

2 多級調(diào)度優(yōu)化策略

多級隊(duì)列調(diào)度是一種搶占式與時(shí)間片輪轉(zhuǎn)(Round-Robin)調(diào)度相結(jié)合的調(diào)度策略,是對位圖調(diào)度策略的擴(kuò)充,即允許線程具有相同的優(yōu)先級。在相同優(yōu)先級線程之間采間片輪轉(zhuǎn)調(diào)度策略,平均分配CPU占用時(shí)間。該策略的思想是盡量選擇那些處于活動狀態(tài)的高優(yōu)先級線程進(jìn)行取指,保證線程緩存區(qū)中的指令極少數(shù)是錯誤路徑的,而且該策略對線程進(jìn)行詳細(xì)的等級劃分,使得只有最低等級的線程才被暫停,提高取指效率[4]。主要數(shù)據(jù)結(jié)構(gòu)如下：

(1)位圖表。與位圖調(diào)度策略中rdy_queue相同;

(2)就緒隊(duì)列。mlq_thread_rdy數(shù)組用來存儲線程指針。與位圖調(diào)度策略不同的是,thread_rdy每一個元素存儲的是一個鏈表頭,其后面可以掛接線程對象形成一個雙向鏈表,THREAD數(shù)據(jù)結(jié)構(gòu)中的next和prey指針使線程成為一個線程雙向鏈表結(jié)點(diǎn)。變量rr_quantum用來指定時(shí)間片大小,當(dāng)某線程時(shí)間片用完時(shí),首先確定是否降低該線程的優(yōu)先級,然后確定是否調(diào)度另一個線程進(jìn)入運(yùn)行狀態(tài)。假定剛用完時(shí)間配額的線程的優(yōu)先級沒有降低,如果有優(yōu)先級相同的就緒線程,則選擇相同優(yōu)先級就緒隊(duì)列中的第一個線程進(jìn)入運(yùn)行狀態(tài),剛用完時(shí)間配額的線程被排到就緒隊(duì)列的隊(duì)尾;如果沒有優(yōu)先級相同的就緒線程,剛用完時(shí)間配額的線程將得到一個新的時(shí)間配額并繼續(xù)運(yùn)行;

(3)可達(dá)截止期優(yōu)先算法?？蛇_(dá)截止期優(yōu)先算法是對截止期優(yōu)先策略的改進(jìn),就緒隊(duì)列的任務(wù)優(yōu)先級,仍然按照截止期順序排隊(duì)。但是,在調(diào)度時(shí)超過截止期的不予調(diào)度。

當(dāng)前時(shí)刻離截止時(shí)刻的時(shí)間：

式中,Tc為系統(tǒng)當(dāng)前時(shí)刻,Te為執(zhí)行整個任務(wù)的估算時(shí)間,Tr為任務(wù)已執(zhí)行部分所用的實(shí)際時(shí)間,Td為截止時(shí)刻。

當(dāng)D ≥0時(shí),任務(wù)預(yù)計(jì)能在截止時(shí)刻前完成(也就是說,該任務(wù)的截止期是當(dāng)前可達(dá)到的),于是可以進(jìn)行調(diào)度,否則放棄該任務(wù)的執(zhí)行。

在可達(dá)截止期最早優(yōu)先算法中,系統(tǒng)時(shí)鐘對任務(wù)的運(yùn)行時(shí)間進(jìn)行累計(jì),空閑任務(wù) IDLE的截止時(shí)刻DeadTime應(yīng)設(shè)為無限大,而估算時(shí)間則為0,就緒隊(duì)列中至少有一個就緒任務(wù)滿足調(diào)度要求。

3 調(diào)度管理模塊

在調(diào)度管理模塊中實(shí)現(xiàn)部分主要有：

(1)基本數(shù)據(jù)類型定義;

(2)線程上下文切換。盡管線程是微內(nèi)核中調(diào)度和執(zhí)行的基本單位,但對于微處理器而言.它不能感知線程實(shí)體的存在,它只能為線程的執(zhí)行提供一個環(huán)境,這個環(huán)境就是相關(guān)的寄存器。由此可見,線程的切換實(shí)質(zhì)就是微處理器的寄存器更換內(nèi)容的過程,而這個過程與處理器體系結(jié)構(gòu)密切相關(guān),因此需要對線程上下文切換過程進(jìn)行封裝,使其在抽象層中實(shí)現(xiàn)。給出位圖調(diào)度策略和多級隊(duì)列調(diào)度策略的實(shí)現(xiàn)流程圖如圖2所示;

圖2 位圖調(diào)度策略和多級隊(duì)列調(diào)度策略流程圖

(3)調(diào)度服務(wù)函數(shù)。調(diào)度管理模塊提供的服務(wù)函數(shù)如表1所示：

表1 調(diào)度服務(wù)函數(shù)

4 測試分析

在通常的位圖調(diào)度策略中,如果取出過多在IQ中停留時(shí)間較長的指令,最終會使IQ中充滿不可發(fā)射的指令,稱之為IQ阻塞(IQ clog),這樣吞吐率降低,使執(zhí)行單元處于空閑狀態(tài),浪費(fèi)資源。利用多級調(diào)度結(jié)合可達(dá)截止期優(yōu)先算法的混合應(yīng)用,時(shí)間片輪轉(zhuǎn)式交替執(zhí)行使指令混合,減少IQ阻塞出現(xiàn)的概率。實(shí)驗(yàn)測試結(jié)果表明改進(jìn)后多級調(diào)度策略相比于原先的位圖調(diào)度策略,IQ阻塞的概率減少了11%。如表2所示,IQ阻塞率在各種線程數(shù)目下都有大幅度降低。

表2 各線程IQ阻塞率

5 結(jié)束語

一個好的調(diào)度方法,需要綜合考慮應(yīng)用程序多樣性以及體系結(jié)構(gòu)兩個方面的特征。本文提出一種基于抽象層的線程調(diào)度策略,在高效的位圖調(diào)度的基礎(chǔ)上擴(kuò)充為多級調(diào)度策略,一種搶占式與時(shí)間片輪轉(zhuǎn)(Round-Robin)調(diào)度相結(jié)合的調(diào)度策略。這種調(diào)度方式避免了某項(xiàng)任務(wù)長時(shí)間占用CPU時(shí)間,既提高了程序的性能,又增強(qiáng)了程序的功能。但隨著進(jìn)程或者線程個數(shù)的增加,以及處理器個數(shù)的增加,需考察的調(diào)度決策數(shù)呈指數(shù)增長。因此調(diào)度算法應(yīng)該和具體的體系結(jié)構(gòu)以及進(jìn)程本身相關(guān),這也是需要繼續(xù)完善的方向。

[1]Sohi G,Roth A.Speculative Multithreaded Processors[J].IEEE Computer,2001,34(4)：66-71.

[2]駱斌,費(fèi)翔林.多線程技術(shù)的研究與應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展,2000,37(4)：407-412.

[3]Seto D B,Lehoczky J,Liu s.Task Period selection and schedulability in real-time systems[J].IEEE Communication Society,1998,16(3)：188-199.

[4]羅宇,商臨鋒.操作系統(tǒng)多線程實(shí)現(xiàn)技術(shù)研究[J].小型微型計(jì)算機(jī)系統(tǒng),2000,21(5)：500-503.

[5]Reinder J B,Elisabeth S,Wim V.Best-case response times and jitter analysis of real-time tasks[J].Journal of Scheduling,2004,7(2)：133-147.