实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

An efficient dynamic scheduling algorithm for multiprocessorreal-time systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters     

Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems

Scheduling program tasks on processors is at the core of the efficient use of multiprocessor systems. Most task-scheduling problems are known to be NP-Hard and, thus, heuristics are the method of choice in all but the simplest cases. The utilization of acknowledged sets of benchmark-problem instances is essential for the correct comparison and analysis of heuristics. Yet, such sets are not available for several important classes of scheduling problems, including multiprocessor scheduling problem with communication delays (MSPCD) where one is interested in scheduling dependent tasks onto homogeneous multiprocessor systems, with processors connected in an arbitrary way, while explicitly accounting for the time required to transfer data between tasks allocated to different processors. We propose test-problem instances for the MSPCD that are representative in terms of number of processors, type of multiprocessor architecture, number of tasks to be scheduled, and task graph characteristics (task execution times, communication costs, and density of dependencies between tasks). Moreover, we define our task-graph generators in a way appropriate to ensure that the corresponding problem instances obey the theoretical principles recently proposed in the literature.     

Minimizing mean flow-time with parallel processors and resource constraints

Summary The problem to be considered is one of scheduling nonpreemptable tasks in multiprocessor systems when tasks need for their processing processors and other limited resources, and when mean flow time is the system performance measure. For each task the time required for its processing and the amount of each resource which it requires, are given. Special attention is paid to the computational complexity of algorithms for determining the optimal schedules for different assumptions concerning the environment. For the case of scheduling independent, arbitrary length tasks when each task may require a unit of an additional resource of one type, an O(n ³) algorithm is given. For more complicated resource requirements, however, it is proved that the problem under consideration is NP-hard in the strong sense, even for the case of two processors.     

一种同构多处理机动态实时调度算法

本文提出一种新型线性复杂度多处理机实时任务启发式调度算法,利用并行技术为动态实时系统提供较优解．使用大量存在可行调度的任务集合测试多处理机实时任务调度算法的性能,分析了几种主要参数对调度成功率的影响．实验表明新调度算法调度成功率较高,适用于不完全知晓任务参数的动态多处理机实时系统．     

Improving the schedulability of soft real-time open dynamic systems: The inheritor is actually a debtor

This paper presents the Clearing Fund Protocol, a three layered protocol designed to schedule soft real-time sets of precedence related tasks with shared resources. These sets are processed in an open dynamic environment. Open because new applications may enter the system at any time and dynamic because the schedulability is tested on-line as tasks request admission. Top-down, the three layers are the Clearing Fund, the Bandwidth Inheritance and two versions of the Constant Bandwidth Server algorithms. Bandwidth Inheritance applies a priority inheritance mechanism to the Constant Bandwidth Server. However, a serious drawback is its unfairness. In fact, a task executing in a server can potentially steal the bandwidth of another server without paying any penalty. The main idea of the Clearing Fund Algorithm is to keep track of processor-time debts contracted by lower priority tasks that block higher priority ones and are executed in the higher priority servers by having inherited the higher priority. The proposed algorithm reduces the undesirable effects of those priority inversions because the blocked task can finish its execution in its own server or in the server of the blocking task, whichever has the nearest deadline. If demanded, debts are paid back in that way. Inheritors are therefore debtors. Moreover, at certain instants in time, all existing debts may be waived and the servers are reset making a clear restart of the system. The Clearing Fund Protocol showed definite better performances when evaluated by simulations against Bandwidth Inheritance, the protocol it tries to improve.     

Supporting lock-free synchronization in Pfair-scheduled real-time systems

We consider the use of lock-free techniques for implementing shared objects in real-time Pfair-scheduled multiprocessor systems. Lock-free objects are more economical than locking techniques when implementing relatively simple objects such as buffers, stacks, queues, and lists. However, the use of such objects on real-time multiprocessors is generally considered impractical due to the need for analytical real-time guarantees. In this paper, we explain how the quantum-based nature of Pfair scheduling enables the effective use of such objects on real-time multiprocessors and present analysis specific to Pfair-scheduled systems. In addition, we show that analytical improvements can be obtained by using such objects in conjunction with group-based scheduling techniques. In this approach, a group of tasks is scheduled as a single entity (called a supertask in the Pfair literature). Such grouping prevents tasks from executing simultaneously, and hence from executing in parallel. Consequently, grouping tasks can improve the worst-case scenario with respect to object contention. Grouping also enables the use of less costly uniprocessor algorithms when all tasks sharing an object reside within the same group. We illustrate these optimizations with a case study that focuses on shared queues. Finally, we present and experimentally evaluate a simple heuristic for grouping tasks in order to reduce object contention. Though the analysis presented herein focuses specifically on Pfair-scheduled systems, the observations and techniques should be applicable to other quantum-scheduled systems as well.     

基于动态松弛时间回收的开销敏感节能实时调度算法

为适应实际系统中任务集的不断变化以及不可忽视状态切换开销的要求,针对多核多处理器系统中常见的周期任务模型,提出一种基于动态松弛时间回收的开销敏感节能实时调度算法DSROM,在每个TL面的初始时刻、任务提前完成时刻实现节能调度及动态松弛时间回收,在不违反周期任务集可调度性的基础上,达到实时约束与能耗节余之间的合理折衷。模拟实验结果表明,DSROM算法不仅保证了周期任务集的最优可调度性,而且当任务集总负载超过某一个值后,其节能效果整体优于现有方法,最多可节能近20%。     

A fault-tolerant dynamic scheduling algorithm for multiprocessorreal-time systems and its analysis

Many time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. The tasks are assumed to be nonpreemptable and each task has two copies (versions) which are mutually excluded in space, as well as in time in the schedule, to handle permanent processor failures and to obtain better performance, respectively. Our algorithm can tolerate more than one fault at a time, and employs performance improving techniques such as 1) distance concept which decides the relative position of the two copies of a task in the task queue, 2) flexible backup overloading, which introduces a trade-off between degree of fault tolerance and performance, and 3) resource reclaiming, which reclaims resources both from deallocated backups and early completing tasks. We quantify, through simulation studies, the effectiveness of each of these techniques in improving the guarantee ratio, which is defined as the percentage of total tasks, arrived in the system, whose deadlines are met. Also, we compare through simulation studies the performance our algorithm with a best known algorithm for the problem, and show analytically the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems     

Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks

In this paper we study the scheduling of parallel and real-time recurrent tasks on multiprocessor platforms. Firstly, we propose a new parallel task model which allows recurrent tasks to be composed of several phases, each one composed of several threads. Each thread requires a single processor for execution and can be scheduled simultaneously. We then propose an algorithm to transpose popular Fork-Join task model to our MPMT task model. Secondly, we define several kinds of real-time schedulers that can be applied to our parallel task model. We distinguish between two scheduling classes: Hierarchical schedulers and Global Thread schedulers. We present and prove correct an exact schedulability test for each class. Lastly, we also evaluate the performance of our scheduling paradigm in comparison with Gang scheduling by means of simulations. In this work we extend the work of Lupu and Goossens in Scheduling of hard real-time multi-thread periodic tasks (Real-Time and Network Systems, 2011) which considers mono-phase multi-thread task model. We extend their previous results to a Multi-Phase Multi-Thread task model.     

Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling

In distributed real-time systems, an application is often modeled as a set of real-time transactions, where each transaction is a chain of precedence-constrained tasks. Each task is statically allocated to a processor, and tasks allocated on the same processor are handled by a single-processor scheduling algorithm. Precedence constraints among tasks of the same transaction are modeled by properly assigning scheduling parameters as offsets, jitters and intermediate deadlines.In this paper we address the problem of schedulability analysis of distributed real-time transactions under the earliest deadline first scheduling algorithm. We propose a novel methodology that reduces the pessimism introduced by previous methods by explicitly taking into account the offsets of the tasks. Moreover, we extend the analysis to account for blocking time due to shared resources. In particular, we propose two kinds of schedulability tests, CDO-TO and MDO-TO, and show, with an extensive set of simulations, that they provides improved schedulability conditions with respect to classical algorithms. Finally, we apply the methodology to an important class of systems: heterogeneous multiprocessor systems, with a general purpose processor and one or more coprocessors (DSPs).     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

A nonpreemptive real-time scheduler with recovery from transient faults and its implementation

