Explicit Preemption Placement for Real-Time Conditional Code Via Graph Grammars and Dynamic Programming
Traditional Worst-Case Execution Time (WCET) analysis must make very pessimistic assumptions regarding the cost of preemptions for a real-time job. For every potential preemption point, the analysis must add to the WCET of a job the Cache-Related Preemption Delay (CRPD) incurred due to the contention for memory resources with other jobs in the system. However, recent paper has shown that CRPD can vary at each preemption point (due to the cache lines that must be reloaded for subsequent code after the preemption). Using this observation and information obtained from schedulability analysis on the maximum length of the non-preemptive region of a job, the authors seek to find the optimal set of Explicit Preemption-Points (EPPs) that minimize the WCET and ensure system schedulability.