Energy efficient fault-tolerant earliest deadline first scheduling for hard real-time systems

Aggressive technology scaling has dramatically increased the power density and degraded the reliability of embedded real-time systems. The goal of our research in this paper is to develop effective scheduling methods that can minimize the energy consumption and, at the same time, tolerate up to \(K\) transient faults when executing a hard real-time system scheduled according to the EDF policy. Three scheduling algorithms are presented in this paper. The first algorithm is an extension of a well-known fault oblivious low-power scheduling algorithm. The second algorithm intends to minimize the energy consumption under the fault-free situation while reserving adequate resources for recovery when faults strike. The third algorithm improves upon the first two by sharing the reserved resources and thus can achieve better energy efficiency. Simulation results show that the proposed algorithms consistently outperform other related approaches in energy savings.     

Sensitivity analysis of arbitrary deadline real-time systems with EDF scheduling

The correctness of a real-time system depends on not only the system’s output but also on the time at which results are produced. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set it is useful to know what changes can be made to a task that will result in a system that is borderline schedulable. It is also beneficial in an engineering context to know the minimum speed of a processor that will deliver a schedulable system. We address the following sensitivity analysis (parameter computations) for EDF-scheduled systems on a uniprocessor: task execution times, speed of the processor, task periods and task relative deadlines. We prove that an optimal (minimum or maximum) system parameter can be determined by a single run of the Quick convergence Processor demand Analysis (QPA) algorithm. This algorithm provides efficient and exact sensitivity analysis for arbitrary deadline real-time systems. We also improve the implementation of this sensitivity analysis by using various starting values for the algorithms. The approaches developed for task parameter computations are therefore as efficient as QPA, and are easily incorporated into a system design support tool.     

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.     

On earliest deadline first scheduling for temporal consistency maintenance

A real-time object is one whose state may become invalid with the passage of time. A temporal validity interval is associated with the object state, and the real-time object is temporally consistent if its temporal validity interval has not expired. Clearly, the problem of maintaining temporal consistency of data is motivated by the need for a real-time system to track its environment correctly. Hence, sensor transactions must be able to execute periodically and also each instance of a transaction should perform the relevant data update before its deadline. Unfortunately, the period and deadline assignment problem for periodic sensor transactions has not received the attention that it deserves. An exception is the More-Less scheme, which uses the Deadline Monotonic (DM) algorithm for scheduling periodic sensor transactions. However, there is no work addressing this problem from the perspective of dynamic priority scheduling. In this paper, we examine the problem of temporal consistency maintenance using the Earliest Deadline First (EDF) algorithm in three steps: First, the problem is transformed to another problem with a sufficient (but not necessary) condition for feasibly assigning periods and deadlines. An optimal solution for the problem can be found in linear time, and the resulting processor utilization is characterized and compared to a traditional approach. Second, an algorithm to search for the optimal periods and deadlines is proposed. The problem can be solved for sensor transactions that require any arbitrary deadlines. However, the optimal algorithm does not scale well when the problem size increases. Hence, thirdly, we propose a heuristic search-based algorithm that is more efficient than the optimal algorithm and is capable of finding a solution if one exists.

Feasibility analysis of real-time transactions

The objective of this paper is two-fold: give a survey of response time analysis (RTA), and contribute to schedulability analysis for the real-time transaction model. The RTA is studied under fixed priority policies (FPP), while schedulability analysis assumes an optimal scheduling algorithm (like the deadline driven scheduling algorithm EDF) in a preemptive context on uniprocessor systems. We compare the transaction model to the family of multiframe models, then present the exact, and approximated methods, as well as a tunable method to compute the RTA. Finally we present a new schedulability analysis method and an efficient algorithm to speed up this test.     

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.     

Chronological scheduling of transactions with temporal dependencies

Database applications often impose temporal dependencies between transactions that must be satisfied to preserve data consistency. The extant correctness criteria used to schedule the execution of concurrent transactions are either time independent or use strict, difficult to satisfy real-time constraints. On one end of the spectrum, serializability completely ignores time. On the other end, deadline scheduling approaches consider the outcome of each transaction execution correct only if the transaction meets its real-time deadline. In this article, we explore new correctness criteria and scheduling methods that capture temporal transaction dependencies and belong to, the broad area between these two extreme approaches. We introduce the concepts ofsuccession dependency andchronological dependency and define correctness criteria under which temporal dependencies between transactions are preserved even if the dependent transactions execute concurrently. We also propose achronological scheduler that can guarantee that transaction executions satisfy their chronological constraints. The advantages of chronological scheduling over traditional scheduling methods, as well as the main issues in the implementation and performance of the proposed scheduler, are discussed.     

Optimal scheduling with deadline constraints in tree networks

The problem of scheduling time-critical messages over a tree network is considered. Messages arrive at any of the nodes and have to reach the root node before their deadlines expire, else they are considered lost. The network is assumed to be operating in discrete time and the messages need one time unit for transmission from one node to the next along its path. The arrival and deadline processes are arbitrary. The policy which transmits messages with smallest extinction (arrival+deadline) time at every link is shown to minimize the number of lost messages over all time intervals and for every sample path     

An efficient response-time analysis for real-time transactions with fixed priority assignment

