Search

Dynamic resource management is an effective way to ensure that real-time systems work correctly in unpredictable environments. For mission-critical systems, dynamic resource managers (RMs) must be verified. Every RM depends on instruments to report the state of the system and its resources, so verified instrumentation is foundational to the larger goal of verified RMs. In this paper we address the verification of instrumentation. We identify the following instruments as necessary for any RM: event times; task execution time; task deadline overrun; resource accessibility; and overall CPU utilization. To assure the core instrumentation functionality, we argue that it is required to establish bounds for the following properties: precision, uncertainty, resource usage, timeliness and intrusiveness. As a case study, we illustrate the detailed verification techniques and experimental results for the event-time instrumentation.

The dynamic distributed real-time applications run on clusters with varying execution time, so re-allocation of resources is critical to meet the applications's deadline. In this paper we present two adaptive recourse management techniques for dynamic real-time applications by employing the prediction of responses of real-time tasks that operate in time sharing environment and run-time analysis of scheduling policies. Prediction of response time for resource reallocation is accomplished by historical profiling of applications' resource usage to estimate resource requirements on the target machine and a probabilistic approach is applied for calculating the queuing delay that a process will experience on distributed hosts. Results show that as compared to statistical and worst-case approaches, our technique uses system resource more efficiently.

For computer vision systems to operate in many real-world environments, processing must occur in real-time under dynamic conditions. An agent-based methodology offers an approach to increase flexibility and scalability to accommodate the demands of a real-time, dynamic environment. This paper presents an agent-based architecture that uses a utility optimization technique to guarantee that important vision tasks are fulfilled even under resource constraints. To ensure that the processing of vision tasks is both reliable and flexible, multiple behaviors are utilized to accomplish the vision application's requirements. A vision behavior consists of a grouping of vision algorithms and a set of service levels associated with these algorithms. Utility functions are adopted to evaluate the performance of all possible behaviors that can address the requirements of a vision application within resource constraints. The maximum overall utility corresponds to the optimal behavior. Two example systems using this model are presented to show the applicability of the architecture. Experimental results show that this agent-based architecture outperforms traditional non-agent-based approaches.

Some classes of realhtime systems function in environments, which cannot be modeled with static approaches. In such environments, the arrival rates of events which drive transient computations may be unknown. Also, periodic computations may be required to process varying numbers of data elements per period, but the number of data elements to be processed in an arbitrary period cannot be known at the time of system engineering, nor can an upper bound be determined for the number of data items; thus, a worst case execution time cannot be obtained for such periodics. This paper presents middleware services that support such dynamic realhtime systems through load balancing. The middleware services have been implemented and employed for (1) the DynBench dynamic realhtime benchmark suite and (2) an experimental Navy system. Experimental results show the effectiveness of our load balancing techniques for consistently delivering realhtime qualityhofhservice, even in highly dynamic environments.

The DeSiDeRaTa project is producing technology to enable the engineering of the emerging generation of distributed real-time systems. Such systems have rigorous Quality of Service (QoS) objectives. They must behave in a dependable manner, respond to threats in a timely fashion and provide continuous availability, even within hostile and unknown environments. To provide the desired QoS in such a context, the DeSiDeRaTa project focuses on QoS specification, dynamic QoS management middleware, and benchmarking of dynamic real-time systems. This paper discusses each of these aspects, and presents experimental results of applying DeSiDeRaTa technology to a dynamic realtime benchmark system.

This paper presents a metrics-driven process and software toolset for the engineering of concurrent, object-oriented, real-time systems. In the engineering of real-time systems, the objective need not be to exploit all potential concurrency, but to exploit only as much concurrency as is needed to enable satisfaction of timing constraints. Thus, the systems engineering process presented in the paper utilizes inter-object concurrency selectively, as a means to meet timelines. To support the selective use of concurrency, this paper describes techniques for computing inter-object concurrency metrics. It is also shown how the concurrency metrics are used to guide the mapping of objects onto processors.

