Accounting for cache-related preemption delay in dynamic priority schedulability analysis

Abstract

Recently there has been considerable interest in incorporating timing effects of microarchitectural features of processors (e.g. caches and pipelines) into the schedulability analysis of tasks running on them. Following this line of work, in this paper we show how to account for the effects of cache-related preemption delay (CRPD) in the standard schedulability tests for dynamic priority schedulers like EDF. Even if the memory space of tasks is disjoint, their memory blocks usually map into a shared cache. As a result, task preemption may introduce additional cache misses which are encountered when the preempted task resumes execution; the delay due to these additional misses is called CRPD. Previous work on accounting for CRPD was restricted to only static priority schedulers and periodic task models. Our work extends these results to dynamic priority schedulers and more general task models (e.g. sporadic, generalized multiframe and recurring real-time). We show that our schedulability tests are useful through extensive experiments using synthetic task sets, as well as through a detailed case study. © 2007 EDAA.