Robust Adaptive Metrics for Deadline Assignment in Distributed Hard Real-Time Systems

Distributed real-time applications usually consist of several component tasks and must be completed by its end-to-end (E-T-E) deadline. As long as the E-T-E deadline of an application is met, the strategy used for dividing it up for component tasks does not affect the application itself. One would therefore like to slice each application E-T-E deadline and assign the slices to component tasks so as to maximize the schedulability of the component tasks, and hence the application. Distribution of the E-T-E deadline over component tasks is a difficult and important problem since there exists a circular dependency between deadline distribution and task assignment. We propose a new deadline-distribution scheme which has two major improvements over the best scheme known to date. It can distribute task deadlines prior to task assignment and relies on new adaptive metrics that yield significantly better performance in the presence of high resource contention. The deadline-distribution problem is formulated for distributed hard real-time systems with relaxed locality constraints, where schedulability analysis must be performed at pre-run-time, and only a subset of the tasks are constrained by pre-assignment to specific processors. Although it is applicable to any scheduling policy, the proposed deadline-distribution scheme is evaluated for a non-preemptive, time-driven scheduling policy. Using extensive simulations, we show that the proposed adaptive metrics deliver much better performance (in terms of success ratio and maximum task lateness) than their non-adaptive counterparts. In particular, the simulation results indicate that, for small systems, the adaptive metrics can improve the success ratio by as much as an order of magnitude. Moreover, the new adaptive metrics are found to exhibit very robust performance over a large variety of application and architecture scenarios.     

Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques

The most crucial aspect of distributed real-time systems is the scheduling algorithm, which must guarantee that every job in the system will meet its deadline. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a heterogeneous 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 alternative versions which allow the insertion of tasks into idle time slots, using various bin packing techniques. The comparison study, based on different workloads and system heterogeneity levels, shows that the alternative versions of the algorithms outperform their respective counterparts.     

面向抖动优化的任务静态优先级指派算法

对任务相对截止时限进行优化设置是一种减少输出抖动的有效方法,但现有方法均是针对最早时限优先调度算法,不能适用于任务集采用静态优先级调度算法的场合.为此,提出通过优化优先级指派实现任务集的整体抖动最小化,并给出一种启发式的优先级指派算法.根据单调速率调度算法确定任务的初始优先级,以最小化局部抖动方式依次对任务的优先级进行再调整,从而得到近似最优的优先级指派.仿真实验结果表明,该算法能有效减少任务集的整体输出抖动.     

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.     

Exploiting slack time for just-in-time scheduling in wireless sensor networks

We consider the problem of real-time data collection in wireless sensor networks, in which data need to be delivered to one or more sinks within end-to-end deadlines. To enhance performance with respect to end-to-end deadline miss ratio, existing approaches schedule packets by prioritizing them based on per-packet deadlines and other factors such as the distance to the sink. However, important factors affecting the end-to-end performance such as queuing delays and buffer overruns have largely been ignored in the existing real-time schemes. Packet prioritization by itself cannot assist with these issues, and may in fact, exacerbate them for real-time data collection, since many high priority packets may simultaneously contend for the constrained network resources. In sensor networks, where the channel bandwidth and buffer space are often quite limited, these issues can dramatically impact real-time performance. Based on this observation, we propose Just-in-Time Scheduling (JiTS) strategies where packets are judiciously delayed within their slack time to reduce contention and load balance the use of the network buffers. We explore several policies for delaying data packets at different intermediate nodes considering potential contention. In addition, we also show that the routing protocol has a significant impact on real-time performance. In particular, shortest path routing leads to considerably better performance than geographic forwarding, which is often used for real-time data transmission in wireless sensor networks. Using an extensive simulation study, we demonstrate that JiTS can significantly improve the deadline miss ratio and packet drop ratio compared to two state-of-the-art approaches for real-time packet delivery for sensor networks (RAP and SPEED) under various scenarios. Notably, JiTS requires neither lower layer (e.g., MAC layer) support nor synchronization among the sensor nodes.     

