44806973
Cache-Conscious Limited Preemptive Scheduling
In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.
8167367
Online QoS Optimization Using Service Classes in Surveillance Radar Systems
Many application level qualities are functions of available computation resources. Recent studies have handled the computation resource allocation problem to maximize the overall application quality. However, such QoS problems are fundamentally multi-dimensional optimization problems that require extensive computation. Therefore, online usage of optimization procedures may significantly reduce the computation resource available for applications. This raises the question of how to best use the optimization procedures for dynamic real-time task sets. In dynamic real-time systems, it is important to improve the performance by re-allocating the resources adapting to dynamic situations. However, the overhead of changing task parameters (i.e., algorithms and frequencies) for resource re-allocation is non-negligible in many applications. Thus, too frequent change of resource allocation may not be desirable. This paper proposes a method called service classes configuration to address the QoS problem with dynamic arrival and departure of tasks. The method avoids online usage of optimization procedures by offline designing templates (called service classes) of resource allocation, which will be adaptively used depending on online situations. The service classes are designed by best trading-off the accuracy of dynamic adaptation against the overhead of resource re-allocation. A simplified radar application is used as an illustrative example.
12313444
Real time guarantee of aperiodic packets in single hop ad hoc wireless networks
Building real-time applications on 802.11 wireless networks is challenging because the medium access protocol is distributed and nodes contend for the channel nondeterministically. So far all attempts at providing real-time services in 802.11 require restrictive traffic assumptions such as periodicity. In this paper we describe distributed admission control, a modification to 802.11 that, when used with distributed prioritization, provides real-time guarantees for aperiodic packets. We show that barring external errors such as interference on the channel or incorrect priority scheduling this protocol guarantees deadlines will be met.
16132542
Stochastic analysis of periodic real-time systems
This paper describes a stochastic analysis method for general periodic real-time systems. The proposed method accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with maximum utilization factor greater than one. The method uniformly covers both fixed-priority scheduling (such as rate monotonic) as well as dynamic-priority scheduling (such as earliest deadline first) and can handle arbitrary relative deadlines and execution time distributions. The accuracy of the method is proven by comparing the results from the analysis with those obtained from simulations, as well as other methodologies in the literature.
42435746
Efficiently supporting hard/soft deadline transactions in real-time database systems
As in other application areas, there is an increasing need for managing a large amount of data in the real-time area. This need gave birth to a system called a real-time database system (RTDBS) that provides database operations with timing constraints. One typical timing constraint in an RTDBS is temporal consistency that states that a transaction must read temporally valid data objects. This requires the data objects to be updated repeatedly. This paper proposes three novel schemes that aim to minimize the number of updates of data objects needed for guaranteeing the temporal consistency requirements of transactions with hard-deadlines. The three guarantee schemes differ from each other in the amount of updates and the implementation complexity. This paper also gives a framework for integrating transactions with soft-deadlines into the three guarantee schemes.
20686264
Finite-Horizon Scheduling of Radar Dwells with Online Template Construction
Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism that is inherent in schedulers that assume a task executes forever. We also develop the notion of modular schedule update which allows portions of a schedule to be altered without affecting the entire schedule, thereby simplifying the scheduler. Through extensive simulations, we validate our claims of providing greater scheduling flexibility without compromising on performance when compared with earlier work based on templates constructed offline.
33610569
Compression-based broadcast strategies in wireless information systems
Data delivery is through broadcast in wireless information systems due to the asymmetric communication property. However, broadcasting data easily wastes large access time because the large amount of data pages needs to be broadcast. In this paper we propose three compression-based strategies considering access order to reduce access time. Then, the expected access time of three proposed strategies is also derived by using the probability model. Our analytic and experimental results show that the compression-based broadcast strategies can dramatically reduce the access time for mobile users (MU).
3095915
On mining general temporal association rules in a publication database
In this paper, we explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items, each containing an individual exhibition period. The current model of association rule mining is not able to handle a publication database due to the following fundamental problems: (1) lack of consideration of the exhibition period of each individual item; and (2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm, progressive-partition-miner (PPM), to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database into exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset based on the intrinsic partitioning characteristics. PPM is also designed to employ a filtering threshold in each partition to prune out those cumulatively infrequent 2-itemsets at an early stage. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by schemes which are directly extended from existing methods.
12503943
Model-based visual feedback control for a hand-eye coordinated robotic system
The integration of a single camera into a robotic system to control the relative position and orientation between the robot's end-effector and a moving part in real time is discussed. Only monocular vision techniques are considered because of current limitations in the speed of computer vision analysis. The approach uses geometric models of both the part and the camera, as well as the extracted image features, to generate the appropriate robot control signals for tracking. Part and camera models are also used during the teaching stage to predict important image features that appear during task completion.<<ETX>>
2051959
Performance Evaluation of Forwarding Strategies for Location Management in Mobile Networks
This paper presents a methodology for evaluating the performance of forwarding strategies for location management in a personal communication services (PCS) mobile network. A forwarding strategy in the PCS network can be implemented by two mechanisms: a forwarding operation which follows a chain of databases to locate a mobile user and a resetting operation which updates the databases in the chain so that the current location of a mobile user can be known directly without having to follow a chain of databases. In this paper, we consider the PCS network as a server whose function is to provide services to the mobile user for ‘updating the location of the user as the user moves across a database boundary’ and ‘locating the mobile user’. We use a Markov chain to describe the behavior of the mobile user and analyze the best time when forwarding and resetting should be performed in order to optimize the service rate of the PCS network. We demonstrate the applicability of our approach with hexagonal and mesh coverage models for the PCS network and provide a physical interpretation of the result.
33337266
A genetic fuzzy agent using ontology model for meeting scheduling system
A Genetic Fuzzy Agent (GFA) using the ontology model for Meeting Scheduling System (MSS) is presented in this paper. The ontology model includes the Fuzzy Meeting Scheduling Ontology (FMSO) and the Fuzzy Personal Ontology (FPO) that can support to construct the knowledge base of the GFA. The FMSO is utilized to record and describe the meeting scheduling domain knowledge for the GFA. In addition, we implement a FMSO editor for generating the Web Ontology Language, OWL, that will be utilized by the GFA. Furthermore, the GFA will infer the suitable meeting time slots based on the ontology model. Moreover, it also adjusts the FMSO and FPO based on the results of the genetic learning mechanism for the next meeting. The experimental results show that our approach can effectively work for MSS.