Resource Reservation in Dynamic Real-Time Systems

This paper focuses on the problem of providing efficient run-time support to multimedia applications in a real-time system, where different types of tasks (characterized by different criticality) can coexist. Whereas critical real-time tasks (hard tasks) are guaranteed based on worst-case execution times and minimum interarrival times, multimedia tasks are served based on mean parameters. A novel bandwidth reservation mechanism (the constant bandwidth server) allows real-time tasks to execute in a dynamic environment under a temporal protection mechanism, so that each task will never exceed a predefined bandwidth, independently of its actual requests. The paper also discusses how the proposed server can be used for handling aperiodic tasks efficiently and how a statistical analysis can be applied to perform a probabilistic guarantee of soft tasks. The performance of the proposed method is compared with that of similar service mechanisms (dynamic real-time servers and proportional share schedulers) through extensive simulation experiments.     

面向方面的实时系统中间件

基于面向方面的中间件构建技术,能够把实时、安全性、可靠性、易管理性、容错性等横切关注从中间件中分离出来,形成独立于中间件的核心功能的方面,遗留中间件实现系统零侵入的实时扩展或重构。运用面向方面的编程技术可实现中间件横切关注和核心功能关注的并行设计与开发。中间件构建实现良好模块化,可配置性,部署时或运行时的可剪裁性,从而平衡实时系统中间件的通用性和专用性。     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

实时多处理器系统中基于能量节约的动态调度算法

当前处理器由于较高的能量消耗。导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．本文提出的调度算法针对多处理器系统，以最短任务优先调度为基础，结合其它有效技术，如共享空闲时间回收等，使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，本文提出两种算法：STFBA1及STFBA2（Shortest Task First—Based Algorithm）．与目前所知的有效算法相比，我们的算法具有更好的性能（调度长度及能量消耗）．     

面向可重构控制器实时中间件的设计与实现

可重构控制器的出现要求系统软件模块不但要满足性能和精度要求,还应具有模块化、可集成、可重用等特性.如果将实时中间件引入到控制器的设计中,由中间件管理模块间的交互,可实现控制器的可重构.建立基于RTLinux和实时CORBA的实时中间件平台,需要将CORBA引入RTLinux实时内核空间.该文给出了RTLinux实时内核中的实时CORBA和minimum CORBA实现RTCK的设计,并基于RTLinux MBuff共享内存驱动和实时FIFO设计和实现了GIOP通信协议,最后给出了RTCK与TAO的延迟抖动测试结果并做了相关的分析.     

Implementation of Hard Real-Time Embedded Control Systems

Although the domain of hard real-time systems has been thoroughly elaborated in the academic sphere, embedded computer control systems –- being an important component in mechatronic designs –- are seldom dealt with consistently. Often, off-the-shelf computer systems are used, with no guarantee that they will be able to meet the requirements specified. In this paper, a design for embedded control systems is presented. Particularly, the paper deals with the hardware architecture and design details, the operating system, and high-level real-time language support. It is shown how estimates of process run-times necessary for schedulability analysis can be acquired on the basis of deterministic behavior of the hardware platform.     

Stable and Real-Time Scheduling of a Class of Hybrid Dynamic Systems

Based on some practical engineering problems arising from process control and space-structure control, this paper studies a class of hybrid dynamic systems in which N plants are controlled by a central controller in sharing time manner, where the plants are described by differential equations and the controller works according to the mechanism of discrete events. An event feedback strategy is suggested to be a scheduling policy such that one and only one plant among N plants is chosen to be controlled at any time. Some conditions of asymptotical and exponential stability are then given and an exponential upper bound of states norm is also estimated for the event feedback scheduling strategy. An algorithm based on event feedback strategy is presented to determine the control laws of the plants to meet the given performance. An example follows to illustrate the application and effect of the results.     

实时异构系统的动态分批优化调度算法

提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.     

实时多处理器系统的动态分批优化调度算法

