安全关键实时操作系统时间隔离保护机制的设计与实现

1、第4l卷第7期2004年7月计算机研究与发展Vol.4l，No.7July2004JOURNALOFCOMPUTERRESEARCANDDEVELOPMENT!安全关键实时操作系统时间隔离保护机制的设计与实现杨仕平桑楠陈慧熊光泽（电子科技大学计算机科学与工程学院（）yangsp!摘要为了设计高可信的安全关键实时操作系统CRTOS2.0，在分析现有操作系统可信性保障机制的基础上，提出成都6l0054）了基于时空隔离保护机制构建安全关键实时操作系统的新思想.空间隔离保护的目的是防止不同地址空间内的程序无意或恶意越界进行非法读写，而时间隔离保护的目的则是为了防止某程序长期独占或超时使用处理器而阻止或

2、延迟其他程序的运行在改进传统处理器能力预留机制的基础上，基于两级调度的思想，提出了新的.为实现时间隔离保护机制，实现方法可从本质上增强安全关键实时操作系统的可信性.时空隔离保护机制的提出，.关键词安全关键；空间隔离；时间隔离；调度分析；实时操作系统中图法分类号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速发展，实时计算日益广泛应用于航空航天、国防、1引言交通运输、核电能源和医疗卫生等诸多安全关键系l（统safetycriticalsystem，SCS）.这些系统之所以称为SCS，是因为它们一旦失效将会导致生命财产在后PC时代，随着我国国民经济信息化的迅收稿日期：修回日期：2003-06-02；20

8、04-03-05基金项目：国家“十五”预研基金项目（；国防科技预研基金项目（4l3l5040l06）2000J6.7.l.DZ0206）7期杨仕平等：安全关键实时操作系统时间隔离保护机制的设计与实现1 07的重大损失以及环境可能遭受严重的破坏.如震惊全世界的前苏联切尔诺贝利核事故、美国亚利安娜V型火箭发射失败及其最近哥伦比亚号航天飞机的坠毁，都给人们留下了惨痛的教训.为减少或防2止SCS发生灾难性事故，增强系统的可信性止或延迟其他任务的执行，进而可能导致整个系统崩溃不同地址空间内的程序非法越界读写.除此，也是经常发生的错误作为计算机系统中的.可见，两种重要资源处理器与内存，必须同时对其进行有效

9、保护，否则将会因一个或几个任务中的设计缺陷而导致整个计算机系统的崩溃.由分析可知，为保证SCS的可信性，介于各任务或应用子系统间的隔离保护机制是十分必要的，其目的是把软件设计缺陷所导致的失效影响控制在一个较小的局部范围（是重点所在dependability）.其中可信性是指系统在任务开始时且可用性给定的情况下，在规定的时间和环境内能够使用且能完成既定功能的能力，即系统“动则成功”的能力实时操作系统.而在SCS中，是惟一紧靠硬件的系统软件，其本身的可信性是其他软件可信职能的根基，在此本文称SCS中的实时操作系统为安全关键实时操作系统（safetycriticaltimeOperatingsyst

10、em，SCRTOS）.由此可见，为增强SCS的可信性，设计高可信的SCRTOS是重点所在，其目标是使操作系统在其工作范围内提供尽可能强的安全防范机制，在用户应用程序与系统资源之间进行符合可信策略的调度，进而防止发生灾难性事故.目前，有关SCRTOS的高可信保障机制已经成为开发商和用户关注的焦点，是学术界和商界亟待研究解决的热点课题.我们正是为了研究课题高可信赖的嵌入式实时操作系统S2.0，进而展开相关研究工作的.为保护计算机系统中的两种重要资源处理器与内存，本文首先说明了实现时间与空间隔离保护的必要性，其中时间隔离保护是为了确保某任务或子系统不会长期独占或超时使用处理器而阻止或延迟其他子系统的

11、运行，而空间隔离保护则是为了保证各应用子系统及操作系统内核有各自独立的地址空间，同时防止不同地址空间内的程序发生无意或恶意越界读写等非法操作.紧接着本文分析了时空隔离保护机制在现有实时操作系统中的应用现状，同时指出了时空隔离保护机制是构建高可信S的关键所在.然后，本文重点研究了时间隔离保护机制的实现方式，提出了确定时间隔离保护区间大小的方法，并通过具体实例进行了例证.最后，就时间隔离保护机制在我室所开发的嵌入式实时操作系统CRTOS2.0中的实现方式进行了讨论，同时也进行了相关的性能测试.时间隔离与空间隔离保护的必要性通常，SCRTOS属于多任务操作系统，且使用优先级调度算法调度各任务.假设由

