安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)

1、第4l卷第7期2004年7月計算機研究與發(fā)展Vol.4l，No.7July2004JOURNALOFCOMPUTERRESEARCANDDEVELOPMENT!安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)楊仕平桑楠陳慧熊光澤（電子科技大學計算機科學與工程學院（）yangsp!摘要為了設計高可信的安全關鍵實時操作系統(tǒng)CRTOS2.0，在分析現(xiàn)有操作系統(tǒng)可信性保障機制的基礎上，提出成都6l0054）了基于時空隔離保護機制構(gòu)建安全關鍵實時操作系統(tǒng)的新思想.空間隔離保護的目的是防止不同地址空間內(nèi)的程序無意或惡意越界進行非法讀寫，而時間隔離保護的目的則是為了防止某程序長期獨占或超時使用處理器而阻止或

2、延遲其他程序的運行在改進傳統(tǒng)處理器能力預留機制的基礎上，基于兩級調(diào)度的思想，提出了新的.為實現(xiàn)時間隔離保護機制，實現(xiàn)方法可從本質(zhì)上增強安全關鍵實時操作系統(tǒng)的可信性.時空隔離保護機制的提出，.關鍵詞安全關鍵；空間隔離；時間隔離；調(diào)度分析；實時操作系統(tǒng)中圖法分類號TP3l6.2DesignandrealizationofsafetyCriticalrealtimeOperatingsystemBasedontemporalisolationsafeguardmechanismsYANGShi-Ping，SANGNan，CENui，andXIONGGuang-Ze（schoolofComPuters

3、cienceandengineering，Unioersityofelectronicscienceandtechnology，Chengdu6l0054）AbstractTodesignhighlydependablesafetycriticalrealtimeoperatingsystemCRTOS2.0，thestatussofexistingoperatingsystemsisfirstlyanalyzed.SincesafetyCuoofdependabilitysafeguardmechanismcriticalsystemsreCuiresthatbothtemporalands

4、patialisolationsafeguardamongdifferentprocessesbemaintained，anovelapproachfordesigningCRTOS2.0isputforward，whichisbasedontemporalandspatialisolationsafeguardmechanism.Thespatialisolationsafeguardmechanismuseshardwarememoryprotectiontoisolateandprotectkernelitselfandusertasksfromincorrectoperationcau

5、sedbyaccidentalandthememoryprotectionprovidessupportformultipleprotectedvirtualerrorsormalicioustampering，thepurposeoftemporalisolationsafeguardaddressspacesdesignedforworst-caseperformance.owever，mechanismistopreventanapplicationfromoverrunningitsallocatedCuotaofresourceusageanddelaytheprogressofot

6、herintegratedapplicationtasks.Inordertorealizetemporalisolationsafeguardmechanism，thetraditionalapproachbasedonprocessorcapacityreservationisimproved，andanovelimplementationapproachbasedontwo-levelhierachicalschedulingapproachisbroughtforwardanddiscussedindetail.ThedependabilityofCRTOS2.0isenhancedw

7、ithtemporalandspatialisolationsafeguardmechanisms.Keywordssystemsafetycritical；spatialisolation；temporalisolation；schedulinganalysis；realtimeoperating速發(fā)展，實時計算日益廣泛應用于航空航天、國防、1引言交通運輸、核電能源和醫(yī)療衛(wèi)生等諸多安全關鍵系l（統(tǒng)safetycriticalsystem，SCS）.這些系統(tǒng)之所以稱為SCS，是因為它們一旦失效將會導致生命財產(chǎn)在后PC時代，隨著我國國民經(jīng)濟信息化的迅收稿日期：修回日期：2003-06-02；20

8、04-03-05基金項目：國家“十五”預研基金項目（；國防科技預研基金項目（4l3l5040l06）2000J6.7.l.DZ0206）7期楊仕平等：安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)1 07的重大損失以及環(huán)境可能遭受嚴重的破壞.如震驚全世界的前蘇聯(lián)切爾諾貝利核事故、美國亞利安娜V型火箭發(fā)射失敗及其最近哥倫比亞號航天飛機的墜毀，都給人們留下了慘痛的教訓.為減少或防2止SCS發(fā)生災難性事故，增強系統(tǒng)的可信性止或延遲其他任務的執(zhí)行，進而可能導致整個系統(tǒng)崩潰不同地址空間內(nèi)的程序非法越界讀寫.除此，也是經(jīng)常發(fā)生的錯誤作為計算機系統(tǒng)中的.可見，兩種重要資源處理器與內(nèi)存，必須同時對其進行有效

9、保護，否則將會因一個或幾個任務中的設計缺陷而導致整個計算機系統(tǒng)的崩潰.由分析可知，為保證SCS的可信性，介于各任務或應用子系統(tǒng)間的隔離保護機制是十分必要的，其目的是把軟件設計缺陷所導致的失效影響控制在一個較小的局部范圍（是重點所在dependability）.其中可信性是指系統(tǒng)在任務開始時且可用性給定的情況下，在規(guī)定的時間和環(huán)境內(nèi)能夠使用且能完成既定功能的能力，即系統(tǒng)“動則成功”的能力實時操作系統(tǒng).而在SCS中，是惟一緊靠硬件的系統(tǒng)軟件，其本身的可信性是其他軟件可信職能的根基，在此本文稱SCS中的實時操作系統(tǒng)為安全關鍵實時操作系統(tǒng)（safetycriticaltimeOperatingsyst

