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

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

一种适应多核处理器核间通信机制的设计

随着单芯片上集成处理器内核数量的增加,在支持多核处理器的应用程序方面,核间通信变得更加重要.通过分析多核运行任务特点,根据处理核上运行任务功能的不同,将处理核分成两类:控制核和计算核.根据对核的分类,提出了一种新的核间通信模型,该模型提供了三种不同的通信通道.运用这三条通道,把应用程序的I/O部分从计算核迁移到控制核来提高多核的利用率,实验结果表明该方式有效提高核间协作以及核间通信的效率,提升处理器的利用率.     

一种调度In-Tree任务图的算法

In-Tree任务图可用来表示归并、求和等分治算法的很多问题,该文针对这种任务图提出一种分层调度算法,利用队列存放被调度的任务,在同层任务调度中,优先把前驱不为空的任务调度到其一个前驱处理器上执行,只有前驱为空的任务才考虑是否分配新的处理器。实验表明,与以前的算法相比,该算法在调度长度相当的情况下,使用了更少的处理器。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上，建立了一种混合型实时容错模型，提出一种调度算法不仅可以调度有容错需求的周期任务，同时也能够调度无容错需求的周期任务和非周期非实时任务，实现了调度混合型任务的目的。     

基于任务间通信的嵌入式组件模型

通用组件技术如COM、CORBA等技术已较完善,但是它们应用于嵌入式系统却有很多局限,如需要庞大的底层基础支持、没有实时调度能力等。根据嵌入式系统以及应用的特点,分析了现有的通用组件模型和当前嵌入式组件技术的发展现状,提出了一种新的嵌入式组件模型——基于任务间通信的嵌入式组件模型。该模型具有资源消耗小、有实时调度能力、无须大量底层支持的优点,该文介绍了系统框架和实现方法以及组件开发方法。     

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

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

一种基于任务全局迁移的静态调度算法

任务调度是分布实时系统中的一个关键问题.TDS等典型算法在优化条件下可得到该问题调度长度上的最优解.但是TDS等算法在节点分配时存在节点选择范围和节点执行时间范围的局限,无法最小化算法所需处理器数目.任务全局迁移调度算法GTT（global task-transferring）在保证调度长度最优的前提下,从全局范围内选择并调度任务节点,有效利用了处理器,可最小化调度所需处理器数目.优化条件下对各种算法的调度实验表明,GTT算法在加速比和效率上比TDS等同类算法有显著提高.GTT算法的时间复杂度是O（d ｜ V｜^ 2）.这里｜V｜是DAG图中的节点数,d是图中各节点入度或出度的最大值.     

一种基于调度簇树的周期性分布实时任务调度算法

本文针对现有的基于任务复制的静态调度算法在调度周期性分布实时任务时存在的缺点,提出了一种称之为调度簇树（SCT）的新的结构并研究了其特性,在此基础上给出了一种基于SCT树的周期性分布实时任务调度算法（SAS）。通过与OSA算法进行比较的实验结果表明,SAS算法可实现调度长度向上最接近分布实时任务周期,最大程度减少所需顸留处理器数目,大大提高分布实时系统的处理器利用率,同时并不增加调度算法的复杂度。     

一种混合优先级的防危调度算法

为增强实时系统任务过载时的防危性,提出一种混合优先级的防危调度算法,其优先级由相对截止期优先级和相对松弛度优先级组成,通过相对松弛度预测任务的可完成性,并采用完全抢占方式防止处理器资源的竞争抖动。仿真结果表明,该算法可充分利用处理器资源,能在发生瞬时过载时有效降低任务的截止期错失率。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。     

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法-PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.     

控制系统中强实时任务的调度

文章通过对控制系统中强实时任务进行分析,指出系统存在的各类强实时任务。针对控制系统中任务的特点,提出了一种实时任务调度方法。对这种调度算法进行了可调度性分析,指出实时控制系统中任务可调度的条件。     

多特征参数的任务模糊调度算法

针对任务具有特征参数多和特征参数不确定性的特点,提出了一种基于模糊理论的任务调度算法。利用模糊集合来描述任务的不确定性特征;使用多层模糊综合评判和最大隶属度原理来综合考虑任务的多个特征参数并确定任务的优先级;采用动态构建多层评判模型的调度策略来减小任务优先级评判的失效率。仿真表明,该算法提高了任务调度的成功率,降低了任务截止期的错失率和任务优先级评判的失效率。该方法可应用于优先等级有限的实时系统任务动态调度中。     

The EDL Server for Scheduling Periodic and Soft Aperiodic Tasks with Resource Constraints

In this paper, we are concerned with the problem of serving soft aperiodic tasks on a uniprocessor system where periodic tasks are scheduled on a dynamic-priority, preemptive basis and exclusively access to critical sections. Scheduling of tasks is handled by the Dynamic Priority Ceiling Protocol working with an Earliest Deadline scheduler. Our analysis determines the maximum processing time which may be stolen from periodic tasks without jeopardizing both their timing constraints and resource consistency. It provides the basis for an on-line scheduling algorithm, the EDL Server, to deal with the minimization of response times for soft aperiodic tasks.     

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

一种批优化调度策略的实时异构系统的集成动态调度算法

针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.     

应用于实时系统的RMS算法的改进

本文阐述了以PLC为核心的HGJD001实验台电气控制系统，并采用上位计算机实现对实验台运行状态的通讯监测。     

容错多处理机中一种高效的实时调度算法

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.     

一个有效的Join任务图的调度算法

已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳.因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数.实验结果表明,与其他算法相比,该算法的调度长度较短且使用的...     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．