12、于软件设计不当而导致某任务长期独占或超时使用处理器，将会阻内 .由于失效影响可在时间与空间上蔓延，所以相应的隔离保护机制也应从空间与时间两个方面进行，其中空间隔离保护机制的主要目的是保证各应用子系统及操作系统内核有各自独立的地址空间，同时防止不同地址空间内的程序发生无意或恶意越界读写等非法操作；而时间隔离保护机制则是为了确保某子系统不会长期独占或超时使用处理器而阻止或延迟其他子系统的运行.目前，通用操作系统中的时间隔离保护机制主要通过处理器能力预留方法来实现 ，而空间隔离保护机制则通过内存保护来实现，即通过处理器的内存管理单元及对外设的寻址方式（主要采用内存、外设统一寻址的方式）来实现5.对于

13、空间隔离保护，在开发设计“十五”项目CRTOS2.0时6，我们主要借鉴了L Linux，VxWOrIs中的内存管理技术，设计出了不均等页面的实时内存管理技术7.鉴于篇幅有限，本文在此不对空间隔离保护机制做详细论述，而是重点研究时间隔离保护机制的设计与实现.通用实时操作系统的局限性众所周知，处理器是计算机系统中的重要资源之一，操作系统必须对其进行有效保护.否则，将可能存在某应用程序长期独占处理器而导致其他应用程序饿死，或导致整个系统崩溃，如不断fOrI（）进程而耗尽整个内存空间.由此可见，保护处理器的主要目的是确保某任务可独占预先分配的CPU处理时间，且不会超时使用处理器而延迟其他任务的运行，即

14、把单个任务的失效影响（独占或超时使用处理器）尽可能地限制在一个局部时间范围内，防止这种失效影响不断蔓延（表现为长时间独占或严重超时使用处理器）而危及整个系统.由前可知，防止独占或超时使用处理器持续发生的有效措施便是时间隔离.然而，目前具有时间隔离保护功能的实时操作系统很少，这是由于其固有的单级调度结构（如图1real“十五”CRTOSCRTO"!1308计算机研究与发展2004年所示）所决定的.9鉴了交换以太网中的思想，对资源（处理器）的竞争范围进行了分割，使资源竞争只在各个子系统范围内存在，这样当一个子系统中的某任务失效时，如独占处理器，将不会影响另一个子系统中任务的运行本文所设计

15、的.基于分割资源竞争范围的思想，强制时间隔离保护原理如图2所示：图1传统的单级调度结构模型由图1所示的单级调度结构模型可以看出，所有任务直接运行在处理器上，共享处理器的处理能力.当由于设计错误而导致高优先级任务长期或超时占用处理器时，这类问题不但很难解决，而且对其他任务的影响也是非常直接的.如任务1独占处理器时，其余!-1个任务将永远不可能得到执行机会.为了在SCRTOS中实现时间隔离保护功能，Mercer与Savage等人做了大量的前沿研究工作8，但他们都是通过处理器处理能力预留的思想来实现时间隔离保护的，这种基于预留机制的时间隔离保护是以牺牲低优先级任务的运行时间为代价的，它只能保证高优先

16、级任务的执行时间.为设计高可信的SCRTOS，本文将在下面探讨实现时间隔离保护机制的新方法.图2基于强制时间隔离保护区的调度模型由图2可以看出，基于强制时间隔离区的调度模型实际上是把所有任务的运行时间划分为多个时间隔离保护区，即多个时间片，且每个时间片内可运行一个或多个任务.在每个时间隔离保护区结束时，处理器被强制转交给下一个时间隔离保护区中的任务.这种基于强制时间隔离保护区的调度模型可把任务的失效影响（独占处理器）控制在该任务所在的时间隔离保护区内，如任务1独占处理器时，只会阻止任务2，而不会阻止或延迟任务4，3的执行，从而实现了任务（群）间的时，!-1，!的执行，5，间隔离保护.下面本文将