10、em，SCRTOS）.由此可見，為增強SCS的可信性，設計高可信的SCRTOS是重點所在，其目標是使操作系統(tǒng)在其工作范圍內(nèi)提供盡可能強的安全防范機制，在用戶應用程序與系統(tǒng)資源之間進行符合可信策略的調(diào)度，進而防止發(fā)生災難性事故.目前，有關SCRTOS的高可信保障機制已經(jīng)成為開發(fā)商和用戶關注的焦點，是學術(shù)界和商界亟待研究解決的熱點課題.我們正是為了研究課題高可信賴的嵌入式實時操作系統(tǒng)S2.0，進而展開相關研究工作的.為保護計算機系統(tǒng)中的兩種重要資源處理器與內(nèi)存，本文首先說明了實現(xiàn)時間與空間隔離保護的必要性，其中時間隔離保護是為了確保某任務或子系統(tǒng)不會長期獨占或超時使用處理器而阻止或延遲其他子系統(tǒng)的

11、運行，而空間隔離保護則是為了保證各應用子系統(tǒng)及操作系統(tǒng)內(nèi)核有各自獨立的地址空間，同時防止不同地址空間內(nèi)的程序發(fā)生無意或惡意越界讀寫等非法操作.緊接著本文分析了時空隔離保護機制在現(xiàn)有實時操作系統(tǒng)中的應用現(xiàn)狀，同時指出了時空隔離保護機制是構(gòu)建高可信S的關鍵所在.然后，本文重點研究了時間隔離保護機制的實現(xiàn)方式，提出了確定時間隔離保護區(qū)間大小的方法，并通過具體實例進行了例證.最后，就時間隔離保護機制在我室所開發(fā)的嵌入式實時操作系統(tǒng)CRTOS2.0中的實現(xiàn)方式進行了討論，同時也進行了相關的性能測試.時間隔離與空間隔離保護的必要性通常，SCRTOS屬于多任務操作系統(tǒng)，且使用優(yōu)先級調(diào)度算法調(diào)度各任務.假設由

12、于軟件設計不當而導致某任務長期獨占或超時使用處理器，將會阻內(nèi) .由于失效影響可在時間與空間上蔓延，所以相應的隔離保護機制也應從空間與時間兩個方面進行，其中空間隔離保護機制的主要目的是保證各應用子系統(tǒng)及操作系統(tǒng)內(nèi)核有各自獨立的地址空間，同時防止不同地址空間內(nèi)的程序發(fā)生無意或惡意越界讀寫等非法操作；而時間隔離保護機制則是為了確保某子系統(tǒng)不會長期獨占或超時使用處理器而阻止或延遲其他子系統(tǒng)的運行.目前，通用操作系統(tǒng)中的時間隔離保護機制主要通過處理器能力預留方法來實現(xiàn) ，而空間隔離保護機制則通過內(nèi)存保護來實現(xiàn)，即通過處理器的內(nèi)存管理單元及對外設的尋址方式（主要采用內(nèi)存、外設統(tǒng)一尋址的方式）來實現(xiàn)5.對于

13、空間隔離保護，在開發(fā)設計“十五”項目CRTOS2.0時6，我們主要借鑒了L Linux，VxWOrIs中的內(nèi)存管理技術(shù)，設計出了不均等頁面的實時內(nèi)存管理技術(shù)7.鑒于篇幅有限，本文在此不對空間隔離保護機制做詳細論述，而是重點研究時間隔離保護機制的設計與實現(xiàn).通用實時操作系統(tǒng)的局限性眾所周知，處理器是計算機系統(tǒng)中的重要資源之一，操作系統(tǒng)必須對其進行有效保護.否則，將可能存在某應用程序長期獨占處理器而導致其他應用程序餓死，或?qū)е抡麄€系統(tǒng)崩潰，如不斷fOrI（）進程而耗盡整個內(nèi)存空間.由此可見，保護處理器的主要目的是確保某任務可獨占預先分配的CPU處理時間，且不會超時使用處理器而延遲其他任務的運行，即

14、把單個任務的失效影響（獨占或超時使用處理器）盡可能地限制在一個局部時間范圍內(nèi)，防止這種失效影響不斷蔓延（表現(xiàn)為長時間獨占或嚴重超時使用處理器）而危及整個系統(tǒng).由前可知，防止獨占或超時使用處理器持續(xù)發(fā)生的有效措施便是時間隔離.然而，目前具有時間隔離保護功能的實時操作系統(tǒng)很少，這是由于其固有的單級調(diào)度結(jié)構(gòu)（如圖1real“十五”CRTOSCRTO"!1308計算機研究與發(fā)展2004年所示）所決定的.9鑒了交換以太網(wǎng)中的思想，對資源（處理器）的競爭范圍進行了分割，使資源競爭只在各個子系統(tǒng)范圍內(nèi)存在，這樣當一個子系統(tǒng)中的某任務失效時，如獨占處理器，將不會影響另一個子系統(tǒng)中任務的運行本文所設計

15、的.基于分割資源競爭范圍的思想，強制時間隔離保護原理如圖2所示：圖1傳統(tǒng)的單級調(diào)度結(jié)構(gòu)模型由圖1所示的單級調(diào)度結(jié)構(gòu)模型可以看出，所有任務直接運行在處理器上，共享處理器的處理能力.當由于設計錯誤而導致高優(yōu)先級任務長期或超時占用處理器時，這類問題不但很難解決，而且對其他任務的影響也是非常直接的.如任務1獨占處理器時，其余!-1個任務將永遠不可能得到執(zhí)行機會.為了在SCRTOS中實現(xiàn)時間隔離保護功能，Mercer與Savage等人做了大量的前沿研究工作8，但他們都是通過處理器處理能力預留的思想來實現(xiàn)時間隔離保護的，這種基于預留機制的時間隔離保護是以犧牲低優(yōu)先級任務的運行時間為代價的，它只能保證高優(yōu)先

