论文部分内容阅读
实时动态调度是一个实用而有趣的课题。例如,在飞行控制系统中,测高任务的运行周期可以是动态的,飞行高度越低采样率越高。类似地,在机器人目标逼近测量场合,机器人越接近目标,测量周期一般也应该缩短。EDF(Earliest Deadline First)是实时系统中的一个经典调度算法。基于该算法,国际著名学者Buttazzo近年提出了一种弹性调度模型,以应对上述实时动态调度场合。Qian改进了这种模型,特别是在计算模型中的一个重要指标“新任务插入时间”时,给出了一个更合理而快捷的公式。一般来说,这一时间越快越好。但是,关于最早插入时间的计算仍然是一个开问题。本文并非去探讨最早插入时间的计算,而是研究在现有成果的基础上,如何才能实现实时新任务运行时的尽早插入。为此,提出了选择性压缩思想,引入了剩余带宽的概念,并将原有模型进行了适当扩展,使之更接近于实际应用场合。如果系统已是满负荷运行,为了任务加速或插入新任务,必须对原有单个或多个任务进行压缩。选择不同的受压任务,往往具有不同的效果。我们提出:选择让新任务等待时间最短的现行任务进行压缩。这是选择性压缩的基本思想。文中对此进行了深入研究和分析。对于受压任务,其本作业周期的剩余执行量是一个重要指标。我们发现:真正重要的应该是这一剩余执行量与剩余时间之比。我们将这一比值定义为剩余带宽,并将剩余带宽与选择性压缩思想相结合,提出了基于剩余带宽的选择性压缩算法,并给出和证明了相关定理。为了先简化问题的研究,Buttazzo和Qian的原有模型都作了一些假定。本文则适当进行了模型扩展。考虑到并非所有场合都要求尽快插入和/或加速,有时只要在某一截止期之前完成就可以了。为此我们引入了任务插入截止期,与选择性压缩思想相结合后,新任务插入又有了新的内涵。为了演示算法和思想的有效性,我们采用了一个交换网仿真工具Switchsim。文中详细描述了算法在仿真工具中的实现。仿真结果表明:上述思想和算法能够较好地完成新任务插入。