This paper presents an overview of a distributed embedded system design assistant called Systems Engineers Workbench (SEW 2.0). SEW 2.0 uses a suite of design frameworks, with supporting representations, to structure the inherent complexity. A set of design assist operatives further improves the ability of the designer to explore the domain space while evaluating performance/resource tradeoffs.

Next-generation networks are expected to support a wide variety of services. Some services such as video, voice, and plant control traffic have explicit timing requirements on a per-message basis rather than on the average. In this paper, we develop a general model of dual-link networks to support real-time communication. We examine the desirable properties of this network and the difficulties in achieving these properties. We then introduce the concept of coherence and develop a theory of coherent dual-link networks. We show that a coherent dual-link network can be analyzed as though it is a centralized system. We then discuss practical considerations in implementing a dual-link network, and implications of this work to address problems observed in the IEEE 802.6 metropolitan area network standard.

Real-time DSP operating systems have recently appeared in several commercial products that integrate multimedia processing into PCs. The DSP OSs, which run on DSP subsystems integrated on PC adapter cards, include admission control capabilities to ensure that timing guarantees are met and sufficient resources are available to handle the processing demands of a given mix of applications. Admission control is possible because the timing characteristics of the kernels are fully understood and real-time scheduling is used for all kernel resources. If a real-time approach is to be successful in host OSs, a similar approach must be followed. We compare the performance of the DSP OS and host OS approaches. We describe the DSP OS architectures and their admission control algorithms. We describe a general framework we have developed which models OSs for the purpose of admission control.

This paper presents an hierarchical end-to-end analysis technique that decomposes the very complex heterogeneous multi-resource scheduling problem into a set of single resource scheduling problems with well defined interactions. We define heterogeneity both in resource types, e.g., CPU, and in scheduling policies, e.g., rate-monotonic scheduling. This analysis technique is one phase of our systems integration framework for designing large-scale, heterogeneous, distributed real-time systems whose timing properties can be strictly controlled and analyzed. This approach, denoted the Distributed Pipelining Framework, exploits the natural pipelining execution pattern found in a large number of continuous (periodic) applications executing over heterogenous resources. A teleconference application is used in this paper to show the utility of the approach.

No abstract available.

This paper develops formal scheduling models for several common system bus architectures used in PC and workstation systems. The scheduling models include fixed priority, round robin, and hybrid bus scheduling policies. The models provide a quantitative means to explore the real-time design space for each of the buses. This paper provides a simple approach for the creation of bus scheduling models which can be used effectively by a bus designer or system user to improve real-time bus performance. The step by step process of model development is presented. In addition, an application modeling methodology is described which separates the application requirements from the bus model. The utility of the scheduling models is demonstrated by analyzing several common system buses.

Multimedia and advanced real-time systems integrate a variety of applications and media types in one environment, many of which have timing properties which are not supported by current window systems running in multitasking environments. This paper discusses several key aspects to designing window systems which support continuous media and other real-time applications. These design considerations were used to construct ARTIFACT, a window system designed to investigate issues in building real-time window systems. Several of the behaviors of a partial implementation of ARTIFACT are described, along with preliminary scheduling models and avenues for further research.

This paper describes the distributed pipeline scheduling framework that provides a systematic approach to designing distributed, heterogeneous real-time systems. This paper formalizes distributed pipelining scheduling by providing a set of abstractions and transformations to map real-time applications to system resources, to create highly efficient and predictable systems, and to decompose the very complex multi-resource system timing analysis problem into a set of simpler application stream and single-resource schedulability problems to ascertain that all real-time application timing requirements are met. Distributed pipeline scheduling includes support for distributed, heterogeneous system resources and diverse local scheduling policies, global scheduling policies for efficient resource utilization, flow-control mechanisms for predictable system behaviour, and a range of system reconfiguration options to meet application timing requirements. An audio/video example is used in this paper to demonstrate the power and utility of distributed pipeline scheduling.