16、級任務的執(zhí)行時間.為設計高可信的SCRTOS，本文將在下面探討實現(xiàn)時間隔離保護機制的新方法.圖2基于強制時間隔離保護區(qū)的調(diào)度模型由圖2可以看出，基于強制時間隔離區(qū)的調(diào)度模型實際上是把所有任務的運行時間劃分為多個時間隔離保護區(qū)，即多個時間片，且每個時間片內(nèi)可運行一個或多個任務.在每個時間隔離保護區(qū)結(jié)束時，處理器被強制轉(zhuǎn)交給下一個時間隔離保護區(qū)中的任務.這種基于強制時間隔離保護區(qū)的調(diào)度模型可把任務的失效影響（獨占處理器）控制在該任務所在的時間隔離保護區(qū)內(nèi)，如任務1獨占處理器時，只會阻止任務2，而不會阻止或延遲任務4，3的執(zhí)行，從而實現(xiàn)了任務（群）間的時，!-1，!的執(zhí)行，5，間隔離保護.下面本文將

17、詳細研究如何實現(xiàn)這種基于強制時間隔離保護區(qū)的調(diào)度模型.!"#基于兩級結(jié)構(gòu)化調(diào)度機制的時間隔離保護模型由圖2及上面的分析可知，實現(xiàn)時間隔離保護區(qū)的關鍵在于處理器處理能力的強制轉(zhuǎn)交，即在每個時間隔離保護區(qū)結(jié)束時，處理器應被強制轉(zhuǎn)交給下一個時間隔離保護區(qū)中的任務何時轉(zhuǎn)交.然而，及怎樣轉(zhuǎn)交處理器是實現(xiàn)時間隔離保護的重點所在本文采用了如圖3所示的兩級結(jié).為解決此問題，10構(gòu)化調(diào)度機制.在圖3所示的兩級結(jié)構(gòu)化調(diào)度機制中，操作系!時間隔離保護機制的新實現(xiàn)由前可知，時間隔離保護的主要目的是確保某任務不會獨占或超時使用處理器而阻止或延遲其他任務的運行，同時把這種獨占或超時使用處理器的失效影響盡可能地控

18、制在很小的時間范圍內(nèi).而在圖1所示的單級調(diào)度結(jié)構(gòu)模型中，所有任務都處于同一個時間范圍內(nèi)，一個任務失效（如獨占處理器）將會直接影響到所有其他任務.為了把這種失效影響控制在一個較小的時間范圍內(nèi)，必須從運行時間上對任務進行強制隔離我們借.為實現(xiàn)強制隔離，圖3基于兩級結(jié)構(gòu)化調(diào)度機制的時間隔離保護模型7期楊仕平等：安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)1309統(tǒng)對各應用任務的調(diào)度是通過高低兩級調(diào)度完成的操作系統(tǒng)首先使用周期性調(diào)度方法.具體實現(xiàn)時，（如時間片輪轉(zhuǎn)）調(diào)用各子系統(tǒng)服務器，即首先為各子系統(tǒng)服務器分配與之相應的處理器時間，然后各子系統(tǒng)服務器再在所分配的處理器時間段內(nèi)使用優(yōu)先級調(diào)度方法（如

19、速率單調(diào)算法）調(diào)度各任務.下面將詳細說明兩級結(jié)構(gòu)化調(diào)度機制的實現(xiàn)方式.!"#兩級結(jié)構(gòu)化調(diào)度模型的實現(xiàn)，!1不是在能力為"a的子系統(tǒng)服務器Sa中被調(diào)度，而是在處理器能力為"a的專用處理器上被調(diào)度相對于處理器能力為1的標準處理.由于"1，a器而言，所有任務的計算時間將增加，即為根據(jù)"a中的充分必要調(diào)度條件可以Lehoczky在文獻13得知，如果子系統(tǒng)Aa內(nèi)的1個任務!，2，!1!1可被處理器能力為"則存在時間a的專用處理器調(diào)度，由第4.1節(jié)的內(nèi)容可知，在實現(xiàn)時間隔離保護機制時，系統(tǒng)中的所有任務不應直接由處理器調(diào)度，而應按功能的不同把所有任

20、務劃分為m個子系統(tǒng)a，且在每個子系統(tǒng)內(nèi)都包含一個子系統(tǒng)服務器Sa，該服務器使用優(yōu)先級搶占調(diào)度算法調(diào)度Aa中的各任務，并同時和其他子系統(tǒng)中的服務器一起共享處理器.另設子系統(tǒng)Aa內(nèi)包含1個任務!1，!2，!1，每個任務!i用三元組Ci，Di，Ti表示，其中Ti為任務!i的周期，Ci為任務!i的最壞執(zhí)行時間，Di為任務!i的死限（deadline），且滿足CiDiTi.為便于后面分析子系統(tǒng)服務器Sa的可調(diào)度性，我們首先作如下定義：定義$"服務器能力.不失一般性，假設標準處理器的總處理速率為1，當把服務器Sa看做一個虛擬處理器時，服務器能力"a是指服務器Sa的處理速率與標準處理器總