This paper gives a taxonomy for the evaluation of object-oriented design methods and implementation languages for the construction of distributed real-time systems. This taxonomy is aimed at answering the following main questions: (1) how well do current approaches support the design of non-functional system features like concurrency and the specification of allocation, timing and fault tolerance constraints and (2) how can we discern essential properties of such methods and languages in order to point out the strengths and weaknesses of contemporary approaches.

This paper describes a general model for pre-run-time scheduling of distributed real-time systems that are composed of abstract data types (definable in languages such as Ada, Clu and Modula-2) and abstract data objects (which can be defined in C++, Eiffel and RT Euclid). An architecture model, a programming paradigm, and execution and communication paradigms form the basis for this general model. The model includesabsolute timing constraints to represent periodicity and deadlines,relative timing constraints to model several kinds of timed precedence relations and synchronization requirements,independency constraints to capture non-determinism of conditionals and repetitions, andconsistency constraints to enforce consistent use of resources. In this paper, the model is formalized to obtain a mathematical foundation on which assignment (Verhoosel et al. 1993a, Welch 1992, Welch et al. 1993) and pre-run-time scheduling problems (Verhoosel et al. 1991, Verhoosel 1992, 1993a, 1993c) are defined. Additionally, the model is extended to allow exploitation of parallelism from programs, a technique that can be used during assignment and scheduling for meeting timing constraints.

This paper describes a test-bed for technology that unifies agent based computing and adaptive resource management for dynamic real-time systems. We describe a unified framework that combines a hybrid agent based architecture with explicit resource adapting mechanisms.

This paper presents a characterization of various current approaches to quality of service (QoS) management in distributed, real-time systems. The characterization is based on an eight-point comparison of selected research: middleware interface, handling of violations, support of distributed applications, monitored data, requirements specification, characteristics of the supported real-time systems, overall system architecture, and quality of service dimensions supported. The comparisons are summarized in a tabular form with key references for further reading.

Real-time computing models that are based on benefit (also called utility and value) offer a generic paradigm that captures the spectrum from hard- to firm- to soft-realtime requirements. Furthermore, it allows robust, flexible real-time systems to be developed. Thus, it is the authors’ opinion that benefit will become increasingly important in the theory and the practice of real-time computing. This paper discusses the notion of benefit in real-time systems and considers issues that must be addressed in order to fully exploit benefit-based models. It discusses how benefit is used in a variety of real-time paradigms and in example applications. It also identifies various types of benefit and presents a taxonomy that organizes the types.

Dynamic real-time systems require adaptive resource management to accommodate varying processing needs. This paper addresses the problem of resource management on a single resource for soft real-time systems (no hard deadline requirements) consisting of tasks that have discrete quality of service (QoS) settings that correspond to varying resource requirements and varying utility. Our approach employs a feedback architecture wherein task QoS settings are adjusted on-line in order to maintain a desired amount of resource slack. These adjustments are calculated based on incremental changes in resource slack using computationally efficient algorithms that provide nearly optimal utility with computable performance bounds. The feedback architecture provides robustness in the presence of additional resource load and imperfect task resource requirement specifications.

Some distributed real-time systems interact with external environments that change dynamically, and it is necessary to take the external variables into account when performing task allocation. We developed an approximation algorithm for task allocation, and it finds allocations that are maximally robust against dynamic changes in multiple external variables. Such an algorithm will help to reduce expensive reallocations triggered by changes in unpredictable environments. The algorithm has a polynomial running time, and its robustness optimality is given by an approximation ratio, which equals 2.41 asymptotically, when workloads are large and workload independent utilization of tasks is insignificant

The growth of load balancing system raises the issue of scalability, and decentralized load balancing architecture has been proposed to address this issue. In this paper, we investigate how a load balancing architecture can be built on decentralized policies based on CORBA and enhanced by predictive algorithm. The L/sub 2/E predictive filtering model was used to supply workstations with robust cluster load information, which allows them to make more accurate independent allocation decisions. Experimental results showed that our decentralized load balancing approach was able to suppress thrashing and oscillations compared to other load monitoring and prediction techniques, and it was able to achieve a highly balanced system than Sun Grid Engine.

