mdh.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 28) Show all publications
Åsberg, M. (2014). Synthesis and Synchronization Support for Hierarchically Scheduled Real-Time Systems. (Doctoral dissertation). Västerås: Mälardalen University
Open this publication in new window or tab >>Synthesis and Synchronization Support for Hierarchically Scheduled Real-Time Systems
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

A piece of software, that we define as a software system, can consist of anything from a few lines of program code or the entire software stack in a vehicle. Software systems can be divided into smaller and partially independent parts called subsystems/partitions (we use the words partition and subsystem interchangeably). The non-functional isolation of subsystems, that appears when the software system is hierarchically divided, has great advantages when it comes to preventing fault propagation between subsystems. The hierarchical division, that we refer to as hierarchical scheduling, has other advantages as well. It facilitates re-usability and it makes timing analysis of software systems easier. Hierarchical scheduling has been shown to be a useful tool in counteracting the verification challenges that comes from the growing complexity in software. For example, the avionics-specification ARINC653 and the safety-critical operating systems seL4 and PikeOS safely divide resources for independent safety-critical applications by using hierarchical scheduling.

Hierarchical scheduling can be implemented in many different ways, depending on what resource that is supposed to be shared among applications. The resource could be the CPU, memory, network etc. The work in this thesis is focused on the practical aspects of timing isolation among subsystems, i.e., sharing of the CPU resource. Hence, this work elaborates on how to adapt and extend the operating-system task-scheduler to support hierarchical scheduling. We have focused on both independent and semi-dependent subsystems. Independent subsystems only share general resources such as the CPU and memory. Semi-independent subsystems share not only the general resources, but also other logical resources that can only be accessed in a mutually exclusive way, i.e., by one subsystem at a time. An example of such a resource could be a shared memory-space, e.g., a database, a memory-mapped device etc.

This thesis has two main parts related to hierarchical scheduling: scheduler synthesis, and synchronization.

Scheduler synthesis is related to implementation and design strategies when adding support for hierarchical scheduling in an operating system. We have focused on various operating systems that were lacking the feature of hierarchical scheduling. The two most interesting operating systems that we worked on was Linux and seL4. These two operating systems represent two extremes, where Linux is more focused towards soft real-time systems and seL4 towards pure hard real-time (safety-critical) systems. Linux-based systems have in general less strict demands on correctness and more requirements on usability. Usability implies less installation efforts and less limitations in the usage of the available Linux functionality. The usability aspect is especially important for Linux systems since kernel updates occur much more frequently compared to any other operating system. Hence, extending/modifying the functionality of Linux must be done in a way that does not require any modifications to the kernel. seL4 on the other hand has strict requirements on safety, i.e., functional and non-functional correctness, but also performance efficiency. Guaranteeing correctness implies a potential loss of performance due to the added overhead that the verified software can bring. The correctness aspect includes strategies on how to verify hierarchical schedulers, but also how to minimize the scheduler overhead and achieve as good run-time performance as possible. Conclusively, there are many challenges when it comes to scheduler synthesis. There are requirements on performance, usability, correctness etc. The contribution in the synthesis part includes a scheduler framework called ExSched (External Scheduler). We have also contributed with a novel approach to verify hierarchical schedulers, and a code generator called TAtoC (Timed Automata to C) which contributes to the effective run-time performance of synthesized timed-automata models.