This paper develops necessary and sufficient conditions for analyzing the schedulability of fixed priority algorithms on resources with limited priority levels. We introduce the degree of schedulable saturation (S/sub max/) as an objective function. A multimedia task set is used to demonstrate how S/sub max/ can be used to optimize the grouping of tasks to priority levels.>

Most existing scheduling algorithms for hard real-time systems apply either to periodic tasks or aperiodic tasks but not to both. In practice, real-time systems require an integrated, consistent approach to scheduling that is able to simultaneously meet the timing requirements of hard deadline periodic tasks, hard deadline aperiodic (alert-class) tasks, and soft deadline aperiodic tasks. This paper introduces the Deferrable Server (DS) algorithm which will be shown to provide improved aperiodic response time performance over traditional background and polling approaches. Taking advantage of the fact that, typically, there is no benefit in early completion of the periodic tasks, the Deferrable Server (DS) algorithm assigns higher priority to the aperiodic tasks up until the point where the periodic tasks would start to miss their deadlines. Guaranteed alert-class aperiodic service and greatly reduced response times for soft deadline aperiodic tasks are important features of the DS algorithm, and both are obtained with the hard deadlines of the periodic tasks still being guaranteed. The results of a simulation study performed to evaluate the response time performance of the new algorithm against traditional background and polling approaches are presented. In all cases, the response times of aperiodic tasks are significantly reduced (often by an order of magnitude) while still maintaining guaranteed periodic task deadlines.>

This paper develops a unified framework for reasoning about timing correctness of packet-switched networks. The unification is in the form of a set of consistent scheduling models for a variety of network architectures and protocols. The unification is important as it allows heterogeneous network types to be analyzed using a consistent methodology and facilitates scheduling over multihop networks where each link is a different type of network. To demonstrate the framework, a scheduling model for a dual-link network, IEEE 802.5 token ring, and FDDI, is presented. The use of this framework to select paths in multi-hop networks is also demonstrated.>

Real-time scheduling theory attempts to guarantee that a real-time task set will always meet its deadlines. Real-time systems are typically implemented via real-time operating systems (RTOSs). However, there currently exists a wide gap between real-time scheduling theory and the reality of RTOS implementation. Bridging the gap requires effort on two fronts. First, real-time scheduling theory must be extended such that implementation realities may be correctly incorporated. Second, the high level of sophistication required to apply real-time scheduling theory to RTOSs bars practitioners from creating scheduling (timing) models of their operating systems. This paper summarizes recent work on developing an engineering methodology that allows novice users and developers to accurately model and evaluate RTOSs. Specifically, we recount the experiences of a CMU undergraduate class's experience in modeling and analyzing three commercial Digital Signal Processor (DSP) operating systems.>

A fast packet-switched network is considered that transmits fixed-sized packets or cells and provides connection-oriented services. A number of rate-based service disciplines that offer timing guarantees have recently been proposed. These disciplines work well for connections which exhibit low burstiness or whose burstiness can be managed by admission control. However, some messages have irregular arrival patterns, but must be delivered with low delay. These aperiodic messages include connection set-up/tear-down messages, link-slate updates, and other status or alarm messages. The authors propose techniques that significantly minimize aperiodic message delay without jeopardizing guarantees made to existing connections. Simple hardware implementations of these techniques that can be embedded in output queues of fast packet-switches are also described.>

Real-time scheduling theory is designed to provide a priori verification that all real-time tasks meet their timing requirements. However, this body of theory generally assumes that resources are instantaneously pre-emptable and ignores the costs of systems services. In previous work [1, 2] we provided a theoretical foundation for including the costs of the operating system scheduler in the real-time scheduling framework. In this paper, we apply that theory to the Real-Time (RT) Mach scheduler. We describe a methodology for measuring the components of the RT Mach scheduler in user space. We analyze the predicted performance of different real-time task sets on the target system using the scheduling model and the measured characteristics. We then verify the model experimentally by measuring the performance of the real-time task sets, consisting of RT Mach threads, on the target system, The experimental measurements verify the analytical model to within a small percentage of error. Thus, using the model we have successfully predicted the performance of real-time task sets using system services, and developed consistent methodologies to accomplish that prediction.

