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

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

基于DMS和EDF的CAN总线混合调度算法

针对CAN总线调度问题,分析了CAN网络中信息帧发生传输错误的概率化最大响应时间,融合DMS算法的可预测性良好、处理器开销低以及对数分区EDF算法的灵活性强、网络利用率高的特点,提出一种考虑消息关键性的混合调度算法;在上述研究基础上,利用MATLAB/SimEvents工具箱建立CAN网络模型,并对3种调度算法进行了仿真,当网络利用率达到约85%时,混合调度算法丢包率为0.8%,但丢失的数据不包含硬实时消息,而且成功降低了处理器的额外开销时间,仿真结果表明混合调度算法既能提高系统的实时性,又能减小处理器的运算负担。     

CAN总线混合调度算法及仿真

在CAN总线组成的网络中,随着传输的信息的增多,固定优先级算法已经不能满足系统在信息传输实时性的需求。文章在分析CAN总线信息模型和常用信息调度算法的基础上,提出了一种能有效提高系统性能的混合调度算法,并引入基于利用率的可调度分析方法对该算法进行了理论上的可调度分析。最后,进行了基于LPC2129的仿真平台进行了仿真实验,结果显示了该算法的有效性。     

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

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

改进型EDF调度算法的研究与实现

分析实时系统EDF调度算法的优缺点,为优化报文调度,提出基于EDF的相对价值可提升的且相对价值最大的任务最优先调度算法,采用多个参数计算报文的优先级。实验结果表明,与传统EDF调度算法相比,改进型算法能充分利用总线带宽,对总线报文进行最优化调度。     

煤矿井下增强型定位分站的研究与实现

在复杂的煤矿井下环境中,现有的井下人员定位分站很难实现对井下人员精确、稳定的定位;研究了一种基于CAN总线通讯技术的增强型井下人员定位分站系统,以ARM7为核心控制芯片,结合ZigBee无线通讯技术,并对系统进行Matlab仿真和实验;仿真图像的对比显示增强型驱动CAN总线信号传输传输距离大于标准型CAN总线,传输时间减小了45%;在传输速率为30kbit/s时进行的实验结果表明,增强型的CAN节点幅值4.5V比标准CAN结点的2.1V提高了约1.2倍;仿真和实验的结果表明,增强型CAN总线定位分站信息传输时信号的传输距离增大、信号延迟减弱、幅值衰减明显减小。     

基于 CAN 总线的网络监控系统调度算法研究与改进

分析RM、EDF、MEF-TOD经典实时调度算法的不足。针对实际网络监控系统中通信对象的特点,结合CAN总线协议,设计一种混合调度算法。利用TrueTime工具箱建立网络监控系统模型,对算法进行仿真、分析,证明了该算法的有效性和优良性。     

CAN总线实时调度算法的应用

为满足电动车CAN通信系统在电动车能源管理系统中对实时性和动态分配带宽的要求,提出一种基于事件通道的CAN总线实时调度算法。该算法利用后端通道配置数据库实时修改CAN总线通道组合方式,为具有不同实时性和可靠性要求的数据动态分配传输通道,满足电动车能源管理系统研究和实施阶段对系统可修改性的需求,缩短系统的研发周期。     

电梯控制器中CAN通讯的设计与实现

将CAN总线用于电梯控制器中,实现了基于51的CAN与基于ARM的CAN之间的通讯;在BasicCAN模式下,对CAN2.0A协议帧信息进行实际内容规划,并对通讯过程中的一些重要参数进行设置;以MEDWIN为软件平台,采用C51编程,实现电梯控制器中楼层控制板和轿厢扩展板的功能,主板控制器、轿厢控制器以及轿顶控制器采用ADS1.2作为软件平台;各控制器通过CAN总线进行信息的传输;实验证明,CAN总线可以用于电梯控制器的通讯中,性能可靠,实时性好.     

CAN总线技术在工业报警网络系统中的应用

为满足工业中报警系统对可靠性、抗干扰性方面的严格要求,通过分析工业中各种总线类型的应用背景,以及对目前常见报警类型进行分类,提出了一种基于CAN总线的报警网络结构.在CAN总线底层协议的基础上,设计了一种更加适用于工业报警系统的较高层CAN总线协议,分析了总线数据传输的实时性和报警信息的传输处理,搭建了该通信网络的实际硬件系统.实验论证了该设计方法的有效性.     

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.     

Feasibility analysis of hard real-time periodic tasks

The problem of determining the feasibility of hard real-time periodic tasks is known to be co-NP-complete when there exists a task with relative deadline shorter than its period. Thus “Processor Demand Approach (PDA)” for synchronous task sets has been considered as a practical tool to solve the feasibility problem. PDA determines the feasibility of a task set by checking whether there exists a task whose deadline is missed by a certain time which is computed based on the characteristic of the task set. In this paper, we present a new method for feasibility test by combining PDA with the analysis methods for aperiodic scheduling. It is shown that the number of tests required of the new method to determine the feasibility is never greater than the smallest number of tests the existing algorithm requires. Although our method has pseudo-polynomial time complexity, experimental results show that the new method requires significantly less computation to determine feasibility.     

基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明:BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

一种考虑截止期的METCD业务组合调度方法

海洋设备检定、校准和检测（Marine Equipment Testing, Calibrate & Detection, METCD）业务规模大、紧急情况多,如何对业务进行合理的调配是海洋计量检定行业亟待解决的问题。本文提出了一种考虑截止期的任务组合METCD业务调度方法。在建立业务调度问题数学模型的基础上,采用最早截止时间优先-蚁群算法(EDF-PACO)对模型求解,在最早截止日期的约束条件下对任务组合处理的最优调度方案,达到降低任务总完成时间和减少执行空间浪费双重优化目标。为了验证方法的可行性,以国家海洋局东海标准技术中心的业务为实例,将EDF-PACO算法与传统的最早截止时间优先算法和蚁群算法进行比较,结果表明本文所提出的调度方法在满足截止期的约束条件下能高效地对海洋设备的计量检定业务进行组合调度。     

基于李雅普诺夫优化和深度强化学习的多任务端边迁移

针对多终端、多边缘服务器场景下异构工业任务的端边协同处理问题,提出一种基于李雅普诺夫优化和深度强化学习的多任务端边迁移算法.首先,以联合优化任务迁移决策、迁移比例和传输功率为目标,充分考虑计算频率、传输功率、长期能耗和任务截止期等约束,构建系统长期平均开销最小化问题;由于问题中长期目标及约束中变量在不同时隙相互耦合,难以求解,基于李雅普诺夫优化理论,将长期平均开销最小化问题解耦为独立时隙的策略优化问题;通过马尔可夫决策过程建模,并采用双层竞争深度神经网络架构,提出基于深度强化学习的多任务迁移算法.实验结果表明,所提算法能够稳定收敛,并在长期能耗约束和任务截止期要求下有效降低系统长期平均开销.     

Energy-efficient deadline scheduling for heterogeneous systems

Energy efficiency is a major concern in modern high performance computing (HPC) systems and a power-aware scheduling approach is a promising way to achieve that. While there are a number of studies in power-aware scheduling by means of dynamic power management (DPM) and/or dynamic voltage and frequency scaling (DVFS) techniques, most of them only consider scheduling at a steady state. However, HPC applications like scientific visualization often need deadline constraints to guarantee timely completion. In this paper we present power-aware scheduling algorithms with deadline constraints for heterogeneous systems. We formulate the problem by extending the traditional multiprocessor scheduling and design approximation algorithms with analysis on the worst-case performance. We also present a pricing scheme for tasks in the way that the price of a task varies as its energy usage as well as largely depending on the tightness of its deadline. Last we extend the proposed algorithm to the control dependence graph and the online case which is more realistic. Through the extensive experiments, we demonstrate that the proposed algorithm achieves near-optimal energy efficiency, on average 16.4% better for synthetic workload and 12.9% better for realistic workload than the EDD (Earliest Due Date)-based algorithm; The extended online algorithm also outperforms the EDF (Earliest Deadline First)-based algorithm with an average up to 26% of energy saving and 22% of deadline satisfaction. It is experimentally shown as well that the pricing scheme provides a flexible trade-off between deadline tightness and price.     

实时数据库的事务调度研究

实时数据库系统的事务调度一般只考虑事务的截止期,但是,在很多情况下,它还与数据截止期直接相关。对不同类型调度策略能否充分考虑数据截止期进行了具体分析,对其中存在的规律进行了归纳总结,并且在全面估算事务运行时间的基础上,给出了基于数据截止期和事务截止期的事务处理策略。     

时间约束下可靠性增强的网格工作流调度算法

如何在动态性极强的网格环境中有效调度工作流应用并满足用户的QoS需求是一个难题.传统的基于资源静态特征的启发式调度算法或预留策略缺乏对资源动态服务能力的有效评估而无法保证工作流应用的截止时间约束.本文采用随机服务模型建模网格资源的动态性能并考虑资源内处理单元失效的情况.利用生灭过程描述资源节点中处理单元数目的变化情况并给出了资源节点在任务截止时间内的可靠性评估方法.在此基础上,提出一种可靠性增强的网格工作流调度算法RSA_TC.实验结果表明RSA_TC算法相对于DSESAW和PFAS算法,能有效保证用户截止时间的要求,对动态网格环境有较好的自适应性.     

A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Recently, a growing number of scientific applications have been migrated into the cloud. To deal with the problems brought by clouds, more and more researchers start to consider multiple optimization goals in workflow scheduling. However, the previous works ignore some details, which are challenging but essential. Most existing multi-objective workflow scheduling algorithms overlook weight selection, which may result in the quality degradation of solutions. Besides, we find that the famous partial critical path (PCP) strategy, which has been widely used to meet the deadline constraint, can not accurately reflect the situation of each time step. Workflow scheduling is an NP-hard problem, so self-optimizing algorithms are more suitable to solve it.In this paper, the aim is to solve a workflow scheduling problem with a deadline constraint. We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning (RL) called DCMORL. DCMORL uses the Chebyshev scalarization function to scalarize its Q-values. This method is good at choosing weights for objectives. We propose an improved version of the PCP strategy calledMPCP. The sub-deadlines in MPCP regularly update during the scheduling phase, so they can accurately reflect the situation of each time step. The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline. Finally, we use four scientific workflows to compare DCMORL and several representative scheduling algorithms. The results indicate that DCMORL outperforms the above algorithms. As far as we know, it is the first time to apply RL to a deadline constrained workflow scheduling problem.