There is a growing interest in using the object paradigm for developing real time software. We believe that an approach that integrates the advancements in both object modeling and design methods, and real time scheduling theory is the key to successful use of object technology for real time software. Surprisingly many past approaches to integrate the two either restrict the object models, or do not allow sophisticated schedulability analysis techniques. The authors show how schedulability analysis can be integrated with object oriented design. More specifically, they show how fixed priority scheduling theory can be applied to designs developed using UML-RT, a specialization of UML for real time software. In conjunction with automatic code generation, we believe that this will greatly streamline the design and development of real time software.

Presents an approach towards the automatic synthesis of implementations from real-time object-oriented design models. From an application design model that addresses the functional requirements of the system, and given end-to-end timing requirements, our synthesis approach generates a feasible implementation model, i.e. one that will meet the timing requirements. The synthesis process is supported by automatic code generation that can take the application design model and the synthesized implementation model, and can generate code for the target platform. The synthesis of an implementation model is facilitated through the use of a generic (application-independent) implementation architecture, thereby reducing the synthesis problem to selecting a mapping of the application design model to the artifacts of the implementation architecture. In this paper, we use a multi-threaded event handling architecture with fixed event priorities. The synthesis problem then consists of determining priorities for events and mapping events to threads. We show how, given such a mapping, the response times can be analyzed, and then how, using the analysis, a feasible implementation model can be automatically synthesized.

The maturity of schedulability analysis techniques for fixed-priority preemptive scheduling has enabled the consideration of timing issues at design time using a specification of the tasking architecture and estimates of execution times for tasks. While successful, this approach has limitations since the preemptive multi-tasking model does not scale well for a large number of tasks, and the fixed-priority scheduling theory does not work well with many object-oriented design methods. In this paper, we present an approach that scales well even when the design consists of a large number of concurrent jobs. The approach avoids any unnecessary preemptability in the system, thereby resulting in reduced run-time overheads from preemptions and associated context switches. It also allows significant memory savings by grouping jobs into non-preemptive groups and then sharing the stack space between them. Our approach is based on our earlier work on scheduling using preemption thresholds that allows parametric control over preemptability in a priority-based system. We show that our approach provides significant advantages over one using a fixed-priority preemptive scheduling architecture. The benefits include higher schedulability for small numbers of tasks and lower run-time overheads, and hence better scalability. We develop algorithms that allow design-time consideration of schedulability and automatic synthesis of an implementation model to minimize run-time overheads.

This paper presents a design synthesis method for distributed embedded systems. In such systems, computations can flow through long pipelines of interacting software components, hosted on a variety of resources, each of which is managed by a local scheduler. Our method automatically calibrates the local resource schedulers to achieve the system's global end-to-end performance requirements. A system is modeled as a set of distributed task chains (or pipelines), where each task represents an activity requiring nonzero load from some CPU or network resource. Task load requirements can vary stochastically due to second-order effects like cache memory behavior, DMA interference, pipeline stalls, bus arbitration delays, transient head-of-line blocking, etc. We aggregate these effects-along with a task's per-service load demand and model them via a single random variable, ranging over an arbitrary discrete probability distribution. Load models can be obtained via profiling tasks in isolation or simply by using an engineer's hypothesis about the system's projected behavior. The end-to-end performance requirements are posited in terms of throughput and delay constraints. Specifically, a pipeline's delay constraint is an upper bound on the total latency a computatation can accumulate, from input to output. The corresponding throughput constraint mandates the pipeline's minimum acceptable output rate-counting only outputs which meet their delay constraints. Since per-component loads can be generally distributed; and since resources host stages from multiple pipelines, meeting all of the system's end-to-end constraints is a nontrivial problem. Our approach involves solving two subproblems in tandem: 1) finding an optimal proportion of load to allocate to each task and channel and 2) deriving the best combination of service intervals over which all load proportions can be guaranteed. The design algorithms use analytic approximations to quickly estimate output rates and propagation delays for candidate solutions. When all parameters are synthesized, the estimated end-to-end performance metrics are rechecked by simulation. The per-component load reservations can then be increased, with the synthesis algorithms rerun to improve performance. At that point, the system can be configured according to the synthesized scheduling parameters-and then revalidated via on-line profiling. In this paper, we demonstrate our technique on an example system, and compare the estimated performance to its simulated on-line behavior.

The increasing complexity of real time software has led to a recent trend in the use of high level modeling languages for development of real time software. One representative example is the modeling language ROOM (real time object oriented modeling), which provides features such as object orientation, state machine description of behaviors, formal semantics for executability of models, and possibility of automated code generation. However these modeling languages largely ignore the timeliness aspect of real time systems, and fail to provide any guidance for a designer to a priori predict and analyze temporal behavior. We consider schedulability analysis for automated implementations of ROOM models, based on the ObjecTime toolset. This work builds on results presented by M. Saksena (1997), where we developed some guidelines for the design and implementation of real time object oriented models. Using the guidelines, we have modified the run time system library provided by the ObjecTime toolset to make it amenable to schedulability analysis. Based on the modified toolset, we show how a ROOM model can be analyzed for schedulability, taking into account the implementation overheads and structure. The analysis is validated experimentally, first using simple periodic models, and then using a large case study of a train tilting system.