This paper extends the previous work on the maximal allowable workload (MAW) problem [D. Juedes et al., (2004)] by investigating a resource allocation problem for distributed real-time systems that contain replicable applications. The systems may use multiple resources of a single type and be affected by multiple environmental factors. The approach searches for a feasible allocation that maximizes a user defined metric of stability. Several algorithms were developed and experiments were conducted to demonstrate the relative strength of these algorithms. The results showed that simulated annealing provides results that are the closest to the optimal for maximizing environmental parameter settings. In addition modified greedy first fit is shown to be the best performing algorithm for finding feasible allocations.

Summary form only given. We propose architecture and a general optimization framework for dynamic, distributed real-time systems. Interesting features of this model include the consideration of adaptive applications and utility functions. We extend by formalizing the corresponding multicriterial optimization problem. As the most difficult part of this problem, we identified the evaluation and comparison of the quality of single allocations and sets of allocations, respectively. To this end, we propose and examine metrics for measuring the goodness of solutions within our general resource management framework. These metrics lay the basis for further work on developing both online and offline algorithms to tackle the general optimization problem and provide an efficient adaptive resource manager for dynamic, distributed real-time systems.

Summary form only given. We examine several heuristic algorithms for the maximum allowable workload (MAW) problem for real-time systems with tasks having variable workloads. Briefly, the problem concerns the allocation of tasks to m processors, where each task t is characterized by a function t.r(w) that gives the running time of the task in terms of its workload (or input size) w. The objective of the maximum allowable workload problem is to find an allocation of tasks to processors so that the allocation is feasible (no task misses its deadline) when each task is given a workload of w or smaller and w is maximized. This optimization problem uses a robustness measure that is closely related to the MAIL (maximum allowable increase in load) metric recently proposed by Gertphol et al. The main contribution of this paper is the comparison of several heuristic algorithms for the MAW-RMS problem. Hillclimbing, random search, simulated annealing, and first-fit heuristics are presented and evaluated via simulation. As we show here, the first-fit greedy heuristic produces solutions of a reasonable quality compared to the other algorithms. In addition, we demonstrate the applicability of our model in air defense systems.

The paper presents a model that is useful for developing resource allocation algorithms for distributed real-time systems that operate in dynamic environments. Interesting aspects of the model include dynamic environments, utility and service levels, which provide a means for graceful degradation in resource-constrained situations and support optimization of the allocation of resources. The paper also provides an allocation algorithm that illustrates how to use the model for producing feasible, optimal resource allocations.

Some classes of real-time systems function in environments which cannot be modeled with static approaches. In such environments, the arrival rates of events which drive transient computations may be unknown. Also, the periodic computations may be required to process varying numbers of data elements per period, but the number of data elements to be processed in an arbitrary period cannot be known at the time of system engineering, nor can an upper bound be determined for the number of data items; thus, a worst case execution time cannot be obtained for such periodics. This paper presents middleware services that support such dynamic real-time systems through adaptive resource management. The middleware services have been implemented and employed for components of the experimental Navy system described by L.R. Welch et al. (1996). Experimental characterizations show that the services provide timely responses, that they have a low degree of intrusiveness on hardware resources, and that they are scalable.

The paper presents DynBench, a benchmark suite that is representative of the emerging generation of dynamic real time distributed systems. The characteristics and architecture of the benchmark application suite are described. Additionally, the paper discusses the DynBench environment, which includes: (1) a technique for specification of "repeatable" dynamic execution scenarios; (2) mechanisms for control (start, stop, replicate and move) of the benchmark applications; (3) interfaces for collection of QoS metrics from the benchmark applications; and (4) an infrastructure for collection of metrics for assessment of adaptive resource management algorithms. The effectiveness of the benchmark for discriminating between good and bad QoS and resource management algorithms is shown via extensive experimentation.

A language supporting the construction of real-time software systems for reusable components is described in this paper. An architecture suited to the efficient execution of such software is also described. Additionally, the author provides a framework for analyzing real-time systems developed and executed in this context. Specifically, the assignment of modules to the processors of a parallel machine is considered and the analysis of programs to determine if deadlines are met is discussed. >