The second part of this thesis, synchronization, is an important general aspect of hierarchically scheduled systems since the isolation of subsystems makes resource sharing among subsystems more challenging. We have advanced the state-of-the-art in this research area by introducing a new synchronization protocol called RRP (Rollback Resource Policy) that improves on the robustness and run-time performance compared to the existing protocols. We have also conducted a large scale experimental evaluation of all existing protocols that we have implemented in the widely used real-time operating system VxWorks.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2014. p. 266
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 149
National Category
Computer Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-23462 (URN)978-91-7485-131-1 (ISBN)
Public defence
2014-01-31, Gamma, Västerås, 10:00 (English)
Opponent
Supervisors
Available from: 2014-01-07 Created: 2013-12-12 Last updated: 2018-01-11Bibliographically approved
Åsberg, M., Behnam, M. & Nolte, T. (2013). An Experimental Evaluation of Synchronization Protocol Mechanisms in the Domain of Hierarchical Fixed-Priority Scheduling. In: ACM International Conference Proceeding Series, 2013: . Paper presented at 21st International Conference on Real-Time Networks and Systems, RTNS 2013; Sophia Antipolis; France; 16 October 2013 through 18 October 2013 (pp. 77-85).
Open this publication in new window or tab >>An Experimental Evaluation of Synchronization Protocol Mechanisms in the Domain of Hierarchical Fixed-Priority Scheduling
2013 (English)In: ACM International Conference Proceeding Series, 2013, 2013, p. 77-85Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents an extensive implementation study where we evaluate and compare different synchronization protocol mechanisms within the domain of two-level hierarchical fixed-priority preemptive scheduling. These protocol mechanisms include HSRPnP (Hierarchical Stack Resource Policy no Payback), HSRPwP (Hierarchical Stack Resource Policy with Payback), SIRAP (Subsystem Integration and Resource Allocation Policy), RRP (Rollback Resource Policy) and SRPwD (Stack Resource Policy with Donation). In an attempt to shed new light to the research in this area, we focus on the actual software implementation of these protocols in a widely used real-time operating system (VxWorks). This study is not based on worst-case schedulability analysis which is the most common angle of work in this research field. All five protocols have been implemented, tested and executed for several months with many different parameters, for example; variant number of subsystems, number of resources, system utilization settings, resource allocation strategies etc. These tests generated a large amount of useful data, for example, protocol overhead, effective subsystem utilization, number of protocol mechanism invocations etc. Due to the large complexity and size of this data, we analyzed the data with state-of-the-art statistical methods and tools (Principal Component Analysis) in order to grasp the efficiency of the protocols with respect to a large number of different parameters.

National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-23458 (URN)10.1145/2516821.2516823 (DOI)2-s2.0-84893499282 (Scopus ID)978-1-4503-2058-0 (ISBN)
Conference
21st International Conference on Real-Time Networks and Systems, RTNS 2013; Sophia Antipolis; France; 16 October 2013 through 18 October 2013
Available from: 2013-12-12 Created: 2013-12-12 Last updated: 2014-02-21Bibliographically approved
Åsberg, M., Pettersson, P. & Nolte, T. (2013). Evaluating the Run-Time Performance of Synthesised Resource-Reservation Schedulers Using TAtoC, UPPAAL and Frama-C.
Open this publication in new window or tab >>Evaluating the Run-Time Performance of Synthesised Resource-Reservation Schedulers Using TAtoC, UPPAAL and Frama-C
2013 (English)Report (Other academic)
Publisher
p. 10
National Category
Embedded Systems
Identifiers
urn:nbn:se:mdh:diva-23459 (URN)MDH-MRTC-282/2013-1-SE (ISRN)
Available from: 2013-12-12 Created: 2013-12-12 Last updated: 2014-06-05Bibliographically approved
Åsberg, M., Nolte, T., Joki, M., Hogbrink, J. & Siwani, S. (2013). Fast Linux Bootup using Non-Intrusive Methods for Predictable Industrial Embedded Systems. In: : . Paper presented at 18th IEEE Conference on Emerging Technologies and Factory Automation (ETFA 2013),Cagliari, Italy, 10-13 September 2013 (pp. Article number 6648027).
Open this publication in new window or tab >>Fast Linux Bootup using Non-Intrusive Methods for Predictable Industrial Embedded Systems
Show others...
2013 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Fast kernel boot-time is one of the major concerns in industrial embedded systems. Application domains where boot time is relevant include (among others) automation, automotive, avionics etc. Linux is one of the big players among operating system solutions for general embedded systems, hence, a relevant question is how fast Linux can boot on typical hardware platforms (ARM9) used in such industrial systems. One important constraint is that this boot-time optimization should be as non-intrusive as possible. The reason for this comes from the fact that industrial embedded systems typically have high demands on reliability and stability. For example, adding, removing or changing critical source-code (such as kernel or initialization code) is impermissible. This paper shows the steps towards a fast-booting Linux kernel using non-intrusive methods. Moreover, targeting embedded systems with temporal constraints, the paper shows how fast the real-time scheduling framework ExSched can be loaded and started during bootup. This scheduling framework supports several real-time scheduling algorithms (user defined, multi-core, partitioned, fixed-priority periodic tasks etc.) and it does not modify the Linux kernel source code. Hence, the non-intrusive bootup optimization methods together with the unmodified Linux kernel and the non-patched real-time scheduler module offers both reliability and predictability.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-21387 (URN)10.1109/ETFA.2013.6648027 (DOI)2-s2.0-84890620798 (Scopus ID)9781479908622 (ISBN)
Conference
18th IEEE Conference on Emerging Technologies and Factory Automation (ETFA 2013),Cagliari, Italy, 10-13 September 2013
Projects
SYNOPSIS - Safety Analysis for Predictable Software Intensive Systems
Available from: 2013-09-17 Created: 2013-09-11 Last updated: 2016-03-10Bibliographically approved
Åsberg, M., Nolte, T. & Behnam, M. (2013). Resource sharing using the rollback mechanism in hierarchically scheduled real-time open systems. In: Real-Time Technology and Applications - Proceedings: . Paper presented at 013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium, RTAS 2013; Philadelphia, PA; United States; 9 April 2013 through 11 April 2013 (pp. 129-140).
Open this publication in new window or tab >>Resource sharing using the rollback mechanism in hierarchically scheduled real-time open systems
2013 (English)In: Real-Time Technology and Applications - Proceedings, 2013, p. 129-140Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we present a new synchronization protocol called RRP (Rollback Resource Policy) which is compatible with hierarchically scheduled open systems and specialized for resources that can be aborted and rolled back. We conduct an extensive event-based simulation and compare RRP against all equivalent existing protocols in hierarchical fixed priority preemptive scheduling; SIRAP (Subsystem Integration and Resource Allocation Policy), OPEN-HSRPnP (open systems version of Hierarchical Stack Resource Policy no Payback) and OPEN-HSRPwP (open systems version of Hierarchical Stack Resource Policy with Payback). Our simulation study shows that RRP has better average-case response-times than the state-of-the-art protocol in open systems, i.e., SIRAP, and that it performs better than OPEN-HSRPnP/OPEN-HSRPwP in terms of schedulability of randomly generated systems. The simulations consider both resources that are compatible with rollback as well as resources incompatible with rollback (only abort), such that the resource-rollback overhead can be evaluated. We also measure CPU overhead costs (in VxWorks) related to the rollback mechanism of tasks and resources. We use the eXtremeDB (embedded real-time) database to measure the resource-rollback overhead.

