计算机应用研究
APPLICATION RESERCH OF COMPUTERS
2000  Vol.17　No.1　P.35-36




实时系统中任务可调度性研究
舒忠梅　胡金柱　左亚尧
摘 要 讨论了有关实时调度理论，对实时系统采用了时间Petri Net方法来建模，并运用实时调度理论对系统中的任务可调度性能进行了全面分析，给出了详细的分析步骤。
关键词 实时任务调度 时间Petri Net
l　引言
　　实时系统性能的好坏至关重要地影响到我们的日常生活，从空中的卫星、雷达系统到地面的交通监控系统、电梯调度系统，都是实时系统的典型例子。其中，任务可调度性是实时系统中的核心。如何决定某一任务序列是可调度的这个问题至今还没有一个系统的方法，本文以电梯调度实时系统为例，采用时间Petri网方法对系统进行建模表示，并运用实时调度理论分析判断任务的可调度性。
2　背景理论
　　在实时系统设计中，系统的正确性不仅依赖于它的结果，还依赖于产生结果的时间。一组任务如何获悉某个CPU是可调度的，我们用速率单调调度理论来进行分析说明。
2.1　利用率界限定理
　　对于一个周期任务ti，其周期为Ti，最坏情况下执行时间为Ci，则CPU利用率为：
　　　　　　　　　　　　　　　　　　　　(1)
如果任务在它期限之前完成其操作，则认为此任务是可调度的。一组任务中每个任务都能满足其期限，则这组任务是可调度的。根据速率单调调度理论，几个相互独立的周期任务由速率单调算法来调度时，总能满足它们的期限，如果：
　　　　　　　　　　　　　　　　　　(2)
其中Ci/Ti是任务Ti的利用率，当n为无限时，界限就为ln2=0.69。此定理是非常悲观的，在实际应用中，任务集合将永远不会碰到最坏情况。因此，即使在条件不满足时，任务集合可能仍满足其期限。
2.2　完全时间定理
　　完全时间定理可以更精确地决定哪些任务是可调度的。在利用率界限定理不起作用时，可运用此定理。完全时间定理假设在最坏情况下，所有处于就绪状态的周期任务都能同时执行。此定理表明：对于一组相互独立的周期任务，如果比任务ti具有更高优先权的所有任务都在启动时，任务ti仍能满足其期限，则它在任何时候总能满足其期限。在应用此定理时，不仅要检测所给定的任务，还要检测所有具有更高优先权的任务。即对于任务tn，其周期为Tn，执行时间为Cn，假设任务t1到tn-1是所有比tn更高优先权的任务，其周期分别为T1到Tn-1，执行时间分别为C1到Cn-1，则任务tn能在其期限内完成它的操作，如果：
　　　　　　　　　　　　　　　　　(3)
其中，I (Tn/Ti)是大于或等于Tn/Ti的最小整数。
2.3　概括的利用率界限定理
　　低优先权的任务进入临界区，将导致其它高优先权的任务不能使用共享资源，这时出现优先权的反转，为了能说明速率单调优先权的反转，对速率单调调度理论进行了扩展—考虑低优先权任务的阻塞，不必遵守速率单调优先权，使高优先权的任务可被剥夺，这就是概括的利用率界限定理。
2.4　概括的完全时间定理
　　如果运用上述利用率界限定理测试失败，可利用概括的完全时间定理。该定理假设所有的任务在其周期开始时准备执行，通过计算这些任务的结束时间来决定哪些任务能完成操作。这个定理考虑了高优先权任务的可剥夺和低优先权任务的阻塞。
3　实时系统建模及其可调度性分析
　　Petri网(PN)是由库所、变迁、弧及TOKEN组成的有向图，它对于同步系统的建模非常有用。目前，已有了许多关于PN模型的扩展，如：时间Petri网(TPN)允许时间信息与变迁的发生相联系。这对于实时系统建模很有效，使得我们可从性能的角度来分析PN模型，我们以电梯控制器的应用为例来探讨TPN系统模型表示，在此基础上来分析系统中的任务可调度性能。
3.1　模型设计
　　电梯系统主要由楼层控制器、调度子系统、电梯控制器等组成。当楼层控制器监测到电梯按钮输入信号时，就向调度子系统发出服务请求，调度子系统根据服务请示进行调度，并发调度者请求给电梯控制器，电梯控制器则根据调度者请求决定升降状态，并启动马达。由此，我们可以抽象出电梯控制器的状态变迁图，用时间Petri网表示如图1所示。在此基础上进行分析，可以得出此图中的实时任务为：监测电梯按钮任务、请示监测任务、升降状态及决策任务、升降控制任务、监测电梯传感器任务、状态处理任务等。

