论文部分内容阅读
本文对单处理器下非周期实时任务调度进行研究。单处理器系统具有结构简单、开销低廉的特点，应用十分广泛。研究单处理器实时系统调度方法，不仅能够丰富实时系统理论，还对实时系统的设计、制造具有重要的实际应用价值。 对于单处理器系统，最早截止期优先(EDF)优先级算法是最优的优先级算法。为保证非周期实时任务的截止期约束，研究EDF优先级下非周期任务的准入控制非常必要。已有的准入控制算法要么存在相当的悲观度，影响系统性能，要么时间复杂度较高，不适合处理非周期任务的单处理器实时系统。除要满足一般准入控制算法系统安全性和低悲观度的要求外，单处理器非周期任务准入控制研究还面临着多项挑战，包括:(i)实现基于利用率的最优准入控制算法;(ii)研究最优利用率的逼近方法和(iii)在常数时间复杂度内实现性能理想的准入控制算法。 针对上述挑战性问题，本文开展了以下创新性工作: 1.提出了基于利用率的最优准入控制算法OPAC。证明了OPAC的最优性，即:(i)OPAC是安全的;(ii)OPAC的准入能力强于任何其他安全的基于利用率的准入控制算法，也就是说在相同的系统状态下，凡是能被任何其他同类算法准入的任务都能被OPAC准入且能被OPAC准入的任务不一定能被其他同类算法准入。 2.提出了最优利用率的逼近方法。定义了特征利用率并通过设计特征利用率的逼近方法实现了对最优利用率的逼近。证明了基于特征利用率的准入控制算法CIS是能区分任务利用率的最优准入控制算法，即:(i)CIS是安全的;(ii)CIS的准入能力强于任何其他安全的能区分任务利用率的准入控制算法。此外，还证明了CIS的准入能力强于已有最好的基于利用率的单处理器非周期任务准入控制算法ASL。通过特征利用率的逼近方法能较高精度地实现对最优利用率的逼近。 3.提出了接近最优的常数时间复杂度准入控制算法CTAC。基于最优利用率的逼近方法，CTAC克服了已有方法低估任务总资源使用量的问题，在常数时间复杂度内计算更精确的系统利用率，大幅降低了准入控制的悲观度。证明了:(i)CTAC是安全的;(ii)CTAC的准入能力强于ASL。通过实验进行的性能评估表明CTAC的各方面性能均明显强于ASL且十分接近基于利用率的最优准入控制算法OPAC。 4.将准入控制算法CTAC应用于实时推理系统中。为有效解决实时推理问题，对实时推理问题进行了建模，提出了实时推理方法框架。基于扩展后的CTAC，提出了一个新的实时推理任务调度算法RTINF。扩展后的CTAC进一步降低了对推理任务进行准入控制时算法的悲观度且适用于任务执行时间动态变化的实时系统，进一步扩大了CTAC算法的适用范围。