Time constrained systems which operate in dynamic environments may have unknown worst case scenarios, may have large variances in the sizes of the data and event sets that they process (and thus, have large variances in execution latencies and resource requirements), and may not be statically characterizable, even by time invariant statistical distributions. The paper presents a specification language for describing environment dependent features. Also presented is an abstract model that is constructed (statically) from the specifications, and is augmented (dynamically,) with the state of environment dependent features. The model is used to define techniques for QoS (quality of service) monitoring, QoS diagnosis, and resource allocation analysis. Experimental results show the effectiveness of the approach for specification of real time QoS, detection and diagnosis of QoS failures, and restoration of acceptable QoS via reallocation of distributed computer and network resources.

This paper describes an on-going effort in constructing a platform for developing distributed, embedded, real-time control systems which have high dependability and scalability requirements. Complex, embedded real-time control systems typically have a very large grain task model upon which hard and soft timing constraints are simultaneously imposed. Often, such systems are required to function in extremely hostile and unpredictable environments. This demands large dependability and availability in a continuous manner We describe a new paradigm to build such systems which is based on the notion of paths-the granularity at which the notion of time is expressed in software. Further the paper describes distributed middleware services that are being developed to provide dependable, adaptive dynamic resource management. To illustrate the approach, an automobile air bag control system is used as an application example. Path descriptions can be applied in system design or system maintenance and during run time optimization. Within this framework, model based evaluation is often required. Therefore, in the second part of the paper a modeling approach for paths based on Stochastic Petri Nets is described, and results of a performance evaluation are presented.

Dynamic real-time systems face many resource management problems. This paper addresses the following problems: (1) dynamic resource allocation to provide QoS objectives, (2) heterogeneous resources, and (3) non-intrusive accurate monitoring of QoS, resource availability and resource needs. This paper describes the techniques of a resource manager handling the above problems to support the QoS of dynamic distributed real-time systems. The contributions of this paper to solve these problems are as follows: unification of dynamic resource requirements among heterogeneous hosts, control of resources in heterogeneous environments, feasibility analysis and dynamic load balancing/sharing. Our heuristic allocation scheme not only allows higher workloads than the random, round-robin and least-load schemes by 257%, 142% and 36.4%, respectively, but it also improves the QoS compared to those schemes by 38.6%, 28.5% and 31.6%, respectively.

Schedulability Analysis (SA) approaches that are based on a priori information and use fixed execution times with constant workloads work well in many application domains and allow pre-deployment guarantees of real-time performance such as Rate Monotonic Analysis (RMA [2]). However, certain realtime applications must operate in highly dynamic environments, thereby precluding accurate characterization of workloads by static models. This leads to the notion that a new SA trigger for dynamic environments, in which applications experience large variations in the workload, needs to guarantee real-time performance during run-time. This paper examines the case of periodic, dynamic real-time systems, and describes an efficient SA policing technique which can trigger SA appropriately, and uses a dynamic threshold which becomes sensitive when the quality of service (QoS) of the dynamic real-time application approaches its deadline.

Researchers are currently investigating applying benefit, or utility functions for allocating resources in limited, soft real time systems [1,2,3]. While the future of real-time computing research and practice will likely exploit the utility of benefit-based models, this will not occur until a suitable system level benefit framework has been defined. This paper provides an overview of ongoing work to develop such an initial framework that can formalize the use of benefit functions in complex real time systems. It is easily shown that this framework can support traditional hard/firm/soft real-time paradigms as well as support newer proposed models for future real time operation [5,6]. We also show that our proposed framework unifies composition of benefit values derived from heterogeneous perspectives, including those derived from the application perspective.

The main contribution of this paper is accurate analysis of real-time performance for dynamic real-time applications. A wrong system performance analysis can lead to a catastrophe in a dynamic real-time system. In addition, real-time performance guarantee combined with efficient resource utilization is observed by experiments, while the previous worst-case approaches primarily focused on performance guarantee but resulted in typically poor utilization. The subsequent contribution is schedulability analysis for a feasible allocation of resource management on the Solaris operating system. This is accomplished with a mathematical model and by accurate response time prediction for a periodic, dynamic distributed real-time application.

