Dynamic priority scheduling of periodic and aperiodic tasks in hard real-time systems

This paper addresses the problem of scheduling aperiodic tasks in real-time systems. The proposed scheme combines the Earliest-Deadline-First algorithm for scheduling periodic tasks with the Deferrable Server approach for servicing aperiodic tasks. Necessary and sufficient conditions are derived for guaranteeing feasibility of a given periodic task set when a deferrable server is present. An analytic model is proposed for selecting the best feasible period and computation time of the server to minimize the mean response time of aperiodic tasks. An evaluation of the proposed model using a simulator indicates that the server parameters selected by the model result in mean response times that are close to the best mean response time determined by the simulator.     

Fault-tolerance through scheduling of aperiodic tasks in hardreal-time multiprocessor systems

Real time systems are being increasingly used in several applications which are time critical in nature. Fault tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. We study a scheme that provides fault tolerance through scheduling in real time multiprocessor systems. We schedule multiple copies of dynamic, aperiodic, nonpreemptive tasks in the system, and use two techniques that we call deallocation and overloading to achieve high acceptance ratio (percentage of arriving tasks scheduled by the system). The paper compares the performance of our scheme with that of other fault tolerant scheduling schemes, and determines how much each of deallocation and overloading affects the acceptance ratio of tasks. The paper also provides a technique that can help real time system designers determine the number of processors required to provide fault tolerance in dynamic systems. Lastly, a formal model is developed for the analysis of systems with uniform tasks     

End-to-end deadline control for aperiodic tasks in distributed real-time systems

A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving the system throughput.

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     

Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems

In this paper, we consider the generalized power model in which the focus is the dynamic power and the static power, and we study the problem of the canonical sporadic task scheduling based on the rate-monotonic (RM) scheme. Moreover, we combine with the dynamic voltage scaling (DVS) and dynamic power management (DPM). We present a static low power sporadic tasks scheduling algorithm (SSTLPSA), assuming that each task presents its worst-case work-load to the processor at every instance. In addition, a more energy efficient approach called a dynamic low power sporadic tasks scheduling algorithm (DSTLPSA) is proposed, based on reclaiming the dynamic slack and adjusting the speed of other tasks on-the-fly in order to reduce energy consumption while still meeting the deadlines. The experimental results show that the SSTLPSA algorithm consumes 26.55–38.67% less energy than that of the RM algorithm and the DSTLPSA algorithm reduces the energy consumption up to 18.38–30.51% over the existing DVS algorithm.     

基于深度强化学习的电子政务云动态化任务调度方法

电子政务云中心的任务调度一直是个复杂的问题。大多数现有的任务调度方法依赖于专家知识,通用性不强,无法处理动态的云环境,通常会导致云中心的资源利用率降低和服务质量下降,任务的完工时间变长。为此,提出了一种基于演员评论家（actor-critic,A2C）算法的深度强化学习调度方法。首先,actor网络参数化策略并根据当前系统状态选择调度动作,同时critic网络对当前系统状态给出评分;然后,使用梯度上升的方式来更新actor策略网络,其中使用了critic网络的评分来计算动作的优劣;最后,使用了两个真实的业务数据集进行模拟实验。结果显示,与经典的策略梯度算法以及五个启发式任务调度方法相比,该方法可以提高云数据中心的资源利用率并缩短离线任务的完工时间,能更好地适应动态的电子政务云环境。     

Slack-based multiprocessor scheduling of aperiodic real-time tasks

We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. The so called Dhall’s effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack—not on deadlines. We prove that if the load on the multiprocessor stays below \((3 - \sqrt{5} )/2 \approx 38.197\%\), the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of-the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%).The bound \((3 - \sqrt{5} )/2\) can be improved if the number of processors m is known. There is a formula for the sharp bound \(U_{\mathit{threshold}}(m) = \frac{3m - 2 - \sqrt{5m^{2} - 8m + 4}}{2(m - 1)}\), which converges to \((3 - \sqrt{5} )/2\) from above as m→∞. For m≥3, the bound is higher (i.e., better) than the corresponding sharp bound for the state-of-the-art algorithm where the priorities of light tasks are based on deadlines.A simulation study also indicates that when m>3 the best effort behavior of the priority assignment scheme suggested here is better than that of the traditional scheme where priorities are based on deadlines.     

CAN总线中非周期信息的随机动态优先级调度

针对CAN总线中非周期信息传输的“死锁”现象,利用动态优先级提升机制中消息在发送队列的位置随等待时间动态改变的思想,对非周期性信息的传输采用基于随机数的动态优先级调度策略,以解决CAN总线中非周期信息传输的“死锁”问题。     