Real-time systems (RTS) are those whose correctness depends on satisfying the required functional as well as the required temporal properties. Due to the criticality of such systems, recovery from faults is an essential part of a RTS. In many systems, such as those supporting space applications, single event upsets (SEUs) are the prevalent type of faults; SEUs are transient faults and affect a single task at a time. We present a scheme to guarantee that the execution of real-time tasks can tolerate SEUs and intermittent faults assuming any queue-based scheduling technique. Three algorithms are presented to solve the problem of adding fault tolerance to a queue of real-time tasks by reserving sufficient slack in a schedule so that recovery can be carried out before the task deadline without compromising guarantees given to other tasks. The first algorithm is a dynamic programming optimal solution, the second is a linear-time heuristic for scheduling dynamic tasks, and the third algorithm comprises extensions to address queues with gaps between tasks (gaps are caused by precedence, resource, or timing constraints). We show through simulations that the heuristics closely approximate the optimal algorithm. Finally, we describe the implementation of the modified admission control algorithm, non-preemptive scheduler, and recovery mechanism in the FT-RT-Mach operating system.     

Task reweighting under global scheduling on multiprocessors

We consider schemes for enacting task share changes—a process called reweighting—on real-time multiprocessor platforms. Our particular focus is reweighting schemes that are deployed in environments in which tasks may frequently request significant share changes. Prior work has shown that fair scheduling algorithms are capable of reweighting tasks with minimal allocation error and that partitioning-based scheduling algorithms can reweight tasks with better average-case performance, but greater error. However, preemption and migration overheads can be high in fair schemes. In this paper, we consider the question of whether non-fair, earliest-deadline-first ( $\mathsf{EDF}$ ) global scheduling techniques can improve the accuracy of reweighting relative to partitioning-based schemes and provide improved average-case performance relative to fair-scheduled systems. Our conclusion is that, for soft real-time systems, global $\mathsf{EDF}$ schemes provide a good mix of accuracy and average-case performance.     

A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted the attention of many researchers in the recent past. Tasks in such systems have deadlines to be met, and most real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. Several resource reclaiming algorithms such as Basic, Early Start, and RV algorithms have been proposed in the recent past. But these pay very little attention to the strategy by which the scheduler can better utilize the benefits of reclaimed resources. In this paper, we propose an esti- mation strategy which can be used along with a particular class of resource reclaiming algorithms (such as Early Start and RV algorithms) by which the scheduler can estimate the minimum time by which any scheduled but unexecuted task will start or finish early, based solely on the start and finish times of tasks that have started or finished execution. We then propose an approach by which dynamic scheduling strategies, which append or reschedule new tasks into the schedules, can use this estimation strategy to achieve better schedulability. Extensive simulation studies are carried out to investigate the effectiveness of this estimation strategy versus its cost.     

Resource sharing among real-time components under multiprocessor clustered scheduling

In this paper we propose a general synchronization protocol for resource sharing among independently-developed real-time applications (components) on multi-core platforms. This protocol is a generalization of a previously proposed synchronization protocol (MSOS). In our proposed protocol, each component is statically allocated on a dedicated subset of processors (called cluster). A component has its own internal scheduler by which its tasks are scheduled. In this paper we focus on multiprocessor global fixed-priority preemptive scheduling algorithms to be used to schedule the tasks inside each component. Sharing the local resources is handled by the Priority Inheritance Protocol (PIP). For sharing the global resources (inter-component resource sharing) we have studied usage of FIFO and Round-Robin queues for access the resources across the components and usage of FIFO and prioritized queues inside the components. We have derived schedulability analysis for the different queue handling alternatives and compared their performance by using experimental evaluations. Finally, we have shown that the integration phase can be formulated in the form of a nonlinear integer programming problem where solution techniques in this domain can be used to minimize the total number of processors required to guarantee the schedulability of all components. As a proof of concept we have only provided the formulation for FIFO queues.     

Converging to periodic schedules for cyclic scheduling problems with resources and deadlines

Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.     

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

Fault-tolerant and real-time scheduling for mixed-criticality systems

The design and analysis of real-time scheduling algorithms for safety-critical systems is a challenging problem due to the temporal dependencies among different design constraints. This paper considers scheduling sporadic tasks with three interrelated design constraints: (i) meeting the hard deadlines of application tasks, (ii) providing fault tolerance by executing backups, and (iii) respecting the criticality of each task to facilitate system’s certification. First, a new approach to model mixed-criticality systems from the perspective of fault tolerance is proposed. Second, a uniprocessor fixed-priority scheduling algorithm, called fault-tolerant mixed-criticality (FTMC) scheduling, is designed for the proposed model. The FTMC algorithm executes backups to recover from task errors caused by hardware or software faults. Third, a sufficient schedulability test is derived, when satisfied for a (mixed-criticality) task set, guarantees that all deadlines are met even if backups are executed to recover from errors. Finally, evaluations illustrate the effectiveness of the proposed test.     

多处理器调度算法实现及其Petri网建模与仿真

多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。