This paper develops an offset-based response-time analysis technique for analyzing complex distributed real-time systems where processing and communication resources use the time-partitioning strategy to isolate the operation of separate software components. Time partitioning may be provided in the processors by an ARINC 653 compliant operating system, and in the networks via the TTP communication protocol. The software components executed by the system may themselves be distributed and complex, composed of many concurrent tasks and with one or more end-to-end flows that may have end-to-end timing requirements. The developed analysis supports hierarchical scheduling where a primary scheduler performs time partitioning into separate partitions, and secondary fixed-priority schedulers dispatch the different concurrent tasks inside each partition. It also supports end-to-end flows that are either synchronized with the partition schedule or not. This is the first time that this kind of analysis is developed. An evaluation of an improvement introduced in the analysis is discussed. Two representative case studies are described.

Real-time distributed systems contain end-to-end flows, which are distributed actions composed of sequences of tasks activated through messages. Such flows usually have an end-to-end deadline but the internal tasks and messages do not have specific timing requirements. However, if EDF schedulers are used, it is necessary to assign scheduling deadlines to tasks and messages, which is usually done by distributing the end-to-end deadline among them. Distributed systems may have synchronized global clocks or non-synchronized local clocks. This work studies the influence of the clocks, global or local, on the deadline-assignment algorithms. A study on the poor performance observed for EDF schedulers with local clocks is presented. Then, a significant optimization of the assignment algorithms is shown, in which an amount of end-to-end deadline larger than the established timing requirement is distributed among tasks and messages. With this technique, two new algorithms for deadline-assignment are proposed, showing that they outperform the existing ones by up to 23 percent of processor utilization in the case of local clocks. Finally, the influence of release jitter in this kind of EDF systems and the positive effects of eliminating it are also studied.

The CAN bus is one of the most used networks in distributed real-time systems. The CAN bus can be divided by means of bridges in order to distribute the network load among different segments and contribute positively to the schedulability of the system. On the other hand, CAN supports the fragmentation of a message in multiple packets when it does not fit into one single CAN frame. The schedulability analysis of CAN has been extensively studied in the literature. Although the proposed methods analyze non-segmented CAN buses, they can be applied to segmented networks. However, the techniques from the related literature obtain quite pessimistic results in the analysis of segmented CAN networks with multi-packet messages. This paper proposes a less pessimistic CAN schedulability analysis method for the mentioned kind of networks. Moreover, this optimized technique can be integrated with methods oriented to the holistic schedulability analysis of a complete distributed real-time system.

The increasing acceptance of the Earliest Deadline First (EDF) scheduling algorithm in industrial environments, together with the continued usage of Fixed Priority (FP) scheduling is leading to heterogeneous systems with different scheduling policies in the same distributed system. Schedulability analysis techniques usually consider the entire system as a whole (holistic approach), with only one preestablished scheduling policy in all the resources. In this work, composition mechanisms will be presented that enable us to combine different FP and EDF response-time analysis techniques for checking the schedulability of heterogeneous systems. Additionally, priority and scheduling deadline assignment techniques will be combined into a new algorithm called HOSPA (Heuristic Optimized Scheduling Parameters Assignment), for optimizing the assignment of priorities and scheduling deadlines to tasks and messages in heterogeneous distributed hard real-time systems.

The present paper is focused on hierarchical modeling in monoprocessor real-time systems. In the current scheduling, each system application is isolated through periodic servers. While previous research oriented both local and global schedulers to fixed priorities, this study extends the scheduling to dynamic priorities (EDF). The new analysis consists in obtaining the response time for the worst case scenario for each task involved in the system applications

