Overrun handling approaches for overload-prone soft real-time systems

Traditional overrun handling approaches for real-time systems enforce some isolation property at the job or task level. This paper shows that by “relaxing” task isolation, it is possible to efficiently deal with overruns in soft real-time systems with highly variable task execution times and proposes Randomized Dropping (RD), a novel overrun handling mechanism. RD is able to bound task overruns in a probabilistic manner, thus providing “soft” task isolation. The paper shows how to combine RD with priority-driven and rate-based scheduling algorithms, and how to analyze the resulting system. Performance evaluation and comparison between simulation and analytical results are discussed.     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

Adaptive cycle management in soft real-time disk retrieval

The objective of this study is to determine the right cycle management policy to service periodic soft real-time disk retrieval. Cycle-based disk scheduling provides an effective way of exploiting the disk bandwidth and meeting the soft real-time requirements of individual I/O requests. It is widely used in real-time retrieval of multimedia data blocks. Interestingly, the issue of cycle management with respect to dynamically changing workloads has not been receiving proper attention despite its significant engineering implications on the system behavior. When cycle length remains constant regardless of varying I/O workload intensity, it may cause under-utilization of disk bandwidth capacity or unnecessarily long service startup latency. In this work, we present a novel cycle management policy which dynamically adapts to the varying workload. We develop pre-buffering policy which makes the adaptive cycle management policy robust against starvation. The proposed approach elaborately determines the cycle length and the respective buffer size for pre-buffering. Performance study reveals a number of valuable observations. Adaptive cycle length management with incremental pre-buffering exhibits superior performance to the other cycle management policies in startup latency, jitter and buffer requirement. It is found that servicing low playback rate contents such as video contents for 3G cellular network requires rather different treatment in disk subsystem capacity planning and call admission criteria because relatively significant fraction of I/O latency is taken up by plain disk overhead.     

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.     

An $\mathsf{EDF}$ -based restricted-migration scheduling algorithm for multiprocessor soft real-time systems

There has been much recent interest in the use of the earliest-deadline-first ( ) algorithm for scheduling soft real-time sporadic task systems on identical multiprocessors. In hard real-time systems, a significant disparity exists between -based schemes and Pfair scheduling: on M processors, the worst-case schedulable utilization for all known variants is approximately M/2, whereas it is M for optimal Pfair algorithms. This is unfortunate because -based algorithms entail lower scheduling and task-migration overheads. However, such a disparity in schedulability can be alleviated by easing the requirement that all deadlines be met, which may be sufficient for soft real-time systems. In particular, in recent work, we have shown that if task migrations are not restricted, then (i.e. , global ) can ensure bounded tardiness for a sporadic task system with no restrictions on total utilization. Unrestricted task migrations in global may be unappealing for some systems, but if migrations are forbidden entirely, then bounded tardiness cannot be guaranteed. In this paper, we address the issue of striking a balance between task migrations and system utilization by proposing an algorithm called , which is based upon and treads a middle path, by restricting, but not eliminating, task migrations. Specifically, under , the ability to migrate is required for at most M−1 tasks, and it is sufficient that every such task migrate between two processors and at job boundaries only. , like global , can ensure bounded tardiness to a sporadic task system as long as the available processing capacity is not exceeded, but, unlike global , may require that per-task utilizations be capped. The required cap is quite liberal, hence, should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization.

A framework for simulating real-time multi-agent systems

In this paper, we describe an implementation of use in demonstrating the effectiveness of architectures for real-time multi-agent systems. The implementation provides a simulation of a simplified RoboCup Search and Rescue environment, with unexpected events, and includes a simulator for both a real-time operating system and a CPU. We present experimental evidence to demonstrate the benefit of the implementation in the context of a particular hybrid architecture for multi-agent systems that allows certain agents to remain fully autonomous, while others are fully controlled by a coordinating agent. In addition, we discuss the value of the implementation for testing any models for the construction of real-time multi-agent systems and include a comparison to related work.

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

RealNet: a neural network architecture for real-time systems scheduling

