论文部分内容阅读
在一个单处理器的实时调度系统中,任务加速或者新任务插入所导致的超负荷可以通过任务压缩来应对,这就是弹性调度中的带宽转让。但是为了避免实际的新任务插入过程中可能会发生的截止期丢失,就有必要采用平滑插入方法,而平滑插入问题的关键就是最早平滑时刻的求取。现有一个初步的最早平滑时刻求取方法——Simple way,该方法的核心就是在逐步延迟的释放过程当中试探新任务的平滑插入点,本文以文献研究和仿真实验等方法对该问题做了进一步的考察,获得了比该方法更先进的研究结果。基于EDF(Earliest Deadline First)算法,本文首先在多任务的带宽转让情形下将实时周期任务的模型简化为一个由执行时间,初始周期和受压后周期所组成的三元组,并且以此为基础重新描述了弹性调度中的实时多任务带宽转让过程和过渡过程。然后对现行任务的压缩过程做了细致的分析,分析了该过程中的处理器需求计算方法,接着提出了一个准则——延迟判断准则,在该准则的证明过程中,本文指出新任务的插入所导致的截止期丢失只有两种情况,第一种是现行任务的截止期丢失,第二种是新任务的截止期丢失,并且最终证明了该准则在这两种情形下都成立。延迟判断准则的正确性意味着如果在当前时刻释放新任务导致了某个截止期d_x丢失,那么在下一轮的尝试时应当至少延迟?个单位才能保证d_x满足,其中?就是上一轮尝试中所产生的检查值。在最后一部分,本文以延迟判断准则为基础构造了一个新的求取方法——Smart way,该算法可以有效地提升最早平滑时刻的求取速度。文中还证明了Smart way算法具有一个良好的性质,该性质有助于进一步减少延迟过程当中的检查轮数。而后通过实时调度平台的仿真示例来对Smart way进行了验证和说明,并且将其和Simple way进行了效率比较,发现在平滑点越远的时候,Smart way的效率优势就越明显。延迟判断准则和Smart way算法的提出是弹性调度研究领域的新成果,其不仅有望为对带宽转让等问题感兴趣的学者们提供一定的启发和思考,也有助于为有相应需求的实时应用实践提供可借鉴的理论框架。