一种求解多处理机调度问题的自适应蚁群算法

将蚁群算法应用于求解多处理机调度问题,提出一种自适应蚁群算法．算法以最小化makespan为调度目标,根据蚂蚁留下的信息素指导蚁群在解空间展开全局搜寻,将任务分配在恰当的机器上,并通过自适应调整阈值实现全局探索与精细查找的平衡．实验结果表明算法具有较好的优化性能．     

硬实时任务在多处理机上的动态调度研究

在硬实时任务集能够在多处理机上进行静态调度的基础上,从理论上研究了相同硬实时任务集在多处理机上能够进行动态调度的条件,并给出了动态调度规则,为硬实时任务的动态调度问题提供了一种新的解决途径。     

多处理机调度问题的一种近似算法

对多处理机调度问题Ｐ∥Ｃｍａｘ，给出一种近似算法，大量实例的计算结果表明，本文的算法是非常有效的。     

一种基于IPGSA的多处理机调度算法

多处理机作业调度问题是一个典型的非线性规划问题,针对具有多条件限制的多处理机作业调度问题,提出了一种基于改进的植物生长模拟算法(IPGSA)来搜索问题解的空间.该方法首先将多条件限制和目标函数定义为该问题的数学模型,然后使用改进的植物生长模拟算法搜索问题的解空间,得出最佳的问题求解方案.在实验中,将该方法与粒子群算法、...     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法的基础上,提出一种高效实时容错调度算法。对于具有容错需求的实时任务而言,由实进容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成。在ＥＢＫＣＬ算法中,如何两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ’上,则两个副版本之间允许有时间上的重叠。     

Linux下的实时调度算法

Linux实现了实时进程的概念,但并没有提供有效的任务调度支持;另一方面,RM和EDF等传统的优先级调度算法在实时系统中已经得到广泛应用,但它们对于确定优先级所采用的标准比较简单和片面,容易导致紧急型任务的截止期限不能被满足或系统资源不能被充分利用。基于RM和EDF,文中提出了一种新的实时调度算法SBRD,它的优先级根据重要性和紧急性两个重要因素共同确定。实验表明,与RM和EDF相比,SBRD兼具二者的优点,在保证重要任务顺利执行的前提下,优先执行紧急型任务,以满足更多的任务,更充分的利用CPU资源;与原Linux的实时调度相比,SBRD能更有效的调度实时任务。     

一种基于ED方法的实时事务调度的改进算法

提出一种实时事务表示模型，该模型给出了一种基于ＥＤ方法的实时务调度的改进算法，该算法与ＥＤ相比，可以减少调度对发生的运行时间错误。     

共享存储器多处理机并行计算编译及调度机制

引入并行程序段标记、程序段归并构造并行程序编译思想,设立并行计算调度状态字构造并行计算调度表,提出了一种有效的共享存储器多处理机程序、作业级并行计算编译调度思想及相应的算法。     

一种基于ED方法的实时事务调度的改进算法

提出一种实时事务表示模型，该模型给出了一种基于ＥＤ方法的实时事务调度的改进算法，该算法与ＥＤ相比，可以减少调度时发生的运行时间错误     

多核平台下一种新的实时调度模型

针对当前嵌入式多核平台下的实时调度模型没有考虑实时周期任务之间的制约关系这一不足,提出了一种能够描述实时周期任务之间存在简单制约关系的任务时序图(TTOG)模型,该模型不仅能体现任务实时性需求,还能反映周期任务之间的依赖关系.根据该模型,提出了一种剩余执行时间越短越优先(RETSF)的调度方法.该方法将根据某个周期任务距离时限的剩余执行时间动态地调整调度方案,与先来先服务(FCFS)算法相比较,在提高系统利用率,以及降低时限丢失率方面有很大改善.     

多处理器混合实时任务调度

