| 1. |
- Behnam, Moris
(författare)
-
Hierarchical Real Time Scheduling and Synchronization
- 2008
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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
|
|
| 2. |
- Behnam, Moris, et al.
(författare)
-
Overrun Methods for Semi-Independent Real-Time Hierarchical Scheduling
- 2009
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The Hierarchical Scheduling Framework (HSF) has been introduced as a design-time framework to enable compositional schedulability analysis of embedded software systems with real-time properties. In this 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 design process, in the paper, the proposed methods allow non-intrusive configuration and tuning of subsystem timing-behaviour via subsystem interfaces for selecting scheduling parameters. This paper considers three methods to handle overruns due to resource sharing between subsystems in the HSF. For each one of these three overrun methods corresponding scheduling algorithms The work in this paper is supported by the Swedish Foundation for Strategic Research (SSF), via the research programme PROGRESS. and associated schedulability 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 technique of calculating resource-holding times within the framework under different scheduling algorithms. The resource holding times being an important parameter in the global schedulability analysis.
|
|
| 3. |
- Behnam, Moris, et al.
(författare)
-
SIRAP: A Global Resource Sharing Protocol Facilitating Integration of Semi-independent Real-Time Systems
- 2007
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This paper presents a protocol for resource sharing in a hierarchical real-time scheduling framework. Together, 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.
|
|
| 4. |
- Bohlin, Markus, 1976-
(författare)
-
A Study of Combinatorial Optimization Problems in Industrial Computer Systems
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- A combinatorial optimization problem is an optimization problem where the number of possible solutions are finite and grow combinatorially with the problem size. Combinatorial problems exist everywhere in industrial systems. This thesis focuses on solving three such problems which arise within two different areas where industrial computer systems are often used. Within embedded systems and real-time systems, we investigate the problems of allocating stack memory for an system where a shared stacks may be used, and of estimating the highest response time of a task in a system of industrial complexity. We propose a number of different algorithms to compute safe upper bounds on run-time stack usage whenever the system supports stack sharing. The algorithms have in common that they can exploit commonly-available information regarding timing behaviour of the tasks in the system. Given upper bounds on the individual stack usage of the tasks, it is possible to estimate the worst-case stack behaviour by analysing the possible and impossible preemption patterns. Using relations on offset and precedences, we form a preemption graph, which is further analysed to find safe upper-bounds on the maximal preemptions chain in the system. For the special case where all tasks exist in a single static schedule and share a single stack, we propose a polynomial algorithm to solve the problem. For generalizations of this problem, we propose an exact branch-and-bound algorithm for smaller problems and a polynomial heuristic algorithm for cases where the branch-and-bound algorithm fails to find a solution in reasonable time. All algorithms are evaluated in comprehensive experimental studies. The polynomial algorithm is implemented and shipped in the developer tool set for a commercial real-time operating system, Rubus OS. The second problem we study in the thesis is how to estimate the highest response time of a specified task in a complex industrial real-time system. The response-time analysis is done using a best-effort approach, where a detailed model of the system is simulated on input constructed using a local search procedure. In an evaluation on three different systems we can see that the new algorithm were able to produce higher response times much faster than what has previously been possible. Since the analysis is based on simulation and measurement, the results are not safe in the sense that they are always higher or equal to the true response time of the system. The value of the method lies instead in that it makes it possible to analyse complex industrial systems which cannot be analysed accurately using existing safe approaches. The third problem is in the area of maintenance planning, and focus on how to dynamically plan maintenance for industrial systems. Within this area we have focused on industrial gas turbines and rail vehicles. We have developed algorithms and a planning tool which can be used to plan maintenance for gas turbines and other stationary machinery. In such problems, it is often the case that performing several maintenance actions at the same time is beneficial, since many of these jobs can be done in parallel, which reduces the total downtime of the unit. The core of the problem is therefore how to (or how not to) group maintenance activities so that a composite cost due to spare parts, labor and loss of production due to downtime is minimized. We allow each machine to have individual schedules for each component in the system. For rail vehicles, we have evaluated the effect of replanning maintenance in the case where the component maintenance deadline is set to reflect a maximum risk of breakdown in a Gaussian failure distribution. In such a model, we show by simulation that replanning of maintenance can reduce the number of maintenance stops when the variance and expected value of the distribution are increased. For the gas turbine maintenance planning problem, we have evaluated the planning software on a real-world scenario from the oil and gas industry and compared it to the solutions obtained from a commercial integer programming solver. It is estimated that the availability increase from using our planning software is between 0.5 to 1.0 %, which is substantial considering that availability is currently already at 97-98 %.
|
|
| 5. |
- Hansen, Ewa, et al.
(författare)
-
Efficient Cluster Formation for Sensor Networks
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The interest in wireless sensor networks is growing and the development of energy efficient infrastructures for such networks is becoming increasingly important.In this paper we investigate the usefulness of enforcing a minimum separation distance between cluster heads in a cluster based sensor network, i.e. prolonging network lifetime by lowering the energy consumption.The simulations where performed in order to determine how much we can lower the energy consumption in the sensor network by separating the cluster heads. We have also investigated how the number of clusters affect the energy consumption for a given minimum separation distance.We show that our sensor network performs up to 150\% better when introducing a minimum separation distance between cluster heads, comparing the number of messages received at the base station.The simulations also show that the minimum separation distance that result in the lowest energy consumption in our network varies with the number of clusters.
|
|
| 6. |
- Hansson, Hans, et al.
(författare)
-
Real-Time in Networked Embedded Systems
- 2009
-
Ingår i: Networked Embedded Systems. - : CRC Press, Taylor & Francis Group.
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 7. |
- Hjertström, Andreas, 1972-
(författare)
-
Information Centric Development of Component-Based Embedded Real-Time Systems
- 2009
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis presents new techniques for data management of run-time data objectsin component-based embedded real-time systems. These techniques enabledata to be modeled, analyzed and structured to achieve data managementduring development, maintenance and execution.The evolution of real-time embedded systems has resulted in an increasedsystem complexity beyond what was thought possible just a few years ago.Over the years, new techniques and tools have been developed to manage softwareand communication complexity. However, as this thesis show, currenttechniques and tools for data management are not sufficient. Today, developmentof real-time embedded systems focuses on the function aspects of thesystem, in most cases disregarding data management.The lack of proper design-time data management often results in ineffectivedocumentation routines and poor overall system knowledge. Contemporarytechniques to manage run-time data do not satisfy demands on flexibility,maintainability and extensibility. Based on an industrial case-study that identifiesa number of problems within current data management techniques, bothduring design-time and run-time, it is clear that data management needs to beincorporated as an integral part of the development of the entire system architecture.As a remedy to the identified problems, we propose a design-time data entityapproach, where the importance of data in the system is elevated to beincluded in the entire design phase with proper documentation, properties, dependenciesand analysis methods to increase the overall system knowledge.Furthermore, to efficiently manage data during run-time, we introduce databaseproxies to enable the fusion between two existing techniques; ComponentBased Software Engineering (CBSE) and Real-Time Database ManagementSystems (RTDBMS). A database proxy allows components to be decoupledfrom the underlying data management strategy without violating the componentencapsulation and communication interface.
|
|
| 8. |
- Hänninen, Kaj, et al.
(författare)
-
Supporting Engineering Requirements in the Rubus Component Model
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we present a component model for development of distributed real-time systems.The model is developed to support development of embedded control systems for ground vehicles. The model aims at supporting three important activities in real-time development, (i) design, (ii) analysis and (iii) synthesis. These activities emphasise different and sometimes conflicting requirements that need to be balanced. For example, developers desire freedom in designing to solve complex tasks, analysis tools require the design to be formal enough for analysis and synthesis need to be efficient for low run-time footprint. We have considered industrial requirements for these activities and developed the RubusCMv3 component model. The model has been developed in close cooperation with industrial partners and it is currently being evaluated on real systems.
|
|
| 9. |
- Möller, Anders, et al.
(författare)
-
Industrial Requirements on Component Technologies for Vehicular Control Systems
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Software component technologies for automotive applications are desired due to the envisioned benefits in reuse, variant handling, and porting; thus, facilitating both efficient development and increased quality of software products. Component based software development has had success in the PC application domain, but requirements are different in the embedded domain and existing technologies does not match. Hence, software component technologies have not yet been generally accepted by embedded-systems industries.In order to better understand why this is the case, we present two separate case-studies together with an evaluation of the existing component technologies suitable for embedded control systems.The first case-study presents a set of requirements based on industrial needs, which are deemed decisive for introducing a component technology. Furthermore, in the second study, we asked the companies involved to grade these requirements.Then, we use these requirements to compare existing component technologies suitable for embedded systems. One of our conclusions is that none of the studied technologies is a perfect match for the industrial requirements. Furthermore, no single technology stands out as being a significantly better choice than the others; each technology has its own pros and cons.The results can be used to guide modifications and/or extensions to existing component technologies in order to make them better suited for industrial deployment in the automotive domain. The results can also serve to guide other software engineering research by showing the most desired areas within component-based software engineering.
|
|
| 10. |
- Neander, Jonas, et al.
(författare)
-
A TDMA scheduler for the AROS architecture
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we present a Time Division Multiple Access (TDMA) scheduler for the Asymmetric communication and ROuting in Sensor networks architecture (AROS). The scheduler enables dynamic network configurations of the AROS architecture. We show that asymmetric multihop communication with dynamic network configurations in AROS prolongs the lifetime of sensor nodes in long distance networks compared to the LEACH architecture.
|
|
