面向物联网终端的任务相关性调度策略

对于具有相关性的任务,调度顺序不合理将影响任务的执行时间和实时性。结合物联网终端任务间依赖关系复杂的特点提出了一种利用任务相关性的调度策略。该策略设计了以作业轮询组为主体的任务模型,根据任务时限建立了优先级因子矩阵作为任务调度的凭据,对于周期任务,在每个任务执行完毕后生成,以任务相关性为参数的增量矩阵用以动态修改任务优先级,使前驱任务能优先执行;对于非周期任务采用了构建临时作业轮询组的方式进行抢占调度。测试结果表明,该策略能够有效减少具有相关性的周期任务集执行时间和调度失败次数,缩短非周期任务响应时间。     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

Modified rate-monotonic algorithm for scheduling periodic jobs withdeferred deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, γ-1) periods or more, where γ is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than [1+n(2¹n/-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

一种作业弹性与截止时间感知的作业调度算法

针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。     

EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法

现有的硬实时周期任务和非周期任务的混合调度方法都没有保证非周期任务的实时性,所以不适合调度具有强实时要求的偶发任务.通过分析和计算EDF算法调度偶发任务所占用的空闲时间和挪用时间,以及调度后对空闲时间和最大可挪用时间的影响,提出一种采用EDF算法统一调度硬实时周期任务和偶发任务时的可调度性充分判定算法.最后用仿真实验得出了该算法在不同系统负载下的判定准确率和偶发任务的平均响应时间.     

基于价值密度和截止期的网格作业调度算法

对商业网格中的作业调度问题进行研究,采用作业的到达时间、计算量、预算和截止期4个参数定义作业的优先级。在此基础上提出基于价值密度和相对截止期的网格作业调度算法,并对其进行仿真。仿真结果表明,该算法在实现价值率、按时完成作业数和加权作业按时完成率3个性能指标上优于现有算法,兼顾了消费者和服务者的利益。     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R2分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

Hadoop平台下基于截止时间限制的动态调度算法的研究

为了满足有截止时间限制的MapReduce作业的需求,提出一种基于截止时间限制的动态调度算法（DCDS）。该算法实时监控作业运行状况,并对作业运行时间进行动态估算,从而确定作业优先级;对于时间紧迫的作业,可通过抢占策略来保证在用户要求的截止时间内完成。实验结果表明,与Hadoop平台现有的调度算法相比,该算法不仅能满足作业截止时间的要求,也提高了系统资源的利用率和吞吐量。     

Optimization of schedules with precedence logical conditions

The problem of constructing a time-optimal schedule for jobs execution with precedence logical conditions is considered. Every job is associated with a list of its direct predecessors, execution time and the number of the completed direct predecessors necessary to start execution of the job. It is shown that the problem can be solved by the methods of the cyclical games theory [1, 2]. We propose a pseudopolynomial algorithm for construction of the optimal schedule; i.e. the presented algorithm is efficient for the problems with small data arrays. The paper extends the results from [3], where AND/OR schedules are considered. A job can be started, when all its direct predecessor have been executed or when at least one of its direct predecessors has been completed.     

Aperiodic task scheduling for Hard-Real-Time systems

A real-time system consists of both aperiodic and periodic tasks. Periodic tasks have regular arrival times and hard deadlines. Aperiodic tasks have irregular arrival times and either soft or hard deadlines. In this article, we present a new algorithm, the Sporadic Server algorithm, which greatly improves response times for soft deadline aperiodic tasks and can guarantee hard deadlines for both periodic and aperiodic tasks. The operation of the Sporadic Server algorithm, its performance, and schedulability analysis are discussed and compared with previously published aperiodic service algorithms.     

Some algorithms of solving minimax multiprocessor scheduling problem

A problem of constructing schedules of minimal length without interrupts and switches is considered for a multiprocessor system, in which the job execution time depends on the processor assigned to the job. To solve this problem, the branch and bound method is developed. The method is based on efficient algorithms for calculating lower and upper bounds of minimal length of the schedule. For the particular case when processors are identical, their number is fixed and the directive deadline is given, a pseudo-polynomial algorithm is proposed for constructing the admissible schedule. The number of processors required for efficient parallelizing of the algorithm is found.     

Multi-QoS constrained and Profit-aware scheduling approach for concurrent workflows on heterogeneous systems

The execution of a workflow application can result in an imbalanced workload among allocated processors, ultimately resulting in a waste of resources and a higher cost to the user. Here, we consider a dynamic resource management system in which processors are reserved not for a job but only to run a task, thus allowing a higher resource usage rate. This paper presents a scheduling algorithm that manages concurrent workflows in a dynamic environment in which jobs are submitted by users at any moment in time, on shared heterogeneous resources, and constrained to a specified budget and deadline for each job. Recent research attempted to propose dynamic strategies for concurrent workflows but only addressed fairness in resource sharing among applications while minimizing the execution time. The Multi-QoS Profit-Aware scheduling algorithm (MQ-PAS) proposed here is able to increase the profit achieved by the provider by considering the budget available for each job to define tasks priorities. We study the scalability of the algorithm with different types of workflows and infrastructures. The experimental results show that our strategy improves provider revenue significantly and obtains comparable successful rates of completed jobs.     

非周期软实时系统的动态最优控制方法

运用多优先级排队系统的分析方法,研究了到达时刻和执行时间均不确定的非周期软实时系统,提出了一种针对DM调度算法的动态最优控制方法。该方法能在统计意义上确保系统的实时性,同时又兼顾系统的QoS需求和提高系统吞吐率。实例表明,该方法能提高系统的实际利用率,降低系统的截止时间错过率,是一种有效的载荷管理方法。     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

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

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

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.     

Scheduling for stability in single-machine production systems

Robust scheduling aims at the construction of a schedule that is protected against uncertain events. A stable schedule is a robust schedule that changes only little when variations in the input parameters arise. This paper presents a model for single-machine scheduling with stability objective and a common deadline. We propose a branch-and-bound algorithm for solving an approximate formulation of the model. The algorithm is exact when exactly one job is disrupted during schedule execution.     

Adaptive checkpointing strategy to tolerate faults in economy based grid

In this paper, we develop a fault tolerant job scheduling strategy in order to tolerate faults gracefully in an economy based grid environment. We propose a novel adaptive task checkpointing based fault tolerant job scheduling strategy for an economy based grid. The proposed strategy maintains a fault index of grid resources. It dynamically updates the fault index based on successful or unsuccessful completion of an assigned task. Whenever a grid resource broker has tasks to schedule on grid resources, it makes use of the fault index from the fault tolerant schedule manager in addition to using a time optimization heuristic. While scheduling a grid job on a grid resource, the resource broker uses fault index to apply different intensity of task checkpointing (inserting checkpoints in a task at different intervals). To simulate and evaluate the performance of the proposed strategy, this paper enhances the GridSim Toolkit-4.0 to exhibit fault tolerance related behavior. We also compare “checkpointing fault tolerant job scheduling strategy” with the well-known time optimization heuristic in an economy based grid environment. From the measured results, we conclude that even in the presence of faults, the proposed strategy effectively schedules grid jobs tolerating faults gracefully and executes more jobs successfully within the specified deadline and allotted budget. It also improves the overall execution time and minimizes the execution cost of grid jobs.     

Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques

The most crucial aspect of distributed real-time systems is the scheduling algorithm, which must guarantee that every job in the system will meet its deadline. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a heterogeneous 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 alternative versions which allow the insertion of tasks into idle time slots, using various bin packing techniques. The comparison study, based on different workloads and system heterogeneity levels, shows that the alternative versions of the algorithms outperform their respective counterparts.