Series
Real-Time Technology and Applications - Proceedings
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-20920 (URN)10.1109/RTAS.2013.6531086 (DOI)000326871500013 ()2-s2.0-84881110752 (Scopus ID)
Conference
013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium, RTAS 2013; Philadelphia, PA; United States; 9 April 2013 through 11 April 2013
Available from: 2013-09-05 Created: 2013-08-16 Last updated: 2018-08-07Bibliographically approved
Åsberg, M., Nolte, T. & Kato, S. (2013). Towards Partitioned Hierarchical Real-Time Scheduling on Multi-core Processors. In: : . Paper presented at 1st International Workshop on Virtualization for Real-Time Embedded Systems (VtRES13, Taipeh, Taiwan, August 2013.
Open this publication in new window or tab >>Towards Partitioned Hierarchical Real-Time Scheduling on Multi-core Processors
2013 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This paper extends previous work on hierarchical scheduling to multi-core systems. We have implemented partitioned multi-core scheduling of servers in the Linux kernel, using the scheduling framework ExSched. Neither ExSched nor the presented scheduler require any modifications to the Linux kernel. Hence, this makes the installation and kernel-version updates easier. We also present a user-space simulator which can be used when developing new multi-core hierarchical schedulers (plug-ins) for ExSched. We evaluate the overhead of our new multi-core hierarchical scheduler and compare it to a single-core hierarchical scheduler. Our results can be useful for developers that want to minimize the scheduler overhead when using partitioned hierarchical multi-core scheduling.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-21406 (URN)
Conference
1st International Workshop on Virtualization for Real-Time Embedded Systems (VtRES13, Taipeh, Taiwan, August 2013
Projects
SYNOPSIS - Safety Analysis for Predictable Software Intensive Systems
Available from: 2013-09-11 Created: 2013-09-11 Last updated: 2013-12-03Bibliographically approved
Åsberg, M., Nolte, T., Kato, S. & Rajkumar, R. (2012). ExSched: An External CPU Scheduler Framework for Real-Time Systems. In: 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'12). Paper presented at 2012 IEEE 18th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 19-22 Aug. 2012,Seoul (pp. 240-249).
Open this publication in new window or tab >>ExSched: An External CPU Scheduler Framework for Real-Time Systems
2012 (English)In: 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'12), 2012, p. 240-249Conference paper, Published paper (Refereed)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-17311 (URN)10.1109/RTCSA.2012.9 (DOI)2-s2.0-84869021305 (Scopus ID)978-0-7695-4824-1 (ISBN)978-1-4673-3017-6 (ISBN)
Conference
2012 IEEE 18th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 19-22 Aug. 2012,Seoul
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2014-01-07Bibliographically approved
Åsberg, M. (2012). On the Development of Hierarchical Real-Time Systems. (Licentiate dissertation). Västerås: Mälardalen University
Open this publication in new window or tab >>On the Development of Hierarchical Real-Time Systems
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. p. 154
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 155
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-14633 (URN)987-91-7485-075-8 (ISBN)
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: 2018-01-12Bibliographically approved
Åsberg, M. & Nolte, T. (2012). Towards a User-Mode Approach to Partitioned Scheduling in the seL4 Microkernel. In: . Paper presented at 5th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2012), San Juan, Puerto Rico, December 4,2012.
Open this publication in new window or tab >>Towards a User-Mode Approach to Partitioned Scheduling in the seL4 Microkernel
2012 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a preliminary study of applying partitioned scheduling in the seL4 microkernel. This microkernel is the first operating system kernel ever to be formally proven for its functional correctness. Even though the kernel is completely verified it still delivers high performance comparable to other L4 kernels. The seL4 kernel implements isolation of components in terms of the memory resource and security. However, there is still a missing part when it comes to isolation and that is time partitioning. Time partitioning can be implemented inside the kernel (privileged mode) or in user space (user mode). The latter is done using regular user-space thread(s) and can easily be modified while the other approach requires re-verification of the kernel whenever modifications to the time-partitioning policy is done. On the other hand, having the time-partitioning mechanism in privileged mode would yield better performance. We have implemented time partitioning (partitioned scheduling) in the seL4 user space and we elaborate on its performance in terms of overhead costs.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-17384 (URN)
Conference
5th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2012), San Juan, Puerto Rico, December 4,2012
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2014-01-07Bibliographically approved
Hallmans, D., Åsberg, M. & Nolte, T. (2012). Towards using the Graphics Processing Unit (GPU) for Embedded Systems. In: IEEE Symposium on Emerging Technologies and Factory Automation, ETFA 2012: . Paper presented at 17th IEEE International Conference on Emerging Technologies & Factory Automation (ETFA'12), Work-in-Progress (WiP) session, September 17-21, Krakow, Poland (pp. Article number: 6489715).
Open this publication in new window or tab >>Towards using the Graphics Processing Unit (GPU) for Embedded Systems
2012 (English)In: IEEE Symposium on Emerging Technologies and Factory Automation, ETFA 2012, 2012, p. Article number: 6489715-Conference paper, Published paper (Refereed)
Abstract [en]

The Graphics Processing Unit (GPU) is becoming a very powerful platform to accelerate graphics and dataparallel compute-intensive applications. It gives a high performance and at the same time it has a low power consumption. This combination is of high performance and low power consumption is useful when it comes to building an embedded system. In this paper we are looking at the possibility to use a combination of CPU and GPU to provide performance metrics that are required in an embedded system. In particular we look at requirements inherent in the process and power industries where we believe that the GPU has the potential to be a useful and natural element in future embedded system architectures.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-17352 (URN)10.1109/ETFA.2012.6489715 (DOI)000320333400184 ()2-s2.0-84876356572 (Scopus ID)
Conference
17th IEEE International Conference on Emerging Technologies & Factory Automation (ETFA'12), Work-in-Progress (WiP) session, September 17-21, Krakow, Poland
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2018-08-08Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-6157-5199

Search in DiVA

Show all publications