17、详细研究如何实现这种基于强制时间隔离保护区的调度模型.!"#基于两级结构化调度机制的时间隔离保护模型由图2及上面的分析可知，实现时间隔离保护区的关键在于处理器处理能力的强制转交，即在每个时间隔离保护区结束时，处理器应被强制转交给下一个时间隔离保护区中的任务何时转交.然而，及怎样转交处理器是实现时间隔离保护的重点所在本文采用了如图3所示的两级结.为解决此问题，10构化调度机制.在图3所示的两级结构化调度机制中，操作系!时间隔离保护机制的新实现由前可知，时间隔离保护的主要目的是确保某任务不会独占或超时使用处理器而阻止或延迟其他任务的运行，同时把这种独占或超时使用处理器的失效影响尽可能地控

18、制在很小的时间范围内.而在图1所示的单级调度结构模型中，所有任务都处于同一个时间范围内，一个任务失效（如独占处理器）将会直接影响到所有其他任务.为了把这种失效影响控制在一个较小的时间范围内，必须从运行时间上对任务进行强制隔离我们借.为实现强制隔离，图3基于两级结构化调度机制的时间隔离保护模型7期杨仕平等：安全关键实时操作系统时间隔离保护机制的设计与实现1309统对各应用任务的调度是通过高低两级调度完成的操作系统首先使用周期性调度方法.具体实现时，（如时间片轮转）调用各子系统服务器，即首先为各子系统服务器分配与之相应的处理器时间，然后各子系统服务器再在所分配的处理器时间段内使用优先级调度方法（如

19、速率单调算法）调度各任务.下面将详细说明两级结构化调度机制的实现方式.!"#两级结构化调度模型的实现，!1不是在能力为"a的子系统服务器Sa中被调度，而是在处理器能力为"a的专用处理器上被调度相对于处理器能力为1的标准处理.由于"1，a器而言，所有任务的计算时间将增加，即为根据"a中的充分必要调度条件可以Lehoczky在文献13得知，如果子系统Aa内的1个任务!，2，!1!1可被处理器能力为"则存在时间a的专用处理器调度，由第4.1节的内容可知，在实现时间隔离保护机制时，系统中的所有任务不应直接由处理器调度，而应按功能的不同把所有任

20、务划分为m个子系统a，且在每个子系统内都包含一个子系统服务器Sa，该服务器使用优先级抢占调度算法调度Aa中的各任务，并同时和其他子系统中的服务器一起共享处理器.另设子系统Aa内包含1个任务!1，!2，!1，每个任务!i用三元组Ci，Di，Ti表示，其中Ti为任务!i的周期，Ci为任务!i的最坏执行时间，Di为任务!i的死限（deadline），且满足CiDiTi.为便于后面分析子系统服务器Sa的可调度性，我们首先作如下定义：定义$"服务器能力.不失一般性，假设标准处理器的总处理速率为1，当把服务器Sa看做一个虚拟处理器时，服务器能力"a是指服务器Sa的处理速率与标准处理器总

21、处理速率的比值.这个比值表示服务器Sa占用标准处理器总处理速率的比例，所以有0"a1.在SCRTOS中，假设操作系统以固定的周期#a周期性地调度子系统服务器Sa，而在每个子系统周期#a内，子系统服务器Sa可使用"a#a个时间单元调度子系统内的任务，其中"a1，且在其余时间间隔#a-"a#a内，子系统服务器Sa被阻塞.当子系统服务器S用速率单调调度算法11，a使12（ratemonotonicalgorithm，RMA）调度各任务时，设Sa内的1个实时任务按优先级关系排序为!1!1-1!1，即!1的优先级最高，!1的优先级最低.当子系统Aa中的1个任务!1

22、，!2，!1在同一时刻I0=0被初始化时，则在0，I（I0）内，优先级高于或等于!i的任务所要求的最坏累积处理器时间i为Wi（I）=】Cj>IT，Lehoczky13证明了j=1j在时间段0，I内子系统Aa中的任务!i可被调度i的条件为Wi（I）I，即】Cj>TjI成立.j=1现在我们假设子系统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内且处理器的能力为"a时，优先级高于或等于!i的任务所要求的