比例公平调度PFair(Proportionate-Fair)算法和边界公平调度BFair(Boundary-fair)是多处理器系统上周期性实时任务的最佳全局调度方法,但在实际的实时系统中,实时任务往往是周期任务和非周期任务混合的任务系统,在研究PFair和BFair调度算法的基础上,提出了基于服务器思想的公平调度方案,实现了对混合实时任务的调度,同时保证了任务公平地使用共享资源,使得公平调度算法适用于多处理器系统中的混合实时任务调度,扩展了其适用范围。     

一种新的多处理器系统实时容错算法

实时多处理器容错算法是实时系统研究领域的一个重要课题.提出了一个动态处理非周期实时任务的容错算法.提出了对待实时任务的基、副版本采用不同的处理器分配策略.对于基版本,尽量提前任务的开始时间;对于副版本,尽量延迟任务的开始时间.通过实验模拟研究了算法的性能.实验表明,算法调度的成功率跟处理器个数、任务数以及任务计算时间有关.与采用单一处理器分配策略相比,具有较高的调度成功率.     

基于混合遗传算法的并行多处理器系统的任务调度

针对并行多处理器系统的任务调度问题,提出一个新的混合遗传算法(HGA)．HGA使用拓扑排序表的交叉来保证下代的合法性和搜索空间的全局性,为了提高HGA的收敛速度,根据拉马克进化理论,在交叉算子中使用贪婪策略来提高个体的适应值,模拟结果显示HGA的调度结果和算法的时间复杂性都是令人满意的．     

基于粒子群优化的多处理器任务调度算法

对于NP(Non-Polynomial)完全问题,现有的算法主要是启发式算法,性能还有待提高。基于粒子群优化智能算法,提出一种新的任务调度算法,目标是在满足任务之间优先关系的条件下,使所有任务整体完成时间最小。算法将粒子位置和任务高度作为任务的优先级,通过表调度技术生成有效的调度方案,并将调度方案对应的调度长度作为粒子的适应值。首先随机产生一群粒子,然后通过使用全局模型的粒子状态更新策略不断迭代,获得可以接受的任务调度方案。仿真实验结果表明,与遗传算法相比,调度长度提高14.7%,运行时间缩短近一半,特别适合于求解规模较大的多处理器任务调度问题。     

An Adaptive Genetic Algorithm for Multiprocessor Real-time Task Scheduling

Real-time task scheduling is of primary significance in multiprocessor systems. Meeting deadlines and achieving high system utilization are the two main objectives of task scheduling in such systems. In this paper,we represent those two goals as the minimization of the average response time and the average task laxity. To achieve this, we propose a genetic-based algorithm with problem-specific and efficient genetic operators. Adaptive control parameters are also employed in our work to improve the genetic algorithms' efficiency. The simulation results show that our proposed algorithm outperforms its counterpart considerably by up to 36% and 35% in terms of the average response time and the average task laxity,respectively.     

多处理器系统最优任务分配问题的一个近似算法

多处理器系统上的最优任务分配的研究是有效利用系统资源处理实际问题的热点课题,文章在考虑任务可分和任务不可分的两种多处理器最优任务分配问题上,首次提出了这两个问题在处理器的个数大于１时都是ＮＰ－完全问题,其次给出了一个有效的近似算法,     

一种多特征综合的实时调度算法

随着科学技术的发展，在国民经济的各个领域中，实时调度算法有着广泛的应用，如交通管制、敏捷制造和电子商务等．实时调度算法主要包括：速度单调算法RM(Rate Monotonic)、截止期最早优先算法EDF(Earliest Deadline First)、最小裕度算法LSF(Least Slack First)、最高价值优先算法HVF(Highest Value First)、     

周期实时任务在多处理器下的可调度条件

研究硬实时周期任务在并行等同多处理器下的可调度问题．在任务/处理器静态绑定和周期任务静态优先权配置策略下，依据单处理器情形下的最优配置RM策略作为一项任务在单个处理器上的可配置条件，给出了以实时任务集合的任务数、利用率和与利用率递减排序为特点的在多处理器环境下的可调度新判据．新判据拓宽了基于阈值判据的可判定范围．最后通过实例分析说明新判据的有效性．