提出了一种实时多处理器系统的新的高效动态调度算法--动态分批优化调度算法,该算法突破了以往算法中一次只安排一项任务的做法,采用在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上运行构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都安排一个处理器或为每个处理器安排一项任务,使得这种安排具有最好的合适性,以增大未安排任务的可行性.这种方法极大地提高了算法的调度成功率.同时,为了研究该算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与节约算法的调度成功率进行了比较.模拟结果显示,在节约算法的调度成功率小于10%的约束条件下,该算法的调度成功率大于90%,说明新算法的优势是非常明显的.     

On the Scheduling of Flexible and Reliable Real-Time Control Systems

Many real-time systems, such as manufacturing plants, have long life cycles. To enable the realization of technological innovations and to mitigate the risk and cost of bringing new control technologies into functioning systems, flexible and reliable real-time software architectures such as Simplex have been developed. There is also an emerging trend that integrates the design of controllers and schedulers. For example, algorithms that identify the optimal frequencies of control tasks subject to schedulability constraints have been developed, and the notion of feedback schedulers has been investigated. However, the optimization of the performance of flexible and reliable architectures with analytically redundant software controllers has remained an open problem. In fact, a direct application of the existing optimization methods would not yield the optimal frequencies. In this paper, we present a method that correctly finds the optimal frequencies for systems using analytically redundant controllers. We also show that the proposed method is robust against inaccuracies in the estimation of failure rates of the controllers.     

Scheduling of Time-Triggered Real-Time Systems

Thispaper introduces a new class of applications for constraint programming.This new type of application originates out of a special classof real-time systems, enjoying increasing popularity in areassuch as automotive electronics and aerospace industry. Real-timesystems of this kind are time triggered in the sense that theiroverall behavior is globally controlled by a recurring clocktick. Being able to compute an appropriate pre-runtime scheduleautomatically is the major challenge for such an architecture.What makes this specific off-line scheduling problem somewhatuntypical is that a potentially indefinite, periodic processinghas to be mapped onto a single time window. In this article wewill show how this problem can be solved by constraint programmingand we will describe which techniques from traditional schedulingand real-time computing led to success and which failed whenconfronted with a large-scale application of this type. The techniquesthat proved to be the most successful were special global constraintsand an elaborate search heuristics from Operations Research.Also for finding a valid schedule mere serialization is shownto be sufficient. The actual implementation was done in the concurrentconstraint programming language Oz.     

Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling

Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to exploit multiple voltage and frequency levels and to prolong their battery life. However, pure DVS techniques do not perform well for systems with dynamic workloads where the job execution times vary significantly. In this paper, we present a novel approach combining feedback control with DVS schemes targeting hard real-time systems with dynamic workloads. Our method relies strictly on operating system support by integrating a DVS scheduler and a feedback controller within the earliest-deadline-first (EDF) scheduling algorithm. Each task is divided into two portions. The objective within the first portion is to exploit frequency scaling for the average execution time. Static and dynamic slack is accumulated for each task with slack-passing and preemption handling schemes. The objective within the second portion is to meet the hard real-time deadline requirements up to the worst-case execution time following a last-chance approach. Feedback control techniques make the system capable of selecting the right frequency and voltage settings for the first portion, as well as guaranteeing hard real-time requirements for the overall task. A feedback control model is given to describe our feedback DVS scheduler, which is used to analyze the system's stability. Simulation experiments demonstrate the ability of our algorithm to save up to 29% more energy than previous work for task sets with different dynamic workload characteristics. This work was supported in part by NSF grants CCR-0208581, CCR-0310860 and CCR-0312695. Preliminary versions of parts of this work appeared in the ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02) (Dudani et al., 2002), in the Workshop on Compilers and Operating Systems for Low Power 2002 (Zhu and Mueller, 2002) and in the IEEE Real-Time Embedded Technology and Applications Symposium 2004 (Zhu and Mueller, 2004a).     

实时中间件动态调度算法的研究及应用

文章建立了实时中间件OPC服务器的实时调度模型,设计了处理混合任务的动态调度算法(基于EDF)和实现方式,分析了算法的可调度性和非周期任务的响应性能及参数设计,并给出了相应的调度结果。     

软件容错模型中的容错实时调度算法

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.     

基于多传感器的控制系统实时调度算法