21、處理速率的比值.這個比值表示服務器Sa占用標準處理器總處理速率的比例，所以有0"a1.在SCRTOS中，假設操作系統(tǒng)以固定的周期#a周期性地調(diào)度子系統(tǒng)服務器Sa，而在每個子系統(tǒng)周期#a內(nèi)，子系統(tǒng)服務器Sa可使用"a#a個時間單元調(diào)度子系統(tǒng)內(nèi)的任務，其中"a1，且在其余時間間隔#a-"a#a內(nèi)，子系統(tǒng)服務器Sa被阻塞.當子系統(tǒng)服務器S用速率單調(diào)調(diào)度算法11，a使12（ratemonotonicalgorithm，RMA）調(diào)度各任務時，設Sa內(nèi)的1個實時任務按優(yōu)先級關系排序為!1!1-1!1，即!1的優(yōu)先級最高，!1的優(yōu)先級最低.當子系統(tǒng)Aa中的1個任務!1

22、，!2，!1在同一時刻I0=0被初始化時，則在0，I（I0）內(nèi)，優(yōu)先級高于或等于!i的任務所要求的最壞累積處理器時間i為Wi（I）=】Cj>IT，Lehoczky13證明了j=1j在時間段0，I內(nèi)子系統(tǒng)Aa中的任務!i可被調(diào)度i的條件為Wi（I）I，即】Cj>TjI成立.j=1現(xiàn)在我們假設子系統(tǒng)Aa中的1個任務!1，!2，IGHi=ITj】j=1，2，i；I=1，2，DiTjUDi使下式成立：iWi（"a，I）=】j=1"aTjI.（1）式（1）中的Wi（"a，I）表示在時間段0，I內(nèi)且處理器的能力為"a時，優(yōu)先級高于或等于!i的任務所要求的

23、最壞累積處理器時間.為便于下面討論，本文在此定義Bi（"a）=maxI-Wi（，GHi"a，II）B（0"a）=）i=1m，2ax，Bi（"a.由定義可知，當任務，1!i可調(diào)度時，Bi（"a）表示在時間段0，Di內(nèi)處理器沒有運行任何優(yōu)先級高于或等于!i的任務的時間，在此稱Bi（"a）為時間段0，Di內(nèi)的i級非活動周期，同時稱B0（"a）為子系統(tǒng)Aa中的最小非活動周期.由上面的分析可知，當子系統(tǒng)Aa運行在處理能力為"a（"a1）的專用處理器上時，子系統(tǒng)Aa中的各任務均可被調(diào)度.當采用如圖3所示的兩級結(jié)構(gòu)化調(diào)

24、度模型時，假設此時處理器的總處理能力為1.0，則我們需要證明在每個周期#a中，當分配給子系統(tǒng)服務器Sa的處理器能力為"a時，子系統(tǒng)Aa中的各任務均可被調(diào)度，即通過比較運行于子系統(tǒng)服務器Sa與處理器能力為"a的專用處理器上任務集的可調(diào)度性，證明下面的定理1成立.定理$"在基于兩級結(jié)構(gòu)化調(diào)度模型的安全關鍵實時操作系統(tǒng)中，子系統(tǒng)Aa可被周期為#a、服務器能力為"a的子系統(tǒng)服務器Sa調(diào)度的條件為!子系統(tǒng)Aa可在處理器能力為"a的專用處理器上被調(diào)度；"不等式#a-#a"aB0（"a），即#aB0（"a）1-&quo

25、t;a）成立.證明.設運行于子系統(tǒng)服務器Sa中的任務除子系統(tǒng)Aa的1個任務!1，!2，!1外，還包括一個額外的任務!0.額外任務!0在每個周期#a內(nèi)都被調(diào)度，計算時間為C0=#a-"a#a，且任務!0的優(yōu)先級最高，即有!1!1-1!1!0，于是任務!0可搶占子系統(tǒng)Aa中的其他任務.則我們需要證明A（1310計算機研究與發(fā)展2004年的是：即使由于任務T的存在而導致Ae中的任務0被搶占，Ae中的任意任務Ti也能在其死限D(zhuǎn)i到達之前完成其計算中的充分必要調(diào)度.根據(jù)文獻13其中Gi=條件可以得知，如果存在I Hi Gi，i即任務的完成時延等于各任為定理1中的條件"，務死限之前的最

26、小非活動周期證畢.!"#子系統(tǒng)周期!及服務器能力"!的確定由第4.2節(jié)的內(nèi)容可知，定理1實質(zhì)上提供了的方法，即確定子系統(tǒng)服務一種確定參數(shù)對（Oe，e）T器Se被調(diào)度的頻率（大小為1以及應在每周期e）TDi，使lTl=1，2，e eTj=1TjC0 Cj則任務TII成立，.e i在服務器Se上可調(diào)度TOe內(nèi)分配多大的處理器能力e去調(diào)度子系統(tǒng)Ae中T的各任務（O.本節(jié)將詳細研究如何確定參數(shù)對e，另外假設任務Ti可在處理器能力為Oe的專用處理器上被調(diào)度，則存在時間Ii Hi，使Bi（Oe）=Ii -Wi（Oe，Ii ） B0（Oe）0成立，其中i=1，7.由前可知，Wi（Oe，I

27、i）是時間Ii的非遞減函數(shù)，可假設Ii=mTe+S，其中S Te，如果S （0Oe），則有iCjIi Tj+C0Ii j=1Te=eWi（Oe，Ii ）+（m+1）C0 e（Ii -B（0Oe）+（m+1）C0=e（Ii -B（0Oe）+（m+1（）1-Oe）Te e（Ii -B（0Oe）+（1-Oe（）Ii -S）+B（0Oe）=i +（1-Oe（）B0（Oe）-S） Ii .（2）相反，如果S B0（Oe），那么在I/i=mTe Ii 時，則有iCjI/iTj+C0I/ij=1TeOe（Ii -B（0O）+mC0 Oe（Ii -S）+m（1-Oe）Te=OeIi+（1-Oe）I/i=I/i

