On the Development of Hierarchical Real-Time Systems

Sammanfattning: 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.