论文部分内容阅读
实时系统应能够在限定的响应时间内提供所需水平的服务。在航空航天、工业控制、军事、汽车电子等具有严格时间约束的硬实时系统开发过程中,必须进行最坏执行时间分析和可调度性分析,验证系统能够满足限定的时间约束。随着集成电路工艺和计算机技术的快速发展,处理器的核心时钟频率越来越快,然而主存存取速度始终跟不上处理器频率的步伐,致使主存和处理器之间速度差异越来越大。缓存在平衡处理器和主存之间的速度差异方面起着重要的作用。在抢占式实时系统中,当抢占发生时,抢占任务和被抢占任务之间的缓存冲突将会使得被抢占任务的缓存块被驱逐出缓存。当被抢占任务重新开始执行时由于缓存失效不得不花费时间来加载这些块,所花费的时间被称为与缓存有关的抢占代价。这必然对实时系统最坏执行时间分析和可调度性分析产生消极的影响。在本文中,我们对实时系统任务进行了建模,并提出了一个有效判定直接抢占点和间接抢占点的算法。这个算法利用任务的最坏执行时间和最好执行时间,判定一个超周期内所有任务的每个作业的直接抢占点和间接抢占点。基于有用缓存块和驱逐缓存块的概念还提出了计算与缓存有关抢占代价的UCB-ECB方法。然后,利用UCB-ECB方法计算各个作业在抢占点处的与缓存有关抢占代价,并将计算出来的抢占代价与该作业的最坏执行时间相加,结果就是该作业最坏执行时间的估算值。一个任务最坏执行时间的估算值就是超周期内该任务各个作业最坏执行时间估算值的最大值。最后利用估算的最坏执行时间和与缓存有关抢占代价通过线性规划方法计算出各个任务的最坏响应时间,进行响应时间可调度性分析,判断任务集是否可调度。为了验证算法的有效性和UCB-ECB方法的优越性,本文采用随机生成实时任务集,与其他计算抢占代价的方法进行抢占代价的对比实验,同时与前人的研究进行最坏执行时间的对比实验。实验数据表明与其他计算抢占代价方法相比UCB-ECB方法可以得到更严格的抢占代价。可调度性分析表明我们得到了一个更安全的最坏执行时间,并且在缓存的影响下任务集是可调度的。