White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Cache Related Pre-emption Delays in Embedded Real-Time Systems

Lunniss, William Richard Elgon (2014) Cache Related Pre-emption Delays in Embedded Real-Time Systems. EngD thesis, University of York.

[img]
Preview
Text (PDF)
Thesis - Final.pdf
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (4Mb) | Preview

Abstract

Real-time systems are subject to stringent deadlines which make their temporal behaviour just as important as their functional behaviour. In multi-tasking real-time systems, the execution time of each task must be determined, and then combined together with information about the scheduling policy to ensure that there are enough resources to schedule all of the tasks. This is usually achieved by performing timing analysis on the individual tasks, and then schedulability analysis on the system as a whole. In systems with cache, multiple tasks can share this common resource which can lead to cache-related pre-emption delays (CRPD) being introduced. CRPD is the additional cost incurred from resuming a pre-empted task that no longer has the instructions or data it was using in cache, because the pre-empting task(s) evicted them from cache. It is therefore important to be able to account for CRPD when performing schedulability analysis. This thesis focuses on the effects of CRPD on a single processor system, further expanding our understanding of CRPD and ability to analyse and optimise for it. We present new CRPD analysis for Earliest Deadline First (EDF) scheduling that significantly outperforms existing analysis, and then perform the first comparison between Fixed Priority (FP) and EDF accounting for CRPD. In this comparison, we explore the effects of CRPD across a wide range of system and taskset parameters. We introduce a new task layout optimisation technique that maximises system schedulability via reduced CRPD. Finally, we extend CRPD analysis to hierarchical systems, allowing the effects of cache when scheduling multiple independent applications on a single processor to be analysed.

Item Type: Thesis (EngD)
Keywords: cache related pre-emption delay, real-time systems, schedulability analysis, fixed priority scheduling, earliest deadline first scheduling
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.639003
Depositing User: MR William Richard Elgon Lunniss
Date Deposited: 03 Mar 2015 11:16
Last Modified: 08 Sep 2016 13:32
URI: http://etheses.whiterose.ac.uk/id/eprint/8162

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)