AS prediction mechanism for distributed threads systems

In distributed real-time systems, if a task misses its deadline, an exception can be thrown. In this context, end-to-end deadline missing prediction mechanisms can reduce exception throwing because they define an estimated response time. With this estimated response time the system can carry out remedial actions in time to avoid the throw of an exception. In this work, we propose the Available Slack (AS) deadline missing prediction mechanism, which defines an estimated response time for distributed tasks using information such as computation time and end-to-end deadline. We show how AS behaves in simulations with different system workloads like pipelines, balanced and non-balanced loads.     

静态实时中间件的优先级映射问题

使用截止期单调(DM)调度算法和分布式优先级冲顶资源访问控制协议(DPCP)的实时CORBA系统中,当节点的本地优先级个数不足时,必须将多个全局优先级映射成一个本地优先级.这需要:①判定映射后任务可调度性的充分必要条件;②减少时间复杂度的映射算法.为此,推导出判定条件,确定了DGPM映射算法.该算法在保证系统可调度的前提下分配任务,或者证明映射后系统不可调度.证明了DGPM算法能调度其他直序列优先级映射算法可调度的任务和GCS集合.判定条件和算法在实际项目中得到了应用.     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

一种基于代价抢占的混合可重构任务调度算法*

针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。     

实时任务准入控制器的自动合成

在许多实时系统中,同一个计算平台上往往既有硬实时关键计算任务又有软实时非关键计算任务.硬实时任务必须在规定时间内完成,否则将导致系统错乱或崩溃等严重后果.而软实时任务若没有在规定时间内完成,虽会影响系统性能,但不会造成重大后果.为确保每个硬实时任务均在其规定时间内完成,在某些情况下需要拒绝一些软实时任务进入任务队列.文章提出了一种基于控制器自动合成策略的解决方案,通过所设计的准入控制器,对系统产生的每一个新任务自动决定是否准其进入任务队列.准入控制器必须使得所有被准入的任务均在规定时间内完成,并且决策序列满足以线性时态逻辑描述的服务质量要求.文章的主要贡献是提出了判定是否存在准入控制器的算法,该算法能在判定结果为真时构造出一个以有限状态时间自动机表达的准入控制器.     

Optimal Control of Multi-Stage Discrete Event Systems With Real-Time Constraints

We consider discrete event systems involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal state trajectory that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider such a multi-stage problem with not only stage-dependent but also task-dependent cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing ldquovirtualrdquo deadlines at each stage except the last one, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that a sequence of solutions to single-stage problems with virtual deadlines updated at each step converges to the global optimal solution of the multi-stage problem. This leads to a virtual deadline algorithm (VDA) which is scalable in the number of processed tasks. We illustrate the scalability and efficiency of the VDA through numerical examples.     

Component-oriented radars with probabilistic timing guarantees

In recent years, many modern phased-array radars are built with commercial off-the-shelf components, and the functions of many hardware components are also reimplemented by software modules. In such systems, radar tasks could be modeled as distributed real-time tasks which require end-to-end deadline guarantees and have precedence constraints. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, the objective of this paper is to propose a joint real-time scheduling algorithm for both transmitter/receiver and signal processor workloads with an analytical framework for offline probabilistic analysis and online admission control. The strength of our approach is verified by analysis results and a series of experiments based on a real phased-array radar for air defense frigates.     

基于树分解的空间众包最优任务分配算法

随着配备高保真传感器的移动设备的普及以及无线网络资费的迅速下降,空间众包成为一种新型的问题解决框架,被用于将位置相关的任务（如路况报告,食品配送）分配给工人（配备智能设备并愿意完成任务的人）。本文研究空间众包中最优任务分配问题,关键在于设计出将每个任务分配给最合适的工人的任务分配策略,以使得完成的总任务数目最大化,而所有的工人可以在完成所分配的任务后,在预期最晚工作时间之前返回起点。找到全局最优分配是一个棘手的问题,因为该问题不等于单个工人的最佳分配的简单累加。本文注意到,仅有部分工人存在任务依赖,因此本文利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法,该算法可以快速地更新启发函数界限,从而高效的对不可能成为最优解分配方案尽早地剪枝。实验表明,本文所提出的方法是非常有效的,可以很好地解决最优任务分配问题。     