Dynamic, distributed, real-time systems control an environment that varies widely without any time-invariant statistical or deterministic characteristic, are spread across multiple loosely-coupled computers, and must control the environment in a timely manner. In order to ensure that such a system meets its timeliness guarantees, there must be a means to monitor and maintain the quality of service in the system. The QoS manager is a monitoring and diagnosis system for real-time paths, collections of time-constrained and precedence-constrained applications. These applications may be distributed across multiple, heterogeneous computers and networks. This paper addresses the QoS negotiation features of the QoS manager and its interaction with the middleware resource manager. The major contributions of the paper are the negotiation algorithms and protocol that minimize the impact on the other paths' QoS while maximizing the unhealthy path's QoS. The approach and algorithms for QoS negotiation are presented.

Resource management for dynamic, distributed real-time systems requires handling of unknown arrival rates for data and events; additional desiderata include: accommodation of heterogeneous resources, high resource utilization, and guarantees of real-time quality-of-service (QoS). This paper describes the techniques employed by a resource manager that addresses these issues. The specific contributions of this paper are: QoS monitoring and resource usage profiling; prediction of real-time QoS (via interpolation and extrapolation of execution times) for heterogeneous resource platforms and dynamic real-time environments; and resource contention analysis.

In this paper we present the architecture and framework for a benchmark suite that has been developed as part of the DeSiDeRaTa project. The proposed benchmark suite is representative of the emerging generation of distributed, mission-critical, real-time control systems that operate in dynamic environments. Systems that operate in such environments may have unknown worst-case scenarios, may have large variances in the sizes of the data and event sets that they process (and thus, have large variances in execution latencies and resource requirements), and may be very difficult to characterize statically, even by time-invariant statistical distributions. The proposed benchmark suite (called DynBench) is useful for evaluation of the Quality of Service (QoS) management and/or Resource Management (RM) services in distributed real-time systems. As such, DynBench includes a set of performance metrics for the evaluation of the QoS and RM technologies in dynamic distributed real-time systems. The paper demonstrates the successful application of DynBench in evaluation of the DeSiDeRaTa QoS management middle-ware.

Dynamic real-time systems function in unpredictable environments and have requirements that span many domains such as time, survivability, and scalability. The system requirements are typically determined as a function of the environment, further exacerbating the unpredictability of the problem. Existing solutions, for the most part, have focussed on problems for which the attributes are static, and there exists a rich set of solutions for such problems. Our problem domain has attributes that are inherently dynamic rather than static, requiring a new approach.

The paper extends and applies a previously published taxonomy for the evaluation of object-oriented languages for the construction of distributed real-time systems. Our main question is: how well do current approaches support the design of concurrency and non-functional system features like the specification of allocation, timing and fault tolerance constraints? In order to demonstrate our approach, we consider two extremes: Ada 95 and our own real-time language Deal. It is shown that our taxonomy is well suited to discern essential properties of such languages and to point out the weaknesses of contemporary approaches.

The complexity of computer systems in many application areas has increased rapidly in the last decade. In order to deal with this complexity, application programs should be constructed by layering reusable modules. Therefore, an object-based design and implementation methodology is advocated. In addition, dependability of these computer systems is very important, and thus timeliness has to be guaranteed. In this paper, a pre-run-time scheduling approach is proposed to guarantee timeliness for computer systems in an almost fully predictable environment and in the presence of faults. The advantages of pre-run-time scheduling over other strategies to guarantee timeliness are discussed. The approach is used to schedule applications with a novel combination of timing and functional constraints. In addition, a novel characteristic of the approach is the enhancement of inherent parallelism of an application in order to find a schedule. >

Object-orientation is an effective means to improve the software engineering process. It provides a natural approach to system modeling, and yields benefits in all lifecycle phases. While much progress has been made in general-purpose object-oriented methods, considerably less progress has been made in the domain of object-oriented real-time computing. In addition to the typical requirements of functional correctness, efficiency, and information hiding, object-oriented real-time systems must also conform to stringent timing requirements. An additional complicating factor is that real-time control systems are frequently distributed in nature. For researchers and engineers, this has ramifications for requirements, object specification, object composition, implementation, verification, testing, languages and run-time systems.