单处理器环境下实时调度算法研究

摘要

随着网络、通信、多媒体计算的迅猛发展，嵌入式系统得到了广泛的应用，实时系统的应用也逐渐从传统的科学研究、国防、工业控制等领域扩展到人类社会的方方面面。实时系统的研究主要集中在两个最关键的问题上，一个是对实时调度算法的研究，另一个是对实时任务集可调度性判定的研究。本文对应分别提出一种硬实时混合调度的可调度性判定算法IISS和一种改进的最小空闲时间优先(LSF)调度算法DPTLSF。
　　 IISS算法主要是解决硬实时周期任务和偶发任务混合调度情况下的可调度性判定问题，以保证偶发任务的可调度性。基于调度与逆调度的概念，分析了最早截止期优先(EDF)调度中任意时刻的最大可挪用时间的计算方法；IISS算法将偶发任务安排在周期任务的执行空隙与推迟周期任务执行后出现的可挪用时间中执行。根据不同偶发任务特征，确定一个动态挪用时间点Tdynamic，得出偶发任务可调度性判定的充分条件。仿真结果表明，IISS算法的预测准确率比已有算法ISS有明显提高，并且对于不同实时任务集的判定更具灵活性。
　　 DPTLSF算法是针对经典LSF调度算法中任务上下文切换频繁及任务截止错失率较高的缺点提出的。通过分析不同空闲时间的任务抢占对LSF调度算法性能的不同影响，基于抢占阈值策略，设计合理的动态抢占阈值，来避免任务切换频繁造成的“颠簸”现象的发生。仿真结果表明，改进后的算法在不同处理器负载、不同周期任务数情况下，都能够显著地减少上下文切换次数，降低任务集的截止期错失率。