基于优先级分类的工业无线网络确定性调度算法

确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况,基于多信道时分多址接入(TDMA)技术,在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上,对网络进行调度预处理,进而排除参数不合理的网络,并向网络管理者反馈.对于通过预处理的网络,调度算法优先为高优先级数据流的链路分配时隙和信道资源,而对属于同一类优先级的数据流,提出一种基于比例冲突空余时间的调度方案,在满足可调度性条件的前提下,根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明,所提出的调度算法可以取得较高的网络调度成功率.     

一种严格按比例派发服务的混合实时调度算法

在混合实时系统中,调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成,又要尽可能地提高软实时任务和非实时任务的服务质量.提出了一种严格按比例派发服务器算法(RPDS),并以此为基础构建了一种层次式调度框架.RPDS将处理器时间流分成连续的小段,并在每一小段中强制为非硬实时任务分配一个时间片.实验结果表明,RPDS可以合理地为各种类型应用分配处理器时间,并且降低了实时任务的截止期错失率.     

一种启发式多传感器任务实时动态分配算法

传感器任务的分配是传感器管理的重要问题。为提高任务分配的实时性和实效性,基于紧急任务优先、最早完成任务优先、复用能力最小优先和随机分配四条原则,提出了一种启发式多传感器任务实时动态分配算法。计算机模拟仿真表明:该算法既能保证优先级任务较早的执行,又能探测到任务的失败,还能维持传感器负载平衡,是一种快捷、高效的分配算法。     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

Deadline division-based heuristic for cost optimization in workflow scheduling

Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.     

多核环境下基于图模型的实时规则调度方法

安全攸关反应式系统的核心要求是：必须在指定时间期限内完成对外部事件的检测和目标事件的响应,否则会产生灾难性的后果.随着安全攸关反应式系统对智能化需求的日益增加,将规则推理应用于这类系统成为必然趋势.规则调度是保证规则推理硬实时约束的关键.为此,提出了一种基于图模型的实时规则调度方法（graph-based real-time rule scheduling,简称GBRRS）.该方法对基于事件图的实时规则推理过程进行建模,提出了基于图的端到端推理任务模型,并给出了端到端推理任务的调度算法,保证了规则调度的安全性.采用模拟实验对GBRRS方法进行了验证,实验结果表明,与DM-EDF方法（通过直接映射把规则上的推理操作转成推理任务后,用全局EDF算法对其进行调度的方法）相比,GBRRS方法在规则调度成功率上平均高出13%~15%,且在规则集的平均负载较高时,仍保持着80%以上的调度成功率.     

A priority-driven flow control mechanism for real-time traffic inmultiprocessor networks

Real-time applications when mapped to distributed memory multiprocessors produce periodic messages with an associated deadline and priority. Real-time messages may be hard or soft deadline. Real-time extensions to wormhole routing (WR) with multiple virtual channels (VCs) and priority-based physical link arbitration and VC allocation have been proposed in the literature. With a fixed number of VCs/link, a message can face an unbounded priority inversion, rendering the global priority ineffective. In this paper, we propose a new flow control mechanism called Preemptive Pipelined Circuit Switching for Real-Time messages (PPCS-RT) to reduce the priority inversion problem. For the proposed model, with some architectural support, we present an off-line approach to compute delivery guarantees of hard deadline real-time messages. We also perform a comparison of real-time WR and PPCS-RT in terms of performance with soft deadline traffic. The overall miss ratio percentage is over 30 percent higher for WR than PPCS-RT with one VC/link at high traffic loads. Finally, we compare the architectural complexity of a PPCS-RT router and other real-time routers