The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively upon a multiprocessor platform using the earliest-deadline first scheduling algorithm. Supported in part by the National Science Foundation (Grant Nos. CCR-9988327 and ITR-0082866). Sanjoy Baruah is a professor of Computer Science at the University of North Carolina at Chapel Hill. He received his Ph.D. from the University of Texas at Austin in 1993. His research and teaching interests are in scheduling theory, real-time and safety-critical system design, and resource-allocation and sharing in distributed computing environments.     

面向流程工业的批在线调度问题

从钢铁生产热轧流程中提炼出了在同构并行机上的批在线调度问题,它是流程工业中MES的重要环节。从理论上给出算法并研究了算法的性能。工件以批的形式到达,目标函数是使工件的最大完成时间最小。当一个批到达时,将这一批中的工件分成若干组,要求在同一组中的工件可以具有不同的开始加工时间但必须具有相同的完成时间。通过将批调度与在线调度的结合,给出了最坏情况比（竞争率）分别为m／（1＋（m-1）ε）,m（1-ε）／（1-ε）,m／（1＋gε）的批在线调度算法。     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

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

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

A New Approach for Scheduling of Parallelizable Tasks in Real-Time Multiprocessor Systems

In a parallelizable task model, a task can be parallelized and the component tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and also obtain better processor utilisation compared to non-parallelized tasks. Non-preemptive parallelizable task scheduling combines the advantages of higher schedulability and lower scheduling overhead offered by the preemptive and non-preemptive task scheduling models, respectively. We propose a new approach to maximize the benefits from task parallelization. It involves checking the schedulability of periodic tasks (if necessary, by parallelizing them) off-line and run-time scheduling of the schedulable periodic tasks together with dynamically arriving aperiodic tasks. To avoid the run-time anomaly that may occur when the actual computation time of a task is less than its worst case computation time, we propose efficient run-time mechanisms.We have carried out extensive simulation to study the effectiveness of the proposed approach by comparing the schedulability offered by it with that of dynamic scheduling using Earliest Deadline First (EDF), and by comparing its storage efficiency with that of the static table-driven approach. We found that the schedulability offered by parallelizable task scheduling is always higher than that of the EDF algorithm for a wide variety of task parameters and the storage overhead incurred by it is less than 3.6% of the static table-driven approach even under heavy task loads.     

一种基于DLS和ACO的平台资源规划方法

平台资源规划方法是作战任务规划的重要组成部分,为作战提供资源分配方案。描述了作战任务、平台以及它们之间的关系,建立了以最小化全部任务完成的截止时间和最大化平台资源的利用率为目标的数学模型。设计了用于求解此模型的动态列表规划(Dynamic List Scheduling,DLS)与蚁群算法(Ant Colony Optimization Algorithm,ACO)相结合的算法,其描述了任务选择方法、ACO的二进制编码方案及候选解构造策略,设计了不可行候选解的修正策略和信息素更新方法,构造了包含任务选择平台的时间优先系数、平台功能能力优先系数和后续任务对平台需求程度3个因素的适应度函数。针对作战想定进行了仿真计算,结果表明,基于DLS和ACO的平台资源规划具有良好的规划效果,相比于他人算法,其具有更少的全部任务完成截止时间和更高的平台资源利用率。     

VxWorks下基于多任务调度的分析和研究

VxWorks操作系统是一个功能强大、而且独立于处理器的实时操作系统,它具有真正微内核的相当小的层次结构。稳定、可靠、高性能的内核以及友好的用户开发环境等优点使得VxWorks被广泛应用于高精尖以及实时性要求极高的领域。文中在分析VxWorks内核的多任务调度以及相应的调度算法的基础上,提出了基于优先级的多任务资源共享问题的解决方案,并介绍了一个解决优先级倒置的方案实例。     

Linux与VxWorks任务调度机制分析

分析了Linux和VxWorks两种多任务操作系统任务调度机制的异同,从任务控制块、调度的时机、调度的优先级和调度的策略方面进行了详细的分析和对比。分析了VxWorks和Linux在POSIX1003．1b调度标准实现上的差异。     

VC中列表控件CListCtrl性能测试与分析

在VC环境中选用正交试验测试列表控件CListCtrl,针对显示记录数,对列表控件的性能进行测试与分析,给出了电脑硬件软件环境对显示记录数的影响,采用逐步回归分析得出列表控件显示记录数与各因素之间的关系。     

FC-AE网络数据发送调度算法的设计与实现

针对FC-AE(Fibre Channel Avionic Environment)网络中缺乏实时有效的调度算法,提出一种基于位图映射的动态优先级调度算法(Bitmap-based Mapping of Dynamic Priority Scheduling-BMDPS),根据发送任务等待时间动态改变优先级,同时将不同优先级的发送任务映射到位图表中,来实现高优先级任务的发送调度;通过与"先来先服务"和"时间片轮转"两种调度算法进行对比,证明了该算法具有较小的平均响应时间和平均周转时间,且在最差的条件下,能保证FC-AE网络数据传输的实时性。     

实时多处理器动态调度算法的研究与应用

实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题。该文首先介绍了实时多处理器动态调度的几种方法,并对这些方法进行了分析、对比和研究。然后针对水下航行器制导系统多任务特点,讨论了水下航行器制导系统的动力学、运动学模型及控制、导引方程,并对其任务进行详细划分。最后结合任务的偏序关系、运行时间及截止期,对水下航行器多任务模型进行了实时多处理器动态调度,给出最佳调度方案。     

Stability of Impulsive Stochastic Neutral Partial Differential Equations With Infinite Delays

In this paper, we study the existence and asymptotic stability in the pth moment of the mild solutions to impulsive stochastic neutral partial differential equations with infinite delays. Sufficient conditions ensuring the stability of the impulsive stochastic system are established. The results are obtained via the Banach fixed point theorem.     

Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks

In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two existing approaches: the Skip-Over task model and the EDL (Earliest Deadline as Late as possible) aperiodic task server. The objective is to provide two on-line scheduling algorithms, namely EDL-RTO and EDL-BWP, in order to minimize the average response time of soft aperiodic requests, while ensuring that the QoS (Quality of Service) of periodic tasks will never be less than a specified bound. We also extend our results to the acceptance of sporadic tasks (i.e., aperiodic tasks with deadlines). We show that these novel scheduling algorithms have better performance compared to related algorithms regarding aperiodic response time and acceptance ratio. Audrey Marchand guaduated in Computer Engineering at the Ecole polytechnique of the University of Nantes (France), in 2002. She is currently a PhD student at the University of Nantes. Her research interests include real-time scheduling theory, aperiodic service mechanisms, quality of service guarantees in soft real-time systems, and Linux-based real-time operating systems and applications. Maryline Chetto received the degree of Docteur de 3ème cycle in control engineering and the degree of Habilitée à Diriger des Recherches in Computer Science from the University of Nantes, France, in 1984 and 1993, respectively. From 1984 to 1985, she held the position of Assistant professor of Computer Science at the University of Rennes, while her research was with the Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes. In 1986, she returned to Nantes and is currently a professor with the Institute of Technology of the University of Nantes. She is conducting her research at IRCCyN. Her main research interests include scheduling and fault-tolerance technologies for real-time applications. She has published more than 60 journal articles and conference papers in the area of real-time operating systems. She is the leader of a French national R&D project, namely Cleopatre, supported by the French government, which aims to provide free open source real-time solutions.     

Stability analysis of buffer priority scheduling policies using Petri nets

A Petri net approach to determining the conditions for stability of a re-entrant system with buffer priority scheduling policy is described in this paper.The concept of buffer boundedness based on the dynamic behavior of the markings in the system model is emphasized.The method is used to demonstrate the stability of the first buffer first served(FBFS)and the last buffer first served(LBFS)scheduling policies.Finally a sufficient condition for instability of systems with a positive feedback Joop(PFL) is established,and an example is given.     

嵌入式Linux中调度算法的实现及优化

本文论述实时嵌入式Linux的多任务调度算法实现机制。结合嵌入式操作系统的特点，重点介绍基于优先级驱动嵌入式系统的一种实时调度优化算法的实现机制，讨论如何在GPL下充分利用现有的实时调度算法开发适合嵌入式Linux的优化调度方法，并提出了具体的实现思路。     

数据流QoS自适应框架调度算法的研究与实现

在数据流QoS自适应框架中,针对如何为具有截止期和重要性两个特征参数的流数据分派优先级,在讨论了了当前调度算法优缺点的基础上,提出了称为截止期-重要性优先DIF（deadline-importance first）的实时调度算法,并利用链表给出了算法的实现.实验结果表明,在所有负载条件下DIF算法相对于EDF（earliest deadline first）算法、HVF（highest value first）算法和CDF（criticalness-deadline first）算法,在性能方面具有明显改善,特别在系统过载的情况下,能够优雅地降级.     

氧化铝配矿调度方法研究及软件实现

为了解决氧化铝配矿调度过程中不确定性因素多、计算工作量大、难以获取最优方案以及生产结构不合理造成能源浪费等问题,以能耗最小为目标函数,结合生产经验,建立了烧结法和拜耳法统一配矿的优化调度模型,并针对模型中存在的非线性、多约束和多目标特点,运用了一种引入变异算于的混合粒子群算法进行寻优.在充分考虑了软件工业实用性及界面友...     

电压稳定在线分析与决策系统

本文致力于开发一种适用于大型电力系统的静态电压稳定实时快速分析及预防调度软件,结合目前电压稳定分析方法在实际系统中的应用,考虑实时分析的速度与精度要求,使用一种基于灵敏度约束与局部曲线拟合相结合来快速寻找崩溃点的方法与基于优化发电功率分配因子来提高系统负荷裕度的方法,研制开发了一套基于B／S模式的“在线电压稳定快速分析及预防调度”软件．使用该软件对湖南电网静态稳定性进行算例分析,验证该软件能满足在线分析的速度与精度要求．     

Fundamentals of Scheduling and Performance of Video Tape Libraries

Robotic tape libraries are popular for applications with very high storage requirements, such as video servers. Here, we study the throughput of a tape library system, we design a new scheduling algorithm, the so-called Relief, and compare it against some older/straightforward ones, like FCFS, Maximum Queue Length (MQL) and an unfair one (Bypass), roughly equivalent to Shortest Job First. The proposed algorithm incorporates an aging mechanism in order to attain fairness and we prove that, under certain assumptions, it minimizes the average start-up latency. Extensive simulation experiments show that Relief outperforms its competitors (fair and unfair alike), with up to 203% improvement in throughput, for the same rejection ratio.     

基于 WebGL 的多AGV物流调度仿真系统的研究与应用

针对K公司汽车总装生产线中多AGV(Automated Guided Vehicle)电量分配不均、路径冲突、AGV利用率低等物流调度问题,为了提高K公司生产线中多AGV物流调度的效率,设计了一种多AGV物流调度仿真系统;利用WebGL(Web Graphics Library) 技术建立了整个生产线场景的三维模型;系统能够自动给AGV分配任务,在AGV执行任务时,将AGV的电池电量和AGV路径规划问题考虑到物流调度系统中;该系统实现了对物流调度系统中AGV运输任务的合理分配,提高了物流调度的效率;经实际应用满足了K公司汽车总装生产线多AGV物流调度工程上的应用。