我想知道是否有可用的Earliest Deadline First (EDF)调度算法的替代方案.如果是,请提供参考链接.

谢谢.

解决方法:

截止日程安排可以分为两类：1)作为实时计算社区的思想; 2)作为调度理论界的思想.类别1是类别2的子集.大多数实时计算从业者不知道类别2.

主要区别在于类别1假设相对简单的特殊情况,即截止日期是满足或错过,并且错过最后期限是失败,因此调度最优性标准是满足所有期限(所谓的“硬”实时) . Earliest Deadline First(EDF)是最常见的1类截止日期调度算法.有关第1类截止日程安排的大量文献 – 例如,在IEEE实时系统研讨会的会议记录中.一本好书是Stankovic等人的Deadline Scheduling for Real-Time Systems – EDF and Related Algorithms.

AFAIK,没有现有的实时操作系统COTS产品实现截止日期调度,特别是EDF.已经尝试了几种商业产品(例如,DEC,IBM),但由于各种困难而被放弃,例如将EDF与OS中的其他资源管理(例如,同步器,非调度活动)集成,同时保持向后兼容性.解决方案是将截止日期调度(EDF和其他算法)从头开始设计为操作系统的组成部分.我知道有三个COTS实时操作系统产品就是这样做的,没有一个产品因为与操作系统无关的组织原因而进入市场：DECs Libra,IBM的OS / 2 for PowerPC(与DEC合作完成),以及Open Software Foundation的OSF-1 Mk7.3a(与DEC和IBM合作完成).从裸硬件设计和实现的一些研究操作系统(例如,CMU的Jensen’s Alpha)已经成功地结合了截止日期调度. Alpha通过允许插入任意调度算法来利用完全*的优势,包括EDF和Utility Acrual算法.其他研究操作系统试图扩充Linux(参见Jonatan Anderson的帖子引用的VA Tech的ChronOS项目). ChronOS受基于Linux的限制,但也支持Utility Accrual调度算法.

类别2一般包含截止日程安排的整个主题,其中类别1是更容易的子集.特别是,第2类承认关于截止日期的早期和迟到的概念.调度最优性标准包括最小化错过的最后期限的数量,最小化平均延迟,最小化最大延迟,以及许多(任何)其他.从技术上讲,类别2减去类别1子集是“软”实时,“虽然实时从业者甚至研究人员使用了许多不同的不精确和不准确的术语”软“实时描述.类别2调度比是第1类调度.然而,它更现实,更广泛适用于许多行业(例如,运输,制造等).文献的内容比第1类更多.一本好的教科书是Pindo的Scheduling: Theory, Algorithms, and Systems .