23、最坏累积处理器时间.为便于下面讨论，本文在此定义Bi（"a）=maxI-Wi（，GHi"a，II）B（0"a）=）i=1m，2ax，Bi（"a.由定义可知，当任务，1!i可调度时，Bi（"a）表示在时间段0，Di内处理器没有运行任何优先级高于或等于!i的任务的时间，在此称Bi（"a）为时间段0，Di内的i级非活动周期，同时称B0（"a）为子系统Aa中的最小非活动周期.由上面的分析可知，当子系统Aa运行在处理能力为"a（"a1）的专用处理器上时，子系统Aa中的各任务均可被调度.当采用如图3所示的两级结构化调

24、度模型时，假设此时处理器的总处理能力为1.0，则我们需要证明在每个周期#a中，当分配给子系统服务器Sa的处理器能力为"a时，子系统Aa中的各任务均可被调度，即通过比较运行于子系统服务器Sa与处理器能力为"a的专用处理器上任务集的可调度性，证明下面的定理1成立.定理$"在基于两级结构化调度模型的安全关键实时操作系统中，子系统Aa可被周期为#a、服务器能力为"a的子系统服务器Sa调度的条件为!子系统Aa可在处理器能力为"a的专用处理器上被调度；"不等式#a-#a"aB0（"a），即#aB0（"a）1-&quo

25、t;a）成立.证明.设运行于子系统服务器Sa中的任务除子系统Aa的1个任务!1，!2，!1外，还包括一个额外的任务!0.额外任务!0在每个周期#a内都被调度，计算时间为C0=#a-"a#a，且任务!0的优先级最高，即有!1!1-1!1!0，于是任务!0可抢占子系统Aa中的其他任务.则我们需要证明A（1310计算机研究与发展2004年的是：即使由于任务T的存在而导致Ae中的任务0被抢占，Ae中的任意任务Ti也能在其死限Di到达之前完成其计算中的充分必要调度.根据文献13其中Gi=条件可以得知，如果存在I Hi Gi，i即任务的完成时延等于各任为定理1中的条件"，务死限之前的最

26、小非活动周期证毕.!"#子系统周期!及服务器能力"!的确定由第4.2节的内容可知，定理1实质上提供了的方法，即确定子系统服务一种确定参数对（Oe，e）T器Se被调度的频率（大小为1以及应在每周期e）TDi，使lTl=1，2，e eTj=1TjC0 Cj则任务TII成立，.e i在服务器Se上可调度TOe内分配多大的处理器能力e去调度子系统Ae中T的各任务（O.本节将详细研究如何确定参数对e，另外假设任务Ti可在处理器能力为Oe的专用处理器上被调度，则存在时间Ii Hi，使Bi（Oe）=Ii -Wi（Oe，Ii ） B0（Oe）0成立，其中i=1，7.由前可知，Wi（Oe，I

27、i）是时间Ii的非递减函数，可假设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，所以当分配给子系统Ae的处理器能力为Oe时，子系统Ae中的各任务可被服务器e调度.由条件!的证明过程可知，通过比较服务器Se上的任务执行序列与处理能力为Oe的专用处理器上的任务执行序列可以看出，在每个子系统周期Te末，服务器Se使用了与专用处理器相同的处理能力（大小为Oe）运行Ae中的各任务，也即定理1中的条件!成立.另外，当Ae中的各任务运行于专用处理器上时，由于此时不存在假定的特殊任务T0，Ae中的各任务将不会被任务T0阻塞，因而它们可在每个周期e内更早的完成.当各任务运行于服务器Se之上时，由于服务器Se还要与系统中的其他子系统服务器竞争处理器，所以很有必要增加

29、额外的条件限制服务器Se中各任务的完成时延，该限制条件即Te）.为方便起见，假设子系统服务器Se使用RMA算法调度子系统Ae中的各任务，同时对处理器能力进行归一化处理，即令处理器的处理能力为1.0.Liu等人11证明了当处理器能力为1.0且使用RMA算法调度各任务时，处理器的利用率Pe不会7超过7（217-1），即有式Pe=7（217-1）i=1Ti成立.于是可推知当处理器能力为Oe（Oe1）且使用RMA调度算法调度各任务时，由于此时处理器的处理速率降低，则任务的计算时间将增加，即由Ci改变为CiOe，于是可得此时处理器的利用率P/e77为 CCi=1OeT，且有iP/e= i=1OeTi 7