Analysis and modeling of control tasks in dynamic systems

Most applications of evolutionary algorithms deal with static optimization problems. However, in recent years, there has been a growing interest in time-varying (dynamic) problems, which are typically found in real-world scenarios. One major challenge in this field is the design of realistic test-case generators (TCGs), which requires a systematic analysis of dynamic optimization tasks. So far, only a few TCGs have been suggested. Our investigation leads to the conclusion that these TCGs are not capable of generating realistic dynamic benchmark tests. The result of our research is the design of a new TCG capable of producing realistic nonstationary landscapes     

Scheduling PVM Tasks

This paper describes a PVM task scheduler designed and implemented by the authors.The scheduler supports selecting idle workstations,scheduling pool tasks and dynamically produced subtasks.It can improve resource utilization,reduce job response time and simplify programming.     

Schedulability analysis of dynamic priority real-time systems with contention

The Journal of Supercomputing - In multicore scheduling of hard real-time systems, there is a significant source of unpredictability due to the interference caused by the sharing of hardware...     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

Exact admission-control for integrated aperiodic and periodic tasks

Admission-controllers are used to prevent overload in systems with dynamically arriving tasks. Typically, these admission-controllers are based on sufficient (but not necessary) capacity bounds in order to maintain a low computational complexity. In this paper we present how exact admission-control for aperiodic tasks can be efficiently obtained. Our first result is an admission-controller for purely aperiodic task sets where the test has the same runtime complexity as utilization-based tests. Our second result is an extension of the previous controller for a baseload of periodic tasks. The runtime complexity of this test is lower than for any known exact admission-controller. In addition to presenting our main algorithm and evaluating its performance, we also discuss some general issues concerning admission-controllers and their implementation.     

Fixed priority scheduling of tasks with arbitrary precedence constraints in distributed hard real-time systems

This paper considers the schedulability analysis of real-time distributed applications where tasks may present arbitrary precedence relations. It is assumed that tasks are periodic or sporadic and dynamically released. They have fixed priorities and hard end-to-end deadlines that are equal to or less than the respective period. We develop a method to transform arbitrary precedence relations into release jitter. By eliminating all precedence relations in the task set one can apply any available schedulability test that is valid for independent task sets.     

A design fix to supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.     

Scheduling component replacement for timely execution in dynamic systems

Timely run‐time software replacement techniques are a corner stone for reconciling real‐time systems development and dynamic behavior. Typical real‐time systems do not consider dynamic behavior because it deeply challenges predictability and timeliness. Current efforts are starting to merge the safe and predictable execution with a controllable level of dynamicity by imposing a set of bounds and limitations to the system dynamic behavior. One of the obstacles for this is how to time‐bound the different operations required to effectively implement component replacement. In this paper, the main challenges for this problem are identified, and a model to ensure that components can be replaced at run time preserving the temporal properties of the system is provided that also avoids failures in replacements. A real example and simulations of our replacement model are provided that validate the presented ideas. Copyright © 2013 John Wiley & Sons, Ltd.     

实时嵌入式异构环境下多优先级混合任务调度动态策略

针对现有异构环境下的调度策略,引入迫切密度和剩余价值密度,分析迫切密度和剩余价值密度调节任务执行紧急程度的影响、对优先级制定,通过构建单有向无环图（ DAG）系统模型实现了混合任务的动态调度。仿真实验结果表明：该调度策略在系统负载较高的情况下,仍有较优的任务执行效能和避免颠簸现象。     

控制系统中实时任务的动态优化调度算法

提出一种新的调度算法——带有非周期服务器的EDF调度算法.分析了所有任务的可调度性,给出了可调度条件,并给出一种新的周期性任务模型以及主优先级和辅助优先级的概念.它们在保证任务可调度的前提下,对周期性任务的采样频率和控制延时进行优化.仿真结果表明,该算法可以提高周期性任务的采样频率,并降低控制延时,即能优化系统的性能.     

Period sensitivity analysis and D-P domain feasibility region in dynamic priority systems

In the design of a real-time application it is fundamental to know how a change in the task parameters would affect the feasibility of the system. Relaxing the classical assumptions on static task sets with fixed periods and deadlines can give higher resource utilisation and better performance. But the changes on task parameters have to be done always maintaining feasibility. In practice, period and deadline modifications are only necessary on single tasks. Our work focuses on finding the feasibility region of deadlines and periods (called D-P feasibility region) for a single task in the context of dynamic, uniprocessor scheduling of hard real-time systems. This way, designers can choose the optimal deadline and period pairs that best fit application requirements. We provide an exact and an approximated algorithm to calculate this region. We will show that the approximated solution is very close to the exact one and it takes considerably less time.