Real-time embedded systems are spreading to more and more new fields and their scope and complexity have grown dramatically in the last few years. Nowadays, real-time embedded computers or controllers can be found everywhere, both in very simple devices used in everyday life and in professional environments. Real-time embedded systems have to take into account robustness, safety and timeliness. The most-used schedulability analysis is the worst-case response time proposed by Joseph and Pandya (Comput J 29:390–395,1986). This test provides a bivaluated response (yes/no) indicating whether the processes will meet their corresponding deadlines or not. Nevertheless, sometimes the real-time designer might want to know, more exactly, the probability of the processes meeting their deadlines, in order to assess the risk of a failed scheduling depending on critical requirements of the processes. This paper presents RealNet, a neural network architecture that will generate schedules from timing requirements of a real-time system. The RealNet simulator will provide the designer, after iterating and averaging over some trials, an estimation of the probability that the system will not meet the deadlines. Moreover, the knowledge of the critical processes in these schedules will allow the designer to decide whether changes in the implementation are required.This revised version was published online in November 2004 with a correction to the accepted date.     

On the schedulability of a data-centric real-time distribution middleware

This work presents an analysis of the Data Distribution Service for Real-Time Systems (DDS), a data-centric distribution middleware that supports the development of predictable applications, from the schedulability point of view. The study focuses on how DDS intends to guarantee the real-time behavior through the mechanisms included in the standard, and proposes some extensions to this standard. Furthermore, the paper looks at other approaches to build distributed systems based on object distribution and remote procedures calls which can guarantee predictability, and shows how to use DDS to obtain real-time applications. A set of concepts defined in the Modelling and Analysis of Real-Time and Embedded systems (MARTE) standard has been integrated into DDS in order to allow using Model-Driven Engineering (MDE) and schedulability analysis techniques. Finally, to emphasize the results obtained from the analysis, the paper also performs a brief evaluation to validate the predictability of a particular DDS implementation.     

Resource management using multiple feedback loops in soft real-time distributed object systems

This paper describes a Resource Management System for a soft real-time distributed object system that is based on a three-level feedback loop. The Resource Management System employs a profiling algorithm that monitors the usage of the resources, a least laxity scheduling algorithm that schedules the methods of the tasks, and hot spot and cooling algorithms that allocate and migrate objects to balance the loads on the resources. The Resource Management System consists of a single Resource Manager for the distributed system, and a Profiler and a Scheduler located on each of the processors in the distributed system.     

实时系统动态行为模型的一种形式分析方法*

提出了一种基于统一建模语言UML 2.0的实时系统动态行为模型的形式分析方法。首先给出了UML顺序图的形式化描述,分析了UML顺序图中事件之间的关系;在此基础上,给出一种对象自动机来描述每个对象在UML顺序图描述的场景中所参与的事件序列的方法,并将该方法扩展到带有组合片段的UML 2.0顺序图;最后通过分析UML 2.0顺序图中的时间建模机制,给出了从UML 2.0顺序图中提取时间约束得到时间自动机的算法。     

Minimal schedulability interval for real-time systems of periodic tasks with offsets

We consider real-time systems in highly safety context where tasks have to meet strict deadlines. Tasks are periodic, may have offsets, share critical resources and be precedence constrained. Off-line scheduling should be of great help for such systems, but methods proposed in the literature cannot deal with them. Our aim is to extend and improve the well-known cyclicity result of Leung and Merill to every scheduling algorithm and to systems of interacting tasks with offsets. One of the main benefit of our result is to enable the use of off-line scheduling methods for those real-time critical systems.     

Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations

In order to meet the inherent need of real-time applications for high quality results within strict timing constraints, the employment of effective scheduling techniques is crucial in distributed real-time systems. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a homogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide an alternative version which allows imprecise computations, taking into account the effects of input error on the processing time of the component tasks of a job. The simulation results show that the alternative versions of the algorithms outperform their respective counterparts. To our knowledge, an imprecise computations approach for the dynamic scheduling of multiple task graphs with end-to-end deadlines and input error has never been discussed in the literature before.     

A framework for specifying and verifying the behaviour of open systems

