Preference-oriented fixed-priority scheduling for periodic real-time tasks

Traditionally, real-time scheduling algorithms prioritize tasks solely based on their timing parameters and cannot effectively handle tasks that have different execution preferences. In this paper, for a set of periodic real-time tasks running on a single processor, where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP), we investigate Preference-Oriented Fixed-Priority (POFP) scheduling techniques. First, based on Audsley’s Optimal Priority Assignment (OPA), we study a Preference Priority Assignment (PPA) scheme that attempts to assign ALAP (ASAP) tasks lower (higher) priorities, whenever possible. Then, by considering the non-work-conserving strategy, we exploit the promotion times of ALAP tasks and devise an online dual-queue based POFP scheduling algorithm. Basically, with the objective of fulfilling the execution preferences of all tasks, the POFP scheduler retains ALAP tasks in the delay queue until their promotion times while putting ASAP tasks into the ready queue right after their arrivals. In addition, to further expedite (delay) the executions of ASAP (ALAP) tasks using system slack, runtime techniques based on dummy and wrapper tasks are investigated. The proposed schemes are evaluated through extensive simulations. The results show that, compared to the classical fixed-priority Rate Monotonic Scheduling (RMS) algorithm, the proposed priority assignment scheme and POFP scheduler can achieve significant improvement in terms of fulfilling the execution preferences of both ASAP and ALAP tasks, which can be further enhanced at runtime with the wrapper-task based slack management technique.     

On the complexity of fixed-priority scheduling of periodic, real-time tasks

We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.     

Dual ceiling protocol for real-time synchronization under preemption threshold scheduling

The application of object-oriented design methods to real-time embedded systems is seriously hindered by the lack of existing real-time scheduling techniques that can be seamlessly integrated into these methods. Preemption threshold scheduling (PTS) enables a scalable real-time system design and thus has been suggested as a solution to this problem. However, direct adoption of PTS may lead to long priority inversion since object-oriented real-time systems require synchronization considerations in order to maintain consistent object states. In this paper, we propose the dual ceiling protocol (DCP) in order to solve this problem. While DCP exploits both priority ceilings and preemption threshold ceilings, this is not a straightforward integration of existing real-time synchronization protocols for PTS. We present the rationale for the locking conditions of DCP and show that it leads to the least blocking and response times by comparison with other real-time synchronization protocols. We also present its blocking properties and schedulability analyses. We implemented PTS and DCP in a real-time object-oriented CASE tool and present the associated experimental results, which show that the proposed protocol is a viable solution that is superior to other real-time synchronization protocols for PTS.     

Dynamic scheduling of real-time tasks under precedence constraints

While scheduling theory has been developed over a long period of time, it is important to note that most results concern problems with static characteristics. However, a real-time system is dynamic and requires on-line and adaptive scheduling strategies. So, an important aspect of real-time systems research is to devise methods flexible enough to react to a dynamic change of processor load and to attempt to schedule all the tasks judiciously.In this paper, we are particularly concerned with the problem of scheduling tasks which are of two kinds: periodic and sporadic, on a monoprocessor machine. Periodic tasks are independent, run cyclically and their characteristics are known in advance. In addition, we allow for the unpredictable occurrence of aperiodic task groups, with timing and precedence constraints. Clearly, the main problem is to devise a schedulability test that makes it possible to decide whether a new occurring group can be accepted, without upsetting the tight timing behavior requirements.We present an optimal acceptance test which returns a decision on the basis of the current state of processor load and by considering tasks to be scheduled according to the well known preemptive algorithm Earliest Deadline. The acceptance algorithm and a complexity analysis are presented.     

低复杂度的阈值优化实时调度算法

嵌入式实时系统在其CPU及内存资源相对稀缺时,必须采用复杂度低,系统开销小的调度算法.基于阈值的调度算法可以提高任务的调度性,减少任务间的切换,以此减少内存需求和系统开销.提出了基于抢占差值的阈值分配优化算法.算法在最小阈值分配法基础上,从高优先级向低优先级方向设置任务的阈值,为任务集找出一组满足最大抢占差值的阈值分配方案.经过理论分析及实例验证,算法可以显著降低任务的切换次数,并且算法的复杂度优于传统的优化算法.     

Sensitivity analysis for fixed-priority real-time systems

At early stages in the design of real-time embedded applications, the timing attributes of the computational activities are often incompletely specified or subject to changes. Later in the development cycle, schedulability analysis can be used to check the feasibility of the task set. However, the knowledge of the worst-case response times of tasks is often not sufficient to precisely determine the actions that would correct a non-schedulable design. In these situations, sensitivity analysis provides useful information for changing the implementation, by giving a measure of those computation times that must be reduced to achieve feasibility, or those that can be increased in case of a product extension, or providing the range of feasible periods for selecting the proper task activation rates. In this work, we exploit the concept of feasibility region to propose a faster and more concise solution to the sensitivity analysis problem with respect to existing techniques based on binary search. Furthermore, we show how the formalization of other problems in the feasibility domain, such as managing overloads through elastic scheduling, can be extended to the exact analysis.     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

Timing analysis for fixed-priority scheduling of hard real-timesystems

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution time, a fixed priority and a deadline. A method for determining the schedulability of each task and subtask is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of any task set on a uniprocessor whose priority structure can be modeled as serially executed subtasks, which can lead to a very complex priority structure. Important examples include task sets that involve interrupts, certain synchronization protocols, certain precedence constraints, nonpreemptible sections, and some message-passing systems. The method is illustrated by a robotics example     

Deterministic preemptive scheduling of real-time tasks

Algorithms for the preemptive scheduling of deterministic, real-time tasks can have applications in providing quality-of-service guarantees to packet flows in multichannel optical networks     

硬实时混合任务在线节能调度技术分析

对混合实时任务节能调度技术进行了分析,深入探讨了目前优秀的硬实时系统在线节能调度算法(OLDVS),指出其存在不足的原因 ,即松弛时间丢失和松弛时间转移。为了提高其节能效果,给出了多种改进思路,为进一步研究工作做出有益的探索。     

Dynamic scheduling of hard real-time tasks and real-time threads

The authors investigate the dynamic scheduling of tasks with well-defined timing constraints. They present a dynamic uniprocessor scheduling algorithm with an O(n log n) worst-case complexity. The preemptive scheduling performed by the algorithm is shown to be of higher efficiency than that of other known algorithms. Furthermore, tasks may be related by precedence constraints, and they may have arbitrary deadlines and start times (which need not equal their arrival times). An experimental evaluation of the algorithm compares its average case behavior to the worst case. An analytic model used for explanation of the experimental results is validated with actual system measurements. The dynamic scheduling algorithm is the basis of a real-time multiprocessor operating system kernel developed in conjunction with this research. Specifically, this algorithm is used at the lowest, threads-based layer of the kernel whenever threads are created     

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.     

Optimal scheduling of measurement-based parallel real-time tasks

Real-Time Systems - In this work we consider a measurement-based model for parallel real-time tasks represented by the work and span parameters of directed acyclic graphs, with different bounds for...     

Uniprocessor scheduling of real-time synchronous dataflow tasks

Real-Time Systems - The synchronous dataflow graph (SDFG) model is widely used today for modeling real-time applications in safety-critical application domains. Schedulability analysis techniques...     

Worst-case execution-time analysis for embedded real-time systems

In this article we give an overview of the worst-case execution time (WCET) analysis research performed by the WCET group of the ASTEC Competence Centre at Uppsala University. Knowing the WCET of a program is necessary when designing and verifying real-time systems. The WCET depends both on the program flow, such as loop iterations and function calls, and on hardware factors, such as caches and pipelines. WCET estimates should be both safe (no underestimation allowed) and tight (as little overestimation as possible). We have defined a modular architecture for a WCET tool, used both to identify the components of the overall WCET analysis problem, and as a starting point for the development of a WCET tool prototype. Within this framework we have proposed solutions to several key problems in WCET analysis, including representation and analysis of the control flow of programs, modeling of the behavior and timing of pipelines and other low-level timing aspects, integration of control flow information and low-level timing to obtain a safe and tight WCET estimate, and validation of our tools and methods. We have focussed on the needs of embedded real-time systems in designing our tools and directing our research. Our long-term goal is to provide WCET analysis as a part of the standard tool chain for embedded development (together with compilers, debuggers, and simulators). This is facilitated by our cooperation with the embedded systems programming-tools vendor IAR Systems.     

Application of real-time monitoring to scheduling tasks with randomexecution times

A real-time monitor is employed to aid in scheduling tasks with random execution times in a real-time computing system. The real-time monitor is composed of dedicated hardware called test and measurement processors (TMPs). It is used to measure accurately and with minimal interference the true execution time, which consists of pure execution time and resource sharing delay. The monitor is a permanent and transparent part of a real-time system. It degrades system performance by less than 0.1% and does not interfere with the host system's execution. The measured pure execution time and resource sharing delay for each task have been used to develop a mechanism that reduces the discrepancy between the worst-case execution time (WET) and the estimated execution time. This result is used to decide at the earliest possible time whether or not a task can meet its deadline. A set of example tasks are experimentally measured in a simulated environment while their characteristics are varied. The measured data are analyzed, demonstrating the utility and power of the proposed real-time monitor     

Two processor scheduling with limited preemption

We introduce deterministic task system scheduling with limited preemption—that is, a preempted task can resume execution only on the processor where it originally executed. Two classes of limited preemptive schedules are introduced, corresponding to whether or not unforced idle time is allowed in the schedule. Our main result is to show that, on two processors, these two classes are equivalent with respect to optimal schedule lengths. We use this result to establish a hierarchy of optimal schedule lengths.     

Algorithms for scheduling real-time tasks with input error andend-to-end deadlines

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task     

Online deadline scheduling with preemption penalties

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of ρ times the weight of the preempted job, where ρ ? 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty.     

An optimal scheduling algorithm for preemptable real-time tasks

An optimal scheduling algorithm is presented for real-time tasks with arbitrary ready times and deadlines in single processor systems. The time complexity of the algorithm is O(n log n), which improves the best previous result of O(n²). Furthermore, the lower bound of the worst-case time complexity of the problem is shown to be of O(n log n) and therefore the time complexity of the presented algorithm is shown to be lower bound.