mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Synchronization Protocols for a Compositional Real-Time Scheduling Framework
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0002-1687-930X
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we propose techniques to simplify the integration of subsystems while minimizing the overall amount of CPU resources needed to guarantee the schedulability of real-time tasks. In addition, we provide solutions to the problem of allowing for the use of logical resources requiring mutual exclusion.

The contribution of the thesis is presented in three parts. In the first part, we propose a synchronization protocol, called SIRAP, to facilitate sharing of logical resources in a hierarchical scheduling framework. In addition, we extend an existing synchronization protocol, called HSRP, such that each subsystem can be developed independently. The performance of the proposed protocols is evaluated by extensive simulations. In the second part, we present an efficient schedulability analysis that exploits the lower scheduling overhead introduced by each of the proposed protocols. Finally, in the third part, we propose new methods and algorithms that find the optimal system parameters (e.g., optimal resource ceiling), that minimize the amount of CPU resources required to ensure schedulability, when using the proposed synchronization protocols in a hierarchical scheduling framework.

The motivation of this work comes from an emerging industrial trend in embedded software systems development to integrate multiple applications (subsystems) on a small number of processors. The purpose of this integration is to reduce the hardware related costs as well as the communication complexity between processors. In this setting a large number of industrial applications face the problem of preserving their real-time properties after their integration onto a single processor. In addition, temporal isolation between the applications during runtime may be required to prevent failure propagation between different applications.

Specifically, we propose a hierarchical scheduling framework that allows for a simplified integration of subsystems. The framework preserves the essential temporal characteristics of the subsystems, both when running in isolation as well as when they are integrated with other subsystems. In this thesis, we assume a model where a system consists of a number of subsystems. The subsystems can interact with each other using shared logical resources. The framework ensures that the individual subsystem respects its allocated share of the processor. The difficulty lies in allowing two or more subsystems to share logical resources, which introduces an additional complexity in the schedulability analysis and also increases the system load.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2010.
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 91
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-10447ISBN: 978-91-86135-95-9 (print)OAI: oai:DiVA.org:mdh-10447DiVA: diva2:357530
Public defence
2010-11-22, Delta, Mälardalens högskola, Västerås, 10:00 (English)
Opponent
Supervisors
Available from: 2010-10-29 Created: 2010-10-18 Last updated: 2014-05-26Bibliographically approved
List of papers
1. SIRAP: A Synchronization Protocol for Hierarchical Resource Sharing in Real-Time Open Systems
Open this publication in new window or tab >>SIRAP: A Synchronization Protocol for Hierarchical Resource Sharing in Real-Time Open Systems
2007 (English)In: EMSOFT'07: Proceedings of the Seventh ACM and IEEE International Conference on Embedded Software, 2007, 279-288 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a protocol for resource sharing in a hierarchical real-time scheduling framework. Targeting real-time open systems, the protocol and the scheduling framework significantly reduce the efforts and errors associated with integrating multiple semi-independent subsystems on a single processor. Thus, our proposed techniques facilitate modern software development processes, where subsystems are developed by independent teams (or subcontractors) and at a later stage integrated into a single product. Using our solution, a subsystem need not know, and is not dependent on, the timing behaviour of other subsystems; even though they share mutually exclusive resources. In this paper we also prove the correctness of our approach and evaluate its efficiency.

National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-1321 (URN)10.1145/1289927.1289970 (DOI)2-s2.0-38849089912 (Scopus ID)9781595938251 (ISBN)
Conference
EMSOFT'07: 7th ACM and IEEE International Conference on Embedded Software; Salzburg; Australia; 30 September 2007 through 3 October 2007
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2014-05-26Bibliographically approved
2. Overrun Methods and Resource Holding Times for Hierarchical Scheduling of Semi-Independent Real-Time Systems
Open this publication in new window or tab >>Overrun Methods and Resource Holding Times for Hierarchical Scheduling of Semi-Independent Real-Time Systems
2010 (English)In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, Vol. 6, no 1, 93-104 p.Article in journal (Refereed) Published
Abstract [en]

The Hierarchical Scheduling Framework (HSF) has been introduced as a design-time framework toenable compositional schedulability analysis of embedded software systems with real-time properties. Inthis paper a software system consists of a number of semi-independent components called subsystems.Subsystems are developed independently and later integrated to form a system. To support this designprocess, in the paper, the proposed methods allow non-intrusive configuration and tuning of subsystemtiming-behaviour via subsystem interfaces for selecting scheduling parameters.This paper considers three methods to handle overruns due to resource sharing between subsystemsin the HSF. For each one of these three overrun methods corresponding scheduling algorithms and associatedschedulability analysis are presented together with analysis that shows under what circumstances one or the other is preferred. The analysis is generalized to allow for both Fixed Priority Scheduling (FPS)and Earliest Deadline First (EDF) scheduling. Also, a further contribution of the paper is the techniqueof calculating resource-holding times within the framework under different scheduling algorithms; theresource holding times being an important parameter in the global schedulability analysis.

