mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
On the Development of Hierarchical Real-Time Systems
Mälardalen University, School of Innovation, Design and Engineering. (Complex Real-Time Embedded Systems (CORE) research group)ORCID iD: 0000-0001-6157-5199
2012 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Hierarchical scheduling (also referred to as resource reservation) is a hot topic within the research of real-time systems. It has many advantages such that it can facilitate software integration, fault isolation, structured analysis, legacy system integration etc. The main idea is to partition resources into well defined slots and the resource itself may be the processor, memory etc. This technique is rarely used in real-time applications, however, it is well adopted in the avionics industry in order to isolate error propagation between system parts, and facilitate analysis of the system.Much of the research within resource reservation deals with theoretical schedulability analysis of partitioned systems, including shared resources (other than the processor). We will in this thesis address more practical issues related to resource reservation. We focus on implementation and prototyping aspects, as well as verification and instrumentation. One of our assumptions is that we deal only with fixed-priority preemptive scheduling (FPPS).The first part in this thesis deals with individual software systems that may have its own tasks as well as a scheduler and it is assumed to be part of another larger system, hence, we refer to this individual system as a subsystem. The subsystem is assumed to be integrated together with other subsystems, but at a early stage, we make it possible to simulate the subsystem running together with the rest of the subsystems. This "simulation`` does not require the actual resource reservation mechanism, the only requirement is an operating system with support for FPPS. This pre-study may be a natural step towards the "real`` integration, since each individual subsystem can be test executed within its assigned partition. All subsystems are assumed to run together using a resource reservation mechanism (during the actual integration). We have developed two prototypes of this mechanism. The first prototype is hand-crafted and it is equipped with a program tracer for partitoned based schedulers. This instrumentation is useful for debugging and visualization of program traces for this type of scheduling. The second prototype is developed using timed automata with tasks (task automata). This model-based scheduler is verified for correctness and it is possible to automatically generate source code for the scheduler. We have successfully synthesized this scheduler for the real-time operating system VxWorks. However, it can easily be executed on most other platforms. Both prototypes has pros and cons. The first version has good performance while the second can guarantee its correctness, hence, there is a trade-off between performance and correctness.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2012. , 154 p.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 155
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-14633ISBN: 987-91-7485-075-8 OAI: oai:DiVA.org:mdh-14633DiVA: diva2:527485
Presentation
2012-06-12, Kappa, Högskoleplan 1, Västerås, 10:15 (English)
Opponent
Supervisors
Available from: 2012-05-21 Created: 2012-05-21 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, (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. A Loadable Task Execution Recorder for Hierarchical Scheduling in Linux
Open this publication in new window or tab >>A Loadable Task Execution Recorder for Hierarchical Scheduling in Linux
2011 (English)In: Proceedings - 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011, 2011, 380-387 p.Conference paper, (Refereed)
Abstract [en]

This paper presents a Hierarchical Scheduling Framework (HSF) recorder for Linux-based operating systems. The HSF-recorder is a loadable kernel module that is capable of recording tasks and servers without requiring any kernel modifications. Hence, it complies with the reliability and stability requirements in the area of embedded systems where proven versions of Linux are preferred. The recorder is built upon the loadable real-time scheduler framework RESCH (REal-time SCHed- uler). We evaluate our recorder by comparing the overhead of this solu- tion against two other recorders. Also, the tracing accuracy of the HSF- recorder is tested by running a media-processing task together with periodic real-time Linux tasks in combination with servers. We experiment with different task parameters and scheduling strategies and measure the performance of the media-processing task. The tests are recorded with the HSF-recorder, and the Ftrace recorder, in order to show the correctness of the experiments and the HSF-recorder itself.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13673 (URN)10.1109/RTCSA.2011.28 (DOI)2-s2.0-84855542255 (Scopus ID)978-076954502-8 (ISBN)
Conference
17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011;Toyama;28 August 2011 through 31 August 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2013-12-03Bibliographically approved
3. Prototyping and Code Synthesis of Hierarchically Scheduled Systems using TIMES
Open this publication in new window or tab >>Prototyping and Code Synthesis of Hierarchically Scheduled Systems using TIMES
2010 (English)In: FTRA Journal of Convergence, ISSN 2093-7741, Vol. 1, no 1, 75-84 p.Article in journal (Refereed) Published
Abstract [en]

In hierarchical scheduling a system is organized as a tree of nodes, where each node schedules its child nodes. A node contains tasks and/or subsystems, where a subsystem is typically developed by a development team. Given a system where each part is subcontracted to different developers, they can benefit from hierarchical scheduling by parallel development and simplified integration of subsystems. Each team should have the possibility to test their system before integration. Hence, we show how a node, in a hierarchical scheduling tree, can be analyzed in the Times tool by replacing all interference from nodes with a small set of higher priority tasks. We show an algorithm that can generate these tasks, including their parameters. Further, we use the Times code-generator, in combination with operating system extensions, to generate source code that emulates the scheduling environment for a subsystem, in an arbitrary level in the tree. Our experiments include two example systems. In the first case we generate source code for an industrial oriented platform (VxWorks) and conduct a performance evaluation. In the second example we generate source code that emulates the scheduling environment for a video application, running in Linux, and we perform a frame-rate evaluation.

Place, publisher, year, edition, pages
Seoul: , 2010
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-14630 (URN)
Available from: 2012-05-21 Created: 2012-05-21 Last updated: 2013-12-03Bibliographically approved
4. Modelling, Verification and Synthesis of Two-Tier Hierarchical Fixed-Priority Preemptive Scheduling
Open this publication in new window or tab >>Modelling, Verification and Synthesis of Two-Tier Hierarchical Fixed-Priority Preemptive Scheduling
2011 (English)In: Proceedings - 23rd EUROMICRO Conference on Real-Time Systems (ECRTS'11), 2011, 172-181 p.Conference paper, (Refereed)
Abstract [en]

Hierarchical scheduling has major benefits when it comes to integrating hard real-time applications. One of those benefits is that it gives a clear runtime separation of applications in the time domain. This in turn gives a protection against timing error propagation in between applications. However, these benefits rely on the assumption that the scheduler itself schedules applications correctly according to the scheduling parameters and the chosen scheduling policy. A faulty scheduler can affect all applications in a negative way. Hence, being able to guarantee that the scheduler is correct is of great importance. Therefore, in this paper, we study how properties of hierarchical scheduling can be verified. We model a hierarchically scheduled system using task automata, and we conduct verification with model checking using the Times tool. Further, we generate C-code from the model and we execute the hierarchical scheduler in the Vx Works kernel. The CPU and memory overhead of the modelled scheduler is compared against an equivalent manually coded two-level hierarchical scheduler. We show that the worst-case memory consumption is similar and that there is a considerable difference in CPU overhead.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13734 (URN)10.1109/ECRTS.2011.24 (DOI)000323257300016 ()2-s2.0-80052990420 (Scopus ID)9780769544427 (ISBN)
Conference
23rd Euromicro Conference on Real-Time Systems, ECRTS 2011;Porto;5 July 2011 through 8 July 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2014-01-07Bibliographically approved

Open Access in DiVA

Kappa(190 kB)509 downloads
File information
File name FULLTEXT01.pdfFile size 190 kBChecksum SHA-512
21b05aca651b0a464fb2e866ae36ac54f2364c19d84f0b94b6a914c1b12a137051b09e7c447d2e76c1b92168a59718455873c79850dc6825a4924e845bd163a6
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Åsberg, Mikael
By organisation
School of Innovation, Design and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 509 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: 599 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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