考虑缓存替换影响的最坏响应时间分析研究

发布时间：2018-05-11 23:13

本文选题：抢占代价 + 有用缓存块　；参考：《湖南大学》2013年硕士论文

【摘要】：实时系统应能够在限定的响应时间内提供所需水平的服务。在航空航天、工业控制、军事、汽车电子等具有严格时间约束的硬实时系统开发过程中，，必须进行最坏执行时间分析和可调度性分析，验证系统能够满足限定的时间约束。随着集成电路工艺和计算机技术的快速发展，处理器的核心时钟频率越来越快，然而主存存取速度始终跟不上处理器频率的步伐，致使主存和处理器之间速度差异越来越大。缓存在平衡处理器和主存之间的速度差异方面起着重要的作用。在抢占式实时系统中，当抢占发生时，抢占任务和被抢占任务之间的缓存冲突将会使得被抢占任务的缓存块被驱逐出缓存。当被抢占任务重新开始执行时由于缓存失效不得不花费时间来加载这些块，所花费的时间被称为与缓存有关的抢占代价。这必然对实时系统最坏执行时间分析和可调度性分析产生消极的影响。在本文中，我们对实时系统任务进行了建模，并提出了一个有效判定直接抢占点和间接抢占点的算法。这个算法利用任务的最坏执行时间和最好执行时间，判定一个超周期内所有任务的每个作业的直接抢占点和间接抢占点。基于有用缓存块和驱逐缓存块的概念还提出了计算与缓存有关抢占代价的UCB-ECB方法。然后，利用UCB-ECB方法计算各个作业在抢占点处的与缓存有关抢占代价，并将计算出来的抢占代价与该作业的最坏执行时间相加，结果就是该作业最坏执行时间的估算值。一个任务最坏执行时间的估算值就是超周期内该任务各个作业最坏执行时间估算值的最大值。最后利用估算的最坏执行时间和与缓存有关抢占代价通过线性规划方法计算出各个任务的最坏响应时间，进行响应时间可调度性分析，判断任务集是否可调度。为了验证算法的有效性和UCB-ECB方法的优越性，本文采用随机生成实时任务集，与其他计算抢占代价的方法进行抢占代价的对比实验，同时与前人的研究进行最坏执行时间的对比实验。实验数据表明与其他计算抢占代价方法相比UCB-ECB方法可以得到更严格的抢占代价。可调度性分析表明我们得到了一个更安全的最坏执行时间，并且在缓存的影响下任务集是可调度的。
[Abstract]:Real-time systems should be able to provide the required level of service within a limited response time. In the development of hard real-time systems with strict time constraints, such as aerospace, industrial control, military and automotive electronics, the worst-case execution time analysis and schedulability analysis must be carried out to verify that the system can meet the limited time constraints. With the rapid development of integrated circuit technology and computer technology, the core clock frequency of the processor becomes faster and faster. However, the access speed of the main memory can not keep up with the speed of the processor, which makes the speed difference between the main memory and the processor more and more big. Caching plays an important role in balancing the speed difference between processor and main memory. In preemptive real-time systems, when preemption occurs, the cache conflict between preemptive task and preemptive task will result in the cache block of preemptive task being expelled from cache. When the preemptive task starts again, it takes time to load these blocks due to cache invalidation, which is called the cost of preemption related to cache. This will inevitably have a negative impact on the worst execution time analysis and schedulability analysis of real-time systems. In this paper, we model the task of real-time system, and propose an effective algorithm to determine the direct preemption point and indirect preemptive point. The algorithm uses the worst execution time and the best execution time to determine the direct preemption point and the indirect preemption point for every job in a super period. Based on the concepts of useful cache block and expelling cache block, a UCB-ECB method to calculate the preemptive cost related to cache is also proposed. Then, the cache related preemption cost of each job at preemption point is calculated by UCB-ECB method, and the calculated preemption cost is added to the worst execution time of the job. The result is the estimated worst execution time of the job. The estimation of the worst execution time of a task is the maximum value of the worst execution time estimate for each job in the super-cycle. Finally, the worst-case response time of each task is calculated by linear programming method using the estimated worst-case execution time and cache related preemption cost, and the schedulability of response time is analyzed to determine whether the task set is schedulable or not. In order to verify the validity of the algorithm and the superiority of the UCB-ECB method, this paper uses random generation of real-time task sets, and compares the preemptive cost with other methods. At the same time, the worst execution time was compared with previous studies. Experimental data show that the UCB-ECB method can obtain more strict preemptive cost than other computational preemptive cost methods. Schedulability analysis shows that we get a more secure worst-case execution time and the task set is schedulable under the influence of cache.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP333

【参考文献】