30、（217-1）成立.然而当各子系统共享处理器能力为1.0的处理器时，则各子系统内的任务可调度时处理器的利用率为Pe（而不是P/e），于是可推知在SCRTOS中，不等式Pe Oe7（217-1）成立，即Pe（7（217-1） Oe成立.由此可知分配给子系统服务器Se的服务器能力Oe应不小于Pe（7（217-1）.这样便确定了子系统服务器Se所需的最小处理器能力Oemin，即有Oemin=Pe（7（217-1）.在各Oe之和不大于1.0的前提下，可适当增加各子系统服务器Se的emin值，这样便可最终确定出各子系统服务器Se的e.在确定好各Oe的值后，便可根据定理1中的条件"：Te B（0

31、Oe）（1-Oe），确定出与Oe相对应的子系统周期Te，到此便完全确定出了各子系统服务器Se的参数对（Oe，Te）.为了用实例证明定理1的正确性，假设存在如表1所示的4个子系统，各子系统中包含几个周期性任务（用三元组Ci，Di，Ti表示）.为方便起见，假设各任务的死限Di等于其周期Ti，且在每个周期Te内使用RMA算法调度子系统Ae中的各任务.2BOOOOISTOO7期杨仕平等：安全关键实时操作系统时间隔离保护机制的设计与实现表!"个子系统中的任务参数任务（ ， ， ）子系统12=0.24!1311ms子系统22=0.17!子系统33=0.26!子系统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可知，运行完子系统1中的各任务后所，即得到的处理器利用率!1=0.24调度性，主要目的在于确定参数对（".由于分 ， ）#配给各子系统的执行周期并不一定需要连续，因而可以在操作系统中灵活地构建周期性调度器，即确定各时间隔离区间的大小可使操作.为简单起见，系统中的调度周期 OS为各子系统调度周期# 的1

33、4最小值（，即 OS=min.对于表1中的4个子 ）#的一个可行分系统，前面已经得到了参数对（" ， ）#1! 10.24，100110160260330同理可计算出其他子系统的处理器利用率分别为0.17，0.26，0.03.为确定出各子系统服务器 的参数对（，应采用前面的方法首先确定出各子" ， ）#分系统服务器 .如对于子系统1， 的处理能力"的处理器能力"不应小于配给子系统服务器 11）（ （即"=0.245>（21521 -1）0.32，1min=!）-1）=0.32.同样可计算出分配给子系统服务器，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"子系统的一组可行处理器能力分配.当分配好各子系统的处理器能力"便可由定理1中的条件!确 后，定出与".最后便可以得到4 相应的子系统周期# 个子系统参数对（的一组可行分配为（"0.32， ， ）#（，（，（，36）0.28，59）0.34，28）0.06，57）.&

35、quot;#"时间隔离区间大小的确定本文在前面分析了子系统及其内部各任务的可5配为（0.32，（0.28，（0.34，（0.06，36）59）28）所以，由于此时的最小子系统周期#s，57） 为28m操作系统中调度器的调度周期 OS可设为28m同s，（，（时4个子系统的可行分配将从0.32，36）0.28，（0.34，（0.06，转换为（0.32，59）28）57）28）（，（0.28，28）0.34，28）0.06，28）.当操作系统以每28m分配给4个子系统的s调度4个子系统时，时间分别为8.96ms=28>0.32ms，7.84ms=28>0.28ms，9.52ms

36、=28>0.34ms，1.68ms=28>即与各子系统相对应的时间隔离区间大小0.06ms，分别为8.96ms，7.84ms，9.52ms，1.68ms.图4为操作系统中调度器的调度周期 OS等于28ms时的时间隔离区间序列.除了操作系统周期性地调度子系统服务器外，子系统服务器还要调度其内部的各任务.为了说明怎样使用优先级调度算法调度每个子系统内的任务流，我们仍使用表1中的例子.由表1可知，在子系统3内包含3个实时任务，处理器图4基于两级结构化调度模型的时间隔离保护调度序列1312计算机研究与发展2004年将在每28m分s内为子系统3的子系统服务器!3配使用RMA调度9.52ms.

