Throttle and preempt: A flow control policy for real-time traffic in wormhole networks

In this paper, we study wormhole routed networks and envision their suitability for real-time traffic in a priority-driven paradigm. A traditional blocking flow control in wormhole routing may lead to a priority inversion in the sense that high priority packets are blocked by low priority packets for unlimited time. This uncontrolled priority inversion causes the frequent deadline missing even at a low network load. This paper therefore proposes a new flow control called throttle and preempt flow control, where high priority packets can preempt network resources held by low priority packets, if necessary. As a result, this flow control does not cause priority inversion. Our simulations show that the throttle and preempt flow control dramatically reduces deadline miss ratio for various real-time traffic configurations without extra virtual channels. It is also observed that the throttle and preempt flow control offers shorter delay for non-real-time traffic than the existing real-time flow control does.     

基于CAN总线实时应用的可靠调度性研究

CAN总线是一种高级的串行通信协议,适用于各种分布式控制系统。在实时应用中,标准的CAN协议使用静态优先级算法,对传输信道的利用率比较低。对基于CAN总线通信的动态优先级调度算法进行研究后,提出了一种基于指数分配方式的MTS算法,在保证强实时性消息的同时兼顾了低优先级消息的公平性。     

Reliability improvement of the dual-priority protocol under unreliable transmission

The dual-priority is a scheduling policy providing the guarantees needed by periodic or sporadic hard real-time tasks while decreasing the response time for aperiodic soft real-time tasks. This scheduling policy can be applied to message scheduling and its performance on controller area network (CAN) will be assessed. Nevertheless, when used in an electromagnetic stressed environment (e.g. automotive communication) leading to transmission errors, this scheduling strategy could lead to serious disappointments. It will be explained why the hard real-time traffic is highly sensitive to transmission errors. The risks of deadline failure will be quantified and a simple mechanism that provides probabilistic guarantees to prevent hard real-time frames from missing their deadlines, will be proposed. This mechanism is compared in terms of performance to the original dual-priority strategy. The chosen performance metrics are the deadline failure probability for hard real-time traffic, the average response time and the variance in response time for soft real-time traffic.     

交换以太网中实时消息截止期划分算法研究

为解决交换式以太网中实时消息在发送及接收链路上的截止期划分问题,首先给出了非抢占式EDF调度算法的可调度性分析方法,并分析了消息的提前释放对非抢占式EDF调度算法可调度性的影响,在此基础上提出了新的截止期划分算法(MDPS)。算法通过计算可满足调度条件时消息在发送链路及接收链路截止期应该划分的下限,并结合截止期的松驰量实现实时消息在发送及接收链路上的截止期划分。算法实验比较和分析表明,该算法在提高网络聚合带宽、减小消息的错失率方面明显优于现有的ADPS算法。     

Adaptive scheduling for integrated traffic on WDM optical networks

One of the important issues in the design of future generation of high-speed networks is to provide differentiated service to different types of traffic with various time constraints. In this paper, we study the problem of providing real-time service to either hard or soft real-time messages and normal transmission service to variable-length messages without time constraints in WDM optical networks. We propose an adaptive scheduling algorithm for scheduling message transmissions in order to improve the network performance when both real-time and non real-time messages are transmitted in one topology. We have analyzed the complexity of the algorithm to show its feasibility. We have conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithm. The study suggests that when scheduling message transmission in WDM networks differentiated services should be considered in order to meet time constraints of real-time messages while non real-time messages are being served so that the overall performance of the network could be improved.     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

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.     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

CAN总线中改进的EDF调度算法可调度性分析

针对于CAN总线的调度问题,因现有的平均分区EDF调度算法在对于优先级反转问题上收效甚微,从而导致消息缺乏一定的可调度性,故提出一种改进的基于幂函数分区的EDF算法;同时借助量化误差的概念,对该调度算法进行可调度性分析,充分论证了在该调度算法下,消息可调度的判定条件;采用CANoe平台进行实验仿真,对比平均分区EDF调度算法和双幂函数分区EDF调度算法,经试验测试验证了双幂函数分区EDF调度算法的可行性和优越性,改善了消息的最坏响应时间,提高了CAN网络通讯的实时性。     