Offset-based response time analysis of tasks scheduled with fixed priorities has demonstrated to be a powerful tool to analyze many task models with different kinds of timing constraints, like regular periodic tasks, suspending tasks, distributed systems, tasks with varying priorities, multi frame models, etc. Offset-based analysis techniques are capable of performing a global schedulability analysis in distributed systems, as opposed to the less efficient techniques that consider each processing or communication resource as independent. In this paper we extend the offset-based schedulability analysis techniques to system with EDF (earliest deadline first) scheduling, using analytical techniques that are similar to those developed for fixed priority scheduling. With this new analysis, we now have a complete set of techniques to perform the analysis of different task models in distributed heterogeneous systems, i.e., processors and communication networks having either fixed priority or EDF schedulers.

Hierarchical schedulers are getting increased attention in many research projects because they bring in flexibility, they can take advantage of the best features of different scheduling policies, and allow the composability of applications developed under different scheduling strategies. Most commercial real-time operating systems have an underlying fixed priority schedule, and for this reason it is necessary to be able to analyze hierarchically-scheduled applications in which the underlying scheduler is of that kind. In this paper we extend the classic response time analysis techniques to analyze applications which can have a mixture of tasks scheduled either with fixed priorities, or with an earliest deadline first (EDF) scheduler running on top of an underlying fixed priority scheduler. We show that the complexity of this analysis is similar to that of existing response time analysis for EDF tasks.

This paper describes a model for representing the temporal and logical elements of real-time applications, called MAST. This model allows a very rich description of the system, including the effects of event or message-based synchronization, multiprocessor and distributed architectures as well as shared resource synchronization. The model is directly obtainable from a description of the system design using a UML tool. A system representation using this model is analyzable through a set of tools that has been developed within the MAST suite, including worst-case schedulability analysis for hard timing requirements, and discrete-event simulation for soft timing requirements. Although the current model only includes fixed priority systems, it is conceived as an open model and is easily extensible to accommodate other kinds of systems.

Presents a schedulability analysis technique for distributed hard real-time systems in which responses to different events may synchronize with each other. This technique uses a representation model for distributed systems that allows us to describe not only the task synchronization due to resource sharing, but also the activation due to combinations of events or the generation of several events by a single task. The model is representative of a large number of systems and is suitable for the treatment of message-passing systems or the client-server architecture. The analysis technique is based on the existing rate monotonic analysis (RMA) techniques for analyzing distributed real-time systems; it allows obtaining upper bounds for the worst-case response times of the system, thus allowing us to make guarantees about the fulfillment of the timing requirements that have been imposed.

In this paper we present improved techniques for the schedulability analysis of tasks with precedence relations in multiprocessor and distributed systems scheduled under a pre-emptive fixed priority scheduler. Recently developed techniques, based on the analysis of tasks with dynamic offsets, take into account the precedence relations between tasks only indirectly, through terms iteratively estimated from the response times of the tasks. With the techniques presented in this paper, we exploit the precedence relations in a more accurate way, and we also take advantage of the priority structure of the different tasks. These considerations permit a significant improvement of the results of the analysis applied to distributed and multiprocessor systems.

We present an improvement of the schedulability analysis technique for distributed hard real time systems that allows us to increase the maximum schedulable resource utilization. Since the improvement affects only the analysis technique, there is no additional implementation cost for the application itself. The improvement in the analysis consists of calculating a lower bound for the best case response time of tasks and messages, in order to reduce the estimated jitter in the activation of subsequent tasks and messages. This reduction of jitter implies reduced worst case bounds for the response times, and thus allows us to increase the maximum schedulable utilization. The paper explores two different ways to calculate a lower bound on the best case execution times. The paper also shows the results of simulations that we have carried out, in which we found that we could increase the maximum schedulable limit of the different resources by approximately 5% more utilization.

In this paper we present an extension to current schedulability analysis techniques for periodic task with offsets, scheduled under a preemptive fixed priority scheduler. Previous techniques allowed only static offsets restricted to being smaller than the task periods. With the extension presented in this paper, we eliminate this restriction and we allow both static and dynamic offsets. The most significant application of this extension is in the analysis of multiprocessor and distributed systems. We show that we can achieve a significant increase of the maximum schedulable utilization by using the new technique, as opposed to using previously known worst-case analysis techniques for distributed systems.