Comments on “Generalized rate monotonic schedulability bounds using relative period ratios”

In this Letter, it is shown that the schedulability test method for task sets with the maximum period ratio larger than or equal to 2 presented in the paper [Wei et al., Generalized rate monotonic schedulability bounds using relative period ratios, Information Processing Letters 107 (5) (2008) 142-148] is not exactly correct by presenting a counter-example. Correct sufficient conditions for using period ratios in RM schedulability test when the maximum period ratio is not less than 2 are also presented.     

Rate monotonic schedulability tests using period-dependent conditions

Feasibility and schedulability problems have received considerable attention from the real-time systems research community in recent decades. Since the publication of the Liu and Layland bound, many researchers have tried to improve the schedulability bound of the RM scheduling. The LL bound does not make any assumption on the relationship between any of the task periods. In this paper we consider the relative period ratios in a system. By reducing the difference between the smallest and the second largest virtual period values in a system, we can show that the RM schedulability bound can be improved significantly. This research has also proposed a system design methodology to improve the schedulability of real time system with a fixed system load.

Generalized rate monotonic schedulability bounds using relative period ratios

One of the most well-studied scheduling algorithms for real-time systems is the Rate Monotonic (RM) scheduling for periodic tasks. In this paper we derive a generalized RM schedulability bound by considering relative period ratios among tasks in a system. We show that schedulability bounds published earlier are special cases of our generalized bound. Our new bound may provide a higher value than earlier results.     

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3m/4=0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m(1−1/e)≈0.6321m, where e≈2.718 is the Euler's number.     

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

时间Petri网的可调度分析及在FMS中的应用

在实时系统中,检查任务执行的计划是否满足要求的时间约束称为可调度分析.通过把时间特性与其他行为特性分离,提出了一种以时间Petri网建模的实时系统调度分析方法.如果特定任务的执行是可调度的,则可以计算任务执行的时间跨度,否则确定出不可调度的变迁以便于调整时间约束和纠正设计错误.提出了一种通过把复杂的任务序列分解成一些子序列来进行可调度性分析的综合时序分析技术,它不仅提高了效率,也有助于关于调度的可达性问题的讨论.讨论了柔性制造系统FMS中的车间装配子系统的可调度性.     

On the convergence of the holistic analysis for EDF distributed systems

Dynamic scheduling techniques, and EDF (Earliest Deadline First) in particular, have demonstrated their ability to increase the schedulability of real time systems compared to fixed-priority scheduling. In distributed systems, the scheduling policies of the processing nodes tend to be the same as in stand-alone systems and, although few EDF networks exist, it is foreseen that dynamic scheduling will gradually develop into real-time networks. There are some response time analysis techniques for EDF scheduled distributed systems, mostly derived from the holistic analysis developed by Spuri. A major factor influencing the response time is the release jitter of each task, which is the maximum variation suffered by the release time of the task jobs. The convergence of the holistic analysis in the context of EDF distributed systems with shared resources had not been studied until now. There is a circular dependency between the task release jitter values, response times and the preemption level ceilings of shared resources. In this paper we present an extension of Spuri’s algorithm and we demonstrate that its iterative formulas are non-decreasing, even in the presence of shared resources. This result enables us to assert that the new algorithm converges towards a solution for the response times of the tasks and messages in a distributed system.¹     

A Process Algebraic Approach to the Schedulability Analysis of Real-Time Systems

To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of ACSR with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can use VERSA, a toolkit we have developed for ACSR, to perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation.     

Search and track coordination in multi-ship multi-radar systems using schedulability envelope

This paper addresses the search and track coordination problems of multiple shipboard radars. The proposed approach first exploits the physical characteristics of a single phased array radar to improve its effective capacity. Its effective capacity is abstracted by a closed-form equation called a schedulability envelope. Using the schedulability envelope for each radar, we deal with search and track coordination as a relative-load-balancing problem in a multi-resource environment. The simulation results show that the proposed approach significantly improves the overall capacity of a multi-ship multi-radar system.

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.     

Minimal schedulability interval for real-time systems of periodic tasks with offsets

We consider real-time systems in highly safety context where tasks have to meet strict deadlines. Tasks are periodic, may have offsets, share critical resources and be precedence constrained. Off-line scheduling should be of great help for such systems, but methods proposed in the literature cannot deal with them. Our aim is to extend and improve the well-known cyclicity result of Leung and Merill to every scheduling algorithm and to systems of interacting tasks with offsets. One of the main benefit of our result is to enable the use of off-line scheduling methods for those real-time critical systems.     

Stochastic analysis of real-time systems under preemptive priority-driven scheduling

