摘要：提出了一种新的CP调度算法，即早期截止（EDF）算法，该算法能够保证硬实时任务不丢失死线，然后易于在分时系统中实现，在分时EDF算法的基础上，提出了一种新的CPU分层调度算法hrfsfq，该算法能够保证不同任务的QS在最后通过人量实验证明上述算法的有效性和正确性。

关键词：分时EDF，多媒体操作系统，CPU调度，HRFSFQ

1、引言

新的多媒体操作系统中有多种类型的任务，如实时硬拷贝、实时软拷贝等。不同的任务对内存、CPU处理器以及其他的系统有着不同的QoS需求。其中最关键也最困难的调度是CPU，所以当下要求合理分配系统的资源，让不同的任务实现自己的QoS的方法是多媒体操作系统首当其冲应该解决的问题。

如今，在多媒体操作系统中有两个主要的链接来实现CPU调度：一是通过多媒体来提高实时任务的优先顺序等加强对现有的分时操作系统的实时任务的支持。这样的方法通常很容易实现，而且与一般的操作系统里安装的应用程序是兼容的。但如果通常使用一般的的调度算法是非常难实现任务的兼容控制，很容易导致系统超负荷运转，不仅没有办法完成任务，更有可能直接使任务终端死机。其次如果想要实现实时任务的这一需求就需要在新的多媒体操作系统中如果使用RM和EDF的常规调度算法。这些常规的调度算法最常出现在工业控制、军事领域的实时任务调度当中。当您在多媒体系统中处理其他类型的工作时，会浪费大量的资源，而且在将实时操作系统用作一般操作系统之前还有很长的路要走。因此，前者是多媒体操作系统在未来的发展中最重要的发展方向。

分级调度方法的出现，是因为要实现多媒体操作系统中多个任务的共存而提出的。这种方法是要使用满足这个级别的调度算法来调度次级别的任务，也就是要将CPU带宽按一定的比例分配给每个任务类别。类间调度算法必须认识到，不同任务之间的分离，即特定类型任务的操作不会影响其他任务类别的带宽，而是会影响WFQ、efvdf、FQ、SFQ等带宽。在使用压缩算法的多媒体操作系统来说最困难的是必须要WFQ和ELF来预测所执行任务的执行时间。SFQ算法不具有上述缺陷，并且可以保证各种任务的最大延迟，并且易于实现在时间共享系统中。但是，因为不容易找到时隙，所以不能完全保证硬件实时任务不会失去死角。

基于上述考察，本文首先提出了一种时间共享EDF算法，其能够确保时间共享系统中的硬件实时任务的QoS，并提供算法的调度测试条件。因此，通过将用于时间共享和CPU层间调度的SFQ算法组合起来，提出hrfsfq算法。

2、模型定义

定义1：硬实时任务t定义为二进制（CP表示任务周期中的最大运行时间，p表示任务周期，而死线）是下一个周期的开始时间。硬实时任务类表示为一组（T1、T2、TN）。为了进一步证明，本文假设周期P1≤p2∞我不知道PN中