We present our experiences in applying real time scheduling theory to embedded control systems designed using ROOM (Real time Object Oriented Modeling) methodology. ROOM has originated from the telecommunications community and has been successfully applied to many commercial systems through the supporting case tool ObjecTime. It is particularly suitable for modeling reactive real time behavior. Furthermore, it provides many other advantages through the use of object orientation, and the use of executable models from which code may be generated quickly and efficiently. Since many real time embedded control systems have significant reactive, event driven behavior, it is attractive to use ROOM methodology to develop such systems. However, the ROOM methodology does not provide tools to specify and analyze the temporal behavior as is required for the hard real time components of embedded systems, and for which the real time scheduling theory provides an analytical basis. We show how real time scheduling theory may be applied to ROOM models using a cruise control example to illustrate. The biggest challenge comes from minimizing the adverse effects of priority inversions. Our results are very encouraging, and we show that not only is it possible to apply real time scheduling theory, but that it can be done very efficiently provided certain guidelines are followed in the design and implementation of the ROOM model.

We present a resource conscious approach to designing distributed real-time systems. This work extends our original solution (Gerber et al., 1995), which was limited to single processor systems. Starting from a given task graph, and a set of end-to-end constraints, we systematically generate task attributes (e.g., periods and deadlines) such that: the task set is schedulable; and the end-to-end constraints are satisfied. The methodology can be mostly automated, and provides useful feedback to a designer when it fails to find a solution. We expect that the techniques presented in this paper will help reduce the laborious process of designing a real-time system, by bringing resource contention and schedulability aspects early into the design process.

We describe our experiments on a real-time system design, focusing on design alternatives such as scheduling jitter, sensor-to-output latency, intertask communication schemes and the system utilization. The prime objective of these experiments was to evaluate a real-time design produced using the period calibration method (Gerber et al., 1995) and thus identify the limitations of the method. We chose a computerized numerical control (CNC) machine as our target real-time system and built a realistic controller and a plant simulator. Our results were extracted from a controlled series of more than a hundred test controllers obtained by varying four test variables. This study unveils many interesting facts: average sensor-to-output latency is one of the most dominating factors in determining control quality; the effect of scheduling jitter appears only when the average sensor-to-output latency is sufficiently small; and loop processing periods are another dominating factor of performance. Based on these results, we propose a new communication scheme and a new objective function for the period calibration method.

In many real-time systems relative timing constraints are imposed on a set of tasks. Generating a correct ordering for the tasks and deriving their proper start-time assignments is an NP-hard problem; it subsumes the non-preemptive scheduling problem. Even when the application imposes a total order on the tasks, generating proper start-times is still nontrivial if execution times may range between upper and lower bounds. We present the technique of parametric dispatching to enforce such timing constraints. During an off-line component, we check if the constraints can be guaranteed. If so, a calendar is produced that allows our on-line algorithm to generate upper and lower bounds on the start time of each task, based on the start times and execution times of previous tasks. A suitable start time for the task may then be selected taking into account the presence of other non-critical tasks in the system.>

The paper presents a comprehensive design methodology for guaranteeing end to end requirements of real time systems. Applications are structured as a set of process components connected by asynchronous channels, in which the end points are the system's external inputs and outputs. Timing constraints are then postulated between these inputs and outputs; they express properties such as end to end propagation delay, temporal input sampling correlation, and allowable separation times between updated output values. The automated design method works as follows: First new tasks are created to correlate related inputs, and an optimization algorithm, whose objective is to minimize CPU utilization, transforms the end to end requirements into a set of intermediate rate constraints on the tasks. If the algorithm fails, a restructuring tool attempts to eliminate bottlenecks by transforming the application, which is then resubmitted into the assignment algorithm. The final result is a schedulable set of fully periodic tasks, which collaboratively maintain the end to end constraints.>

This paper addresses the problem of guaranteed delivery of messages with hard deadlines in a DQDB network. The authors present a cyclic reservation scheme capable of allocating bandwidth with any arbitrary granularity and provide deterministic delay guarantees. They propose two implementations of the allocation scheme within the framework of DQDB medium access control protocol. The proposed implementations are very simple, incur minimal overhead and require only minor changes in the adopted standard.>

This paper presents a comprehensive design methodology for guaranteeing end-to-end requirements of real-time systems.Applications are structured as a set of process components connected by asynchronous channels, in which the endpoints are the system's external inputs and outputs.Timing constraints are then postulated between these inputs and outputs; they express properties such as end-to-end propagation delay, temporal input-sampling correlation, and allowable separation times between updated output values.The automated design method works as follows: First the end-to-end requirements are transformed into a set of intermediate rate constraints on the tasks, and new tasks are created to correlate related inputs.The intermediate constraints are then solved by an optimization algorithm, whose objective is to minimize CPU utilization.If the algorithm fails, a restructuring tool attempts to eliminate bottlenecks by transforming the application, which is then re-submitted into the assignment algorithm.The nal result is a schedulable set of fully periodic tasks, which collaboratively maintain the end-to-end constraints.

We study the problem of transmitting time constrained synchronous messages in a slotted ring based local area network, carrying synchronous and asynchronous traffic. A bandwidth allocation scheme for synchronous messages is developed on top of a media access control protocol that assigns preemptive priority to synchronous traffic over asynchronous traffic. We derive sufficient conditions for schedulability of time critical synchronous messages and show that the scheme achieves high levels of schedulable utilization. A slot access protocol is proposed for synchronous streams that implements the allocation scheme with minimal additional overhead and loss of schedulable utilization. The protocol is distributed in the sense that any node can locally determine if it can use a slot, without exchanging any explicit messages with other nodes.>