将简单反馈控制与任务准入/回归、可达/夭折等策略相结合,设计新的动态调度框架。在此基础上,综合截止期、关键度和最坏执行时间3种特征参数,提出基于反馈控制的混合策略调度算法,该算法也适用于对任务的其他多种特征参数的综合。从截止期错失率、错失任务平均关键度和CPU有效利用率3个方面,分析算法的性能。实验结果表明,该算法在混合任务和动态负载下与最早截止期优先和最高价值优先算法相比具有更好的性能。     

Integrated Adaptive QoS Management in Middleware: A Case Study

Distributed real-time and embedded (DRE) systems in which application requirements and environmental conditions may not be known a priori—or which may vary at run-time—can benefit from an adaptive approach to management of quality-of-service (QoS) to meet key constraints, such as end-to-end timeliness. Moreover, coordinated management of multiple QoS capabilities across multiple layers of applications and their supporting middleware can help to achieve necessary assurances of meeting these constraints.This paper offers two contributions to the study of adaptive DRE computing systems: (1) a case study of our integration of multiple middleware QoS management technologies to manage quality and timeliness of imagery adaptively within a representative DRE avionics system and (2) empirical results and analysis of the impact of that integration on key trade-offs between timeliness and image quality in that system.This work was supported in part by AFRL contract F33615-97-D-1155/0005 (WSOA), NSF ITR CCR-0312859, Siemens, and DARPA/AFRL contracts F33615-03-C-4112, F30602-98-C-0187 and F33615-00-C-1694. Approved for public release, distribution unlimited.Christopher D. Gill is an Assistant Professor in the Department of Computer Science and Engineering at Washington University in St. Louis. He has published over 50 refereed technical articles in leading journals, conferences, workshops, and book series. His research focuses on distributed real-time embedded systems, with particular emphasis on adaptive mresource management, scheduling, and software design and implementation for time-and-space constrained systems. Dr. Gill has chaired numerous workshop and conference program committees, and has participated widely in review panels and standards organizations in the distributed and real-time systems areas. The research he has led has produced several freely available open-source software frameworks including the Kokyu scheduling and dispatching framework and the nORB small-footprint real-time object request broker.Jeanna Gossett joined The Boeing Company in 1999 as a member of Bold Stroke/Open Systems Architecture team. Jeanna has worked on several CRAD projects including Weapon Systems Open Architecture (WSOA) where she was responsible for incorporating quality of service and resource management software technology into the fighter aircraft real-time embedded system application. Jeanna has since joined the F/A-18 New Product Development Mission Systems team. Prior to joining The Boeing Company in 1999, she worked in the telecommunications industry as an embedded systems developer at Ericsson and Siemens AG. Jeanna received a B.S. in Electrical Engineering from Southern Illinois University, Edwardsville and is a 2005 M.B.A. candidate at Washington University in St. Louis.David Corman is a Technical Fellow at the Boeing Company, located in St. Louis, Mo. Dave is the chief scientist for the Network Centric Operations (NCO) thrust in Phantom Works (PW) and is responsible for developing the NCO technology research agenda and investment strategy. He is also the Principle Investigator (PI) for a variety of Air Force and Defense Advanced Research Project Agency (DARPA) programs that are producing technologies for integrating legacy platforms into the emerging Global Information Grid and for autonomous control of unmanned systems. Since joining the former McDonnell-Douglas (now part of the Boeing Company) in 1983, Dave has worked on numerous projects ranging from embedded systems to large C4I and weapon systems. A major focus of Daves career has been on the development of C4I system simulations and in mission planning system development for aircraft and missiles. He has also served as a consultant to many weapon system and C4I programs in St. Louis, Seattle, and California. Prior to joining McDonnell-Douglas, Dave spent five years at the Johns Hopkins University Applied Physics Laboratory. He was the first recipient of a Naval Research Laboratory Fellowship from the University of Maryland—College Park where he received his PhD in Electrical Engineering in 1983.Joseph Loyall is a division scientist at BBN Technologies, where he leads the Distributed Real-time Embedded (DRE) systems research thrust in the Distributed Systems Advanced Middleware Technology group. He is actively involved in developing integrated dynamic resource management capabilities and advanced software engineering using model driven architecture (MDA) approaches, and in applying adaptive behavior to operational embedded systems such as collections of unmanned and manned air vehicles. Dr. Loyall has a Ph.D. and M.S. in computer science from the University of Illinois and a B.S. in computer science from Indiana University. He can be contacted at jloyall@bbn.com.Richard E. Schantz is a principal scientist at BBN Technologies in Cambridge, Mass., where he has been a key contributor to advanced distributed computing R&D for the past 30 years. His research has been instrumental in defining and evolving the concepts underlying middleware since its emergence in the early days of the Internet. He was directly responsible for developing the first operational distributed object computing capability and transitioning it to production use. More recently, he has led research efforts toward developing and demonstrating the effectiveness of middleware support for adaptively managed Quality Of Service control, as principal investigator on a number of key DARPA projects in the areas of adaptive real-time behavior, survivability and advanced software engineering. Schantz received his Ph.D. degree in Computer Science from the State University of New York at Stony Brook, in 1974.Michael Atighetchi is a senior scientist at BBN Technologies and a senior member of the Distributed Systems Advanced Middleware Technology group. His interests include use of adaptation in survivable systems, network and operating system security, and distributed coordination. Contact him at matighet@bbn. comDouglas C. Schmidt (d.schmidt@vanderbilt.edu) is a Professor of Electrical Engineering and Computer Science, Associate Chair of the Computer Science and Engineering program, and a Senior Researcher in the Institute for Software Integrated Systems (ISIS) at Vanderbilt University. He has published over 300 technical papers and books that cover a range of research topics, including patterns, optimization techniques, and empirical analyses of software frameworks and domain-specific modeling environments that facilitate the development of distributed real-time and embedded (DRE) middleware and applications running over high-speed networks and embedded system interconnects. Dr. Schmidt has served as a Deputy Office Director and a Program Manager at DARPA, where he led the national R&D effort on middleware for DRE systems.     