Avoiding request–request type message-dependent deadlocks in networks-on-chips

When an application is running on a network-on-chip (NoC)-based multiprocessor system-on-chip (MPSoC), two types of deadlocks may occur: (i) the routing-dependent deadlocks, and (ii) the message-dependent deadlocks. The former type of deadlocks can be avoided by removing any cyclic paths on the application’s channel dependency graph. The message-dependent deadlocks, caused by mutual dependency of different control and/or data messages, on the other hand, are very complicated to deal with. In this paper, we focus our study on the request–request type message-dependent deadlocks which may appear in a peer-to-peer streaming system. This type of deadlocks can have devastating effects on applications using streaming protocols that often demands real-time processing over continuous data streams. We show that request–request type of deadlocks can be avoided by proper inclusion of virtual channels (VCs) for the links along the selected routing path. These VCs are not bounded to a particular communication path. Instead, they can be shared among multiple existing communication flows. In this paper, we have formally proved a sufficient condition that determines the minimum number of VCs actually needed for each link of a communication flow such that, request–request type message-dependent deadlocks can be completely avoided. Following this sufficient condition, we propose a path selection and minimum VC allocation (PSMV) algorithm to help determine the minimum number of non-uniform VCs for each link. The PSMV algorithm consists of two major steps. In the first step, we attempt to minimize the maximum number of VCs among all the links. This problem is NP-complete in nature, and it is solved using the proposed mixed integral linear programming (MILP)-based algorithm. In the second step, based on the solution suggested in the first step, the minimum number of VCs for each link is finally determined. The PSMV algorithm can literally be integrated with any existing application mapping algorithm to provide deadlock-free mapping results. One such deadlock-free mapping algorithm is suggested in this paper. Our experiments also show that, compared to an existing flow control based deadlock avoidance method (CTC) and a deadlock recovery method (DR), increase of buffers size in PSMV is within 5% compared to a baseline network configuration. The message latency of PSMV is the lowest among all three designs.     

Network access protocol for hard real-time communication systems

Distributed hard real-time systems are characterized by communication messages associated with timing constraints, typically in the form of deadlines. A message should be received at the destination before its deadline expires. Carrier sense multiple access with collision detection (CSMA/CD) appears to be one of the most common communication network access schemes that can be used in distributed hard real-time systems. In this paper, we propose a new real-time network access protocol which is based on the CSMA/CD scheme. The protocol classifies the messages into two classes as ‘critical’ and ‘noncritical’ messages. The messages close to their deadlines are considered to be critical. A critical message is given the right to access the network by preempting a noncritical message in transmission. Extensive simulation experiments have been conducted to evaluate the performance of the protocol. It is shown that the protocol can provide considerable improvement over the virtual time CSMA/CD protocol proposed for hard real-time communication by Zhao et al.¹.     

Hard real-time communication in multiple-access networks

With the increasing use of distributed hard real-time systems, the ability of computer networks to handle hard real-time message traffic is becoming more important. For traditional networks, maximizing the throughput or minimizing the average message delay is the most important performance criteria. In the hard real-time domain, however, concern focuses on satisfying the time constraints of individual messages. This paper examines recent developments in hard real-time communication in local area multiple-access networks. Two general strategies are used in hard real-time communication: the guarantee strategy and the best-effort strategy. In the former, messages are guaranteed to meet their deadlines during normal operation of the network. In the best-effort strategy, the network will attempt to send messages before their deadlines, but no guarantees are given. Real-time message traffic can be distinguished according to whether it is best suited for the guarantee strategy or the best-effort strategy. Although this paper concentrates on multiple-access networks, many of the concepts presented and lessons learned are also applicable to other types of networks.     

基于Windows＋RTX的伺服作动系统测控软件开发

文章以某伺服作动系统测试设备的软件研发为背景,针对Windows系统由于线程优先级少、隐含不确定的线程调度机制以及优先级倒置等原因而造成的非实时性差,无法满足实时测控要求的缺陷,通过设计一种基于RTX和VC＋＋的多任务实时测控系统,利用RTX来增强Windows的实时性,实时任务部分运行于实时子系统RTSS下,非实时部分则运行于Win32子系统下,实时部分和非实时任务之间的通信通过共享内存的方式实现。该系统利用VC＋＋开发人机交换界面。解决了在Windows无法进行实时测试的缺陷,搭建一种在Windows下实时测控的软件平台,实现了在Windows平台下对伺服作动系统的功能和性能实时检测。     

Aperiodic servers in a deadline scheduling environment

A real-time system may have tasks with soft deadlines, as well as hard deadlines. While earliest-deadline-first scheduling is effective for hard-deadline tasks, applying it to soft-deadline tasks may waste schedulable processor capacity or sacrifice average response time. Better average response time may be obtained, while still guaranteeing hard deadlines, with an aperiodic server. Three scheduling algorithms for aperiodic servers are described, and schedulability tests are derived for them. A simulation provides performance data for these three algorithms on random aperiodic tasks. The performances of the deadline aperiodic servers are compared with those of several alternatives, including background service, a deadline polling server, and rate-monotonic servers, and with estimates based on the M/M/1 queueing model. This adds to the evidence in support of deadline scheduling,versus fixed priority scheduling.     

结合价值密度和截止期的网格实时作业调度

在商业网格和云计算环境中,作业有到达时间、计算量、预算、截止期等参数,其中,预算是时间的函数。准确区分作业的重要性和紧迫性是作业调度系统的一个关键问题。综合利用这四个参数来定义作业的优先级,并提出基于价值密度和相对截止期的网格作业调度算法。分别对弱实时和强实时网格作业的调度进行仿真。仿真结果显示,所提出的调度算法的性能在两种情况下都优于所有对比算法的性能,且在强实时作业情况下优势更明显。     

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

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

Convex optimization framework for intermediate deadline assignment in soft and hard real-time distributed systems

It is generally challenging to determine end-to-end delays of applications for maximizing the aggregate system utility subject to timing constraints. Many practical approaches suggest the use of intermediate deadline of tasks in order to control and upper-bound their end-to-end delays. This paper proposes a unified framework for different time-sensitive, global optimization problems, and solves them in a distributed manner using Lagrangian duality. The framework uses global viewpoints to assign intermediate deadlines, taking resource contention among tasks into consideration. For soft real-time tasks, the proposed framework effectively addresses the deadline assignment problem while maximizing the aggregate quality of service. For hard real-time tasks, we show that existing heuristic solutions to the deadline assignment problem can be incorporated into the proposed framework, enriching their mathematical interpretation.     

TinyOS中DSA调度策略的研究

针对TinyOS任务调度采用非剥夺的先来先服务调度策略,而产生的系统紧急任务不能及时得到响应及节点吞吐量下降情况,该文提出一种新的可抢占时限短作业调度策略——DSA。在绝对时限前执行硬实时任务,满足了系统对实时任务的响应要求,提高处理器的响应速度,对软实时任务实行短作业优先调度策略,提高系统的吞吐量。在TinyOS上测试表明,DSA策略在不影响TinyOS原有性能的情况下,改进了传感器网络承担实时性任务的运行效果。     

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

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

Mutex降解uC/OS-II优先级翻转

实时性是嵌入式应用中一个重要的指标,而优先级翻转是影响系统实时性的一个重要因素。可剥夺型内核中,任务以独占方式使用共享资源时,将出现低优先级任务先于高优先级任务运行的现象,即优先级翻转。本文以实时操作系统uC/OS-II为例,分析了产生优先级翻转的原因,阐述了利用互斥信号量解决该问题的原理并通过具体的应用程序对这一方法的可行性进行了验证。