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
Hierarchical Real Time Scheduling and Synchronization
Mälardalen University, School of Innovation, Design and Engineering. (PROGRESS)ORCID iD: 0000-0002-1687-930X
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. , 153 p.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 94
National Category
Computer Engineering
Research subject
Datavetenskap
Identifiers
URN: urn:nbn:se:mdh:diva-1324ISBN: 978-91-86135-09-6 (print)OAI: oai:DiVA.org:mdh-1324DiVA: diva2:37888
Presentation
Kappa, Västerås (English)
Opponent
Supervisors
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2013-12-03Bibliographically approved
List of papers
1. Towards Hierarchical Scheduling in VxWorks
Open this publication in new window or tab >>Towards Hierarchical Scheduling in VxWorks
Show others...
2008 (English)In: OSPERT 2008, Proceedings of the Fourth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, 2008, 63-72 p.Conference paper, Published paper (Refereed)
Abstract [en]

Over the years, we have worked on hierarchical schedulingframeworks from a theoretical point of view. In thispaper we present our initial results of the implementationof our hierarchical scheduling framework in a commercialoperating system VxWorks. The purpose of the implementationis twofold: (1) we would like to demonstrate feasibilityof its implementation in a commercial operating system,without having to modify the kernel source code, and (2) wewould like to present detailed figures of various key propertieswith respect to the overhead of the implementation.During the implementation of the hierarchical scheduler,we have also developed a number of simple task schedulers.We present details of the implementation of Rate-Monotonic(RM) and Earliest Deadline First (EDF) schedulers. Finally,we present the design of our hierarchical schedulingframework, and we discuss our current status in the project.

National Category
Computer Engineering
Identifiers
urn:nbn:se:mdh:diva-1319 (URN)
Conference
OSPERT 2008, Fourth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, Prague, Czech Republic, July 1, 2008
Projects
PROGRESS
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2014-01-09Bibliographically approved
2. 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
3. Scheduling of Semi-Independent Real-Time Components: Overrun Methods and Resource Holding Times
Open this publication in new window or tab >>Scheduling of Semi-Independent Real-Time Components: Overrun Methods and Resource Holding Times
2008 (English)In: Proceedings of the 13th IEEE International Conference on Emerging echnologies and Factory Automation (ETFA’08), 2008, 575-582 p.Conference paper, Published paper (Refereed)
Abstract [en]

The Hierarchical Scheduling Framework (HSF) has been introduced as a design-time framework enabling compositional schedulability analysis of embedded software systems with real-time properties. In this paper a 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 design process, our proposed methods allow nonintrusive configuration and tuning of subsystem timing behaviour via subsystem interfaces for selecting scheduling parameters. This paper considers two methods to handle overruns due to resource sharing between subsystems in the HSF. We present the scheduling algorithms for overruns and their associated schedulability analysis, together with analysis that shows under what circumstances one or the other overrun method is preferred. Furthermore, we show how to calculate resource-holding times within our framework.

National Category
Computer Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-1322 (URN)10.1109/ETFA.2008.4638456 (DOI)000260495500099 ()2-s2.0-56349168936 (Scopus ID)978-1-4244-1505-2 (ISBN)
Conference
13th IEEE International Conference on Emerging Technologies and Factory Automation Location: Hamburg, GERMANY Date: SEP 15-18, 2008
Available from: 2008-10-15 Created: 2008-10-15 Last updated: 2013-12-03Bibliographically approved
4. 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(275 kB)970 downloads
File information
File name FULLTEXT01.pdfFile size 275 kBChecksum SHA-512
e9b59c9fe91b029c1edca1d67f5dd4b6fd654e3fcdaf5ee3476c932138d1424ca95e8e99c0171f6680e78d602f952a8bec1495202e7e52fe2e7876bb502a6fb4
Type fulltextMimetype application/pdf

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 970 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: 233 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