28、.（3）由于I/i Gi，所以當分配給子系統(tǒng)Ae的處理器能力為Oe時，子系統(tǒng)Ae中的各任務可被服務器e調(diào)度.由條件!的證明過程可知，通過比較服務器Se上的任務執(zhí)行序列與處理能力為Oe的專用處理器上的任務執(zhí)行序列可以看出，在每個子系統(tǒng)周期Te末，服務器Se使用了與專用處理器相同的處理能力（大小為Oe）運行Ae中的各任務，也即定理1中的條件!成立.另外，當Ae中的各任務運行于專用處理器上時，由于此時不存在假定的特殊任務T0，Ae中的各任務將不會被任務T0阻塞，因而它們可在每個周期e內(nèi)更早的完成.當各任務運行于服務器Se之上時，由于服務器Se還要與系統(tǒng)中的其他子系統(tǒng)服務器競爭處理器，所以很有必要增加

29、額外的條件限制服務器Se中各任務的完成時延，該限制條件即Te）.為方便起見，假設子系統(tǒng)服務器Se使用RMA算法調(diào)度子系統(tǒng)Ae中的各任務，同時對處理器能力進行歸一化處理，即令處理器的處理能力為1.0.Liu等人11證明了當處理器能力為1.0且使用RMA算法調(diào)度各任務時，處理器的利用率Pe不會7超過7（217-1），即有式Pe=7（217-1）i=1Ti成立.于是可推知當處理器能力為Oe（Oe1）且使用RMA調(diào)度算法調(diào)度各任務時，由于此時處理器的處理速率降低，則任務的計算時間將增加，即由Ci改變?yōu)镃iOe，于是可得此時處理器的利用率P/e77為 CCi=1OeT，且有iP/e= i=1OeTi 7

30、（217-1）成立.然而當各子系統(tǒng)共享處理器能力為1.0的處理器時，則各子系統(tǒng)內(nèi)的任務可調(diào)度時處理器的利用率為Pe（而不是P/e），于是可推知在SCRTOS中，不等式Pe Oe7（217-1）成立，即Pe（7（217-1） Oe成立.由此可知分配給子系統(tǒng)服務器Se的服務器能力Oe應不小于Pe（7（217-1）.這樣便確定了子系統(tǒng)服務器Se所需的最小處理器能力Oemin，即有Oemin=Pe（7（217-1）.在各Oe之和不大于1.0的前提下，可適當增加各子系統(tǒng)服務器Se的emin值，這樣便可最終確定出各子系統(tǒng)服務器Se的e.在確定好各Oe的值后，便可根據(jù)定理1中的條件"：Te B（0

31、Oe）（1-Oe），確定出與Oe相對應的子系統(tǒng)周期Te，到此便完全確定出了各子系統(tǒng)服務器Se的參數(shù)對（Oe，Te）.為了用實例證明定理1的正確性，假設存在如表1所示的4個子系統(tǒng)，各子系統(tǒng)中包含幾個周期性任務（用三元組Ci，Di，Ti表示）.為方便起見，假設各任務的死限D(zhuǎn)i等于其周期Ti，且在每個周期Te內(nèi)使用RMA算法調(diào)度子系統(tǒng)Ae中的各任務.2BOOOOISTOO7期楊仕平等：安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)表!"個子系統(tǒng)中的任務參數(shù)任務（ ， ， ）子系統(tǒng)12=0.24!1311ms子系統(tǒng)22=0.17!子系統(tǒng)33=0.26!子系統(tǒng)44=0.03!（3，100，1

32、00）（8，110，110）（9，160，160）（13，260，260）（10，330，330）（3，50，50）（4，90，90）（4，120，120）（6，170，170）（6，78，78）（9，110，110）（16，160，160）（1，80，80）（3，140，140）由表1可知，運行完子系統(tǒng)1中的各任務后所，即得到的處理器利用率!1=0.24調(diào)度性，主要目的在于確定參數(shù)對（".由于分 ， ）#配給各子系統(tǒng)的執(zhí)行周期并不一定需要連續(xù)，因而可以在操作系統(tǒng)中靈活地構(gòu)建周期性調(diào)度器，即確定各時間隔離區(qū)間的大小可使操作.為簡單起見，系統(tǒng)中的調(diào)度周期 OS為各子系統(tǒng)調(diào)度周期# 的1

33、4最小值（，即 OS=min.對于表1中的4個子 ）#的一個可行分系統(tǒng)，前面已經(jīng)得到了參數(shù)對（" ， ）#1! 10.24，100110160260330同理可計算出其他子系統(tǒng)的處理器利用率分別為0.17，0.26，0.03.為確定出各子系統(tǒng)服務器 的參數(shù)對（，應采用前面的方法首先確定出各子" ， ）#分系統(tǒng)服務器 .如對于子系統(tǒng)1， 的處理能力"的處理器能力"不應小于配給子系統(tǒng)服務器 11）（ （即"=0.245>（21521 -1）0.32，1min=!）-1）=0.32.同樣可計算出分配給子系統(tǒng)服務器，3，的最小處理器能力"

34、;，3min，分 "2 42min"4min別為0.22，0.33，0.04.在各" 的總和不大于1的情，況下可適當增大所計算出的最小處理器能力"1min，2=0.28，4=0.06便是4個如""1=0.32"3=0.34"子系統(tǒng)的一組可行處理器能力分配.當分配好各子系統(tǒng)的處理器能力"便可由定理1中的條件!確 后，定出與".最后便可以得到4 相應的子系統(tǒng)周期# 個子系統(tǒng)參數(shù)對（的一組可行分配為（"0.32， ， ）#（，（，（，36）0.28，59）0.34，28）0.06，57）.&

