Comparative analysis of two different middleware approaches for reconfiguration of distributed real-time systems

Software-based reconfiguration of distributed real-time systems is a complex problem with many sides to it ranging from system-wide concerns down to the intrinsic non-robust nature of the specific middleware layer and the used programming techniques. In a completely open distributed system, mixing reconfiguration and real-time is not possible; the set of possible target states can be very large threatening the temporal predictability of the reconfiguration process. Over the last years, middle ware solutions have appeared mainly for general purpose systems where efficient state transitions are sought for, but real-time properties are not considered. One of the few contributions to run-time software reconfiguration in distributed real-time environments has been the iLAND middleware, where the germ of a solution with high potential has been conceived and delivered in practice.¹ The key idea has been the fact that a set of bounds and limitations to the structure of systems and to their open nature needs to be imposed in order to come up with practical solutions. In this paper, the authors present the different sides of the problem of software reconfiguration from two complementary middleware perspectives comparing two strategies built inside distribution middleware. We highlight the lessons learned in the iLAND project aimed at service-based reconfiguration and compare it to our experience in the development of distributed real-time Java reconfiguration based on distributed tasks rescheduling. Authors also provide a language view of both solutions. Lastly, empirical results are shown that validate these solutions and compare them on the basis of different programming language realizations.     

低复杂度重构在分布式实时数据密集型Web服务架构中的应用

针对下一代分布式实时系统在重构时实时性要求较高的问题,本文提出了一种降低系统图复杂度并在有限时间内重构的方法。首先,利用服务组合确保重构在有限时间内实现;然后,通过路径选择算法和路径发送算法对图进行实时剪裁;最后,引入图构建算法消除具有更多非可调度路径的服务实现来降低图的复杂度。在iLAND服务重构和组合组件内部验证了本文方法,实验结果表明,本文方法能够显著减少解空间,大大减少了重构过程的计算时间。     

Adaptive resource management for dynamic distributed real-time applications

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.     

Contingencies-based reconfiguration of distributed factory automation

In this paper, we describe our experience using a Java-based platform to implement an emerging real-time distributed control model (IEC 61499). We provide a simple example of a control application that is distributed across two devices (Dallas Semiconductor TINI boards) and also investigate how this distributed implementation can be exploited to enhance the system's fault tolerance using a contingencies-based approach to reconfiguration.     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

Collaborative reconfiguration mechanism for holonic manufacturing systems

Although holonic manufacturing systems (HMS) are recognized as a paradigm to cope with the changes in manufacturing environment based on a flexible architecture, development of reconfiguration mechanism is required to realize the advantages of HMS. Finding a solution from scratch to deal with changes in HMS is not an appropriate approach as it may lead to chaos at the shop floor. The objective of this paper is to propose a viable design methodology to achieve effective reconfiguration in HMS based on the cooperation of holons. We formulate and study a holarchy reconfiguration problem and define an impact function to characterize the impact of resource failures on different holons in a holarchy. A collaborative reconfiguration algorithm based on the impact function is proposed to effectively reconfigure the systems to achieve minimal cost solutions.     

基于直接自适应控制的重构飞控系统研究

通常,飞控系统重构设计需知系统的故障信息,而使用直接自适应控制技术可在不知道系统故障信息的情况下,对飞控系统操纵面损伤进行重构,并且可使故障飞机很好地跟踪参考模型的输出．采用优化算法设计反馈补偿器以保证故障系统的严格正实性,并利用Lyapunov函数证明重构系统的渐近稳定性．将该方法用于某型飞机侧向控制系统的设计,仿真结果表明,在操纵面严重受损的情况下,飞机仍能保持良好的性能．     

Language constructs for real-time distributed systems

The paper observes syntactic and semantic requirements for a language for programming real-time distributed systems. A proposal for language features that meet these requirements is offered, and the features are applied to an example.     

Embedded real-time systems in cyber-physical applications: a frequency domain analysis methodology

ABSTRACT

Cyber-Physical Systems (CPSs) use sensors and actuators to interface between an embedded system and the physical world. The time-continuous domain of the physical world should be periodically sampled by real-time tasks in an embedded system to preserve its dynamic properties in the time-discrete domain.

Because the task execution pattern may vary during runtime, a jitter in the execution of a real-time task hinders the periodicity of its execution. The effects of jitters in CPSs are difficult to determine when the premises of the Nyquist-Shannon sampling theorem are not satisfied.

This paper proposes using frequency domain analysis to determine the perturbations that a real-time system produces on real-world applications; accordingly, the paper defines both a design and an evaluation criterion for real-time systems in CPS applications. The Fixed Priority discipline is analysed through simulations to conclude that no special design techniques are required when the utilization factors are less than 20%.     

End-to-end deadline control for aperiodic tasks in distributed real-time systems

A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving the system throughput.

Supporting soft real-time parallel applications on multiprocessors

The prevalence of multicore processors has resulted in the wider applicability of parallel programming models such as OpenMP and MapReduce. A common goal of running parallel applications implemented under such models is to guarantee bounded response times while maximizing system utilization. Unfortunately, little previous work has been done that can provide such performance guarantees. In this paper, this problem is addressed by applying soft real-time scheduling analysis techniques. Analysis and conditions are presented for guaranteeing bounded response times for parallel applications under global EDF multiprocessor scheduling.     

Network invariants for real-time systems