Towards a Mobile Code Management Environment for Complex,Real-Time,Distributed Systems

We present a novel mobile code management environment,currently under design and development. Our design employs anopen architecture, suitable for ``plug-and-play' with COTS andother groups' tools. While we have studied new algorithms, costand objective functions, and other fundamental issues, the maincontribution of this experimental research work is in the environmentitself. It should be noted that networked platforms, such asthe World Wide Web, are inherently not suitable for traditional,predictable real-time applications. Thus, real-time concernsnecessarily need to be blended with others concerns, and thetarget applications, making use of our environment, will toobe a blend of partially hard real-time and partially (or mostly)soft-real- time ones. The prototype environment will thereforesupport performance-based analysis and management focusing notonly on predictability but also on compilation, efficiency, safetyand other tradeoffs. We have selected the Java language and itsbytecode format as a representation for mobile code as well asa language for our implementation.     

一种基于分组与适当选取策略的实时多处理器系统的动态调度算法

在分析了近视算法和节约算法缺点的基础上，提出了一种新的实时多处理器系统的动态调度算法——分组适度算法．分组适度算法包括两个策略：分组策略和适当选取策略．分组策略是为了提高资源的利用率，在保证具有较小目标函数值的任务截止期限的情况下，优先选择可以共享访问资源的任务进行扩展．适当选取策略是为了提高处理器的利用率，当任务不访问资源以及任务所需资源的最早可用时间小于系统中处理器的最小最早可用时间时，选择最早可用时间最小的处理器；否则，选择最早可用时间最接近资源的最早可用时间的处理器．模拟结果表明，分组适度算法的任务接受率高于近视算法和节约算法的任务接受率．     

Voltage-Clock Scaling for Low Energy Consumption in Fixed-Priority Real-Time Systems

Power and energy constraints are becoming increasingly prevalent in real-time embedded systems. Voltage-scaling is a promising technique to reduce energy and power consumption: clock speed tends to decrease linearly with supply voltage while power consumption goes down quadratically. We therefore have a tradeoff between the energy consumption of a task and the speed with which it can be completed. The timing constraints associated with real-time tasks can be used to resolve this tradeoff. In this paper, we present two algorithms for voltage-scaling. Assuming that a processor can operate in one of two modes: high voltage and low voltage, we show how to schedule the voltage settings so that deadlines are met while reducing the total energy consumed. We show that significant reductions can be made in energy consumption.