图1　电梯控制器的TPN模型
3.2　性能分析
　　TPN系统模型的性能可用实时调度理论来分析，我们总结出其评价步骤如下。
　　(1)通过跟踪相应TPN子系统的执行过程获得系统中每个同步任务的时间。在模型中可能不止一条执行路径，因此考虑最大执行时间的最坏情况。在电梯控制器应用中，每个任务的最坏执行时间(记为CPU时间)列举如表1。
　　(2)以子系统为基础定义所有的事件序列，并为这些子系统分配优先权和任务周期(使同一事件序列中的任务具有相同的周期)；对于非周期任务，将之视为周期任务，并让其周期为所在事件序列的最小到达时间。电梯控制器实例中的任务优先权及其周期如表1所示。
表 1　电梯控制器的任务调度分析表
任务CPU时间周期利用率分配的优先权
监测电梯传感器3.52000.01751
升降控制16.52000.08252
状态处理4.52000.02254
监测电梯按钮2.52000.01252
请示监测11.52000.05755
升降状态及决策17.52000.08750

　　(3)根据公式(1)，计算系统中的所有任务的利用率。如果任务是独立的，并保持速率单调优先(如高优先权任务的周期较短)，公式(2)中的条件成立，则系统中的任务满足其期限。否则，回到第(1)步。由表1计算出的所有任务利用率为0.28，比最坏情况下的界限0.69小。但是，此例中的所有任务都具有相同的周期，优先权并不是根据周期的长度来分配的，速率单调优先权失效，因此，要进行下一步的测试。
　　(4)计算每个事件序列的任务利用率。考虑表1中的事件序列：监测电梯传感器，升降控制，状态处理器，升降状态及决策。在最坏情况下，该事件序列的执行时间为42个单位时间，其执行利用率为：
　　42/200 =0.21。
　　(5)计算高优先权可剥夺任务的利用率。在表1的事件序列中，监测电梯按钮可被另一事件序列中的升降控制和升降状态及决策剥夺，这需要2.5个单位时间处理电梯按钮异步信号。另一方面，升降控制又可被升降状态及决策所剥夺。这样执行下去，只需要34个单位时间，故可剥夺利用率为：
　　(34+2.5) /200=0.185。
　　(6)合计第(4)步中的任务利用率和第(5)步中的高优先权可剥夺利用率。如果利用率总和小于利用率界限定理所给定的上界，根据概括利用率界限定理，这个事件序列是满足其期限的。在表1中的事件序列的所有利用率为：0.185+0.21=0.385<0.69，因此该事件序列满足其期限。
　　(7)为系统中的每一事件序列重复执行(4)~(6)步。如果概括利用率界限定理失效，则在下一步运用概括的完全时间定理；否则认为所有的任务是可调度的，性能分析就此结束。
　　(8)对于每一事件序列，计算序列中所有任务的执行时间和不在此序列中但具有高优先权任务的可剥夺时间。如果总的时间小于当前序列的任务周期，根据概括的完全时间定理，此事件序列中的所有任务是可调度的。
4　结束语
　　本文以电梯调度器为例，讨论了实时系统的调度理论及其TPN建模技术，并运用实时调度理论对其性能进行了细致地分析。我们认为TPN方法是建模表示实时系统的良好工具，运用实时调度理论来判定任务的可调度性是有效途径，值得我们进一步地研究和探讨。(注：胡金柱同志为本文第三作者)
舒忠梅（华中师范大学计科系 武汉 430079）
胡金柱（华中师范大学计科系 武汉 430079）
左亚尧（华南师范大学 广州 510631）
参考文献
1P. Huber, K. Jensen, R. Shapiro, Hierarchies in Coloured Petri Nets, Lecture Notes in Computer Science, Vol.483; Advances in Petri Nets 1990, pp313～341
2Heinz Oswald, An Environment for Specifying and Executing Hierarchical Petri Nets, Proceedings of the International Conference on Software Engineering, 1990, pp164～172
3S. Lui, R. Rajkumar, S. S. Sathaye, Generalized Rate-monotonic Scheduling Theory Proceedings of the IEEE, Vol. 82, pp68～82, Fan 1994
收稿日期：1999年6月20日
