基于RMS调度周期、非周期混合任务集的一种新方法(西北工业大学，陕西西安710072)摘要：提出了一种利用速率单调（RMS）算法确定计算机实时系统中整个任务集优先级的新方法。该方法利用数理统计的规律克服了普通RMS算法只能对系统中周期任务进行有效调度而不能对系统中的非周期任务进行有效调度的局限，扩大了RMS算法的适用范围，简化了非周期任务的处理过程，减小了系统开销。利用该方法在先进飞机电气综合控制与管理系统中进行了整个任务集的可调度性测试、验证，并给出了任务集的实际调度的验证实例。??关键词：速率单调算法；周期任务；非周期任务；分布假设检验；可调度性测试与验证??中图法分类号：TP316．2文献标识码：A：1001-3695(2006)08-0076-04??NewMethodofSchedulingPeriodicandAperiodicTasksviaRMS??XIEShuanqin,NIUYun,LINWen??（NorthwesternPolytechnicalUniversity,Xi’anShanxi710072,China）Abstract:ThispaperadvancesanewmethodbasedonRateMonotonicScheduling(RMS)whichcanbeusedtodeterminethepriorsofthetasksincomputerrealystem.ThemethodovercomesthefaultthatcommonRMSonlyadaptstoperiodictasksbymeansofthetheoryaboutmathematicalstatistics,anditmakestheprocessofhandlingaperiodictaskssimplerthantraditionalmethods.Finallytheschedulabilityofthewholetasksiscalculatedtomakesureallthetaskscansatisfytheirdeadlinesandtheresultofexperimentshowthatthescheduletablebasedonthenewmethodisschedulable.??Keywords:RateMonotonicScheduling(RMS);PeriodicTasks;AperiodicTasks;TestingStatisticalHypotheses;TestingandValidatingforSchedulability实时系统最本质的特征是指系统能够在规定的时间内响应事件的请求并给出正确的处理结果。评判实时系统的正确性不仅依赖于计算结果，而且还与该计算结果产生的时间开销有关。如果任务没有在规定的时间内完成，计算结果不仅毫无意义，甚至还会引起严重后果。因此，实时系统的首要目标是满足系统内实时任务的时间约束，合理地调度并执行这些任务，使之能在各自的规定时限之前完成操作。这就使高效的调度算法成为提高实时系统性能的关键之一。??1任务的优先级驱动调度算法??实时系统中的任务可以分为周期性任务和非周期性任务两大类。周期任务是指计算或数据传输按照规则的或半规则的时间间隔，反复不断地执行，以便为系统提供某个功能；非周期任务是系统为了处理一些异步事件或紧急事件所需要执行的任务，这类任务占用机时较少而且数目也较少。实时系统的任务调度处理过程是先调度周期任务，在保证周期任务时限约束的基础上，再考虑如何调度非周期任务。当整个任务集通过调度执行都满足各自的任务时限，则称此任务集是可调度的。优先级驱动调度算法是一种常用的实时任务调度算法，可分为两大类：①静态调度算法是指事先为每个任务赋予一个优先级，然后根据优先级大小调度任务，主要算法有先进先出法（FIFO）、速率单调调度算法（RMS）、时限单调调度算法（DMS）等；②动态调度算法主要有最早紧急度优先（LLF）、最早任务期限优先（EDF）、最短处理时间优先（SPTF）、最小裕度算法等。动态调度算法虽然在某些性能上优于静态调度算法，但静态调度算法比动态调度算法的额外开销小，稳定性和可预测性好，分析任务的时间行为较为容易，便于实现。经实际验证，目前综合指标最优的静态调度算法是RMS算法。该算法主要是解决单一处理器上的多任务调度问题，其基本思想是基于任务的周期设置其优先级，周期越短，任务的优先级越高，再根据任务优先级高低调度执行。但传统的RMS只适用于周期任务的调度，本文将提出一种新方法使RMS也适用于非周期任务的调度。这样做的主要依据是任务的可调度性，讨论可调度性之前，先对周期任务和非周期任务建模。??设有一个任务集??s=Tp1,Tp2,…,Tpnn;Tap1,Tap22,…,Tapm（1）????其中，Tpi(1≤i≤n)??为周期任务，每个周期任务Tpi可用式（2）所示的四元式表示：??Tpi=(Cpi,Ppi,Rpi,Dpi)（2）??其中，Cpi为任务的最大计算时间，Ppi为任务周期，Rpi为任务触发时刻，Dpi为任务...