We extend the approach of model checking parameterized networks of processes by means of network invariants to the setting of real-time systems. We introduce timed transition structures (which are similar in spirit to timed automata) and define a notion of abstraction that is safe with respect to linear temporal properties. We strengthen the notion of abstraction to allow a finite system, then called network invariant, to be an abstraction of networks of real-time systems. In general the problem of checking abstraction of real-time systems is undecidable. Hence, we provide sufficient criteria, which can be checked automatically, to conclude that one system is an abstraction of a concrete one. Our method is based on timed superposition and discretization of timed systems. We exemplify our approach by proving mutual exclusion of a simple protocol inspired by Fischer’s protocol, using the model checker TLV. Part of this work was done during O. Grinchtein’s stay at Weizmann Institute. This author was supported by the European Research Training Network “Games”.     

Design of flexible transfer lines: A case-based reconfiguration cost assessment

Shortening product life cycles leads competing companies to continually release new products or modifying the existing ones; this is one of the major issues in production systems design. According to the changes in product features, production systems need to be properly configured or reconfigured to efficiently tackle new production requirements. A configuration approach for multi-product flexible transfer lines is presented which aims at minimizing the equipment cost. The approach is applied to a manufacturing case in the automotive sector. The robustness of the solution is tested against changes that affect the products to highlight reconfiguration costs and the penalty associated to the lack of a pro-active configuration approach.     

An architecture for real-time distributed artificial intelligent systems

This paper introduces a new architecture for a real-time distributed artificial intelligence system: DENIS—a Dynamic Embedded Noticeboard Information System. The fundamental idea underlying the architecture draws heavily upon a distributed human system analogy, as seen, for example, in the workplace. The aim of DENIS is to provide a simple, meaningful means by which autonomous intelligent agents can cooperate and coordinate their actions in order to enhance the reliability and effectiveness of a real-time distributed control system. Based on a human paradigm, the architecture inherently allows for the control of an intelligent agent to be taken over by a human operator, yet still to maintain consistency in the distributed system. The key to the thinking in this new approach is to try to model how humans work together, and to implement this in a distributed architecture. One of the main issues raised is that humans owe much of their flexibility to their ability to reason, not only logically, but also in terms of time.     

Demand-based schedulability analysis for real-time multi-core scheduling

In real-time systems, schedulability analysis has been widely studied to provide offline guarantees on temporal correctness, producing many analysis methods. The demand-based schedulability analysis method has a great potential for high schedulability performance and broad applicability. However, such a potential is not yet fully realized for real-time multi-core scheduling mainly due to (i) the difficulty of calculating the resource demand under dynamic priority scheduling algorithms that are favorable to multi-cores, and (ii) the lack of understanding how to combine the analysis framework with deadline-miss conditions specialized for those scheduling algorithms. Addressing those two issues, to the best of our knowledge, this paper presents the first demand-based schedulability analysis for dynamic job-priority scheduling algorithms: EDZL (Earliest Deadline first until Zero-Laxity) and LLF (Least Laxity First), which are known to be effective for real-time multi-core scheduling. To this end, we first derive demand bound functions that compute the maximum possible amount of resource demand of jobs of each task while the priority of each job can change dynamically under EDZL and LLF. Then, we develop demand-based schedulability analyses for EDZL and LLF, by incorporating those new demand bound functions into the existing demand-based analysis framework. Finally, we combine the framework with additional deadline-miss conditions specialized for those two laxity-based dynamic job-priority scheduling algorithms, yielding tighter schedulability analyses. Via simulations, we demonstrate that the proposed schedulability analyses outperform the existing schedulability analyses for EDZL and LLF.     

A complexity model for sequence planning in mixed-model assembly lines

Sequence planning is an important problem in assembly line design. It is to determine the order of assembly tasks to be performed sequentially. Significant research has been done to find good sequences based on various criteria, such as process time, investment cost, and product quality. This paper discusses the selection of optimal sequences based on complexity induced by product variety in mixed-model assembly line. The complexity was defined as operator choice complexity, which indirectly measures the human performance in making choices, such as selecting parts, tools, fixtures, and assembly procedures in a multi-product, multi-stage, manual assembly environment. The complexity measure and its model for assembly lines have been developed in an earlier paper by the authors. According to the complexity models developed, assembly sequence determines the directions in which complexity flows. Thus proper assembly sequence planning can reduce complexity. However, due to the difficulty of handling the directions of complexity flows in optimization, a transformed network flow model is formulated and solved based on dynamic programming. Methodologies developed in this paper extend the previous work on modeling complexity, and provide solution strategies for assembly sequence planning to minimize complexity.     

A web-based expert system to assess the complexity of manufacturing organizations

Information-theoretic modelling of manufacturing organizations and their supply chains has led to the development of measures of manufacturing complexity. The measures include assessment of the structural, dynamic and decision-making complexity associated with the processing and movement of material and information around a manufacturing system. A computer program has been written to calculate the decision-making complexity of a manufacturing system, under different system layouts and operating characteristics. In order to make the results of this program accessible to manufacturing organizations, an expert system has been developed to act as a mediator between the program and interested organizations. Given some simple quantitative data on manufacturing performance, the expert system can estimate the organization's complexity and suggest some recommendations to reduce it, based on the data provided by the organization. The expert system will be implemented on the web to enable on-line acquisition and searching of data on companies. The quid pro quo of the expert system is that anonymized data on the organizations will be retained so that complexity benchmarks may be established.