（計算機軟件與理論專業(yè)論文）一種反饋控制機制在edf算法上的應(yīng)用.pdf

太原理工大學(xué)碩士研究生學(xué)位論文 一種反饋控制機制在e d f 算法上的應(yīng)用 摘要 實時調(diào)度算法是嵌入式實時系統(tǒng)設(shè)計和實現(xiàn)的關(guān)鍵問題之一，也是保 障實時系統(tǒng)兩個必備特性( 時限性和可靠性) 的重要方法，是實時系統(tǒng)中重要 而活躍的研究領(lǐng)域。 在眾多的實時調(diào)度算法中，速率單調(diào)( r a t em o n o t o n i c ，r m ) 和最早截止 期限優(yōu)先( e a r l i e s td e a d l i n ef i r s t ，e d f ) 分別是靜態(tài)調(diào)度和動態(tài)調(diào)度領(lǐng)域中經(jīng) 典的調(diào)度算法。r m 算法屬于靜態(tài)調(diào)度算法，在系統(tǒng)運行前決定任務(wù)的調(diào)度， 實現(xiàn)簡單，在滿足前提條件的情況下可以保證實時任務(wù)集的成功調(diào)度。e d f 算法屬于動態(tài)調(diào)度算法，在系統(tǒng)運行時決定任務(wù)的調(diào)度，c p u 利用率可以 達到1 0 0 ( 理想情況下) 。雖然r m 和e d f 算法以其各自所具備的優(yōu)良性 能在嵌入式實時系統(tǒng)中得到了廣泛應(yīng)用，但是我們也不能忽視它們本身存 在的實時性問題。 雖然一些改進后的算法能支持更復(fù)雜的任務(wù)集特性，但這些算法都是 開環(huán)的調(diào)度算法。開環(huán)就意味著一旦調(diào)度器被創(chuàng)建，它們就不能基于持續(xù) 的反饋進行調(diào)整了。盡管開環(huán)調(diào)度算法在負(fù)載精確建模的靜態(tài)或動態(tài)系統(tǒng) 中執(zhí)行良好，但是該類算法在不可預(yù)測的動態(tài)系統(tǒng)環(huán)境下性能卻較差。 本文是在考慮“系統(tǒng)過載 的情況下，通過在e d f 調(diào)度算法中引入反 饋控制機制來提高e d f 調(diào)度算法的實時性及穩(wěn)定性。 首先介紹實時調(diào)度算法的應(yīng)用背景：實時系統(tǒng)、嵌入式系統(tǒng)、實時操 作系統(tǒng)和嵌入式實時操作系統(tǒng)。 接著對現(xiàn)有的實時調(diào)度模型、實時調(diào)度基本理論、調(diào)度策略和實時調(diào) 度算法進行了分析和研究。對r m 和e d f 實時調(diào)度算法進行了詳細分析， 并舉例說明了它們的調(diào)度過程。 然后介紹了本文提出的反饋控制機制用到的相關(guān)理論一比例一積分微 太原理工大學(xué)碩士研究生學(xué)位論文 分( p r o p o r t i o n a l i n t e g r a l d e r i v a t i v e , ri d ) 自動控制理論和操作方法，并說明了單神 經(jīng)元智能控制的基本理論。 最后，通過使用自適應(yīng)單神經(jīng)元p i d 算法對e d f 調(diào)度算法進行動態(tài)反 饋控制，動態(tài)調(diào)整過載時系統(tǒng)中的任務(wù)數(shù)量，運用每次運行獲得的截止期錯 失率作為下一次運行的輸入?yún)?shù)進行實時任務(wù)調(diào)度，以此來提高實時系統(tǒng) 的實時性和穩(wěn)定性，達到有效改善過載的目的。本文模擬了基于p i d 反饋控 制機制的最早截止期限優(yōu)先調(diào)度算法，并比較了引入反饋控制機制前后的 實驗情況。實驗結(jié)果表明：引入自適應(yīng)單神經(jīng)元p i d 反饋調(diào)度算法可以快 速穩(wěn)定并積極改善實時系統(tǒng)達到過載時的情況，可以優(yōu)化系統(tǒng)降級時的性 能。說明了使用p i d 反饋控制對改善e d f 調(diào)度算法執(zhí)行情況的可行性和有 效性。該結(jié)論對實時調(diào)度算法的研究和使用有一定的理論和實踐意義。 本文的創(chuàng)新之處在于引入了單神經(jīng)元p i d 反饋控制機制，使反饋控制 更具智能型，實現(xiàn)了自適應(yīng)單神經(jīng)元p i d 控制算法在嵌入式實時調(diào)度算法 領(lǐng)域的運用。 關(guān)鍵詞：嵌入式實時系統(tǒng)，實時調(diào)度，e d f 調(diào)度算法，自適應(yīng)單神經(jīng)元p i d 反饋控制 太原理工大學(xué)碩士研究生學(xué)位論文 af e e d b a c kc o n t r o ls c h e m ea p p l ! dt oe a r l s t d e a d l ef i r s ts c h e d u l 玳ga l g o r i t h m a b s t r a c t r e a l t i m es c h e d u l i n ga l g o r i t h mi so n eo fm a j o rd e s i g ni s s u e sf o re m b e d d e d r e a l t i m es y s t e m s i ti sa l s oa l li m p o r t a n tm e t h o dt og u a r a n t e et i m ec o n s t r a i n s a n dr e l i a b i l i t yf o rr e a l t i m es y s t e m s ，a c t i v e l yb e i n gr e s e a r c h e di nt h i sf i e l d a m o n gt h es c h e d u l i n ga l g o r i t h m s ，r m ( r a t em o n o t o n i c ) a n d e d f ( e a r l i e s td e a d l i n ef i r s t ) a r et w oc l a s s i c a ls c h e d u l i n ga l g o r i t h m s r mi sag o o d a l g o r i t h mi nt h ef i e l do fs t a t i cs c h e d u l i n g r md e c i d e dt a s ks c h e d u l i n go r d e r b e f o r es y s t e mr u n n i n g ，a n di ti se a s yt oc a r r yo u t i fp r e c o n d i t i o n sa r em e t ，r m c a l ls c h e d u l er e a l t i m et a s ks e t ss u c c e s s f u l l y e d fi sag o o da l g o r i t h mi nt h e f i e l do fd y n a m i cs c h e d u l i n g e d fd e c i d e dt a s ks c h e d u l i n go r d e rd u r i n gs y s t e m r u n n i n g t h ec p uu t i l i z a t i o no fe d fs c h e d u l i n ga l g o r i t h mc a nb e1 0 0 i n p e r f e c tc o n d i t i o n a l t h o u g hh a v i n gn o t i c e dt h a tr ma n de d fd oh a v eg o o d p e r f o r m a n c ea n db r o a d l yu s e di ne m b e d d e dr e a l t i m es y s t e m s ，w ec a nn o t i g n o r et h es h o r t c o m i n g so fr e a l t i m ep e r f o r m a n c eo f t h et w oa l g o r i t h m s w h i l es o m ei m p r o v e de a r l i e s td e a d l i n ef i r s ta n dr a t em o n o t o n i c s c h e d u l i n ga l g o r i t h m sc a ns u p p o r tm o r es o p h i s t i c a t e dt a s ks e tc h a r a c t e r i s t i c s ， t h e ya r es t i l la l lo p e nl o o ps c h e d u l i n ga l g o r i t h m s o p e nl o o pm e a n st h a to n c e s c h e d u l e sa r ec r e a t e dt h e yc a nn o ta d j u s tt h e m s e l v e sb a s e do nc o n t i n u o u s f e e d b a c k w h i l eo p e n l o o ps c h e d u l i n ga l g o r i t h m sc a np e r f o r mw e l li ns t a t i co r d y n a m i cs y s t e m sw h e r et h ew o r k l o a d sa r ea c c u r a t e l ym o d e l e d ，m e ys t i l lc a n p e r f o r mp o o r l yi nu n p r e d i c t a b l ed y n a m i cs y s t e m s i nt h ec o n s i d e r a t i o no fs y s t e mo v e r l o a d ，af e e d b a c kc o n t r o ls c h e m ei s 1 1 i 太原理工大學(xué)碩士研究生學(xué)位論文 i n t r o d u c e di nt h i st h e s i st oe n h a n c et h er e a l t i m ep e r f o r m a n c ea n ds t a b i l i t yo f e d f s c h e d u l i n ga l g o r i t h m f i r s t l y , t h eb a c k g r o u n d ( r e a l t i m es y s t e m ，e m b e d d e ds y s t e m ，r e a l t i m e o p e r a t i n gs y s t e ma n de m b e d d e dr e a l t i m eo p e r a t i n gs y s t e m ) o fr e a l - - t i m e s c h e d u l i n ga l g o r i t h m sw a si n t r o d u c e d s e c o n d l y , r e a l t i m es c h e d u l i n gm o d e l s ，t h eb a s i ct h e o r yo fr e a l t i m e s c h e d u l i n g ，r e a l t i m es c h e d u l i n gs t r a t e g i e sa n dr e a l t i m es c h e d u l i n ga l g o r i t h m s w e r ed e s c r i b e d r ma n de d fw e r ed i s c u s s e di nd e t a i la n ds o m ee x a m p l e sw e r e u s e dt oe x p l a i nt h e i rs c h e d u l i n gp r o c e s s e s t h i r d l y , t h ec o r r e l a t e dt h e o r yu s e df o ro u rf e e d b a c ks c h e m ep r o p o s e di n t h i sp a p e rw a si n t r o d u c e d i ti so np i d ( p r o p o r t i o n a l - i n t e g r a l d e r i v a t i v e ) i n a u t o c o n t r o lt h e o r ya n do p e r a t i o nm e t h o d t h et h e o r yo n s i n g l en e u r a le l e m e n t s e l f - a d a p t i v ep i dm e t h o dw a sa l s oi l l u s t r a t e d f i n a l l y , i tc a nb ea c h i e v e dt h a to v e r l o a ds i t u a t i o nc a nb ei m p r o v e dt h r o u g h u s i n gs i n g l en e u r a le l e m e n ts e l f - a d a p t i v ep i da l g o r i t h mt om a k ef e e d b a c k c o n t r o lo ne d fs c h e d u l i n g i tc a nd y n a m i c a l l ya d j u s tt a s kn u m b e ri no v e d o a d s y s t e ma n du s et h er e c e i v e dd e a d l i n em i s sr a t i of o re a c hr u n n i n ga st h ei n p u t p a r a m e t e rf o rn e x tr e a l t i m es c h e d u l i n g w es i m u l a t e dae d fs c h e d u l i n gw i t ha p i df e e d b a c kc o n t r o ls c h e m e ，t h e nc o m p a r e dt h ee x p e r i m e n t sb e f o r ea n da f t e r i n t r o d u c e ds u c hf e e d b a c kc o n t r o ls c h e m e t h er e s u l t ss h o wt h a tt h ei n t r o d u c e d s i n g l en e u r a le l e m e n ts e l f - a d a p t i v ep i da l g o r i t h mc a nf a s ts t a b i l i z ea n d a c t i v e l yi m p r o v et h er e a l t i m es y s t e mo v e r l o a d e d ，a n do p t i m i z et h ep e r f o r m a n c e w h e ns y s t e md e g r a d e d i tp r o v e st h ef e a s i b i l i t ya n dv a l i d a t i o no ft h ep i d f e e d b a c kc o n t r o ls c h e m ef o re d fs c h e d u l i n g t h ec o n c l u s i o n so ft h i st h e s i sc a n b er e f e r e n c e df o rt h e o r ya n da p p l i c a t i o no fr e a l t i m es c h e d u l i n ga l g o r i t h m t h ei n n o v a t i n go ft h i st h e s i si st h a ti n t r o d u c i n gs i n g l en e u r a le l e m e n t s e l f - a d a p t i v ep i ds c h e m et om a k ef e e d b a c kc o n t r o lo nr e a l t i m es c h e d u l i n gb e i v 太原理工大學(xué)碩士研究生學(xué)位論文 m o r ei n t e l l i g e n ta n di m p l e m e n t i n gt h i sa l g o r i t h ma p p l i e di ne m b e d d e dr e a lt i m e s c h e d u l i n g k e yw o r d s ：e m b e d d e dr e a l t i m e s c h e d u l i n ga l g o r i t h m ， p i d v s y s t e m ，r e a l t i m es c h e d u l i n g ，e d f s i n g l en e u r a le l e m e n ts e l f - a d a p t i v e 聲明尸明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在指導(dǎo)教師的指導(dǎo)下， 獨立進行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文 不包含其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究 做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明。本聲明的 法律責(zé)任由本人承擔(dān)。 論文作者簽名：鯔 日期：趔垂皇篁旦! 鯉 關(guān)于學(xué)位論文使用權(quán)的說明 本人完全了解太原理工大學(xué)有關(guān)保管、使用學(xué)位論文的規(guī)定，其 中包括：學(xué)校有權(quán)保管、并向有關(guān)部門送交學(xué)位論文的原件與復(fù)印 件；學(xué)?？梢圆捎糜坝?、縮印或其它復(fù)制手段復(fù)制并保存學(xué)位論文； 學(xué)?？稍试S學(xué)位論文被查閱或借閱；。學(xué)?？梢詫W(xué)術(shù)交流為目的， 復(fù)制贈送和交換學(xué)位論文；學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi) 容( 保密學(xué)位論文在解密后遵守此規(guī)定) 。 簽 名。：螻各 日期：蘭墮璽翊幽 導(dǎo)師簽名：二童旺日期：一 太原理l ：人學(xué)碩十研究生學(xué)位論文 1 1 選題背景 第一章緒論 實時。i 生( r e a l t i m e ) 是指系統(tǒng)能夠在限定時間內(nèi)完成任務(wù)并對外部事件做出及時響應(yīng)。 限定時間的范圍因?qū)崟r應(yīng)用要求的不同而有較大的變化，可以從微秒級到分鐘級。實時 與快速是有區(qū)別的，實時要求快速，但實時不等于快速，快速是無時間限制的，是從事 件發(fā)生到系統(tǒng)響應(yīng)之間的時間越短越快越好。雖然實時也給人們快速的感覺，并且它也 要求系統(tǒng)在一定程度上能快速響應(yīng)。但是，實時是有時間余量和時間期限的。 實時任務(wù)( r e a l t i m e t a s k ) 是指在時間期限內(nèi)啟動，在規(guī)定時間內(nèi)完成的任務(wù)。實時系 統(tǒng)與非實時系統(tǒng)的本質(zhì)區(qū)別就在于實時系統(tǒng)中的任務(wù)都有時間限制，實時任務(wù)必須在其 截止時問內(nèi)丌始和完成。截止時間可以劃分為開始截止時間和完成截止時問兩種。丌始 截止時間要求任務(wù)在某個時間內(nèi)必須丌始執(zhí)行；完成截止則要求任務(wù)在某個時問內(nèi)必須 完成。 實時系統(tǒng)( r e a l t i m es y s t e m s ) 是指計算的正確性不僅取決于程序的邏輯正確性，也取 決于計算結(jié)果產(chǎn)生的時間。如果系統(tǒng)的時間約束條件得不到滿足，將會導(dǎo)致系統(tǒng)出錯。 實時調(diào)度( r e a l t i m es c h e d u l i n g ) 是指在有限的系統(tǒng)資源下，為一系列任務(wù)決定何時以 及在哪個處理器上運行，并分配任務(wù)運行所需要的資源，以保證其時間和資源得到滿足。 調(diào)度的實質(zhì)是資源的分配，包括給任務(wù)分配相應(yīng)的資源和時間從而保證任務(wù)的實時性要 求。 實時調(diào)度是整個實時系統(tǒng)的重要組成部分，采用調(diào)度算法的優(yōu)劣是實時系統(tǒng)性能的 1 關(guān)鍵。實時調(diào)度算法( r e a l t i m es c h e d u l i n ga l g o r i t h m ) 的研究起源于l i u 和l a y l a n d ”1 在1 9 7 3 年提出的單調(diào)速率優(yōu)先算法r m ( r a t e m o n o t o n i ) 幣l 最早截止期優(yōu)先算法e d f ( e a r l i e s t d e a d l i n ef i r s t ) 。他們對這兩個算法的可調(diào)度性判定條件和調(diào)度特性進行了詳細的研究， 但在討論這兩個算法時，他們提出了幾個前提假設(shè)，分別為【2 】： ( 1 ) 所有的任務(wù)請求都是周期性的，具有硬時限要求，即必須在限定的時限內(nèi)完成； ( 2 ) 任務(wù)的時限要求僅限于一個任務(wù)必須在該任務(wù)的下一個請求發(fā)生之自i 完成； ( 3 ) 任務(wù)之間都是獨立的，每個任務(wù)的請求不5 依賴于其他任務(wù)請求的丌始或完成； 太原理l ：人學(xué)碩十研究生學(xué)位論文 ( 4 ) 每個任務(wù)的運行時l 日j 是不變的，這罩任務(wù)的運行時間是指處理器在無中斷情況 下用于處理該任務(wù)的時間； ( 5 ) 調(diào)度和任務(wù)切換的時間忽略不計； ( 6 ) 任務(wù)之間是可搶占的； ( 7 ) 所有任務(wù)的分配都在單處理器上進行。 這些假設(shè)條件一方面方便了問題的討論和模型的建立，但另一方面也限制了整個理 論系統(tǒng)的實用性。隨著實時系統(tǒng)的發(fā)展，這些限定條件不斷遭遇著挑戰(zhàn)，為了改善實時 調(diào)度性能，產(chǎn)生了很多杰出的研究成果。 搶占的e d f 算法被評估為動態(tài)最優(yōu)調(diào)度算法，因其自身的明顯優(yōu)點和缺陷，該算 法在研究應(yīng)用方面?zhèn)涫芮嗖A。e d f 算法以其理論上系統(tǒng)利用率可達1 0 0 的性能優(yōu)點在 各種實時系統(tǒng)中有著廣泛的應(yīng)用，例如，實時操作系統(tǒng)，網(wǎng)絡(luò)通信，多媒體傳輸，自動 化控制等。e d f 算法的缺點是當(dāng)系統(tǒng)發(fā)生過載時，算法的調(diào)度性能會退化很快，甚至?xí)?n 1 引發(fā)多米諾效應(yīng)”。 針對過載問題，到目6 i 己進行了大量以e d f 算法為基礎(chǔ)的調(diào)度機制的研究工作， r d l 產(chǎn)生了許多有效的改進算法，但這類傳統(tǒng)的實時調(diào)度算法所遇到的一個普遍問題是， 任務(wù)的所有時問約束( 如執(zhí)行時問、截止期等) 需要精確知道，并在可預(yù)測環(huán)境下j 能提 供性能保證。然而在許多實際問題中，系統(tǒng)的任務(wù)特征通常是模糊不確定的，比如，任 務(wù)的執(zhí)行時間通常是不準(zhǔn)確的，從而空閑時間也是不準(zhǔn)確的；任務(wù)的關(guān)鍵性也是相對的， 通常不太適合用某個確切的數(shù)值來區(qū)分不同任務(wù)之問的關(guān)鍵程度，任務(wù)的截止期通常也 不是準(zhǔn)確的，它可以在某個范圍內(nèi)隨機變化；至于就緒時間、周期等也不是絕對精確知 道的。所有這些特征都可以看成是不確定的。而隨著此類問題出現(xiàn)，近年來，實時調(diào)度 算法都在不斷優(yōu)化中向著層次化、智能化的方向發(fā)展，因此在許多工業(yè)控制領(lǐng)域都有著 廣泛的應(yīng)用前景。 本課題主要集中研究e d f 實時調(diào)度算法及近年來提出的一些改進算法、及以其為 基礎(chǔ)設(shè)計的調(diào)度控制機制，在深入分析這些研究成果的基礎(chǔ)上，將一種反饋控制機制應(yīng) 用于e d f 算法，以改善實時系統(tǒng)的調(diào)度性能。該反饋控制機制的核心是一個單神經(jīng)元 p i d 算法，使調(diào)度控制更具智能性。反饋機制的引入使得該調(diào)度比傳統(tǒng)調(diào)度更接近于實 際，更適用于在實時系統(tǒng)中實現(xiàn)。 本課題是對計算機技術(shù)，智能控制理論及其綜合運用的探索，希望為將來繼續(xù)探索 2 太原理工大學(xué)碩士研究生學(xué)位論文 與研究實時調(diào)度方面提供一定的依據(jù)。 1 2 實時調(diào)度研究現(xiàn)狀 隨著信息技術(shù)，計算機技術(shù)和移動技術(shù)的發(fā)展，世界迎來了一個新的時代，那就是 以嵌入式系統(tǒng)為核心的“后p c 時代 。伴隨著電子技術(shù)的不斷發(fā)展和數(shù)字信號處理與 人機交互界面等相關(guān)技術(shù)的不斷成熟和完善，嵌入式系統(tǒng)己經(jīng)有了較好的發(fā)展。嵌入式 系統(tǒng)有著無比廣闊的市場需求和發(fā)展前景。一般來說，嵌入式系統(tǒng)是硬件與軟件的結(jié)合， 將特定的軟件固化在一定的硬件環(huán)境上的實用系統(tǒng)。嵌入式軟件與嵌入式硬件共同構(gòu)成 了嵌入式系統(tǒng)。 嵌入式系統(tǒng)通常都具有特定的功能。當(dāng)我們使用電器，使用手機時，我們都會接觸 到一些不同功能的嵌入式系統(tǒng)。絕大多數(shù)的嵌入式系統(tǒng)，都具有實時性能的要求，我們 就把這樣的系統(tǒng)稱為嵌入式實時系統(tǒng)( e m b e d d e dr e a l t i m es y s t e m ) 。同樣，一個實時系統(tǒng) 也有可能在資源上受到限制，從而具有嵌入式特性。 隨著實時系統(tǒng)應(yīng)用范圍的不斷擴大，系統(tǒng)復(fù)雜性不斷提高，以及應(yīng)用背景的不同， 對實時調(diào)度理論提出了許多新的要求： ( 1 ) 過載運行調(diào)度 實踐中，有的實時系統(tǒng)不能保證足夠的時間來處理所有的任務(wù)，無法保證所有的任 務(wù)在時間約束內(nèi)完成，即出現(xiàn)過載運行的情況，此時如何處理和調(diào)度任務(wù)就非常重要。 在任務(wù)調(diào)度的研究領(lǐng)域，很多是針對系統(tǒng)過載的情況進行研究的。在實時調(diào)度算法中， r 氣1 e d f 在正常負(fù)載的情況下是動態(tài)最優(yōu)算法，但是l o c k e 的實驗顯示在過載的情況下 e d f 易導(dǎo)致多米諾效應(yīng)，其執(zhí)行性能會急劇降級。b u t t a z z o 等人提出了系統(tǒng)產(chǎn)生過載時 的兩種處理機制：保證性和健壯性機制，并對幾種基本的調(diào)度算法( 包括e d f ) 采用這兩 種處理機制后的執(zhí)行性能進行了比較，結(jié)論得出在非過載情況下e d f 算法的性能最優(yōu)， 而在過載情況下，采用健壯性機制的最大價值密度算法h d f ( h i g h e s td e n s i t yf i r s t ) 性能 最優(yōu)。該研究還指出，可依據(jù)系統(tǒng)處于不同負(fù)載的情況選擇合適的調(diào)度算法，使調(diào)度更 具靈活性，為以后的算法過載性能研究提供了一定的指導(dǎo)意義。根據(jù)系統(tǒng)處于不同負(fù)載 r 釘 時可采用不同的調(diào)度算法的思想，s s w a m i n a t h a 等人提出了一種混合調(diào)度算法，該算 法將基于價值的調(diào)度與截止期的調(diào)度相結(jié)合，經(jīng)模擬實驗證明，該算法可以對系統(tǒng)處于 3 太原理工大學(xué)碩士研究生學(xué)位論文 過載時的性能有一定的改善。在這一方面，中國科學(xué)院在充分研究e d f 及其他基本調(diào) 度算法過載性能的基礎(chǔ)上，提出了新的算法框架“。該算法將截止期等任務(wù)特征參 f 7 1f r lr 0 1 數(shù)集成到一張優(yōu)先級表中，并以該表作為實時調(diào)度的依據(jù)。經(jīng)實驗證明，該算法相對 e d f 算法有較大改進，在過載時可以在一定程度上實現(xiàn)性能優(yōu)雅降級。 針對搶占引入過載的研究方面，k a t c h e r l l 0 1m 1 等人的實驗結(jié)果表明，在實時系統(tǒng)的 實際實現(xiàn)中，因搶占開銷使預(yù)期的任務(wù)處理器利用率比理想情況低得多。j u k k a n 2 1 3 1 等 人分別改進了l i u 的響應(yīng)時間分析方法r t a ，將帶有偏移量的任務(wù)考慮進來，并逐步 降低了算法復(fù)雜度。a r v i n d ”1 則在其技術(shù)報告中提出了作業(yè)響應(yīng)時間方程，以此來判定 任務(wù)搶占次數(shù)的界限，并據(jù)此修改了e d f 的可調(diào)度條件。r e i n d e r 1 5 1 、r e d e l l 1 句n 刀則分 別提出最好情況和最壞情況下的響應(yīng)時間分析方法，該方法通過優(yōu)化單個任務(wù)的響應(yīng)時 間以減少此任務(wù)被搶占的次數(shù)，但不能確定整個任務(wù)集發(fā)生搶占的次數(shù)是否相應(yīng)減少， 針對此類問題國內(nèi)研究學(xué)者提出了一套對周期性任務(wù)的就緒隊列進行微調(diào)度的搶占模 型n 8 1 ，通過改變搶占關(guān)系來減少搶占次數(shù)、優(yōu)化實時系統(tǒng)性能。 ( 2 ) 多處理器調(diào)度 多處理器系統(tǒng)是指整個系統(tǒng)內(nèi)包含有多個處理器單元，各處理器可以同時并發(fā)工 作。在多任務(wù)單處理器系統(tǒng)中，多個任務(wù)在宏觀上是并發(fā)的，但在微觀上是順序執(zhí)行的。 在多處理器系統(tǒng)中，多個任務(wù)可以分別在不同的處理器上執(zhí)行，宏觀上和微觀上都是并 發(fā)的。按照多處理器的結(jié)構(gòu)，多處理器系統(tǒng)可以分為緊耦合系統(tǒng)和松耦合系統(tǒng)兩種。緊 耦合系統(tǒng)是多個處理器通過共享內(nèi)存空間來交換信息的系統(tǒng)，而松耦合系統(tǒng)是多個處理 器通過通信鏈路來鏈接和交換信息的系統(tǒng)。 現(xiàn)在的計算機也逐步跨進了多核時代。隨著實時應(yīng)用的日趨復(fù)雜，多處理器系統(tǒng)因 其高性能和可靠性，逐漸成為處理復(fù)雜應(yīng)用的有效方法。多處理器實時系統(tǒng)的調(diào)度算法 是一個重要的研究課題。 單處理器e d f 經(jīng)理論證明是動態(tài)最優(yōu)的，在系統(tǒng)不過載的情況下，可以達到1 0 0 的c p u 利用率，也正是因為這一點，e d f 調(diào)度算法被廣泛應(yīng)用于各種實時系統(tǒng)中。然 而，實際證明，單處理器e d f 算法及其他最優(yōu)在線調(diào)度算法必須在足夠快的處理器上 執(zhí)行才能達到最優(yōu)性能，若硬件條件不能提供足夠快的處理速度，這一點就不能保證1 9 1 。 4 太原理工大學(xué)碩士研究生學(xué)位論文 在單處理器下得到的e d f 算法是動態(tài)最優(yōu)的結(jié)論，在多處理器環(huán)境下并不成立。 因為沒有最優(yōu)的多處理器在線調(diào)度算法剛，而且多處理器調(diào)度比單處理器調(diào)度更容易發(fā) 生搶占口1 1 ，因此調(diào)度多處理器調(diào)度算法的研究更復(fù)雜。多處理器系統(tǒng)有局部調(diào)度和全局 調(diào)度兩類實時調(diào)度方法，關(guān)于e d f 的局部調(diào)度算法有e i ) f f f ( e d f f i r s tf i o 算法口2 1 ， 全局調(diào)度算法有e d f 貪心算法g e d f l 2 3 1 ( g r e e d ye d f ) ( 優(yōu)先級越高的任務(wù)得到的處理器 速度越快) 。 ( 3 ) 實時任務(wù)的混合調(diào)度 基于前提：系統(tǒng)中存在硬實時的周期任務(wù)，且它們的c p u 利用率小于1 ，同時存在 軟實時的非周期任務(wù)。調(diào)度目標(biāo)是在保證硬實時周期任務(wù)截止期的前提下，盡可能的提 高軟實時的非周期任務(wù)的響應(yīng)速度。當(dāng)兩種類別不同的任務(wù)放在一起進行調(diào)度時，必須 優(yōu)先讓硬實時周期任務(wù)得到響應(yīng)，保證其滿足截止期限，從而保證系統(tǒng)的可靠性。 般有下面幾種典型的混合調(diào)度方法1 2 4 2 5 1 2 6 1 2 7 ： 基于調(diào)度服務(wù)器模型的軟實時任務(wù)調(diào)度算法。此算法是為了縮短硬實時周期任務(wù) 和軟實時非周期任務(wù)混合調(diào)度中軟實時非周期任務(wù)的響應(yīng)時間以及防止軟實時非周期 任務(wù)錯過其截止期限而提出的調(diào)度算法。通常有：后臺執(zhí)行法、資源保留法和挪用法三 種基于服務(wù)器模型的任務(wù)調(diào)度算法。 軟實時任務(wù)靈活調(diào)度模型及算法。靈活調(diào)度是軟實時調(diào)度發(fā)展的一個趨勢。靈活 調(diào)度不需要我們事先確定任務(wù)的最壞截止時間和預(yù)留系統(tǒng)資源數(shù)量，不需要對實時任務(wù) 的類型加以區(qū)分。在靈活調(diào)度模型中，實時系統(tǒng)被當(dāng)作一個控制系統(tǒng)，任務(wù)通常被看作 各種采樣信號，其目的是通過反饋控制維持實時系統(tǒng)負(fù)載的穩(wěn)定性和系統(tǒng)資源的高利用 率。 弱硬實時模型及調(diào)度算法。弱硬實時能夠準(zhǔn)確而科學(xué)地對軟實時任務(wù)的實時特性 進行界定和分類，使研究者可以方便地對不同的軟實時任務(wù)進行定量分析。在弱硬實時 系統(tǒng)中，實時任務(wù)可以錯過截止期限，但任務(wù)錯過的截止期限必須可預(yù)知且被限制在一 定的范圍內(nèi)。 混合調(diào)度器的設(shè)計方式還有：以截止期劃分任務(wù)子集，對組進行e d f 調(diào)度，對組 內(nèi)任務(wù)的調(diào)度采用其他調(diào)度形式。該調(diào)度結(jié)構(gòu)經(jīng)實驗證明也是有效的，較之單一的調(diào)度 器有適合系統(tǒng)多種需求的優(yōu)勢佇8 1 。 5 太原理工大學(xué)碩士研究生學(xué)位論文 雖然此后對實時調(diào)度算法的分析和研究又進行了多方面的擴展，如有資源共享的周 期任務(wù)、有非周期任務(wù)運行的情況、在分布式實時系統(tǒng)下的調(diào)度算法等等。不過，這些 擴展都是以r m 或e d f 為基礎(chǔ)，r m 和e d f 調(diào)度算法在實時調(diào)度領(lǐng)域中占有重要地位。 對經(jīng)典的r m 和e d f 算法的研究一直都是理論研幫2 9 1 1 3 0 1 的一個重點。 ( 4 ) 反饋調(diào)度 也屬于軟實時任務(wù)靈活調(diào)度的一種，但是。盡管實時調(diào)度有了很多重大的成果，但 許多現(xiàn)實世界中的問題仍不容易解決。雖然e d f ，r m 等調(diào)度算法能支持復(fù)雜的任務(wù)集 特性( 例如截止期，先前約束，共享資源，抖動等等) ，但這些算法都是開環(huán)的調(diào)度算 法。開環(huán)就意味著一旦調(diào)度器被創(chuàng)建，它們就不能基于持續(xù)的反饋進行調(diào)整了。盡管開 環(huán)調(diào)度算法在負(fù)載精確建模的靜態(tài)或動態(tài)系統(tǒng)中執(zhí)行良好，該類算法在不可預(yù)測的動態(tài) 系統(tǒng)環(huán)境下性能還是較差卜1 。 基于這些算法的缺點，因此有必要在實時調(diào)度中引入反饋控制。結(jié)合控制理論的優(yōu) 點，帶有反饋控制器的調(diào)度機制被越來越多的研究和應(yīng)用。其中，由于基本p i d 控制的 優(yōu)點，以p i d 控制作為基本反饋控制技術(shù)的研究比較多，具體理由為以下幾點： ( 1 ) 根據(jù)控制理論，調(diào)度系統(tǒng)是一個動態(tài)系統(tǒng)，例如，一個系統(tǒng)的輸入不僅依賴當(dāng) 前的輸入，還依賴系統(tǒng)以前的輸入。而p i d 控制是一種在動態(tài)系統(tǒng)中廣泛應(yīng)用的控制技 術(shù)。 ( 2 ) 與其他控制技術(shù)相比，p i d 控制的重要特點是它不要求被控系統(tǒng)的精確分析模 型?；诮颇Ｐ偷膒 i d 控制器能達到滿意的性能。而由于當(dāng)前計算機系統(tǒng)中極度復(fù)雜 的行為，不可能精確地為實際調(diào)度系統(tǒng)的動態(tài)因素建模。 ( 3 ) 根據(jù)控制理論，基本的p i d 控制能為低級別的動態(tài)系統(tǒng)提供穩(wěn)定的控制，而自 適應(yīng)的p i d 控制形式能為更高級別的動態(tài)系統(tǒng)提供穩(wěn)定的控制。 1 3 論文的組織結(jié)構(gòu) 本文總體上是通過引入智能p i d 反饋控制調(diào)度機制對實時系統(tǒng)中一個較通用的動 態(tài)優(yōu)先級調(diào)度算法一e d f 調(diào)度算法的實時性能進行優(yōu)化，將每次調(diào)度后獲得的結(jié)果作為 反饋控制的輸入，運用這些輸入值以及動態(tài)調(diào)整的參數(shù)來輔助在線實時系統(tǒng)使用e d f 算法進行實時任務(wù)調(diào)度，來提高實時系統(tǒng)的實時性和穩(wěn)定性。最后用模擬的方法比較了 引入反饋控制機制之前和之后的任務(wù)截止期錯失率，從模擬實驗結(jié)果看出，通過引入反 6 太原理工大學(xué)碩士研究生學(xué)位論文 饋控制機制( 在第四章進行了詳細介紹) 可以對實時任務(wù)的調(diào)度性能進行優(yōu)化，可以積 極改善過載，從而提高嵌入式實時系統(tǒng)的實時性和穩(wěn)定性。 進一步，本論文共分為六章。第一章介紹本論文的選題背景，實時調(diào)度現(xiàn)狀等內(nèi)容， 主要是對論文的概況介紹。第二章詳細說明實時系統(tǒng)以及嵌入式實時操作系統(tǒng)。對嵌入 式系統(tǒng)和實時操作系統(tǒng)等內(nèi)容作了闡述。該章主要是對本論文應(yīng)用背景的分析和研究。 第三章對本論文的主要操作對象一實時調(diào)度作了詳盡的分析和研究。介紹了現(xiàn)有的實時 調(diào)度理論、策略和算法，通過實例對r m 和e d f 調(diào)度算法進行了分析和說明。第四章 對本論文要用到的p i d 反饋控制機制進行了分析。第五章對引入反饋控制的具體方法、 內(nèi)容和過程進行了詳細分析和研究。通過模擬實驗說明使用該方法的可行性和有效性， 改善了e d f 算法的實時調(diào)度性能。該結(jié)論可以為實時調(diào)度算法的研究和使用提供一定 的參考。若應(yīng)用于實踐，可以提高嵌入式實時系統(tǒng)的實時性和穩(wěn)定性。 7 太原理工大學(xué)碩士研究生學(xué)位論文 第二章實時系統(tǒng) 2 1 實時系統(tǒng)的特性及其分類 實時系統(tǒng)( r e a l t i m es y s t e m ) 是具有實時性的計算機系統(tǒng)，是計算機的應(yīng)用與科學(xué)計 算在控制領(lǐng)域應(yīng)用兩者相結(jié)合的結(jié)果。實時系統(tǒng)與非實時系統(tǒng)之間最大的區(qū)別就是要滿 足處理與時間的關(guān)系。實時系統(tǒng)最重要的能力要求就是必須滿足在一個事先設(shè)定好的時 間限制內(nèi)對外部和內(nèi)部的事件進行響應(yīng)和處理的能力。 2 1 1 實時系統(tǒng)特性 實時系統(tǒng)一般應(yīng)具備以下幾個重要的特性： ( 1 ) 實時性 實時系統(tǒng)結(jié)果產(chǎn)生的時間有著嚴(yán)格的要求，只有符合時間要求的結(jié)果才是正確的。 任務(wù)必須在其截止期限內(nèi)完成，以保證系統(tǒng)所產(chǎn)生的結(jié)果在時間上的正確性。 ( 2 ) 可靠性 可靠性主要包含兩個方面的含義：一方面指系統(tǒng)的正確性，即系統(tǒng)本身要連續(xù)穩(wěn)定 運行，系統(tǒng)所產(chǎn)生的結(jié)果在返回值和運行時都是正確的；另一方面指系統(tǒng)的健壯性，即， 如果系統(tǒng)出現(xiàn)了錯誤或外部環(huán)境與預(yù)先假定的外部環(huán)境不符合，系統(tǒng)檢查出故障后要有 一定的補救措施及故障排除功能，系統(tǒng)仍然可以處于可預(yù)測狀態(tài)，仍可以安全地帶錯運 行。 ( 3 ) 并行性 一般來說，實時系統(tǒng)通常有多個外部輸入端口。因此，這就要求系統(tǒng)具有一定的并 行處理能力，以便能同時響應(yīng)來自不同端口的輸入信號。 ( 4 ) 可預(yù)測性 實時系統(tǒng)的任務(wù)必須在一定的限度內(nèi)開始或截止，而這個限度是根據(jù)系統(tǒng)需要定義 的。這意味著系統(tǒng)對來自外部輸入的反映必須全部是可預(yù)測的，即使在最壞的條件下， 系統(tǒng)也要嚴(yán)格滿足截止期限。 9 太原理工大學(xué)碩士研究生學(xué)位論文 2 1 2 實時系統(tǒng)分類 根據(jù)實時任務(wù)側(cè)重點不同可將實時系統(tǒng)進行多種分類。如，按系統(tǒng)的可擴展性可分 為專用系統(tǒng)和開放系統(tǒng)；按系統(tǒng)的集中性可分為集中式系統(tǒng)和分布式系統(tǒng)。下面是兩種 常用的分類方法： 根據(jù)任務(wù)的作業(yè)到達時刻規(guī)律的不同，可分為周期性和非周期性。對于周期任務(wù)， 其相鄰兩次作業(yè)到達時刻之間的間隔是一個固定的數(shù)值，即周期。非周期任務(wù)的作業(yè)到 達時刻則沒有規(guī)律。隨著實時理論的發(fā)展，人們又將非周期任務(wù)進行了細化，分為一般 非周期任務(wù)和零星任務(wù)d 2 1 。零星任務(wù)是非周期任務(wù)的極端情況，其出現(xiàn)的規(guī)律更加難以 預(yù)測。由于周期任務(wù)的到來比較規(guī)律，所以在實時系統(tǒng)中，周期任務(wù)的執(zhí)行比較容易保 障。而一般非周期任務(wù)和零星任務(wù)則由于發(fā)生不規(guī)律，通常不容易保障。 按對截止期限的要求程度可分為硬實時( h a r dr e a l t i m e ) 和軟實時( s o f tr e a l t i m e ) 。硬 實時要求可確定性強，具有明確的時間約束，對系統(tǒng)有很高的實時要求，對操作系統(tǒng)有 嚴(yán)格的實時限制，系統(tǒng)必須及時的對事件做出反應(yīng)，絕對不能發(fā)生錯過截止期限的情況。 如果在某個限定時刻之前不能完成任務(wù)則導(dǎo)致整個實時應(yīng)用的失敗。軟實時也對時間敏 感，而且要求其基本上滿足實時性要求。軟實時允許系統(tǒng)在重負(fù)載的情況下發(fā)生錯過截 止期限的情況，一般不會造成大的危害，不至于影響全局。硬實時系統(tǒng)和軟實時系統(tǒng)在 選擇實時調(diào)度算法上有較大區(qū)別?；趦?yōu)先級調(diào)度的算法可以滿足軟實時系統(tǒng)的實時需 求，而且可以提供高速的響應(yīng)和較大的系統(tǒng)吞吐率。而對硬實時系統(tǒng)來說，需要使用的 算法就應(yīng)該是調(diào)度方式簡單，反應(yīng)速度快的調(diào)度算法。 在現(xiàn)實世界中，硬實時應(yīng)用和軟實時應(yīng)用都大量存在，并可能在同一個系統(tǒng)中共存。 而且，隨著實時應(yīng)用的發(fā)展，實時概念也在不斷地發(fā)展變化。傳統(tǒng)意義上的軟實時任務(wù) 概念不能夠準(zhǔn)確地描述一些新出現(xiàn)的軟實時系統(tǒng)，從而進一步根據(jù)響應(yīng)時間將實時系統(tǒng) 分為了三種類型： ( 1 ) 弱實時系統(tǒng) 弱實時系統(tǒng)是使各個任務(wù)運行的越快越好，沒有嚴(yán)格限定某一任務(wù)必須在多長時間 內(nèi)完成。弱實時系統(tǒng)更多地關(guān)注軟件運行的結(jié)果正確與否及安全性能等其他方面，而對 任務(wù)執(zhí)行時間的要求相對較寬松。一般它的響應(yīng)時間可以是數(shù)十秒或更長，并可能隨著 系統(tǒng)負(fù)載的輕重而有所變化。 ( 2 ) 一般實時系統(tǒng) 】0 太原理工大學(xué)碩士研究生學(xué)位論文 一般實時系統(tǒng)是弱實時系統(tǒng)和強實時系統(tǒng)的折衷。在錯過截止期限后，其計算結(jié)果 的價值是降低而不是變?yōu)? 。它的響應(yīng)時間可以在秒的數(shù)量級上。如p d a 、手機等就屬 于一般實時系統(tǒng)。 ( 3 ) 強實時系統(tǒng)。 在強實時系統(tǒng)中，各個任務(wù)不僅要保證執(zhí)行過程和結(jié)果的正確，同時還要保證在系 統(tǒng)能夠允許的時間內(nèi)完成任務(wù)。錯過截止期限后，任務(wù)計算結(jié)果的價值變?yōu)閛 。它的響 應(yīng)時間在毫秒或者微秒的數(shù)量級上。這對于安全和軍事領(lǐng)域的軟硬件系統(tǒng)來說是至關(guān)重 要的。 2 2 嵌入式系統(tǒng) 嵌入式系統(tǒng)( e m b e d d e ds y s t e m ) 是指以應(yīng)用為中心、以計算機技術(shù)為基礎(chǔ)、軟硬件可 剪裁、適應(yīng)應(yīng)用系統(tǒng)對功能、可靠性、成本、體積和功耗嚴(yán)格要求的專用計算機系統(tǒng)。 可以說，嵌入式系統(tǒng)就是應(yīng)用軟件和系統(tǒng)硬件的一體化，它集成了計算機技術(shù)、半導(dǎo)體 微電子技術(shù)、數(shù)據(jù)傳輸技術(shù)、傳感器技術(shù)，體現(xiàn)了當(dāng)代最新技術(shù)的發(fā)展。硬件部分通常 由嵌入式處理器、內(nèi)存、i o 端口及一些與應(yīng)用密切相關(guān)的控制和電子、機械系統(tǒng)組成。 軟件部分通常由嵌入式操作系統(tǒng)和應(yīng)用軟件組成，高端的應(yīng)用可能還會使用到圖形平 厶 1 7 3o 嵌入式處理器是硬件的核心內(nèi)容，有4 位、8 位、1 6 位、3 2 位、6 4 位的微處理器 可供選擇。通常從功能和應(yīng)用方向可將嵌入式處理器分為以下幾種： ( 1 ) 嵌入式微處理器。嵌入式微處理器目前主要有a m l 8 6 8 8 ，3 8 6 e x ，s c 一4 0 0 ，p o w e r p c ，6 8 0 0 0 ，m i p s ，a r m s t r o n g a r m 系列等。 ( 2 ) 嵌入式微控制器。其典型代表是在控制系統(tǒng)中廣泛應(yīng)用的單片機，即將整個計 算機系統(tǒng)集成到一塊芯片中。最有代表性的通用系列有8 0 5 1 ，m c s 9 6 系列以及m c 6 8 h 系列等。 ( 3 ) 嵌入式d s p 處理器( e m b e d d e dd i g i t a ls i g n a lp r o c e s s o r , e d s p ) 。此種處理器是專 門為信號處理設(shè)計的，其在系統(tǒng)結(jié)構(gòu)和指令算法方面都進行了特殊設(shè)計。目前主要的嵌 入式d s p 處理器主要有r n 公司的t m s 3 2 0 c2 0 0 0 c 5 0 0 0 系列，i n t e l 的m c s 一2 9 6 和 s i e m e n s 的t r i c o r e 等。 嵌入式系統(tǒng)在硬件上受到很多限制，使得軟件同普通軟件有所不同，而這些硬件和 軟件的不同區(qū)分了嵌入式系統(tǒng)的不同發(fā)展階段。嵌入式系統(tǒng)的發(fā)展，大致經(jīng)歷了以下四 l 】 太原理工大學(xué)碩士研究生學(xué)位論文 個階段： 第一階段是以單芯片為核心的可編程控制器形式的嵌入式系統(tǒng)。這種系統(tǒng)大部分應(yīng) 用于專業(yè)性極強的工業(yè)控制系統(tǒng)中，一般沒有操作系統(tǒng)的支持。此階段系統(tǒng)的主要特點 是：系統(tǒng)結(jié)構(gòu)和功能相對單一，處理效率較低，存儲容量較小，幾乎沒有用戶接口。 第二階段是以嵌入式c p u 為基礎(chǔ)、以專用簡單操作系統(tǒng)為核心的嵌入式系統(tǒng)。這一 階段系統(tǒng)的主要特點是：c p u 種類較多，通用性較弱；系統(tǒng)開銷小，效率高；操作系統(tǒng) 具有一定的兼容性和擴展性；應(yīng)用軟件較專業(yè)，用戶界面不夠友好；系統(tǒng)主要用來控制 系統(tǒng)負(fù)載以及監(jiān)控應(yīng)用程序運行。 第三階段是以嵌入式操作系統(tǒng)為標(biāo)志的嵌入式系統(tǒng)。這一階段系統(tǒng)的主要特點是： 嵌入式操作系統(tǒng)能運行于各種不同類型的微處理器上，兼容性好；操作系統(tǒng)內(nèi)核精小、 效率高，并且具有高度的模塊化和擴展性；具備文件和目錄管理、設(shè)備支持、多任務(wù)網(wǎng) 絡(luò)支持、圖形窗口以及用戶界面等功能；具有大量的應(yīng)用程序接口，開發(fā)應(yīng)用程序簡單， 嵌入式應(yīng)用軟件豐富。 第四階段是以基于i n t e m e t 為標(biāo)志的嵌入式系統(tǒng)，這是一個正在迅速發(fā)展的階段。 目前大多數(shù)嵌入式系統(tǒng)還孤立于i n t e m e t 之外，但隨著i n t e m e t 的發(fā)展以及i n t e m e t 技術(shù) 與信息家電、工業(yè)控制技術(shù)等結(jié)合日益密切，嵌入式設(shè)備與i n t e m e t