In the general context of tasks with offsets (general transactions), only exponential methods are known to calculate the exact worst-case response time (WCRT) of a task. The known pseudo-polynomial techniques give an upper bound of the WCRT. In this paper, we present a new worst-case response-time analysis technique (mixed method) for transactions scheduled by fixed priorities, and executing on a uniprocessor system. This new analysis technique gives a better (i.e. lower) pseudo-polynomial upper bound of the WCRT. The main idea is to combine the principle of exact calculation and the principle of approximation calculation, in order to decrease the pessimism of WCRT analysis, thus allowing improving the upper bound of the response time provided while preserving a pseudo-polynomial complexity. Then we define the Accumulative Monotonic property on which a necessary condition of feasibility is discussed. We also propose, to speed up the exact and mixed analysis, the dominated candidate task concept that allows reducing significantly the number of critical instants to study in an analysis.     

Incorporating load factor into the scheduling of soft real-time transactions for main memory databases

Many real-time applications have very tight time constraints which couldn't be met by disk resident databases. For those applications, main memory database where entire database is stored in main memory is the proper choice. It has been shown that coarse-granule locking is better than fine-granule locking for main-memory databases. Coarse-granule locking makes it easy to extract data access patterns correctly from canned transactions of main memory real-time database systems. In this paper, we propose two real-time transaction scheduling algorithms — CCA-ALF (Cost Conscious Approach with Average Load Factor) and EDF-CR-ALF (Earliest Deadline First-Conditional Restart with ALF) — which use both static (e.g., deadline) and dynamic information (e.g., system load) for main memory databases by utilizing data access patterns of transactions. We compare the performance of those algorithms with CCA and EDF-HP which do not use system load information at all. Our simulations on main memory databases indicate that: i) CCA-ALF is better than EDF-HP, CCA, and EDF-CR-ALF in terms of miss percent and mean lateness, and ii) CCA-ALF adapts well to the changes in the system load.     

Optimal anticipative scheduling with asynchronous transmissionopportunities

Service is provided to a set of parallel queues by a single server. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the connectivity instances for queue i. The service of different customers cannot overlap. Scheduling is required to resolve potential contention of services initiated at closely spaced, closer than the service time, connectivity instances. At any time t, the future connectivity instances are available for scheduling. An anticipative policy is given, which at time t schedules the transmissions until a certain future time t+h. The length of the scheduling horizon h is selected based on the backlog at t. The allocation of the server in the interval [t, t+h], is done in accordance to the backlogs of the individual queues at t. The throughput region of the system is characterized, and it is shown that the policy we propose achieves maximum throughput. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors. The average delay and the scheduling complexity are studied by simulation, and the trade-off between the two is demonstrated. The above scheduling problem arises in the access layer of the cross-links of a satellite network     

Automated competitive analysis of real-time scheduling with graph games

This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks contribute some utility to the system. Given such a taskset \({\mathcal {T}}\), the competitive ratio of an on-line scheduling algorithm \({\mathcal {A}}\) for \({\mathcal {T}}\) is the worst-case utility ratio of \({\mathcal {A}}\) over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset \({\mathcal {T}}\) and any finite-memory on-line scheduling algorithm \({\mathcal {A}}\), we show that the competitive ratio of \({\mathcal {A}}\) in \({\mathcal {T}}\) can be computed in polynomial time in the size of the state space of \({\mathcal {A}}\). Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset \({\mathcal {T}}\), and the goal is to automatically synthesize an optimal on-line scheduling algorithm \({\mathcal {A}}\), i.e., one that guarantees the largest competitive ratio possible for \({\mathcal {T}}\). We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the computational complexity of solving this game is Np-complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design.     

Lower bounds on online deadline scheduling with preemption penalties

We generalize and improve previous results of online preemptive deadline scheduling with preemption penalties. We consider both the preemption-restart and the preemption-resume models, and give new or improved lower bounds on the competitive ratio of deterministic online algorithms. In many cases the bounds are optimal when the job deadlines are tight. Our results show that the competitiveness varies linearly with the penalty factor.     

网格计算中时间和费用限制下的任务调度算法

在网格计算中,一个好的管理系统应有出色的算法来调度用户提交的任务。前人基于不同目的已设计了各种调度算法,但通常不易施行：重点考虑工作完成时间和所耗费用,给出确定的模型以调度独立的任务。通过恰当的建模,所求解的问题将演变成0—1规划问题,而这种问题清晰明了,且有现成算法求解,从而使得时间和费用最小化。给出一个例子验证了该算法的有效性。     

Schedulability of asynchronous real-time concurrent objects

We present a modular method for schedulability analysis of real time distributed systems. We extend the actor model, as the asynchronous model for concurrent objects, with real time using timed automata, and show how actors can be analyzed individually to make sure that no task misses its deadline. We introduce drivers to specify how an actor can be safely used. Using these drivers we can verify schedulability, for a given scheduler, by doing a reachability check with the Uppaal model checker. Our method makes it possible to put a finite bound on the process queue and still obtain schedulability results that hold for any queue length.     

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.     

A hybrid algorithm for scheduling scientific workflows in IaaS cloud with deadline constraint

The Journal of Supercomputing - Scientific workflows are used to process large amounts of data and perform complex analyses; thus, they require powerful computing resources to produce the desired...     

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.     

Competitive analysis of online real-time scheduling algorithms under hard energy constraint

In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings, we prove that no online algorithm can achieve a competitive factor greater than 1-\frace_maxE1-\frac{e_{\max}}{E}, where e _max is the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm EC-EDF ^∗ which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these settings. In non-uniform value density settings, we derive an upper bound on the competitive factor achievable by any online algorithm, as well as the competitive factors of EC-EDF and EC-EDF ^∗ algorithms. We also investigate the implications of having additional constraints on the online scheduling algorithm, including non-idling and non-preemptive execution constraints. Moreover, we analyze the case where the processor can adjust its speed at run-time through Dynamic Voltage Scaling (DVS) capability.