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

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

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

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

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

一种有限优先级的静态优先级分配算法

静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义.     

一种基于混合任务集的高能效调度算法

动态电源与频率调整技术能够帮助实时系统显著减少能耗,之前的研究大多聚焦于基于周期性任务的线程调度算法,却很少考虑周期性与非周期性任务混合的模型。同时,尽管基于CPU利用率的DVS算法可以从系统级上减少能耗,但不能保证实时性。本文提出一种新的算法,它结合减慢因子的DVFS调度算法与系统级的DVS技术,融合PID控制器与自适应的权衡策略为软实时系统提供更好的能耗减少方法。该算法的能耗在服务器利用率低于25%的情况下比加州大学提出的算法下降了14.2%²5.9%,周期性任务超过时限率低于3%。     

基于任务复制的静态调度算法研究

任务调度是分布实时系统中的一个关键问题。基于任务复制的静态调度算法是任务调度问题中的研究热点。通过概括任务复制静态调度算法的算法模型以及基本术语后,详细分析比较了几种典型算法。还考虑了优化条件、调度长度、处理器数目以及时间复杂度等研究方向。最后,结合国内外研究现状,提出以减少处理器数目为研究目标。     

实时调度算法分类研究

调度是实时系统的一个研究热点。一个调度算法的好坏决定着实时任务能否在规定的时限内完成。本文对实时调度进行了讨论;研究了经典静态调度算法中的速率单调调度算法,并提出了对该算法的改进;分析了动态调度中的最早截止期最优先算法;最后,对实时调度研究策略方向进行了展望。     

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。     

嵌入式系统的细粒度多处理器实时抢占式调度算法

现有的嵌入式实时系统调度算法一般以任务级为调度单位,对此提出一种细粒度的线程级多处理器实时调度算法。采用DAG图描述实时系统的任务,并采用任务分解法将其分解为线程形式;为任务级调度采用基于干扰的可调度性分析,为线程级调度采用基于工作负载的可调度性分析;将线程的偏移、截止期与优先级作为三个调度目标,设计混合线程级调度算法。仿真实验结果表明,算法对于多线程任务的实时系统具有较好的性能。     

基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值δ的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。     

Increasing processor utilization in hard-real-time systems with checkpoints

Often hard real-time systems require results that are produced on time despite the occurrence of processor failures. This paper considers a distributed system where tasks are periodic and each task occurs in multiple copies which are periodically synchronized in order to handle failures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely executed before the next occurrence of the same task. First, a static scheduling algorithm is proposed which uses periodic checkpoints to tolerate processor failures. Then, the performance of the algorithm is substancially improved employing a mixed strategy which constructs a schedule where high frequency tasks are duplicated, and low frequency tasks are periodically checkpointed. The performance of the solution proposed is evaluated in terms of the minimum achievable processor utilization due to the useful computation of the tasks. Moreover, analytical and simulation studies are used to reveal interesting trade-offs associated with the scheduling algorithm. In particular, if high frequency tasks are less than 70 percent of the total number of tasks then the mixed strategy yields a higher processor utilization than the task duplication scheme.     

单层树型网格下独立任务的周期性调度

提出单层树型网格下单位独立任务的周期性调度方法,单位独立任务是大小相等的独立任务.首先,为单层树型网格下的单位独立任务调度建立线性规划模型,通过分析整数线性规划求解过程,发现一个单层树型网格平台在节点构成不同时,分别具有非饱和态、临界态或冗余态特征;并且,随着网格节点上任务数的增多,线性规划最优解呈线性增长,任务调度具有周期性特性.据此给出非饱和态、临界态或冗余态网格的定义、性质和判定方法,推导出单位独立任务调度的周期长度.最后,分析了周期性调度的时间复杂性,提出一种周期性调度算法Periodic-Sched.实验结果表明,周期性调度是有效的.单位独立任务的周期性调度将大规模的任务调度问题简化为一个周期内的任务调度,降低了调度问题的复杂度.该调度方法适用于对Hadoop平台的Map任务进行调度.     

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.     

Reliability-aware low energy scheduling in real time systems with shared resources

Dynamic voltage scaling (DVS) is a technique which is widely used to save energy in a real time system. Recent research shows that it has a negative impact on the system reliability. In this paper, we consider the problem of the system reliability and focus on a periodic task set that the task instance shares resources. Firstly, we present a static low power scheduling algorithm for periodic tasks with shared resources called SLPSR which ignores the system reliability. Secondly, we prove that the problem of the reliability-aware low power scheduling for periodic tasks with shared resources is NP-hard and present two heuristic algorithms called SPF and LPF respectively. Finally, we present a dynamic low power scheduling algorithm for periodic tasks with shared resources called DLPSR to reclaim the dynamic slack time to save energy while preserving the system reliability. Experimental results show that the presented algorithm can reduce the energy consumption while improving the system reliability.     

一种面向部分可重构系统的实时调度算法

针对当前可重构资源模型难以实现或资源利用率低等不足,提出一种新的资源模型。基于此模型,设计一种能够调度周期和非周期任务的混合实时任务调度算法。把周期任务分成若干组,在FPGA上为每组任务预留一个槽。当有非周期任务到达时,预先调度当前忙碌期内的所有周期任务,在保证当前忙碌期内周期任务满足截止期限且不影响下一个忙碌期内周期任务执行的情况下,把非周期任务调度到某个槽内执行。实验结果表明,该算法能够充分利用可重构资源,满足所有接收任务的截止期限。     

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

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

Allocation and scheduling of precedence-related periodic tasks

This paper discusses a static algorithm for allocating and scheduling components of periodic tasks across sites in distributed systems. Besides dealing with the periodicity constraints, (which have been the sole concern of many previous algorithms), this algorithm handles precedence, communication, as well as replication requirements of subtasks of the tasks. The algorithm determines the allocation of subtasks of periodic tasks to sites, the scheduled start times of subtasks allocated to a site, and the schedule for communication along the communication channel(s). Simulation results show that the heuristics and search techniques incorporated in the algorithm are very effective     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

实时多处理器系统的双优先级调度算法

针对同构多处理器系统提出一种基于双优先级的实时任务调度算法.对偶发任务进行接受测试,进一步提高了系统对偶发任务调度的成功率.模拟结果表明,当多核处理器系统利用率达到极限时,该算法依然能够在完成强实时周期任务的成功调度前提下,保证软实时周期任务和偶发任务具有较高的调度成功率.