6 Search Results for "Davis, Robert I."


Document
Schedulability Analysis for Multi-Core Systems Accounting for Resource Stress and Sensitivity

Authors: Robert I. Davis, David Griffin, and Iain Bate

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)


Abstract
Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, and proofs of optimal priority assignment provided. The MRSS task model is underpinned by a proof-of-concept industrial case study.

Cite as

Robert I. Davis, David Griffin, and Iain Bate. Schedulability Analysis for Multi-Core Systems Accounting for Resource Stress and Sensitivity. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 7:1-7:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{davis_et_al:LIPIcs.ECRTS.2021.7,
  author =	{Davis, Robert I. and Griffin, David and Bate, Iain},
  title =	{{Schedulability Analysis for Multi-Core Systems Accounting for Resource Stress and Sensitivity}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{7:1--7:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.7},
  URN =		{urn:nbn:de:0030-drops-139388},
  doi =		{10.4230/LIPIcs.ECRTS.2021.7},
  annote =	{Keywords: real-time, multi-core, scheduling, schedulability analysis, cross-core contention, resource stress, resource sensitivity}
}
Document
A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems

Authors: Robert I. Davis and Liliana Cucu-Grosjean

Published in: LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1


Abstract
This survey covers probabilistic timing analysis techniques for real-time systems. It reviews and critiques the key results in the field from its origins in 2000 to the latest research published up to the end of August 2018. The survey provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas: static probabilistic timing analysis, measurement-based probabilistic timing analysis, and hybrid methods. In addition, research on supporting mechanisms and techniques, case studies, and evaluations is also reviewed. The survey concludes by identifying open issues, key challenges and possible directions for future research.

Cite as

Robert I. Davis and Liliana Cucu-Grosjean. A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 03:1-03:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{davis_et_al:LITES-v006-i001-a003,
  author =	{Davis, Robert I. and Cucu-Grosjean, Liliana},
  title =	{{A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:60},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a003},
  doi =		{10.4230/LITES-v006-i001-a003},
  annote =	{Keywords: Probabilistic, real-time, timing analysis}
}
Document
A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems

Authors: Robert I. Davis and Liliana Cucu-Grosjean

Published in: LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1


Abstract
This survey covers schedulability analysis techniques for probabilistic real-time systems. It reviews the key results in the field from its origins in the late 1980s to the latest research published up to the end of August 2018. The survey outlinesfundamental concepts and highlights key issues. It provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas as well as research on supporting techniques. The survey concludes by identifying open issues, key challenges and possible directions for future research.

Cite as

Robert I. Davis and Liliana Cucu-Grosjean. A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 04:1-04:53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{davis_et_al:LITES-v006-i001-a004,
  author =	{Davis, Robert I. and Cucu-Grosjean, Liliana},
  title =	{{A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{04:1--04:53},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a004},
  doi =		{10.4230/LITES-v006-i001-a004},
  annote =	{Keywords: Probabilistic, real-time, schedulability analysis, scheduling, }
}
Document
Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies

Authors: Robert I. Davis, Iain Bate, Guillem Bernat, Ian Broster, Alan Burns, Antoine Colin, Stuart Hutchesson, and Nigel Tracey

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)


Abstract
This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.

Cite as

Robert I. Davis, Iain Bate, Guillem Bernat, Ian Broster, Alan Burns, Antoine Colin, Stuart Hutchesson, and Nigel Tracey. Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{davis_et_al:LIPIcs.ECRTS.2018.7,
  author =	{Davis, Robert I. and Bate, Iain and Bernat, Guillem and Broster, Ian and Burns, Alan and Colin, Antoine and Hutchesson, Stuart and Tracey, Nigel},
  title =	{{Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.7},
  URN =		{urn:nbn:de:0030-drops-89955},
  doi =		{10.4230/LIPIcs.ECRTS.2018.7},
  annote =	{Keywords: real-time systems, industrial impact, automotive, avionics}
}
Document
On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling

Authors: Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)


Abstract
In this paper, we take a careful look at speedup factors, utilization bounds, and capacity augmentation bounds. These three metrics have been widely adopted in real-time scheduling research as the de facto standard theoretical tools for assessing scheduling algorithms and schedulability tests. Despite that, it is not always clear how researchers and designers should interpret or use these metrics. In studying this area, we found a number of surprising results, and related to them, ways in which the metrics may be misinterpreted or misunderstood. In this paper, we provide a perspective on the use of these metrics, guiding researchers on their meaning and interpretation, and helping to avoid pitfalls in their use. Finally, we propose and demonstrate the use of parametric augmentation functions as a means of providing nuanced information that may be more relevant in practical settings.

Cite as

Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis. On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2017.9,
  author =	{Chen, Jian-Jia and von der Br\"{u}ggen, Georg and Huang, Wen-Hung and Davis, Robert I.},
  title =	{{On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{9:1--9:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.9},
  URN =		{urn:nbn:de:0030-drops-71619},
  doi =		{10.4230/LIPIcs.ECRTS.2017.9},
  annote =	{Keywords: Real-time systems, speedup factors, utilization bounds, capacity augmentation bounds}
}
Document
A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays

Authors: Will Lunniss, Sebastian Altmeyer, and Robert I. Davis

Published in: LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1


Abstract
In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm.

Cite as

Will Lunniss, Sebastian Altmeyer, and Robert I. Davis. A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays. In LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1, pp. 01:1-01:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Article{lunniss_et_al:LITES-v001-i001-a001,
  author =	{Lunniss, Will and Altmeyer, Sebastian and Davis, Robert I.},
  title =	{{A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:24},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v001-i001-a001},
  doi =		{10.4230/LITES-v001-i001-a001},
  annote =	{Keywords: Real-time systems, Fixed priority, EDF, Pre-emptive scheduling, Cache related pre-emption delays}
}
  • Refine by Author
  • 6 Davis, Robert I.
  • 2 Bate, Iain
  • 2 Cucu-Grosjean, Liliana
  • 1 Altmeyer, Sebastian
  • 1 Bernat, Guillem
  • Show More...

  • Refine by Classification
  • 4 Computer systems organization → Real-time systems
  • 2 Software and its engineering → Real-time schedulability
  • 1 Computer systems organization
  • 1 Software and its engineering
  • 1 Software and its engineering → Correctness
  • Show More...

  • Refine by Keyword
  • 3 real-time
  • 2 Probabilistic
  • 2 Real-time systems
  • 2 schedulability analysis
  • 2 scheduling
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2019
  • 1 2014
  • 1 2017
  • 1 2018
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail