Real-time scheduling of periodic tasks with processing times and deadlines as parametric fuzzy numbers

Task scheduling is very important in real-time systems as it accomplishes the crucial goal of devising a feasible schedule of the tasks. However, the uncertainty associated with the timing constrains of the real-time tasks makes the scheduling problem difficult to formulate. This motivates the use of fuzzy numbers to model task deadlines and completion times. In this paper a method for intuitively defining smooth membership functions (MFs) for deadlines and execution times has been proposed using mixed cubic-exponential Hermite interpolation parametric curves. The effect of changes in parameterized MFs on the task schedulability and task priorities are also reported. A new technique is proposed based on the concept of dynamic slack calculation to make the existing model more practical and realistic. Examples are given to demonstrate the more satisfactory performance of the new technique.     

计算机控制中的模糊调度设计

研究了具有模糊截止期的多控制任务的实时调度问题,提出了奉献度的概念和最大奉献优先（LDF）的调度策略．为了减小因任务间频繁切换造成的系统开销。提出了基于抢占阈值的最大奉献优先（TLDF）调度策略．最后,通过仿真比较了LDF和TLDF两种调度策略,实现了具有模糊截止期的控制任务调度,在减少并均衡控制性能损失的同时提高系统计算资源的使用率．     

实时控制任务的模糊反馈调度系统研究

分析了实时控制任务的控制性能在不同控制阶段与处理器利用率需求间的关系,提出一种实时控制任务的模糊反馈调度系统.模糊控制器通过监测实时控制任务的误差及其变化率,查询模糊决策表,动态决定任务的优先级,反馈调度器根据优先级分配任务的利用率.仿真结果表明，在计算资源有限时，该方法能有效改善实时控制任务的控制性能.     

一种开放混合实时系统的开放自适应调度算法

开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.     

模糊动态抢占调度算法

针对不确定任务特征,提出应用模糊理论进行动态抢占调度,用语言模糊集来描述任务的不确定特征和不同的优先级等级,利用最大隶属度原理确定任务的优先级等级,采用优先调度高优先级等级任务的调度策略提高重要任务的调度成功率,实现具有不确定任务特征的抢占调度,与传统的EDF和LSF算法相比较,仿真表明,所提算法能够提高重要任务的调度成功率,并降低重要任务的截止期错失率;同时,任务间的平均切换次数大大小于LSF的平均切换次数,而与EDF保持相当,该方法可应用于计算机控制系统的控制任务调度,并借鉴于其它具有不确定任务特征或具有有限优先级等级的实时调度问题研究中。     

Real-time task scheduling by multiobjective genetic algorithm

Real-time tasks are characterized by computational activities with timing constraints and classified into two categories: a hard real-time task and a soft real-time task. In hard real-time tasks, tardiness can be catastrophic. The goal of hard real-time tasks scheduling algorithms is to meet all tasks’ deadlines, in other words, to keep the feasibility of scheduling through admission control. However, in the case of soft real-time tasks, slight violation of deadlines is not so critical.In this paper, we propose a new scheduling algorithm for soft real-time tasks using multiobjective genetic algorithm (moGA) on multiprocessors system. It is assumed that tasks have precedence relations among them and are executed on homogeneous multiprocessor environment.The objective of the proposed scheduling algorithm is to minimize the total tardiness and total number of processors used. For these objectives, this paper combines adaptive weight approach (AWA) that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point. The effectiveness of the proposed algorithm is shown through simulation studies.     

Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives

This paper presents the taxonomy of real-time systems with special emphasize on pre-run-time scheduling problem. Firstly, we present real-time systems, real-time tasks, timing, precedence and exclusion constraints. Then, we describe the problem of pre-run-time scheduling of tasks under constraints. After that, we present the most existing efficient techniques to deal with the latter problem. We summarize the discussion of existing techniques and possible research perspectives after surveying the Artificial Intelligence’s point of view about the problem of pre-run-time scheduling of real-time tasks. The Artificial Intelligence survey includes Constraint Satisfaction Problems class since pre-run-time scheduling belongs to the latter class. The Artificial Intelligence survey includes also Path-finding Problems from which intelligent algorithms could be observed such as Learning-Real-Time-A1(LRTA1) thanks to its important properties (optimality, linear space complexity and determinism). The development of an algorithm like LRTA1 to solve Constraints Satisfaction Problems and particularly the pre-run-time scheduling of real-time tasks problem is one clear research direction to deal with large-scale real-time systems. The overall objective of this paper is to show what are the perspectives to Artificial Intelligence literature that could be beneficial firstly to Artificial Intelligence community itself and secondly to real-time systems community.     

基于对象分布式实时系统约束的一致性研究

在分布式实时系统中,时间约束规格的一致性是解决任务分配和调度等关键问题的必要前提。该文给出了一种基于对象分布式实时系统调度的通用模型,并对该模型进行了形式化描述。该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时约束的不足,允许从方法和活动上描述所需的约束,降低了单一约束描述的繁杂程度。为了解决使用该模型进行约束规格的一致性问题,该文给出了绝对时间约束、相对时间约束、一致性约束以及相对时间约束和一致性约束之间的一致性判定的必要条件。     

Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints

In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n ² N ³) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.     

Linux2．6进程调度策略分析

分析了Linux2．6进程调度密切相关的一些数据结构,详细描述了进程调度的时机、调度的策略和调度的算法上的策略,这些改进使得Linux2．6进程调度程序实现了O（1）调度算法,支持抢占式调度,并且增强了对实时任务和SMP的支持。     

Rate-monotonic analysis for real-time industrial computing

Issues of real-time resource management are pervasive throughout industrial computing. The underlying physical processes of many industrial computing applications impose explicit timing requirements on the tasks processed by the computer system. These timing requirements are an integral part of the correctness and safety of a real-time system. It is tempting to think that speed (for example, processor speeds or higher communication bandwidths) is the sole ingredient in meeting system timing requirements, but speed alone is not enough. Proper resource-management techniques also must be used to prevent, for example, situations in which long, low priority tasks block higher priority tasks with short deadlines. One guiding principle in real-time system resource management is predictability, the ability to determine for a given set of tasks whether the system will be able to meet all of the timing requirements of those tasks. Predictability calls for the development of scheduling models and analytic techniques to determine whether or not a real-time system can meet its timing requirements. The author illustrates an analysis methodology, rate monotonic analysis, for managing real-time requirements in a distributed industrial computing situation. The illustration is based on a comprehensive robotics example drawn from a typical industrial application     

一种实时系统中的多任务可预测调度算法

通过研究实时系统中可能出现的任务类型,提出了一种实时系统任务模型和基于这个模型的多任务调度算法,分析了该算法下所有周期任务和非周期任务可调度的条件。该算法结合了DMS(Dcadlinc Monotonic Scheduling)和DD(Deadline Driven)算法,在保证系统中周期任务执行的前提下,也使非周期任务获得了,较好的响应时间。     

强实时环境下调度非周期任务的时限寻优方法

文章提出了强实时环境下调度弱时限非周期任务的时限寻优方法（ＤＯＡ）,该方法在保证周期任务和偶发性任务满足时限要求的前提下,使非周期任务的响应时间达到最优。它还可根据实时应用的需要对算法的执行性能和计算复杂度进行折衷调整。仿真实验表明,ＤＯＡ与现有的动态调度算法相比,使非周期任务响应时间更短,同时它收敛快,额外开销小,计算复杂度低,实现方便,因此是强实时环境下对周期任务与非周期任务进行混合调度的一种较好的方法。     

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反     

Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations

In order to meet the inherent need of real-time applications for high quality results within strict timing constraints, the employment of effective scheduling techniques is crucial in distributed real-time systems. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a homogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide an alternative version which allows imprecise computations, taking into account the effects of input error on the processing time of the component tasks of a job. The simulation results show that the alternative versions of the algorithms outperform their respective counterparts. To our knowledge, an imprecise computations approach for the dynamic scheduling of multiple task graphs with end-to-end deadlines and input error has never been discussed in the literature before.     

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

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

管道流量泄漏在线监测中的模糊调度设计

针对管道流量泄漏和管网突发性的爆管,以管道流量泄漏为应用对象,将模糊调度设计应用于管道流量泄漏监测中,研究具有模糊截止期的多控制任务的实时调度问题,提出奉献度概念和最大奉献优先（LDF）的调度策略。为了减小因任务间频繁切换造成的系统开销,提出基于抢占阈值的最大奉献优先（TLDF）调度策略。最后通过仿真比较LDF和TLDF两种调度策略,实现具有模糊截止期的控制任务调度,能够减少并均衡控制性能的损失,同时提高系统计算资源的使用率。     

面向软件系统的指令时序建模与分析方法

软件指令时序调度是实时软件系统运行的基本问题,如何识别出实时系统中的关键任务,并对其进行及时调度和处理则是解决这一基本问题的关键。应用企业过程建模原理,构造了实时系统的软件过程时序模型,并基于SADT模型,提出了一个基于CPU时间和带宽分配的指令活动模型TB-SADT。引入合成数的概念以求解不确定性软件过程关键路径。针对软件过程模型的控制结构,考虑CPU时间和通信时间的分配,探讨模型中各活动之间时序调度问题。     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

A two-phase scheduling strategy for real-time applications with security requirements on heterogeneous clusters

Nowadays, increasing attention has been directed towards the issue of security service for real-time applications with security requirements on clusters. However, the study of integrating security demands of real-time applications into scheduling is rare. In this paper, we propose a novel two-phase scheduling strategy TPSS which takes timing constraints and security needs into consideration for security-critical real-time applications on heterogeneous clusters. In the first-phase, a novel algorithm DSRF is proposed to schedule real-time tasks. When the system is in heavy burden, DSRF is able to degrade the security levels of new tasks and tasks waiting in local queues so as to enhance guarantee ratio. On the contrary, when the system is in light burden, DSRF is capable of employing slack time to improve the security quality of new tasks and adequately utilize the system resource. The minimal security level can guarantee the system security, and higher security level is able to make the system more secure. In the second-phase, a new algorithm FMSL is proposed to minimize the difference of security levels of accepted tasks and further improve the security levels of accepted tasks on the whole, which degrades the probability of the applications being attacked. We compare TPSS, DSRF, SAEDF and RF by extensive simulations. The experimental results indicate that TPSS significantly improves the flexibility of scheduling and outperforms other algorithms.