A compact task graph representation for real-time scheduling

A new task graph representation, namely the compact task graph (CTG), is developed to aid in the scheduling of a set of communicating periodic real-time tasks. This representation explicitly expresses the potential for parallelism across tasks as well as the idle times that may be encountered within application tasks. A CTG based scheduler can generate schedules that are able to meet deadlines by interleaving the execution of tasks on a single processor and/or overlapping the execution of tasks on multiple processors. The construction of a CTG is based upon the busy-idle execution profiles for the tasks generated by the compiler. The profiles are computed assuming that sufficient resources are available for parallel execution of all tasks. Thus, they expose all opportunities for overlapped and interleaved execution. The compiler analyzes the profiles to identify useful opportunities for interleaving and expresses them in the CTG without unnecessary partitioning of the tasks. The CTG is powerful because it expresses schedules that are not expressed by existing approaches for constructing task graphs. Schedules can be generated efficiently since a CTG's construction minimizes the splitting of tasks. We briefly demonstrate the usefulness of CTGs in scheduling real-time tasks and scheduling monitoring tasks without affecting the timing of application tasks.Supported in part by the National Science Foundation through a Presidential Young Investigator Award CCR-9157371 and Grant CCR-9212020.     

Computerized real-time analysis of football games

Computer systems support many coaching activities performed before and after competitions, such as strategy development and performance evaluation, but competent assistance during games is much more demanding. It requires real-time interpretation of sensor data, the recognition and classification of ball actions, and fast-action game analysis and assessment. Only recently has high-precision microwave technology enabled computer systems to simultaneously track the position of players and the ball. Consequently, real-time game analysis systems must be able to automatically recognize intentional activities in a multiagent system with continually acting agents. To meet these demands, we've developed the football interaction and process model and a software system that can acquire, interpret, and analyze this model. Our FIPM system can acquire models of player skills, infer action-selection criteria, and determine player and team strengths and weaknesses.     

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).     

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.     

Stochastic games on a graph

Stochastic games on a graph are considered under the assumption that the phase space of a system and the space of values of the control actions of both players are complete separable metric spaces. The sufficient conditions for the existence of the optimal stationary nonrandomized Markovian strategies for both players are obtained. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 13–144, September–October, 1999.     

Unbounded parallel-batching scheduling with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel-batching machine. The batching machine can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. Two main categories of batch processing based on the compatibility of job families or agents are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. The goal is to find a schedule for all jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent below or at a fixed value Q. Polynomial-time and pseudo-polynomial-time algorithms are provided to solve various combinations of regular objective functions for the scenario in which job families are either incompatible or compatible.     

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.     

Multi-camera video surveillance for real-time analysis and reconstruction of soccer games

Soccer analysis and reconstruction is one of the most interesting challenges for wide-area video surveillance applications. Techniques and system implementation for tracking the ball and players with multiple stationary cameras are discussed. With video data captured from a football stadium, the real-world, real-time positions of the ball and players can be generated. The whole system contains a two-stage workflow, i.e., single view and multi-view processing. The first stage includes categorizing of players and filtering of the ball after changing detection against an adaptive background and image-plane tracking. Occlusion reasoning and tracking-back is applied for robust ball filtering. In the multi-view stage, multiple observations from overlapped single views are fused to refine players’ positions and to estimate 3-D ball positions using geometric constraints. Experimental results on real data from long sequences are demonstrated.     

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.     

Automated reasoning for attributed graph properties

Graphs are ubiquitous in computer science. Moreover, in various application fields, graphs are equipped with attributes to express additional information such as names of entities or weights of relationships. Due to the pervasiveness of attributed graphs, it is highly important to have the means to express properties on attributed graphs to strengthen modeling capabilities and to enable analysis. Firstly, we introduce a new logic of attributed graph properties, where the graph part and attribution part are neatly separated. The graph part is equivalent to first-order logic on graphs as introduced by Courcelle. It employs graph morphisms to allow the specification of complex graph patterns. The attribution part is added to this graph part by reverting to the symbolic approach to graph attribution, where attributes are represented symbolically by variables whose possible values are specified by a set of constraints making use of algebraic specifications. Secondly, we extend our refutationally complete tableau-based reasoning method as well as our symbolic model generation approach for graph properties to attributed graph properties. Due to the new logic mentioned above, neatly separating the graph and attribution parts, and the categorical constructions employed only on a more abstract level, we can leave the graph part of the algorithms seemingly unchanged. For the integration of the attribution part into the algorithms, we use an oracle, allowing for flexible adoption of different available SMT solvers in the actual implementation. Finally, our automated reasoning approach for attributed graph properties is implemented in the tool AutoGraph integrating in particular the SMT solver Z3 for the attribute part of the properties. We motivate and illustrate our work with a particular application scenario on graph database query validation.     

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.     

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     

RTLinux实时调度算法的改进与实现

为提高RTLinux的实时调度性能,分析了RTLinux的工作原理,针对其现有调度算法的不足,提出了改进的最小裕度优先算法,有效减少了颠簸现象,提高了算法性能.深入分析了RTLinux下ILLF调度器的实现,提高了CPU的使用率,增强了系统调度性能,并通过程序验证和调度器仿真,验证了算法的可行性和有效性.     

Efficient real-time divisible load scheduling

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, current approaches are not efficient and do not scale well. In this paper, we propose a linear algorithm for real-time divisible load scheduling. Unlike existing approaches, the new algorithm relaxes the tight coupling between the task admission controller and the task dispatcher. By eliminating the need to generate exact schedules in the admission controller, the algorithm avoids high overheads. We also proposed a hybrid algorithm that combines the best of our efficient algorithm and a previously best-known approach. We experimentally evaluate the new algorithm. Simulation results demonstrate that the algorithm scales well, can schedule large numbers of tasks efficiently, and performs similarly to existing approaches in terms of providing real-time guarantees.     

Open problems in real-time scheduling

We state some of the most important open algorithmic problems in real-time scheduling, and survey progress made on these problems since the 2009 Dagstuhl scheduling seminar.     

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     

A novel real-time scheduling algorithm and performance analysis of a MapReduce-based cloud

MapReduce, a popular programming model for processing data-intensive tasks, has achieved great success in a wide range of applications such as search indexing, social network mining, collaborative recommendation, and spam detection. However, the ability of MapReduce is limited in two respects by its default schedulers. First, it does not support concurrent services sharing a cloud datacenter and second, it fails to guarantee response time for deadline-constrained services. This paper proposes the Paused Rate Monotonic (PRM) algorithm for scheduling hard real-time tasks on a MapReduce-based cloud. The scheduling performance is analyzed theoretically. We prove a bound on cluster utilization, which can be used as a sufficient condition to test whether a given task set can be scheduled. Both the theoretical analysis and experimental evaluation show that the PRM algorithm outperforms traditional real-time ones by improving the probability that a real-time task set can be scheduled on a MapReduce-based cloud.     

Wireless real-time on-demand data broadcast scheduling with dual deadlines

In this paper, issues involved in the design of real-time on-demand broadcast system which maintains data temporal constraints are discussed. We propose a new online scheduling algorithm, called RDDS that incorporates access frequency, data size, request-deadline and data-deadline of pending requests for real-time on-demand broadcast system with dual deadlines. Furthermore, the concepts of deferrable requests and non-deferrable requests are introduced, cases of non-deferrable requests are analyzed, and Non-deferrable Request First policy is proposed and integrated into RDDS to form another new algorithm, called RDDS-W. We have performed a series of simulation experiments to evaluate the performance of our algorithms as compared with other previously proposed methods. The experimental results show that our algorithms can substantially outperform other algorithms under a wide range of scenarios, especially when combining with Non-deferrable Request First policy, which improves the performance significantly.     

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