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
Synthesis of Optimal Interfaces for Hierarchical Scheduling with Resources
Mälardalen University, School of Innovation, Design and Engineering. (PROGRESS)ORCID iD: 0000-0002-1687-930X
Mälardalen University, School of Innovation, Design and Engineering. (PROGRESS)ORCID iD: 0000-0001-6132-7945
Mälardalen University, School of Innovation, Design and Engineering. (PROGRESS)ORCID iD: 0000-0001-7586-0409
2008 (English)In: Proceedings of the 29th IEEE International Real-Time Systems Symposium (RTSS08)., 2008, p. 209-220Conference 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.

 

Place, publisher, year, edition, pages
2008. p. 209-220
National Category
Computer Engineering
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-1323DOI: 10.1109/RTSS.2008.34ISI: 000262709900019Scopus ID: 2-s2.0-67249163524ISBN: 978-0-7695-3477-0 (print)OAI: oai:DiVA.org:mdh-1323DiVA, id: diva2:37885
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: 2018-01-12Bibliographically approved
In thesis
1. Hierarchical Real Time Scheduling and Synchronization
Open this publication in new window or tab >>Hierarchical Real Time Scheduling and Synchronization
2008 (English)Licentiate thesis, comprehensive summary (Other scientific)
Abstract [en]

 

The Hierarchical Scheduling Framework (HSF) has been introduced to enable compositional schedulability analysis and execution of embedded software systems with real-time constraints. In this thesis, we consider a system consisting of a number of semi-independent components called subsystems, and these subsystems are allowed to share logical resources. The HSF provides CPU-time to the subsystems and it guarantees that the individual subsystems respect their allocated CPU budgets. However, if subsystems are allowed to share logical resources, extra complexity with respect to analysis and run-time mechanisms is introduced. In this thesis we address three issues related to hierarchical scheduling of semi-independent subsystems. In the first part, we investigate the feasibility of implementing the hierarchical scheduling framework in a commercial operating system, and we present the detailed figures of various key properties with respect to the overhead of the implementation.

In the second part, we studied the problem of supporting shared resources in a hierarchical scheduling framework and we propose two different solutions to support resource sharing. The first proposed solution is called SIRAP, a synchronization protocol for resource sharing in hierarchically scheduled open real-time systems, and the second solution is an enhanced overrun mechanism.

In the third part, we present a resource efficient approach to minimize system load (i.e., the collective CPU requirements to guarantee the schedulability of hierarchically scheduled subsystems). Our work is motivated from a tradeoff between reducing resource locking times and reducing system load. We formulate an optimization problem that determines the resource locking times of each individual subsystem with the goal of minimizing the system load subject to system schedulability. We present linear complexity algorithms to find an optimal solution to the problem, and we prove their correctness

 

 

 

 

 

 

 

Place, publisher, year, edition, pages
Västerås: Mälardalens högskola, 2008. p. 153
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 94
National Category
Computer Engineering
Research subject
Datavetenskap
Identifiers
urn:nbn:se:mdh:diva-1324 (URN)978-91-86135-09-6 (ISBN)
Presentation
Kappa, Västerås (English)
Opponent
Supervisors
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2018-01-12Bibliographically approved
2. Synchronization Protocols for a Compositional Real-Time Scheduling Framework
Open this publication in new window or tab >>Synchronization Protocols for a Compositional Real-Time Scheduling Framework
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:nbn:se:mdh:diva-10447 (URN)978-91-86135-95-9 (ISBN)
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

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Behnam, MorisNolte, ThomasSjödin, Mikael

Search in DiVA

By author/editor
Behnam, MorisNolte, ThomasSjödin, Mikael
By organisation
School of Innovation, Design and Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 56 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