35、quot;#"時間隔離區(qū)間大小的確定本文在前面分析了子系統(tǒng)及其內(nèi)部各任務的可5配為（0.32，（0.28，（0.34，（0.06，36）59）28）所以，由于此時的最小子系統(tǒng)周期#s，57） 為28m操作系統(tǒng)中調(diào)度器的調(diào)度周期 OS可設為28m同s，（，（時4個子系統(tǒng)的可行分配將從0.32，36）0.28，（0.34，（0.06，轉(zhuǎn)換為（0.32，59）28）57）28）（，（0.28，28）0.34，28）0.06，28）.當操作系統(tǒng)以每28m分配給4個子系統(tǒng)的s調(diào)度4個子系統(tǒng)時，時間分別為8.96ms=28>0.32ms，7.84ms=28>0.28ms，9.52ms

36、=28>0.34ms，1.68ms=28>即與各子系統(tǒng)相對應的時間隔離區(qū)間大小0.06ms，分別為8.96ms，7.84ms，9.52ms，1.68ms.圖4為操作系統(tǒng)中調(diào)度器的調(diào)度周期 OS等于28ms時的時間隔離區(qū)間序列.除了操作系統(tǒng)周期性地調(diào)度子系統(tǒng)服務器外，子系統(tǒng)服務器還要調(diào)度其內(nèi)部的各任務.為了說明怎樣使用優(yōu)先級調(diào)度算法調(diào)度每個子系統(tǒng)內(nèi)的任務流，我們?nèi)允褂帽?中的例子.由表1可知，在子系統(tǒng)3內(nèi)包含3個實時任務，處理器圖4基于兩級結(jié)構(gòu)化調(diào)度模型的時間隔離保護調(diào)度序列1312計算機研究與發(fā)展2004年將在每28m分s內(nèi)為子系統(tǒng)3的子系統(tǒng)服務器!3配使用RMA調(diào)度9.52ms.

37、假設子系統(tǒng)服務器!3算法調(diào)度子系統(tǒng)內(nèi)的各任務，則在所分配的9.52ms內(nèi)，3個實時任務的調(diào)度序列如圖4的上半部所示.給即將運行的子系統(tǒng)，該子系統(tǒng)再在所分配的時間片內(nèi)調(diào)度各應用任務.而圖5所示的調(diào)度控制流程圖正是整個時間隔離保護機制的實現(xiàn)流程，其中的定時中斷服務器主要用于實現(xiàn)時間隔離、子系統(tǒng)運行環(huán)境切換等功能.5時間隔離保護機制在CRTOS中的實現(xiàn)“九五”期間CRTOS是我校實時系統(tǒng)研究室在開發(fā)的擁有自主知識產(chǎn)權(quán)的嵌入式實時操作系統(tǒng)，它的2.0版本正處于開發(fā)之中“十五”項目研.結(jié)合究高可信賴嵌入式實時操作系統(tǒng)的需要，我們提出了基于時空隔離保護機制構(gòu)建安全關鍵實時操作系統(tǒng)CRTOS的新思想基于內(nèi)存

38、保護技.到目前為止，術(shù)的空間隔離機制已在CRTOS2.0中成功實現(xiàn)，而本節(jié)將簡單介紹時間隔離保護機制在CRTOS2.0中的實現(xiàn)方法.由前面的內(nèi)容可知，要在CRTOS中實現(xiàn)時間隔離保護機制，首先必須把所有任務的運行時間按功能的不同分割成多個時間隔離保護區(qū)本.同時，文使用兩級結(jié)構(gòu)化調(diào)度模型確定出了各時間隔離保護區(qū)的時間片大小，隔離區(qū)大小的確定只是從理論上證明了時間隔離保護機制的可行性，如何在CRTOS中具體實現(xiàn)還有許多問題待解決.由于我們的時間隔離保護機制是基于兩級結(jié)構(gòu)化調(diào)度實現(xiàn)的，則存在兩個調(diào)度器，即CRTOS內(nèi)核中的周期性調(diào)度器與各子系統(tǒng)服務器中的優(yōu)先級調(diào)度器，然而前者處于內(nèi)核空間，而后者則處

39、于用戶空間.由于兩個調(diào)度器處于不同的地址空間，這就需要一種機制能把處理器的控制權(quán)在兩者之間進行轉(zhuǎn)移.除了需要協(xié)調(diào)兩個調(diào)度器外，我們還需要兩個定時器（，timer）一個是位于內(nèi)核空間的定時器，它主要用于確定各時間隔離區(qū)的大小，而另一個則是位于子系統(tǒng)中的定時器，它主要用于配合子系統(tǒng)中的優(yōu)先級調(diào)度器調(diào)度各15為便于理解我們在任務.CRTOS2.0中實現(xiàn)時間隔離保護機制的原理，我們使用圖5所示的調(diào)度圖5子系統(tǒng)的調(diào)度控制流程圖對于CRTOS中的時間隔離保護機制，子系統(tǒng)16，為此我們使用間運行環(huán)境的切換是十分重要的圖6做進一步地詳細說明：圖6時間隔離機制在CRTOS2.0中的實現(xiàn)原理首先假設圖6中的當前子