37、假设子系统服务器!3算法调度子系统内的各任务，则在所分配的9.52ms内，3个实时任务的调度序列如图4的上半部所示.给即将运行的子系统，该子系统再在所分配的时间片内调度各应用任务.而图5所示的调度控制流程图正是整个时间隔离保护机制的实现流程，其中的定时中断服务器主要用于实现时间隔离、子系统运行环境切换等功能.5时间隔离保护机制在CRTOS中的实现“九五”期间CRTOS是我校实时系统研究室在开发的拥有自主知识产权的嵌入式实时操作系统，它的2.0版本正处于开发之中“十五”项目研.结合究高可信赖嵌入式实时操作系统的需要，我们提出了基于时空隔离保护机制构建安全关键实时操作系统CRTOS的新思想基于内存

38、保护技.到目前为止，术的空间隔离机制已在CRTOS2.0中成功实现，而本节将简单介绍时间隔离保护机制在CRTOS2.0中的实现方法.由前面的内容可知，要在CRTOS中实现时间隔离保护机制，首先必须把所有任务的运行时间按功能的不同分割成多个时间隔离保护区本.同时，文使用两级结构化调度模型确定出了各时间隔离保护区的时间片大小，隔离区大小的确定只是从理论上证明了时间隔离保护机制的可行性，如何在CRTOS中具体实现还有许多问题待解决.由于我们的时间隔离保护机制是基于两级结构化调度实现的，则存在两个调度器，即CRTOS内核中的周期性调度器与各子系统服务器中的优先级调度器，然而前者处于内核空间，而后者则处

39、于用户空间.由于两个调度器处于不同的地址空间，这就需要一种机制能把处理器的控制权在两者之间进行转移.除了需要协调两个调度器外，我们还需要两个定时器（，timer）一个是位于内核空间的定时器，它主要用于确定各时间隔离区的大小，而另一个则是位于子系统中的定时器，它主要用于配合子系统中的优先级调度器调度各15为便于理解我们在任务.CRTOS2.0中实现时间隔离保护机制的原理，我们使用图5所示的调度图5子系统的调度控制流程图对于CRTOS中的时间隔离保护机制，子系统16，为此我们使用间运行环境的切换是十分重要的图6做进一步地详细说明：图6时间隔离机制在CRTOS2.0中的实现原理首先假设图6中的当前子

40、系统正处于运行状态，即该子系统拥有处理器的控制权，一旦当前子系统的时间隔离区时间片用完，则会连续发生以下5个过程：（处1）当前子系统中的定时器产生定时中断，理此中断的中断处理器位于内核空间，它首先保存当前子系统的环境状态，以便下一个时间隔离区到达时能接着执行，同时该定时中断处理器也装载下一子系统的执行环境；（2）通过事件交付对象实现内核空间到用户空间的转换，其中事件交付对象内主要包含时间隔离控制流程图进行简单说明.在实现时间隔离保护机制之前，应首先离线建立一个静态的调度时间表，该时间表主要用于指定每个子系统何时可以使用CPU，以及使用CPU的时间长度.实际运行时，CRTOS内核应首先检查调度时

41、间表，以确定哪一个子系统即将被调度；紧接着，如设置递CRTOS内核初始化必要的运行环境，减计数器以使在每个子系统时间片耗尽时产生定时中断等；最后，CRTOS内核把处理器的使用权转交期杨仕平等：安全关键实时操作系统时间隔离保护机制的设计与实现1313区间大小等信息；（后，图6中的下一子系统已拥3）经过过程2）有处理器的控制权，此时该子系统中的事件服务器便做一些日常工作，如初始化子系统内部的定时器，除此，事件服务器也调用子系统内部的调度器；（任务的执行环境由多个处于用户空4）通常，间与内核空间的寄存器组成，当子系统内部的调度器调度下一个任务时，由于环境装载器发生在用户空间，则发生特权级违反异常，为

42、解决此问题，我们增加了一个周期性调度器我们.对于应用级任务，仍选用表1中的任务作为实例研究，同时如表1所在基于示把所有任务分为4个子系统.由前可知，两级结构化调度模型实现时间隔离保护机制时，操作系统内核应首先使用周期性调度器调度各子系统，而在各子系统内部再使用优先级调度算法调度各任务内核中的.当一个子系统切换事件发生时，周期性调度器应首先保存当前子系统的运行环境，同时也应装载下一个即将执行的子系统运行环境.使用核环境交换请求原语代表内核做环境装载工作，同时处理器的控制权被转交给内核；（5）最后，内核把处理器的控制权转交给由内核环境交换请求原语中所确定的任务.以上是我们在研究“十五”项目高可信赖

