New response time bounds for fixed priority multiprocessor scheduling

Nan Guan, Martin Stigge, Wang Yi, Ge Yu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

107 Citations (Scopus)

Abstract

Recently, there have been several promising techniques developed for schedulability analysis and response time analysis for multiprocessor systems based on over-approximation. This paper contains two contributions. First, to improve the analysis precision, we apply Baruah's window analysis framework [6] to response time analysis for sporadic tasks on multiprocessor systems where the deadlines of tasks are within their periods. The crucial observation is that for global fixed priority scheduling, a response time bound of each task can be efficiently estimated by fixed-point computation without enumerating all the busy window sizes as in [6] for schedulability analysis. The technique is proven to dominate theoretically state-of-the-art techniques for response time analysis for multiprocessor systems. Our experiments also show that the technique results in significant performance improvement compared with several existing techniques for multiprocessor schedulability analysis. As the second main contribution of this paper, we extend the proposed technique to task systems with arbitrary deadlines, allowing tasks to have deadlines beyond the end of their periods. This is a non-trivial extension even for single-processor systems. To our best knowledge, this is the first work of response time analysis for multiprocessor systems in this setting, which involves sophisticated techniques for the characterization and computation of response time bounds.
Original languageEnglish
Title of host publicationProceedings - Real-Time Systems Symposium, RTSS 2009
Pages387-397
Number of pages11
DOIs
Publication statusPublished - 1 Dec 2009
Externally publishedYes
EventReal-Time Systems Symposium, RTSS 2009 - Washington, D.C., United States
Duration: 1 Dec 20094 Dec 2009

Conference

ConferenceReal-Time Systems Symposium, RTSS 2009
CountryUnited States
CityWashington, D.C.
Period1/12/094/12/09

Keywords

  • Fixed priority scheduling
  • Multiprocessor
  • Real-time scheduling
  • Response time analysis

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this