40、系統(tǒng)正處于運行狀態(tài)，即該子系統(tǒng)擁有處理器的控制權(quán)，一旦當前子系統(tǒng)的時間隔離區(qū)時間片用完，則會連續(xù)發(fā)生以下5個過程：（處1）當前子系統(tǒng)中的定時器產(chǎn)生定時中斷，理此中斷的中斷處理器位于內(nèi)核空間，它首先保存當前子系統(tǒng)的環(huán)境狀態(tài)，以便下一個時間隔離區(qū)到達時能接著執(zhí)行，同時該定時中斷處理器也裝載下一子系統(tǒng)的執(zhí)行環(huán)境；（2）通過事件交付對象實現(xiàn)內(nèi)核空間到用戶空間的轉(zhuǎn)換，其中事件交付對象內(nèi)主要包含時間隔離控制流程圖進行簡單說明.在實現(xiàn)時間隔離保護機制之前，應首先離線建立一個靜態(tài)的調(diào)度時間表，該時間表主要用于指定每個子系統(tǒng)何時可以使用CPU，以及使用CPU的時間長度.實際運行時，CRTOS內(nèi)核應首先檢查調(diào)度時

41、間表，以確定哪一個子系統(tǒng)即將被調(diào)度；緊接著，如設置遞CRTOS內(nèi)核初始化必要的運行環(huán)境，減計數(shù)器以使在每個子系統(tǒng)時間片耗盡時產(chǎn)生定時中斷等；最后，CRTOS內(nèi)核把處理器的使用權(quán)轉(zhuǎn)交期楊仕平等：安全關鍵實時操作系統(tǒng)時間隔離保護機制的設計與實現(xiàn)1313區(qū)間大小等信息；（后，圖6中的下一子系統(tǒng)已擁3）經(jīng)過過程2）有處理器的控制權(quán)，此時該子系統(tǒng)中的事件服務器便做一些日常工作，如初始化子系統(tǒng)內(nèi)部的定時器，除此，事件服務器也調(diào)用子系統(tǒng)內(nèi)部的調(diào)度器；（任務的執(zhí)行環(huán)境由多個處于用戶空4）通常，間與內(nèi)核空間的寄存器組成，當子系統(tǒng)內(nèi)部的調(diào)度器調(diào)度下一個任務時，由于環(huán)境裝載器發(fā)生在用戶空間，則發(fā)生特權(quán)級違反異常，為

42、解決此問題，我們增加了一個周期性調(diào)度器我們.對于應用級任務，仍選用表1中的任務作為實例研究，同時如表1所在基于示把所有任務分為4個子系統(tǒng).由前可知，兩級結(jié)構(gòu)化調(diào)度模型實現(xiàn)時間隔離保護機制時，操作系統(tǒng)內(nèi)核應首先使用周期性調(diào)度器調(diào)度各子系統(tǒng)，而在各子系統(tǒng)內(nèi)部再使用優(yōu)先級調(diào)度算法調(diào)度各任務內(nèi)核中的.當一個子系統(tǒng)切換事件發(fā)生時，周期性調(diào)度器應首先保存當前子系統(tǒng)的運行環(huán)境，同時也應裝載下一個即將執(zhí)行的子系統(tǒng)運行環(huán)境.使用核環(huán)境交換請求原語代表內(nèi)核做環(huán)境裝載工作，同時處理器的控制權(quán)被轉(zhuǎn)交給內(nèi)核；（5）最后，內(nèi)核把處理器的控制權(quán)轉(zhuǎn)交給由內(nèi)核環(huán)境交換請求原語中所確定的任務.以上是我們在研究“十五”項目高可信賴

43、的嵌入式實時操作系統(tǒng)CRTOS2. 所設計的時間隔離保護機制，理論上講，該設計是合理的.可以預測的是，基于兩級調(diào)度思想的時間隔離保護機制存在一定的時空開銷.然而，我們只有有所不為，才能有所為.畢竟，我們所研究的CRTOS主要是針對而設計的，只要其開銷在所允許的范圍內(nèi)，這樣的設計便是合理的、可行的.為此，我們將在下節(jié)中針對上面的設計構(gòu)建相關的實驗原型，同時對其進行性能測評.原型實驗及性能測評為了驗證本文所提出的時間隔離保護機制的可行性，我們使用了華恒科技有限公司的嵌入式評估板HHPPC86 -3COM-2ETH-R1，該評估板上不但集成了摩托羅拉的嵌入式處理器POWerPC86 5 MHZ），還

44、集成有16MB的S R M以及4MB的lash.當然，POWerPC86 支持存儲管理單元MMU）也是我們選用此板的重要原因，它將支持我們在CRTOS中實現(xiàn)空間隔離保護機制.由于本文所設計的時間隔離保護機制是基于兩級調(diào)度結(jié)構(gòu)實現(xiàn)的，因而處理器的時鐘分辨率是至關重要的，erPC86 的最小時鐘分辨率為2 ns，滿足了我們的設計需求.實際應用中，當使用周期性調(diào)度器調(diào)度各子系統(tǒng)服務器時，我們使用的時鐘分辨率為ns，而在各子系統(tǒng)服務器內(nèi)部調(diào)用各任務時，我們所使用的時鐘分辨率為4 ns，這樣做的目的是確保各子系統(tǒng)強制切換時的準確性.在構(gòu)建兩級結(jié)構(gòu)化調(diào)度模型時，我們更改了S原有的單級RM 調(diào)度結(jié)構(gòu)，在此結(jié)

45、構(gòu)之下一旦成功裝載新的子系統(tǒng)運行環(huán)境，該子系統(tǒng)將擁有處理器的使用權(quán)，緊接著在規(guī)定的隔離保護時間片內(nèi)調(diào)度各應用任務.由上面的分析可知，基于兩級結(jié)構(gòu)化調(diào)度模型實現(xiàn)時間隔離保護機制時，相對于傳統(tǒng)的單級調(diào)度模型而言，子系統(tǒng)間的切換開銷是時間隔離保護機制所引入開銷的關鍵所在.為此，我們針對表1中的任務及子系統(tǒng)進行了多次切換開銷測試，其最大、最小及平均測試開銷如表2所示：表"子系統(tǒng)間的切換開銷!m最大開銷最小開銷平均開銷34.326.53 .4必須說明的是，到目前為止，我們已在CRTOS 中成功實現(xiàn)了基于內(nèi)存保護技術(shù)的空間隔離保護機制.而對于時間隔離保護機制，由于實現(xiàn)難度較大，目前我們只是針對表

46、1中的任務群構(gòu)建了一個實驗原型，其目的是為了驗證其可行性.而由表2中的切換開銷可知，基于兩級結(jié)構(gòu)化調(diào)度模型實現(xiàn)時間隔離保護機制時所引入的開銷較小，其實現(xiàn)方式是可行的.作為我們的下一步研究工作，我們準備在內(nèi)核中提供一個通用的模塊，以便根據(jù)任務個數(shù)及子系統(tǒng)功能劃分的需要進行定制.結(jié)束語隨著實時計算技術(shù)在SCS中廣泛應用，系統(tǒng)的可信性問題日益受到關注.為增強SCS的可信性，設計高可信的SCRTOS是重點所在.本文以內(nèi)存與處理器為保護對象，指出時空隔離保護機制是構(gòu)建高可信SCRTOS的關鍵所在.為此，在本文中始終貫穿著“隔離”的思想，并從時間與空間上展開了相應隔離機制的研究，時空隔離機制的目的就是把個

47、體的失效影響控制在局部的時間與空間范圍內(nèi).對于空間隔離，本文只做了簡單討論，而對于時間隔離，鑒于國內(nèi)外的許多操作系統(tǒng)很少涉及，故本文進SCS2.!（F（POW2 CRTO#1314計算機研究與發(fā)展122004年行了詳細研究本文所做的研究工作只能算.然而，是滄海一粟，有關SCRTOS高可信保障機制的研究還有大量的工作需要去做，如不同子系統(tǒng)間數(shù)據(jù)完整性的保證，實時容錯技術(shù)等都是亟待研究課題.隨著該領域研究的深入，我們的國民生活才有可能進一步提高，國防事業(yè)才可能進一步增強.NAudsley，ABurns，MRichardson，!"#$.ardreal-timescheduling：The

48、deadlinemonotonicapproach.The8thIEEEWorkshoponReal-TimeOperatingSystemsandSoftware，13Atlanta，CA，USA，1991JLehoczky，SLiu，YDing.Therate-monotonicschedulingalgorithm：Exactcharacteristicsandaveragecasebehavior.IEEELosAlamitos，CA，1989Real-TimeSystemsSymposium，14CCan，KJLin，CJou.Distanceconstrainedschedulin

49、ganditsapplicationstoreal-timesystems.IEEETransonComputers，參考文獻JCKnight.Safetycriticalsystems：Challengesanddirections.The24thIntlConfonSoftwareEngineering，Orlando，F(xiàn)lorida，2002KJWika.Safetykernelenforcementofsoftwaresafetypolicies：PhDdissertation.Charlottesville，VA：DepartmentofComputerScience，Univers

50、ityofVirginia，1995JWahbe，SLucco，TAnderson.Efficientsoftware-basedfaultisolation.The14thACMSymponOperatingSystemPrinciples，NorthCarolina，UnitedStates，1996GLamastra.Thedesignofoperatingsystemssupportingtemporalisolation：PhDdissertation.Pisa，Italy：ReTisLaboratory，ScuolaSuperioreSAnna，2000CCBakshi，LBela

51、.Avirtualmemorysystemforreal-timeapplications.Real-TimeSystemsSymposium，Arizona，USA，1992MYZhu，LLuo，GZGuang.Aprovablycorrectoperatingsystem：!-Core.ACMSIGOPSOperatingSystemsReview，2001，35（1）：17"33KElphinstone，Geiser.L4referencemanual.SchoolofComputerScienceandEngineering，UniversityofNewSouthWales

52、，TechRep，1997.http：.audisyL4MIPSl4uman.ps.gzCWMercer，SSavage，Tokuda.Temporalprotectioninreal-timeoperatingsystems.The11thIEEEWorkshoponReal-TimeOperatingSystemandSoftware，Seattle，WA，1994YSong.TimeconstrainedcommunicationoverswitchedEthernet.The4thIntlConfonFieldbusSystemsandTheirAppl

53、ications，Nancy，F(xiàn)rance，2001ZDeng，JWLiu.Schedulingreal-timeapplicationsinanopenenvironment.IEEEReal-TimeSystemsSymposium，SanFrancisco，CA，1997CLLiu，JWLayland.Schedulingalgorithmsformultiprogramminginahardrealtimeenvironment.JournalofACM，1973，20（1）：46"611996，45（7）：814"82615YLee，DKim，MYounis，!&

54、quot;#$.PartitionschedulinginAPEXruntimeenvironmentforembeddedavionicssoftware.IEEEReal-TimeComputingSystemsandApplications，iroshima，Japan，199816DKim，YLee，MYounis.SPIRIT-#Kernelforstronglypartitionedreal-timesystems.The7thIntlConfonReal-TimeComputingSystemsandApplications，ChejuIsland，SouthKorea，2000楊仕平男，1974年生，博士研究生，主要研究方向為高可信安全關鍵實時操作系統(tǒng)的防危機制與實現(xiàn)、分布式安全關鍵實時系統(tǒng).桑楠男，1964年生，博士研究生，副教授，主要研究方向為高可信實時系統(tǒng).陳慧女，1973年生，博士研究生，主要研究方向為高可靠硬實時網(wǎng)絡.熊光澤男，1938年生，教授，博士生導