定义2：硬实时任务类的具体硬实时任务类定义为{（T1，R1）、（T2R2）我不知道n，r）表示第一个请求的任务t和时间。硬实时任务类可以触发多个不同的特定硬实时任务类在调度算法下可以调度硬实时任务类，这意味着在算法下可以调度任何特定的硬实时任务类

定义3：如果CPU调度时间许可长度为d，则系统调度任务的时间定义为相邻两个调度点之间的最大间隔d。在以下说明中，假设DP。如果不这样做的话，很容易就能明白无论采用了哪个调度算法，任务组都不能进行调度

定义4：硬件实时任务类是累积状态，此含义将表明当下有需要等待解决或者要处理的硬件任务的指令。

最后，按照时间的单位是时钟，那么如果系统内的时间是离散的，那么系统内的任意时间就可以用自然数来表示。

3、分时EDF算法

EDF的时分概念对应于EDF算法：系统总是调度优先级最高的任务，所以最接近的死任务优先级最高。

定理1将系统中相邻规划点之间的最大距离设定为d。如果硬实时任务类a可以调度，则

证明，下面证明若a不满足1）或2），则至少存在a的一个具体硬实时任务类wr∈w不可调度。

A）设a不满足1），令wr={（T1，0），（T2，0），…（Tn，0）}，取t=p1p2…·Pn，在（0，t）内的CPU需求表示为a（0，t），则 ;若条件1）不满足，则有a（0，t）>t，显然wr不可调度。

B）设a不满足条件1），令wr={（T1，1），（T2，0），…（Tn，1）};在时刻0调度Ti执行，则执行时间为min（d，c）;对于任意L∈（p1，pi），（0，L）内的CPU 需求为a（0，L）= ;若2）不满足，则有a（0，L）>L，L，wr不可调度。

由A），B）指导的结论是因为定理1成立，证毕。

定理2.因为硬实时任务类a满足定理1中的条件1）和2），所以a用分时EDF算法可调度。

证明，首先要用反证法：假设a满足条件1），2），但是，由于特定的硬件实时任务失去了死亡线，如果将任务第一次失去死亡线的时间设定为Ta，则所有任务都可以分为三个类别。

S1：请求的死限为TD的任务。

S2：即使在TD之前生成了请求，如果该死线大于DT的任务，则将这些请求设为B1、bk（k<n）。

S3：以下考虑其他任务（这种任务的第一个请求的时间大于TD）的两种情况：

在td之前，S2的b1，...，bk请求都未执行。设t0为wk在td之前最后一次由空闲进入积累的时刻，则在（t0，td）内wk所需的处理时间为a（t0，td）≤ （当所有任务的请求都在t0发出时等号成立）.因在td处丢失死线，故有td-t0<a（t0-td）≤ a）假设不可持续时，（a）条件不可持续。B） B1号，我不知道，BK使用S2请求在TD之前执行，在TD之前的S2中指定10作为最后执行的任务，如果wk在（10，TD）之间是空的，则在TD之前指定10作为最后一个调度点;如果wk在TD之前是空的，则指定TC（10±0±TD）为wk在TD之前的最后一个累积时间 假设是不可持续的;因此，假定如果TK在TD中失去了死亡线，在（T0，TD）之间没有一周的空闲时间，那么以下几点是真的：

a）TD 10->

（b）除10项外，只有在10项定义所确定的10项内（10项，TD）的期间少于10项任务的请求才予以执行;

（c）除第十项外，在（10、TD）项下提出的任何申请，均不得在第十项产生，否则将不会安排第十项;

（d）在十时，所有期限少于TD的申请均已完成;

（e）由于d±P1±PK±10，因此在（10，TD）之间至少存在一个规划点;

（f）在（10，TD）中执行10次，根据以上各点（d，CI）的最小值，考虑到wk in（10，TD）中的处理器要求（b），只执行任务10，我不知道，目前正在处理10-1，根据c） T1，我不知道，10-1 in（10，TD）的处理器请求是否与I（10+1，TD）相同，因此a（10，TD）≤min（d，ci）+ ;又td处丢失死线，故a（ti，td）>td-ti;令L=td-ti，则 （1）从PI>td Ti可以知道l<p，可以知道PK<TD Ti到l>PK≥P1。因此，方程（1）与条件2相矛盾，因此不能支持情况B）的假设。

a）、b）的定理2证明。

定理1和定理2可以得出以下推论

使用推论1时间共享EDF算法，硬实时任务类别A将充分满足调度可能性的必要条件

1）

2）对于有

推论1中的必要充分条件的计算复杂度很大，不适合用作容许控制条件。因此，简单的计算将充分的条件列举在以下。

使用推论2时间共享EDF算法，调度硬实时任务的充分条件是：

证明方法与定理2类似，略.推论2中的条件又可改写为 时，如果条件1 ）得到满足，则表示只要条件2 ）得到满足，且d足够小，则分时EDF的可调度性测试条件与EDF的可调度性测试条件相同。

通过将时间共享EDF的可调度性测试条件用于系统的可接受控制，可以确保实时任务不会丢失死区。

4、HRFSFQ 层次调度算法

在执行硬实时任务是最大的问题就是不可以保证在执行过程中死机，这也是SFQ算法最致命的缺点。所以我们提出了结合分时EDF和sfq算法的hrfsfq算法，详细的解读如下：

如果把系统CPU规划的时间长度定义为D，那么，相邻两个规划点之间的最大距离就是D;

如果实时任务类有指令，就会分配给CPU，这时分时EDF就会用调度算法来请求执行。这时根据SFQ算法就会将CPU分为软实时任务类和最优干预任务类。

为什么在HRSFQ通过后，EDF的分时调度测试条件与之前的调度算法不一样。这是由于当硬实时任务类指令下达后，其他任务类可能正在执行，这样此指令就不可以立即执行。

定理3在多媒体操作系统中，当hrfsfq作为CPU的分层调度算法时，使用分时EDF算法进行硬实时任务调度的充分条件如下

证明方法与定理2类似，略

定理3给出的调度可能性测试条件和实时任务的负荷的限制（例如总负荷小于 相结合，即作系统中硬实时任务的允许控制条件。

硬fsfo类和硬fsfo类的带宽可以根据硬fsfo类的基本带宽理论进行保证，但硬fsfo类也可以保证实时任务调度。以下是硬fsfo类的基本带宽

定义5 FC服务器（移动受限服务器）参数（c，c））表示在繁忙周期[T1、T2] W （T1、T2）中执行的工作符合以下条件：W （T、T2）c（tt1）-8（c）1

根据FC服务器的功能1，hrfsfq可以保证其他任务类所取得的最大CPU带宽和最小请求延迟。理论4的（c）越小，其他任务类的延迟和带宽越好。如何在优化hrfsfq性能的δ （C）下讨论如何降低

硬实时任务的执行突然发生：如图2（a）所示，如果能够将执行序列转换为图2 （b）、图8 （c）所示的形式，则累积周期和喷发的空周期交替出现。使用两种优化方法，可以实现如图2B所示的执行序列。

1）更改硬实时任务的开始时间以减少运行序列的突然现象。从模拟中可以看出，相同的硬件实时任务类

（c）特定的硬件实时任务类别不同

2）硬盘实时任务可积极释放CPU，缩短CPU持续占用时间。采用以下人道分配策略：将硬实时任务类设置为T-Time累计周期（如果在累积周期中）。在某个时间点内，t +d，之后，放弃CPU。否则，CPU将根据原来的算法来分配这个策略的想法是简单的，但是在实验中，放弃策略表明，放弃策略不会导致硬实时任务的死亡损失。

5、模拟结果

我们可以得出三个总结点：以此来验证分时EDF算法的正确性、验证hrfsfq中硬件实时调度测试条件的正确性、然后作为CPU级计划算法的hrfsfq的可行性。实验环境是由分散实时系统模拟器DRTSS开发的。

5.1分时EDF算法及其可调度性测试条件的正确性

实验方法是选择任意一组硬实时任务，模拟在使用EDF算法时是否会丢失死线，这是十分必要的时间分配和结论1。下面的两个模拟结果与其他结果也是一样的。

1）任务集为{（1.8、1.10）、> 4.11、& 13.40 }，CPU利用率为0.913。从结论1中可以看出，如果任务集是计划的，则需要进行d±6;测试此任务集中的12，000个特定任务集，并且得出的结论是没有

2）任务集为{ 1.8 >，（1.10）、（2.11）、（940）} CPU利用率为0.632，方法与1相同。理论d值为d ≤ 8。实测结果表明，当D 28和4800实际执行任务的时候，所以并没有丢失死线。

从以上结果可以看出，时间共享EDF算法的调度测试条件可以准确地保证硬实时任务不丢失盲区。

5.2HRFSFO 中硬实时任务类可调度的充分条件

实施方法与第5.1节相同。以下是一组模拟结果，其他结果相同：

任务集为（<;1.8）、（1.10）、（2.11）、（9.40）} CPU利用率为0.632，D6取自定理3;对上述12，000个特定任务集进行了测试，得出了D ≤ 8时没有丢失的结论;