Coding no longer represents the main issue in developing software applications. It is the design and verification of complex software systems that require to be addressed at the architectural level, following methodologies which permit us to clearly identify and design the components of a system, to understand precisely their interactions, and to formally verify the properties of the systems. Moreover, this process is made even more complicated by the advent of the “network-centric” model of computation, where open systems dynamically interact with each other in a highly volatile environment. Many of the techniques traditionally used for closed systems are inadequate in this context.We illustrate how the problem of modeling and verifying behavioural properties of open system is addressed by different research fields and how their results may contribute to a common solution. Building on this, we propose a methodology for modeling and verifying behavioural aspects of open systems. We introduce the IP-calculus, derived from the π-calculas process algebra so as to describe behavioural features of open systems. We define a notion of partial correctness, acceptability, in order to deal with the intrinsic indeterminacy of open systems, and we provide an algorithmic procedure for its effective verification.     

Prototype of fault adaptive embedded software for large-scale real-time systems

This paper describes a comprehensive prototype of large-scale fault adaptive embedded software developed for the proposed Fermilab BTeV high energy physics experiment. Lightweight self-optimizing agents embedded within Level 1 of the prototype are responsible for proactive and reactive monitoring and mitigation based on specified layers of competence. The agents are self-protecting, detecting cascading failures using a distributed approach. Adaptive, reconfigurable, and mobile objects for reliablility are designed to be self-configuring to adapt automatically to dynamically changing environments. These objects provide a self-healing layer with the ability to discover, diagnose, and react to discontinuities in real-time processing. A generic modeling environment was developed to facilitate design and implementation of hardware resource specifications, application data flow, and failure mitigation strategies. Level 1 of the planned BTeV trigger system alone will consist of 2500 DSPs, so the number of components and intractable fault scenarios involved make it impossible to design an ‘expert system’ that applies traditional centralized mitigative strategies based on rules capturing every possible system state. Instead, a distributed reactive approach is implemented using the tools and methodologies developed by the Real-Time Embedded Systems group.     

实时协同的调度算法研究

研究了目前流行的实时调度技术,归纳总结了不同调度技术下的典型调度算法,介绍了实时调度算法的调度规则、调度特点、适用场合以及需要解决的问题,分析了典型商业实时操作系统中的调度技术,提出了增强操作系统实时性能需要解决的技术问题,为将优秀的实时调度算法应用在实时操作系统中奠定了理论基础。     

An iterative approach to verification of real-time systems

Verification of real-time systems is a complex problem, requiring construction of aregion automaton with a state space growing exponentially in the number of timing constraints and the sizes of constants in those constraints. However, some properties can be verified even when some quantitative timing information is abstracted. We propose a new verification procedure, where increasingly more complex abstractions of the region automaton are iteratively constructed. In many cases, the procedure can be stopped early, and thus can avoid the state space explosion problem.     

The need for a new experimental environment for HCI research into multi-agent,real-time systems

Abstract

Much of the current research in HCI is carried out using experimental environments based on word processors, database search, or other conventional office automation. While this approach meets many needs it lacks the power required for investigating many unconventional situations. Complex multi-agent real-time systems are not typically found in offices and cannot easily be investigated in typical word processing or office automation contexts. The paper refers to four environments where multi-agency exists in a real-time environment: flight systems, plant control, telephone networks, and complex office systems. Consideration is given to the requirements of an alternative experimental environment which could allow HCI research to explore a wider range of issues.     

The need for a new experimental environment for HCI research into multi-agent, real-time systems

Much of the current research in HCI is carried out using experimental environments based on word processors, database search, or other conventional office automation. While this approach meets many needs it lacks the power required for investigating many unconventional situations. Complex multi-agent real-time systems are not typically found in offices and cannot easily be investigated in typical word processing or office automation contexts. The paper refers to four environments where multi-agency exists in a real-time environment: flight systems, plant control, telephone networks, and complex office systems. Consideration is given to the requirements of an alternative experimental environment which could allow HCI research to explore a wider range of issues.     

基于UPPAAL的实时系统模型验证

UPPAAL是一种使用时间自动机模型的实时系统验证工具,它可以避免时间自动机求积时状态空间的爆炸。介绍了时间自动机理论和工具UPPAAL,着重说明如何用UPPAAL进行模型检查,并给出了一个应用实例。