一种基于EDF的实时任务调度算法浅析

刘伟

摘 要 实时系统的高可靠性、计算准确性及输出结果的实时性使得其在各领域的应用越来越广泛。而实时调度算法是实时系统中的关键技术。本文在EDF算法的基础上提出了一种新的实时调度算法，该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间。

关键词 实时性；实时调度算法；单调速率优先；最早截止期优先；计算时间

前言

实时系统是指能够及时响应外部发生的随机事件，并在规定时间内完成对事件处理的计算机系统。实时系统具有高可靠性、实时性、少人工干预、专用性等特征，广泛应用于航天控制、工业控制、机器人智能控制、云计算、多处理器下多媒体流调度以及嵌入式智能设备等各个重要领域。实时系统不仅应用广泛，而且要求严格。对实时调度算法的研究，是实时领域的一个重要的研究课题[1]。

1 实时调度算法

实时调度算法可以分为两类：静态调度算法和动态调度算法。RM 和 EDF 调度算法分别是经典的静态和动态实时高度算法，在实时调度领域占有重要地位。EDF调度算法按照实时任务截止期的远近来分配优先级，截止期越近的任务优先级越高，任何时刻总是运行优先级最高的任务，即总是优先运行最紧迫的任务。因为在不同时刻，两个周期任务截止期的远近关系可能会改变，所以EDF调度算法是一种动态优先级调度算法。EDF算法不仅对于硬实时周期任务调度，而……