从以上结果可以看出，由于给定的预定测试条件仅为充分条件，因此允许的控制相对严格，但可以保证通过测试的硬实时任务不会丢失死线。

5.3HRFSFQ 用作CPU层次调度

将hrfsfq作为CPU层级调度算法使用的关键是在任务类之间按规定比例分配CPU带宽。FC参数（c）越小越好。实验的这个部分主要说明影响FC参数和效果的因素。

1） D对FC参数的影响

在仿真中，将选择多个任务组来测试时间点d对（c）的影响。一组作业为{（1.18）} 7.26 ";，5.38±7.40 }。仿真结果如图3所示，其他结果类似。仿真中发现的实际问题δ （C）值远远小于理论值，d的变化很小

产生上述结果的主要原因是，我们反复放宽了建立不平等的条件，使所给出的结果过于悲观，从而为分析提供了方便的正式结果。

2）优化策略对FC参数的影响

我们将在“多组任务模拟”的第4部分中选择优化策略和CPU占用率对硬实时任务（c）的影响。分组工作周期分别为（8 . 10 . 11 . 40）和d = 4。仿真结果如图4所示。其他结果类似于图4。「最佳化1」代表已修改工作的发布时间;「最佳化2」代表CPU的主动释放，而「最佳化3」则代表前两个工作的组合。实际结果显示在实验结果中。δ （C）该值根据硬件实时任务的CPU占有率而略有变化，远小于前一节的实验相同的理论值。优化2的结果优于优化1的结果。但在实验中发现，由于硬实时任务类可能在分配模式到达累积期之前进入空状态，因此优化2可能对某些任务组不起作用;两种优化方法的结合可获得满意的结果。

