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.     

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

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

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

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

Aperiodic servers in a deadline scheduling environment

A real-time system may have tasks with soft deadlines, as well as hard deadlines. While earliest-deadline-first scheduling is effective for hard-deadline tasks, applying it to soft-deadline tasks may waste schedulable processor capacity or sacrifice average response time. Better average response time may be obtained, while still guaranteeing hard deadlines, with an aperiodic server. Three scheduling algorithms for aperiodic servers are described, and schedulability tests are derived for them. A simulation provides performance data for these three algorithms on random aperiodic tasks. The performances of the deadline aperiodic servers are compared with those of several alternatives, including background service, a deadline polling server, and rate-monotonic servers, and with estimates based on the M/M/1 queueing model. This adds to the evidence in support of deadline scheduling,versus fixed priority scheduling.     

Handling mixed sets of tasks in combined offline and online scheduled real-time systems

Many industrial applications with real-time demands are composed of mixed sets of tasks with a variety of requirements. These can be in the form of standard timing constraints, such as period and deadline, or complex, e.g., to express application specific or nontemporal constraints, reliability, performance, etc. As many algorithms focus on specific sets of task types and constraints only, system design has to focus on those supported by a particular algorithm, at the expense of the rest. In this paper, we present a method to deal with a combination of mixed sets of tasks and constraints: periodic tasks with complex and simple constraints, soft and firm aperiodic, and sporadic tasks. We propose the use of an offline scheduler to manage complex timing and resource constraints of periodic tasks and transform these into a simple EDF model with start-times and deadlines. At run-time, the execution of the offline scheduled tasks is flexibly shifted in order to allow for feasible inclusion of dynamically arriving sporadic and aperiodic tasks. Sporadic tasks are guaranteed offline based on their worst-case activation frequencies. At run-time, this pessimism is reduced by the online algorithm which uses the exact knowledge about sporadic arrivals to reclaim resources and improve response times and acceptance of firm aperiodic tasks.     

引入虚拟特征参数的混合实时任务调度及应用

提出了在实时环境下周期任务与非周期任务混合调度的一种新方法。引入非周期实时任务虚拟截止期、虚拟周期的特征参数,综合考虑各实时任务的多特征参数进行优先级设计,克服了单独考虑任务的个别参数以及忽略非周期任务自身特征的调度策略的局限性及调度风险,且能够尽可能地加快非周期任务的响应速度,提高系统整体的调度性能。将该方法在RT-Linux实时环境中实现,并针对无人飞艇的自动驾驶仪进行了任务实例的可调度性测试,证明了该调度策略的可行性。     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

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

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

Feasibility analysis of hard real-time periodic tasks

The problem of determining the feasibility of hard real-time periodic tasks is known to be co-NP-complete when there exists a task with relative deadline shorter than its period. Thus “Processor Demand Approach (PDA)” for synchronous task sets has been considered as a practical tool to solve the feasibility problem. PDA determines the feasibility of a task set by checking whether there exists a task whose deadline is missed by a certain time which is computed based on the characteristic of the task set. In this paper, we present a new method for feasibility test by combining PDA with the analysis methods for aperiodic scheduling. It is shown that the number of tests required of the new method to determine the feasibility is never greater than the smallest number of tests the existing algorithm requires. Although our method has pseudo-polynomial time complexity, experimental results show that the new method requires significantly less computation to determine feasibility.     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

Reliability improvement of the dual-priority protocol under unreliable transmission

The dual-priority is a scheduling policy providing the guarantees needed by periodic or sporadic hard real-time tasks while decreasing the response time for aperiodic soft real-time tasks. This scheduling policy can be applied to message scheduling and its performance on controller area network (CAN) will be assessed. Nevertheless, when used in an electromagnetic stressed environment (e.g. automotive communication) leading to transmission errors, this scheduling strategy could lead to serious disappointments. It will be explained why the hard real-time traffic is highly sensitive to transmission errors. The risks of deadline failure will be quantified and a simple mechanism that provides probabilistic guarantees to prevent hard real-time frames from missing their deadlines, will be proposed. This mechanism is compared in terms of performance to the original dual-priority strategy. The chosen performance metrics are the deadline failure probability for hard real-time traffic, the average response time and the variance in response time for soft real-time traffic.     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

Scheduling aperiodic tasks in dynamic priority systems

In this paper we present five new on-line algorithms for servicing soft aperiodic requests in realtime systems, where a set of hard periodic tasks is scheduled using the Earliest Deadline First (EDF) algorithm. All the proposed solutions can achieve full processor utilization and enhance aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Operation of the algorithms, performance, schedulability analysis, and implementation complexity are discussed and compared with classical alternative solutions, such as background and polling service. Extensive simulations show that algorithms with contained run-time overhead present nearly optimal responsiveness.A valuable contribution of this work is to provide the real-time system designer with a wide range of practical solutions which allow to balance efficiency against implementation complexity.     

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

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

Schedulability analysis of periodic and aperiodic tasks with resource constraints

In this paper, we address the problem of scheduling hybrid task sets consisting of hard periodic and soft aperiodic tasks that may share resources in exclusive mode in a dynamic environment, where tasks are scheduled based on their deadlines. Bounded blocking on exclusive resources is achieved by means of a dynamic resource access protocol which also prevents deadlocks and chained blocking. Aperiodic responsiveness is enhanced by an efficient servicing technique which assigns each aperiodic request a suitable deadline. Feasibility conditions are extended to handle tasks with deadlines different from periods and a reclaiming technique is presented to deal with early completions.     

硬实时环境下截止期缓冲区管理方法

针对硬实时环境的特点，提出了一种新的利用任务截止期来管理缓冲区的方法，前提是该环境下使用最早截止期优先的任务调度算法。该截止期缓冲区管理方法的主要特点是：在保证周期任务的缓冲区可用的同时，有效利用缓冲区资源，得到最佳的非周期实时任务缓冲区请求响应。详细讨论了该方法及其实现。     

MINIMIZING SERVICE DELAY OF APERIODIC TASKS IN DYNAMIC‐PRIORITY NON‐PREEMPTIVE HARD REAL‐TIME SYSTEMS

A scheduling technique is presented to minimize service delay of aperiodic tasks in hard real‐time systems that employ dynamic‐priority scheduling and do not allow task preemption. In a real‐time scheduling process, the execution of periodic tasks can be deferred as long as this does not cause other tasks to violate their time constraints. However, aperiodic tasks that usually have urgent missions should complete execution as early as possible. In this paper, it is assumed that aperiodic tasks also have time constraints. Thus, the problem of deciding whether an aperiodic task with an unpredictable arrival time can be scheduled successfully or not is difficult to solve because delaying periodic tasks may cause them to fail to meet their time constraints. We present a dynamic scheduling technique to solve this problem which makes use of the symmetric property of a schedule. The maximum possible idle slot is always reserved at every scheduling point so that aperiodic tasks can be serviced immediately if the reserved idle slot is big enough to service them. The proposed technique also maximizes utilization of idle slots by reserving them for the longest possible time span.     

A priority-driven flow control mechanism for real-time traffic inmultiprocessor networks

Real-time applications when mapped to distributed memory multiprocessors produce periodic messages with an associated deadline and priority. Real-time messages may be hard or soft deadline. Real-time extensions to wormhole routing (WR) with multiple virtual channels (VCs) and priority-based physical link arbitration and VC allocation have been proposed in the literature. With a fixed number of VCs/link, a message can face an unbounded priority inversion, rendering the global priority ineffective. In this paper, we propose a new flow control mechanism called Preemptive Pipelined Circuit Switching for Real-Time messages (PPCS-RT) to reduce the priority inversion problem. For the proposed model, with some architectural support, we present an off-line approach to compute delivery guarantees of hard deadline real-time messages. We also perform a comparison of real-time WR and PPCS-RT in terms of performance with soft deadline traffic. The overall miss ratio percentage is over 30 percent higher for WR than PPCS-RT with one VC/link at high traffic loads. Finally, we compare the architectural complexity of a PPCS-RT router and other real-time routers     

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

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