43、的嵌入式实时操作系统CRTOS2. 所设计的时间隔离保护机制，理论上讲，该设计是合理的.可以预测的是，基于两级调度思想的时间隔离保护机制存在一定的时空开销.然而，我们只有有所不为，才能有所为.毕竟，我们所研究的CRTOS主要是针对而设计的，只要其开销在所允许的范围内，这样的设计便是合理的、可行的.为此，我们将在下节中针对上面的设计构建相关的实验原型，同时对其进行性能测评.原型实验及性能测评为了验证本文所提出的时间隔离保护机制的可行性，我们使用了华恒科技有限公司的嵌入式评估板HHPPC86 -3COM-2ETH-R1，该评估板上不但集成了摩托罗拉的嵌入式处理器POWerPC86 5 MHZ），还

44、集成有16MB的S R M以及4MB的lash.当然，POWerPC86 支持存储管理单元MMU）也是我们选用此板的重要原因，它将支持我们在CRTOS中实现空间隔离保护机制.由于本文所设计的时间隔离保护机制是基于两级调度结构实现的，因而处理器的时钟分辨率是至关重要的，erPC86 的最小时钟分辨率为2 ns，满足了我们的设计需求.实际应用中，当使用周期性调度器调度各子系统服务器时，我们使用的时钟分辨率为ns，而在各子系统服务器内部调用各任务时，我们所使用的时钟分辨率为4 ns，这样做的目的是确保各子系统强制切换时的准确性.在构建两级结构化调度模型时，我们更改了S原有的单级RM 调度结构，在此结

45、构之下一旦成功装载新的子系统运行环境，该子系统将拥有处理器的使用权，紧接着在规定的隔离保护时间片内调度各应用任务.由上面的分析可知，基于两级结构化调度模型实现时间隔离保护机制时，相对于传统的单级调度模型而言，子系统间的切换开销是时间隔离保护机制所引入开销的关键所在.为此，我们针对表1中的任务及子系统进行了多次切换开销测试，其最大、最小及平均测试开销如表2所示：表"子系统间的切换开销!m最大开销最小开销平均开销34.326.53 .4必须说明的是，到目前为止，我们已在CRTOS 中成功实现了基于内存保护技术的空间隔离保护机制.而对于时间隔离保护机制，由于实现难度较大，目前我们只是针对表

46、1中的任务群构建了一个实验原型，其目的是为了验证其可行性.而由表2中的切换开销可知，基于两级结构化调度模型实现时间隔离保护机制时所引入的开销较小，其实现方式是可行的.作为我们的下一步研究工作，我们准备在内核中提供一个通用的模块，以便根据任务个数及子系统功能划分的需要进行定制.结束语随着实时计算技术在SCS中广泛应用，系统的可信性问题日益受到关注.为增强SCS的可信性，设计高可信的SCRTOS是重点所在.本文以内存与处理器为保护对象，指出时空隔离保护机制是构建高可信SCRTOS的关键所在.为此，在本文中始终贯穿着“隔离”的思想，并从时间与空间上展开了相应隔离机制的研究，时空隔离机制的目的就是把个

47、体的失效影响控制在局部的时间与空间范围内.对于空间隔离，本文只做了简单讨论，而对于时间隔离，鉴于国内外的许多操作系统很少涉及，故本文进SCS2.!（F（POW2 CRTO#1314计算机研究与发展122004年行了详细研究本文所做的研究工作只能算.然而，是沧海一粟，有关SCRTOS高可信保障机制的研究还有大量的工作需要去做，如不同子系统间数据完整性的保证，实时容错技术等都是亟待研究课题.随着该领域研究的深入，我们的国民生活才有可能进一步提高，国防事业才可能进一步增强.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，Florida，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，France，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年生，博士研究生，主要研究方向为高可信安全关键实时操作系统的防危机制与实现、分布式安全关键实时系统.桑楠男，1964年生，博士研究生，副教授，主要研究方向为高可信实时系统.陈慧女，1973年生，博士研究生，主要研究方向为高可靠硬实时网络.熊光泽男，1938年生，教授，博士生导