提高软非周期任务响应性能的调度算法

An Algorithm to Improve the Responsive Performance for Scheduling Soft Aperiodic Tasks

实时环境中常常既包含硬周期任务，又包含软非周期任务，引入一种改进软非周期实时任务响应时间的算法．已有的解决混合任务调度问题的方法都是基于速率单调（ＲａｔｅＭｏｎｏｔｏｎｉｃ）策略的，其中从周期任务“挪用时间”的算法被证明优于其他所有算法．但是，速率单调算法限制了处理器的使用率，从而使周期任务的可“挪用”时间受到限制．最后期限驱动（ＤｅａｄｌｉｎｅＤｒｉｖｅｎ）策略ＤＤ可使潜在的处理器利用率达到１００％．新算法正是在周期任务的调度中适当加入了ＤＤ策略，从而使非周期任务的响应时间得以缩短．仿真实验的结果表明，这种算法的性能优于已有的所有算法，而由它所带来的额外开销却不算很高．

Many real time systems have hard deadline periodic tasks along with soft deadline aperiodic tasks. An algorithm to improve response time of soft aperiodic tasks is presented in this paper. Existing methods of scheduling both periodic and aperiodic tasks are all based on RM (rate monotonic) scheme. Among them, stealing slack time from periodic tasks has been proved to be an optimal method. However, the RM scheme limits the processor utilization, therefore limits the stealable time of periodic tasks. The potential processor utilization of the DD (deadline driven) scheme can reach 100%. The presented algorithm applies the DD scheme to periodic task scheduling as it needs, and shortens the response time of aperiodic tasks. The experimental results show that the new algorithm provides performance higher than all existing algorithms, and the increased run time overhead is not very high.