Keyword
Real time scheduling, resource sharing, hierarchical scheduling
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-10442 (URN)10.1109/TII.2009.2037918 (DOI)000274383700012 ()2-s2.0-76849101765 (Scopus ID)
Available from: 2010-10-18 Created: 2010-10-18 Last updated: 2013-12-03Bibliographically approved
3. Overrun and Skipping in Hierarchically Scheduled Real-Time Systems
Open this publication in new window or tab >>Overrun and Skipping in Hierarchically Scheduled Real-Time Systems
2009 (English)In: 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2009, 519-526 p.Conference paper, Published paper (Refereed)
Identifiers
urn:nbn:se:mdh:diva-10443 (URN)10.1109/RTCSA.2009.62 (DOI)000276774500057 ()2-s2.0-72349097496 (Scopus ID)978-0-7695-3787-0 (ISBN)
Conference
RTCSA'09
Available from: 2010-10-18 Created: 2010-10-18 Last updated: 2014-01-09Bibliographically approved
4. Bounding the number of self-blocking occurrences of SIRAP
Open this publication in new window or tab >>Bounding the number of self-blocking occurrences of SIRAP
2010 (English)In: Proceedings - Real-Time Systems Symposium, 2010, 61-72 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a new schedulability analysis for hierarchically scheduled real-time systems executing on a single processor using SIRAP; a synchronization protocol for inter subsystem task synchronization. We show that it is possible to bound the number of self-blocking occurrences that should be taken into consideration in the schedulability analysis of subsystems. Correspondingly, we present two novel schedulability analysis approaches with proof of correctness for SIRAP. An evaluation suggests that this new schedulability analysis can decrease the analytical subsystem utilization significantly

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-10444 (URN)10.1109/RTSS.2010.20 (DOI)000287965300006 ()2-s2.0-79951779466 (Scopus ID)978-076954298-0 (ISBN)
Conference
31st IEEE Real-Time Systems Symposium, RTSS 2010;San Diego, CA;30 November 2010through3 December 2010
Available from: 2010-10-18 Created: 2010-10-18 Last updated: 2014-01-09Bibliographically approved
5. Schedulability analysis of synchronization protocols based on overrun without payback for hierarchical scheduling frameworks revisited
Open this publication in new window or tab >>Schedulability analysis of synchronization protocols based on overrun without payback for hierarchical scheduling frameworks revisited
2010 (English)Report (Other academic)
Abstract [en]

In this paper, we show that both global as well as local schedulability analysis of synchronization protocols based on the stack resource protocol (SRP) and overrun without payback for hierarchical scheduling frameworks based on fixed-priority pre-emptive scheduling (FPPS) are pessimistic.We present improved global and local schedulability analysis,illustrate the improvements by means of examples, and show that the improved global analysis is both uniform and sustainable.We evaluate the improved global and local schedulabilityanalysis based on an extensive simulation study and comparethe results with the existing analysis.

Place, publisher, year, edition, pages
Mälardalen Real-Time Research Centre, Mälardalen University, 2010
Series
MRTC report, ISSN 1404-3041
Identifiers
urn:nbn:se:mdh:diva-10446 (URN)
Available from: 2010-10-18 Created: 2010-10-18 Last updated: 2014-01-09Bibliographically approved
6. Refining SIRAP with a Dedicated Resource Ceiling for Self-Blocking
Open this publication in new window or tab >>Refining SIRAP with a Dedicated Resource Ceiling for Self-Blocking
2009 (English)In: 9th ACM & IEEE International Conference on Embedded Software, 2009, 157-166 p.Conference paper, Published paper (Refereed)
Identifiers
urn:nbn:se:mdh:diva-10445 (URN)10.1145/1629335.1629357 (DOI)2-s2.0-72249088588 (Scopus ID)978-160558627-4 (ISBN)
Conference
Embedded Systems Week 2009, ESWEEK 2009 - 9th ACM International Conference on Embedded Software, EMSOFT '09; Grenoble; 11 October 2009 through 16 October 2009
Available from: 2010-10-18 Created: 2010-10-18 Last updated: 2014-01-09Bibliographically approved
7. Synthesis of Optimal Interfaces for Hierarchical Scheduling with Resources
Open this publication in new window or tab >>Synthesis of Optimal Interfaces for Hierarchical Scheduling with Resources
2008 (English)In: Proceedings of the 29th IEEE International Real-Time Systems Symposium (RTSS08)., 2008, 209-220 p.Conference paper, Published paper (Refereed)
Abstract [en]

 

This paper presents algorithms that (1) facilitate system independent synthesis of timing-interfaces for subsystems and (2) system-level selection of interfaces to minimize CPU load. The results presented are developed for hierarchical fixed-priority scheduling of subsystems that may share logical recourses (i.e., semaphores). We show that the use of shared resources results in a tradeoff problem, where resource locking times can be traded for CPU allocation, complicating the problem of finding the optimal interface configuration subject to schedulability. This paper presents a methodology where such a tradeoff can be effectively explored. It first synthesizes a bounded set of interface-candidates for each subsystem, independently of the final system, such that the set contains the interface that minimizes system load for any given  system. Then, integrating subsystems into a system, it finds the optimal selection of interfaces. Our algorithms have linear complexity to the number of tasks involved. Thus, our approach is highly suitable for adaptable and reconfigurable systems.

 

National Category
Computer Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-1323 (URN)10.1109/RTSS.2008.34 (DOI)000262709900019 ()2-s2.0-67249163524 (Scopus ID)978-0-7695-3477-0 (ISBN)
Conference
Real Time Systems Symposium 2008 Barcelona, SPAIN, NOV 30-DEC 03, 2008 IEEE Comp Soc; Tech Comm Real-Time Syst
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2016-06-03Bibliographically approved

Open Access in DiVA

fulltext(1238 kB)508 downloads
File information
File name FULLTEXT02.pdfFile size 1238 kBChecksum SHA-512
d2da75c204bdd23fdd23ad0b5ea188191cb883fa065fe0abc75efa9e81e12693df51114741c0594d715cb4324b31157f3ffe266c0180c99fefd4dbcb198cf1ea
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Behnam, Moris
By organisation
School of Innovation, Design and Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 508 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 347 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf