基于Pfair的分布式实时调度策略Linux下实现

任务调度策略是嵌入式分布式实时系统关键问题之一,以Pfair公平调度为代表的全局调度技术是当前研究的热点,调度方法要在实际中得到应用,需要与具体的操作系统相结合。分析了分布式实时系统的调度理论,比较研究了几种Pfair算法,通过修改Linux内核的数据结构和调度函数,初步实现了Pfair的PD^2算法,实验证明达到了预期的实验结果。     

一种分布式实时系统任务调度算法的设计

结合分布式系统和实时系统的特点,分析了分布式系统任务调度算法和实时系统任务调度算法,为了能够较好地实现系统的并行性能、实时任务的调度性能以及网络的负载平衡,提出一种将分布式系统任务调度算法和实时系统任务调度算法想结合的算法,采用层次式调度算法以及动态权值的轮转调度算法和速率单调调度算法相结合,在队列权值固定的实验基础上,采用随机改变队列权值的算法,实验证明该随机改变队列权值的算法能够更好地调度任务.     

分布式实时系统任务与消息综合调度算法研究

分布式实时系统作为一种典型的实时系统应用受到了关注，目前提出了许多分布式实时系统的调度策略。但是，绝大多数策略往往忽略了全局任务调度时的消息调度。本文提出一种综合任务调度和消息调度的算法，提供了一种实时系统调度的新思路。     

分布式实时系统中的预测调度算法

对于分布式实时系统中的周期性任务,人们提出了一系列静态分配调度算法,有效地解决了各种特定条件下的任务分配和调度问题.这些算法的主要特点是,它们均要求被调度任务的特征参数为已知条件.然而在很多实时系统中,周期性任务的运行时间或任务数量常常是一些具有一定规律的随机过程,因而上述静态算法的效能将受到限制.在分析了特定应用背景中的处理流程之后,抽象得到两类随机任务模型,针对这两类模型介绍了在分布式实时系统中已经得到应用的静态分配调度算法SAA(static allocation algorithms),进而提出了多任务分配调度的预测算法PAA(predicting allocation algorithm).它根据周期性任务执行时间或子任务数量的统计特性,实现任务参量的合理预测和多任务的动态调度,以提高系统的实时性能.仿真结果表明,对于两类任务模型,PAA算法与SAA算法相比,在任务完成时间、负载均衡度、系统响应时间及任务夭折率等多方面均有显著改善.     

基于启发式算法降低比例公平调度开销策略

在多处理器系统中已经证明了比例公平(proportion fair, Pfair)算法是调度周期任务最优的全局调度算法。然而在该算法的最坏执行情况下,任务在每个调度时刻均产生切换或迁移,导致系统开销过大。针对这一问题,对Pfair算法进行深入研究后发现,任务的分配过程是一个重要原因。基于此,提出基于启发式算法的模拟退火比例公平(simulated annealing-proportion fair, SA-Pfair)调度算法,即在Pfair算法做出调度决策后,用启发式算法将任务分配给处理器,以弥补原算法的不足。最后,采用LITMUS-RT平台对SA-Pfair算法和以此为基础设计的调度器进行仿真。结果表明,新算法在一定程度上减少了任务的切换次数以及50%以上的任务迁移总量,且能够有效地降低调度过程中的系统开销。     

一种两级分布调度算法

针对传统分布式调度算法研究中将调度策略与机制相分离的不足，本文提出了两级分布调度算法，它能较好地结合两种调度机制（远程执行与进程迁移），提高了系统的性能。     

单处理器系统的实时调度算法研究

实时调度算法是实时系统中的关键技术.文章在研究单处理器系统中常用实时调度算法:固定优先级调度算法和动态优先级调度算法基础上,详细分析了常用固定优先级调度算法RM、DM算法和动态优先级调度算法EDF、LLF和MLLF算法的运算过程和使用条件,提出了各个算法在实际应用中存在的问题,为实际应用中选择何种实时调度算法确定了依据.     

DRT-UNIX系统的任务调度

任务调度是分布式实时系统的核心问题之一.文章概述了实时系统的任务调度,结合DRT-UNIX系统的实际情况,提出了一种任务调度算法,并对算法的优点进行了分析.     

多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

组合窗口约束(m,k)＾的实时系统分析与研究

在研究基于窗口约束(m,k)模型的实时系统的基础上,提出一种基于非重叠组合窗口约束的实时系统.通过对该实时系统的可调度性条件的研究,提出一种新的组合窗口约束(m,k)＾的调度算法,该算法充分利用组合约束的特点,考虑本次调度对该窗口的可调度的影响来确定任务的优先级,并以此来提高任务的可调度性、减少组合窗口限制违例.仿真试验表明该算法在组合窗口约束的调度上,优于传统的独立比较两个约束确定优先级的调度算法.     

信息物理系统中基于保护阈值的实时调度算法研究

信息物理融合系统CPS是一种融合计算、通信与控制的新型复杂实时分布式系统,系统中计算过程和物理过程在开放环境下持续交互、深度融合。为了对物理世界的信息作出实时反馈,系统一般会采用抢占式调度的方法,保障关键任务能够在截止期前完成。但是,分布式环境中抢占式调度方式容易导致频繁的任务切换,影响系统的实时性。提出了基于保护阈值的调度算法,通过建立保护阈值模型,最大化低优先级任务的执行时间,减少任务切换次数。通过实验验证,算法有效地减少了任务切换次数,提高了CPS系统的实时性能。     

基于YARN的分布式资源动态调度与协同分配系统

Storm on YARN是目前主流的分布式资源调度框架,但其存在需要人工干预和无法根据资源可用性实时调整系统资源的不足。根据流数据处理的实时延迟计算系统负载情况,在Storm平台上基于YARN设计分布式资源调度和协同分配系统。建立包含系统层和任务层的双层调度模型,系统层通过对流数据处理负载的实时监测进行资源分配预测,任务层利用ZooKeeper和YARN对集群资源的高效管理能力进行动态资源管理。实验结果表明,该系统可以实时调整集群资源分布,有效减小系统延迟。     

基于Matlab环境的网络控制系统仿真平台

网络控制系统NCS(NetworkedControlSystem)是一种分布式实时控制系统,网络控制系统的设计与研究涉及系统控制与网络调度两个方面,目前集成的控制与调度仿真工具很少。该文对网络控制系统的仿真平台进行了分析,给出了Matlab构建的网络控制系统框架,分析了网络控制系统仿真模型,介绍了一种基于Matlab的网络控制系统的理想仿真工具TrueTime。     

高性能路由器操作系统HEROS的设计与实现

实时分布式操作系统是高性能分布式路由器的控制核心 ,为了保证路由器系统的整体性能和安全性 ,本文设计并实现了实时分布式操作系统 HEROS(Highly Efficient Router Operating System) .HEROS基于微内核体系结构 ,其多任务内核实现了基于优先级的抢先式调度 ,高效率的任务间同步和通信原语 ,实时的中断处理和高效的内存管理机制 .为了更好地服务于分布式路由器体系结构 ,HEROS基于 Compact PCI总线实现了一种分布式通信机制和面向网络协议的高性能的缓冲管理机制 .目前 ,基于 HEROS的高性能安全路由器原型系统已经设计完成     

Simulation of resource synchronization in a dynamic real‐time distributed computing environment

Today, more and more distributed computer applications are being modeled and constructed using real‐time principles and concepts. In 1989, the Object Management Group (OMG) formed a Real‐Time Special Interest Group (RT SIG) with the goal of extending the Common Object Request Broker Architecture (CORBA) standard to include real‐time specifications. This group's most recent efforts have focused 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 the authors have developed which meet the requirements of dynamic distributed real‐time systems as specified by Dynamic Scheduling Real‐Time CORBA (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. In order to evaluate the performance of the proposed protocols, we analyzed each protocol's schedulability. Since the schedulability of the system is affected by numerous system configuration parameters, we have designed simulation experiments to isolate and illustrate the impact of each individual system parameter. Simulation experiments show the proposed protocols have better performance than one would realize by applying a schema that utilizes dynamic priority ceiling update. Copyright © 2004 John Wiley & Sons, Ltd.     

分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法,该算法能保证硬实时任务不丢失死线,并易于在分时系统中实现。以分时EDF算法为基础,提出一种新的CPU层次调度算法－－HRFSFQ,该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。     

Framework of agent-based intelligence system with two-stage decision-making process for distributed dynamic scheduling

The advent of multiagent systems, a branch of distributed artificial intelligence, introduced a new approach to problem solving through agents interacting in the problem solving process. In this paper, a collaborative framework of a distributed agent-based intelligence system is addressed to control and resolve dynamic scheduling problem of distributed projects for practical purposes. If any delay event occurs, the self-interested activity agent, the major agent for the problem solving of dynamic scheduling in the framework, can automatically cooperate with other agents in real time to solve the problem through a two-stage decision-making process: the fuzzy decision-making process and the compensatory negotiation process. The first stage determines which behavior strategy will be taken by agents while delay event occurs, and prepares to next negotiation process; then the compensatory negotiations among agents are opened related with determination of compensations for respective decisions and strategies, to solve dynamic scheduling problem in the second stage. A prototype system is also developed and simulated with a case to validate the problem solving of distributed dynamic scheduling in the framework.     

基于μC/OS-II的无人驾驶车辆分布式车体控制系统开发

设计了一款无人驾驶智能车的分布式底层控制系统,系统中的模块均以飞思卡尔S12DG12816位单片机为核心,并在单片机中移植了μC/OS-II实时操作系统,优化了模块的任务分配及调度,同时极大地增强了系统的可靠性和稳定性,也使系统硬件变得模块化,功能升级和拓展更为灵活。     

On the convergence of the holistic analysis for EDF distributed systems

Dynamic scheduling techniques, and EDF (Earliest Deadline First) in particular, have demonstrated their ability to increase the schedulability of real time systems compared to fixed-priority scheduling. In distributed systems, the scheduling policies of the processing nodes tend to be the same as in stand-alone systems and, although few EDF networks exist, it is foreseen that dynamic scheduling will gradually develop into real-time networks. There are some response time analysis techniques for EDF scheduled distributed systems, mostly derived from the holistic analysis developed by Spuri. A major factor influencing the response time is the release jitter of each task, which is the maximum variation suffered by the release time of the task jobs. The convergence of the holistic analysis in the context of EDF distributed systems with shared resources had not been studied until now. There is a circular dependency between the task release jitter values, response times and the preemption level ceilings of shared resources. In this paper we present an extension of Spuri’s algorithm and we demonstrate that its iterative formulas are non-decreasing, even in the presence of shared resources. This result enables us to assert that the new algorithm converges towards a solution for the response times of the tasks and messages in a distributed system.¹