Exact stochastic analysis of most real-time systems under preemptive priority-driven scheduling is unaffordable in current practice. Even assuming a periodic and independent task model, the exact calculation of the response time distribution of tasks is not possible except for simple task sets. Furthermore, in practice, tasks introduce complexities such as release jitter, blocking in shared resources, etc., which cannot be handled by the periodic independent task set model. In order to solve these problems, exact analysis must be abandoned for an approximated analysis. However, in the real-time field, approximations must not be optimistic, i.e. the deadline miss ratios predicted by the approximated analysis must be greater than or equal to the exact ones. In order to achieve this goal, the concept of pessimism needs to be mathematically defined in the stochastic context, and the pessimistic properties of the analysis carefully derived. This paper provides a mathematical framework for reasoning about stochastic pessimism, and obtaining mathematical properties of the analysis and its approximations. This framework allows us to prove the safety of several proposed approximations and extensions. We analyze and solve some practical problems in the implementation of the stochastic analysis, such as the problem of the finite precision arithmetic or the truncation of the probability functions. In addition, we extend the basic model in several ways, such as the inclusion of shared resources, release jitter or non-preemptive sections.

An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor edf schedulability analysis, and permits the derivation of an improved speed-up bound.

基于多核处理器系统多维限制的节能实时调度

介绍了多核处理器系统所面对的处理器实际限制、抢占调度实际限制和并行任务模型实际限制等多维限制挑战, 主要针对处理器开销模型、有限抢占模型和复杂并行任务模型等方面, 深入探讨了基于系统实际多维模型的多核节能实时调度研究, 为促进多核处理器系统在实时嵌入式领域的应用提供理论和技术参考.     

Lowest priority first based feasibility analysis of real-time systems

The feasibility problem of periodic tasks under fixed priority systems has always been a critical research issue in real-time systems and a number of feasibility tests have been proposed to guarantee the timing requirements of real-time systems. These tests can be broadly classified into: (a) inexact and (b) exact tests. The inexact tests are applied to the task sets that present lower utilization, while the exact tests become inevitable when system utilization is high. The exact tests can be further classified into: (a) Scheduling Points Tests (SPT) and (b) Response Time Tests (RTT). The SPT analyze task set feasibility at the arrival times while the RTT utilize fixed-point techniques to determine task feasibility. All of the available exact feasibility tests, whichever class it belongs to, share pseudo-polynomial complexity. Therefore, the aforementioned tests become impractical for online systems. Currently, both SPT and RTT employ the Highest Priority First (HPF) approach, which determines the system feasibility by testing the schedulability of individual tasks in the decreasing order of priority. In contrast, this work exploits the Lowest Priority First (LPF) alternative which is an aggressive solution based on the observation that the system infeasibility is primarily due to the lower priority tasks and not because of the higher priority tasks. For the average case analysis, our technique demonstrates promising results. Moreover, in the worst case scenario our solution is no inferior to the existing state of the art alternatives. We compare our proposed technique with the existing tests: (a) by counting the number of scheduling points used by a test that belongs to the SPT, (b) by counting the number of inner-most loops executed by an algorithm for the RTT, and (c) by measuring the actual running time of the existing alternatives.     

实时系统最坏执行时间分析*

实时系统开发过程中必须强调时间的重要性和支持时间的可预报性。最坏执行时间分析与可调度性分析构成了实时系统时间方面操作可信的基础。最坏执行时间分析计算任务执行时间的上界,这些任务的上界用来分配正确的CPU时间给实时任务。最坏执行时间是可调度分析工具的输入,可调度分析决定了一组任务在一个给定的目标系统下是否可调度。对最坏执行时间分析方面的研究进行了综述,给出在这一领域所取得的进展。 还讨论了在最坏执行时间分析方面存在的问题,给出了将来的研究方向。     

Utilization bound for periodic task set with composite deadline

Due to polynomial time complexity, utilization based tests are desired for online feasibility analysis of periodic task systems. However, the associated disadvantage with these tests is that they propose a bound on system utilization, which trade processor utilization for performance. On the contrary, response time based tests share pseudo-polynomial time complexity, which are very expensive in terms of analysis time and therefore, impractical for analyzing feasibility of online systems. Realizing the advantage of utilization based tests over response time tests, attempts are being made to propose utilization based exact tests that achieve 100% CPU utilization for the system by modifying task parameters such as restricting task periods to be harmonic. We show that in systems where task deadlines are large, better results are obtained by making the task deadlines harmonic. The paper proposes a novel solution to feasibility problem of periodic task system under the assumption of composite deadline by providing a utilization based exact test with an upper bound of 1 and complexity O(n).     

Power efficient rate monotonic scheduling for multi-core systems

More computational power is offered by current real-time systems to cope with CPU intensive applications. However, this facility comes at the price of more energy consumption and eventually higher heat dissipation. As a remedy, these issues are being encountered by adjusting the system speed on the fly so that application deadlines are respected and also, the overall system energy consumption is reduced. In addition, the current state of the art of multi-core technology opens further research opportunities for energy reduction through power efficient scheduling. However, the multi-core front is relatively unexplored from the perspective of task scheduling. To the best of our knowledge, very little is known as of yet to integrate power efficiency component into real-time scheduling theory that is tailored for multi-core platforms. In this paper, we first propose a technique to find the lowest core speed to schedule individual tasks. The proposed technique is experimentally evaluated and the results show the supremacy of our test over the existing counterparts. Following that, the lightest task shifting policy is adapted for balancing core utilization, which is utilized to determine the uniform system speed for a given task set. The aforementioned guarantees that: (i) all the tasks fulfill their deadlines and (ii) the overall system energy consumption is reduced.