An algorithm for optimally partitioning two-level memory systems for deterministic, real-time performance is presented. The algorithm finds the optimal solution in polynomial time, which supports on-line reconfiguration of memory resources in response to changing requirements.>

Scheduling theory holds great promise as a means to a priori validate timing correctness of real-time applications. However, there currently exists a wide gap between scheduling theory and its implementation in operating system kernels running on specific hardware platforms. The implementation of any particular scheduling algorithm introduces overhead and blocking components which must be accounted for in the timing correctness validation process. This paper presents a methodology for incorporating the costs of scheduler implementation within the context of fixed priority scheduling algorithms. Both event-driven and timer-driven scheduling implementations are analyzed. We show that for the timer-driven scheduling implementations the selection of the timer interrupt rate can dramatically affect the schedulability of a task set, and we present a method for determining the optimal timer rate. We analyzed both randomly generated and two well-defined task sets and found that their schedulability can be significantly degraded by the implementation costs. Task sets that have ideal breakdown utilization over 90% may not even be schedulable when the implementation costs are considered. This work provides a first step toward bridging the gap between real-time scheduling theory and implementation realities. This gap must be bridged for any meaningful validation of timing correctness properties of real-time applications.>

The authors develop a general model of reservation-based dual-link networks to support real-time communication. They examine the desirable properties of this network and the difficulties in achieving these properties. They then introduce the concept of coherence and develop a theory of coherent dual-link networks. It is shown that a coherent dual-link network can be analyzed as though it is a centralized system. It is also shown that a coherent dual-link network can be analyzed similarly to an equivalent centralized system in terms of its schedulability for periodic message traffic.>

A scheduling approach is given for servicing the nondeterministic workload demands of time-critical recovery operations triggered by the detection of errors in periodic real-time workloads. This approach, referred to as the transient server, has been developed within the context of fixed-priority preemptive systems. For these systems, it is proved that deadline monotonic scheduling is optimal in maximizing the service opportunities for recovery requests. A scheduling-theoretic framework for integrating time-invariant deadline- and criticalness-based priorities is developed, motivated by the need to guarantee that the real-time workload experiences a graceful degradation during recovery.>

SMART, a technique for providing predictable cache performance for real-time systems with priority-based preemptive scheduling, is presented. The technique is implemented in a R3000 cache design. The value density acceleration (VDA) cache allocation algorithm is also introduced, and shown to be suitable for run-time cache allocation.>

The results of implementation studies utilizing commercially available IEEE 802.5 chip sets and boards are reported. Serious implementation flaws were discovered that prevent the full potential of the IEEE 802.5 token ring standard from being realized for real-time applications. Specifically, unbounded delays can be introduced which not only destroy the desired response time determinism offered by algorithmic scheduling, but which also negate asynchronous alert class guarantees and unnecessarily increase other asynchronous response times. An analysis is made of the scheduling properties of current implementations, and modifications to the current implementations are proposed to allow them to realize the full potential offered by the IEEE 802.5 standard for real-time applications.>

An approach for scheduling the IEEE 802.5 token ring for hard real-time applications is presented that not only guarantees deadlines for synchronous class messages, but also greatly reduces asynchronous class response times. Highly responsive guaranteed service is introduced for alert class asynchronous messages. Conventional use of the IEEE 802.5 token ring provides synchronous communication services using time-domain multiplexing (TDM) while relegating asynchronous class message services to background status. An algorithmic-based scheduling approach is presented that supports a priori schedulability determination for arbitrary synchronous message sets without the costly time-line development, testing, and tuning associated with TDM techniques. This capability allows the IEEE 802.5 to support dynamic, adaptive and reconfigurable run-time environments where the inflexibility of TDM would be prohibitive. Advanced real-time scheduling applied to the IEEE 802.5 token ring greatly enhances the responsiveness of asynchronous class messages while still maintaining guaranteed service for the synchronous class.>