3）HRFSFQ 对其它任务类的带宽保证

在实验中，采用hrfsfq作为类间调度算法，分别采用sfq和多级反馈优先级方法进行软实时任务类和最佳efft任务类选择大量的循环计算任务来测试CPU带宽标准是单位时间内完成的周期数在不同的硬实时任务负载下测试另外两个任务类的带宽保证，将每个硬实时任务的CPU占用率保持在10%，实验结果如图5所示。当另个任务可以使用带宽的时候，说明硬实时任务载荷小;随着硬实时任务数上升到4时，硬实时任务由于权限控制的作用而不能再进入系统。到目前为止，CPU软实时任务和最佳干预任务的比例整体趋于35%和15%左右。其中一小部分的带宽是被系统开销和硬实时任务类的差异占用了，这和预期的结果相同。

从以上仿真结果可以看出，hrfsfq作为CPU的分层调度算法，不仅可以保证硬实时任务不丢失盲区，从而为了实现不同任务执行的CPU资源共享，是需要确保软实时任务和最佳干预任务的CPU带宽的。

6结束语

本文通过分析分时EDF算法和hrfsfq算法中实际价值最大的地方是此算法可以在多媒体操作系统的内核当中实现。从本文中可以得出，在hrfsfq算法中，如果要减轻硬实时任务对其他任务产生的影响，有两种解决办法，解决办法如下：这两种方案都可以在一定程度下提升hrfsfq的效率。从相对应的实验当中，也可以得出硬实时任务采用的放弃策略会有很大的实用性，可以让不同类型 的任务安全分离;而另一种就是实施非常简单。因为当放弃策略在执行的时候，硬实时任务如果违反了其（C、P）参数时，就会发送更多的指令。这样的丢弃策略指令是不会影响到其他类型执行的任务。

参考文献：

[1] 张怡， 张拥军， 彭宇行， & 陈福接. （2001）. 分时edf算法及其在多媒体操作系统中的应用. 计算机学报， 24（3）， 6.

[2] 马柳. （2016）. 离线下载系统任务调度算法的研究. （Doctoral dissertation， 北京交通大学）.

[3] 周耀义. （1996）. 多媒体技术及其在电力系统中的应用（一）. 江苏电机工程（1）， 60-62.

[4] 阮俊波， 李红兵， 金惠华. 实时连续多媒体任务模型及调度算法[J]. 北京航空航天大学学报， 2005， 31（8）：863-868.

[5] 薛红伟， 孙建辉， 王传峰， 张敏杰， 樊天旭， & 李寒涛等. （2013）. 一种基于CAN总线技术的采煤机位置检测方法.  CN102914304A.

[6] 李凡， 陈琦， & 朱光喜. （2002）. 屏幕共享技术及其在多媒体技术中的应用. 电视技术.