层次调度 篇1
关键词：层次调度,EDF,DBS
1 引言
实时调度是实时系统研究中的一个关键问题。自从20世纪70年代中期以来，实时调度算法几乎是呈指数增长[1]。实时调度算法的好坏，直接影响到系统的吞吐量、系统的响应时间，甚至是任务能否得以成功调度。对实时调度算法的研究，是实时领域的一个重要的研究课题[2]。随着实时系统应用范围的不断扩大，实时应用变得日趋复杂，任务量和数据量的增加以及计算复杂度的加大，调度算法会向面向分布、动态、弱实时、混合调度以及实时多处理机系统调度的方向发展。这就提出了实时系统中混合任务集的层次调度方案。
本文描述一个周期性、偶发性(释放时间是随机的，但是强时限的)和非周期性任务(释放时间是随机的，是弱时限或没有时限)混合调度的层次调度方案，它能够为在单处理器上执行的各个应用提供定时隔离。每个应用包含任意数目和类型的任务。通过这样的设计，此方案允许不同的应用使用不同的调度算法。因此，每个应用可以用最适合的方式调度。
2 层次调度方案的设计思想
根据层次调度方案，每类应用都由一个服务器执行。底层为调度层，上层为调度策略分配层。在调度层，处于较低级的调度程序被称为系统调度器。系统调度器维护EDF和DBS(dynamic bandwidth server，动态带宽服务器)调度服务器，并基于EDF算法调度所有就绪服务器。在较高级别，每个服务器的调度程序调度由服务器执行的应用程序中的就绪作业。其调度结构图如图1所示。
2.1 测试与筛选器
测试与筛选器主要负责任务集的读取和分析，并决定使用的调度策略。其主要功能：
1)负责原始任务集的读取和分析。根据任务的类型区分是周期性任务、偶发性任务，还是非周期性任务，并设置相应的参数;通过调度筛选器来选择合适的调度器。例如周期性任务选择EDF调度服务器，非周期性任务选择DBS调度服务器，偶发性任务则选择接受测试，通过测试的插入EDF维护的周期性队列，否则拒绝。
2)对周期性任务进行可调度性测试。
3)对偶发性任务进行接受测试。所采取的算法是每释放一个偶发作业，调度程序便对其进行一个接受测试。若根据现有的调度算法，在其时限之前如果有足够的时间能够完成该偶发作业，并且不会导致其它作业错过时限，调度程序就接受并调度该作业，否则拒绝。调度程序在拒绝了释放后无法及时调度的偶发作业之后，会给应用系统足够的时间采取必要的恢复行动。已接受的偶发作业与周期作业一起，基于EDF算法进行调度。
2.2 EDF调度服务器
EDF调度服务器主要负责周期性任务和偶发性任务的调度。
对于EDF调度服务器，本文采用三元组Sh=
1)在有任务加入队列或是任务完成退出队列时，根据在EDF算法中，任务调度优先级的定义：pr=di(t)-t(pr为优先级，di(t)为任务第i个作业的时限，t为当前时刻)动态更新任务的优先级并对队列重新排序。
2)带宽计算：根据公式(1)估算周期性任务和偶发性任务所需要的带宽U。并把它传给系统调度器。
2.3 DBS调度服务器
DBS调度服务器主要负责非周期性任务的调度。
对于DBS调度服务器，本文采用三元组Ss=
DBS的消耗和补充规则如下：
消耗规则(Consumption Rule)：
服务器只有在它执行时才消耗其预算，其执行预算按照每单位时间一个的速率消耗。
补充规则(Replenishment Rule)：
R1初始状态，Es=0，并且Ds=0。
R2当一个执行时间为e的非周期性作业在时刻t到达一个空的非周期性作业队列时，令d等于max(Ds,t)+Es/Us,并且Es=e。
R3当服务器完成了当前的非周期性作业时，就把这个作业从它的队列中删除。
1)如果服务器有储备，就把服务器的时限设置为Ds+Es/Us,并且Es=e。
2)如果服务器空闲，则不做任何操作。
2.4 系统调度器
系统调度器的主要任务是维护EDF和DBS调度服务器，并基于EDF算法调度所有就绪服务器。其主要功能如下：
1)维护EDF和DBS调度服务器。根据EDF调度服务器传过来的带宽U，把U调整为Uh(U≤Uh≤1)，(为了避免了过度频繁的带宽调整，根据U的波动情况，估算一个合理的区间。仅当U的变化超过该区间时，才调整它的带宽Uh[3])。然后把Uh利用公式：Uh+Us+U0=1(假设其它消耗占用的CPU带宽为一个固定值U0，由于EDF和DBS调度服务器共享一个CPU，如果令CPU的运行带宽为1，那么有：Uh+Us+U0=1)，计算时刻t时，DBS调度服务器所占用CPU的带宽Us，并把Us传给DBS调度服务器，同时把Uh传给EDF调度服务器。
2)根据需要对服务器预算进行补充。因为EDF调度服务器不存在没有预算的情况，Eh可设为无穷大[3]。对于DBS调度服务器，是根据Us，按照DBS算法进行预算补充。
3)EDF和DBS调度服务器通过各自的算法得到各自的时限，系统调度器就会依据它们的时限，采用EDF算法对它们进行调度，时限短的服务器将被优先执行。
4)EDF调度服务器为主调度服务器，可以根据需要，无条件占用CPU带宽。当EDF调度服务器需要带宽时，系统调度器根据相应的调整策略将DBS调度服务器所占用CPU带宽的部分或全部转让给EDF调度服务器。
3 小结
1)通过把调度过程分为两个阶段，将调度器的筛选和具体的调度分开来，使多种调度策略都得到支持，相对于只对单种调度策略提供支持的方案，拓展了系统的可使用范围。
2)混合任务的层次调度方案就是利用测试与筛选器来为预定义的任务集按合理的方式分配调度策略，再利用任务调度器来调度就绪队列中的任务分配处理机使之执行。
参考文献
[1]Krishna C M,Kang G S.实时系统[M].戴海琼,译.北京:清华大学出版社,2004.
[2]王娟,吴秀文,张钟澍.实时操作系统集成调度的两级方案设计[J].成都信息工程学院学报,2007,22(1):36-40.