Considering The Cache Replacement The Worst-case Response Time Analysis Research

Real-time system should be able to provide the required level of service in thelimited response time. During the development process of hard real-time systems withstrict time constraints, like the aerospace, industrial control, military, automotiveelectronics, the worst-case execution time analysis and schedulability analysis mustbe made to verify that the system can meet the limited time constraints.With the rapid development of integrated circuit technology and computertechnology, the clock frequency of the processor becomes faster and faster. However,the main memory access speed always cannot keep up with the pace of processorfrequency, resulting in the greater speed gap between the main memory and theprocessor. Cache plays an important role in balancing speed gap between theprocessor and the main memory. In preemptive real-time systems, when preemptionoccuring, the cache conflict between the preempting and preempted tasks leads to thecache misses of the preempted one. When resuming its execution, the preempted taskneeds to take some time to reload the evicted blocks. The delay caused by the cachemisses is referred to as the cache-related preemption delay, which contributes the partof the worst-case execution time and has negative effect on the worst-case executiontime analysis and schedulability analysis.In this paper, we establish a real-time task model and propose a new algorithm.The algorithm can identify the direct and the indirect preemption points of every jobof all tasks within a hyper-period by the worst-case execution time and the best-caseexecution time. Based on the useful cache blocks and the evicting cache blocks, theUCB-ECB approach to calculating the cache-related preemption delay is proposed.The cache-related preemption delay of every job at every preemption points can becalculated by the UCB-ECB approach and is added to the worst-case execution timeof the corresponding job. The estimated WCET of a task is the maximum value of theworst-case execution times of all its jobs. At last, the worst-case execution time andthe preemption delay are used to compute the worst-case response time by the linearprogramming approach and make schedulability analysis, namely in order to verifywhether the task-set is schedulable.In order to estimate the effectiveness of our algorithm and the superiority of theUCB-ECB approach, our paper conducts the comparison experiments of the preemption delay between the UCB-ECB approach and other approaches tocalculating the preemption delay, and the comparison experiments of the worst-caseexecution time between our algorithm and the previous algorithm, by randomlygenerating real-time task-sets. The results of our experiments show that the UCB-ECBapproach can get the tighter preemption delay compared with other approaches. Theschedulability analysis shows a safer bound on the worst-case execution time thanprevious algorithm, moreover, the task-set is schedulable.