Nowadays, one of the most challenging design issues of battery-driven real-time embedded systems is how to reduce energy consumption such that the battery life can be prolonged. Based on dynamic voltage scaling technology, many energy-efficient real-time task scheduling algorithms have been proposed, however, relatively little work is done in the presence of task synchronization. In this paper, energy-efficient synchronization approaches for real-time embedded systems have been investigated under various characteristics of shared resources (e.g., non-preemptible, preemptible, and abortable critical sections) and system architectures (e.g., uniprocessor and multi-core processor).

In this paper, we are interested in the energy-efficient scheduling of real-time tasks which may access lock-free objects in a non-ideal DVS processor. We propose an algorithm, called interference-aware speed assignment (IASA), to assign proper execution speeds to tasks which are scheduled by the earliest deadline first (EDF) scheduling policy. The execution speeds are calculated based on the schedulability analysis of the EDF policy with the cost of lock-free objects' retry loops. As a result, the energy consumption can be reduced while satisfying the timing constraints of real-time tasks. Our experimental results show that the IASA algorithm is very effective in energy saving.

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job must be executed within one of its feasible intervals. In this paper, we are interested in maximizing the sum of the weights of the multiple feasible interval jobs that complete in time when jobs are associated with weights for its in-time completion. We develop heuristic algorithms that apply the least-earliest-completion-time-first (LECF) strategy as a schedulability test or apply variations of the LECF strategy with job evictions. The capability of our proposed algorithms is verified by a series of simulations.

Extensible markup language (XML) has become an active research topic in recent years. Many excellent model-mapping-schema-based approaches have been proposed to translate and manipulate XML documents in relational databases. However, most previous work has a potential performance problem for retrieving XML data from a relational database, because a large number of join operations are needed. In this paper, we introduce a new model-mapping-schema-based approach, called XPred, to reduce significant join costs for providing real-time access to XML data. The basic idea is to store the structural information distributely into nodes to reduce the number of join operations when processing user queries. In particular, for every node in a given XML document, we store its predecessor's information within itself. It can eliminate the join operations for parent-child traversing such that the performance of query processing can be improved. The capability of our proposed approach was verified by a series of simulation experiments based on the XMark [1][2], for which we have some encouraging experimental results.

Energy efficiency remains a critical design issue for wireless sensor networks. How to maintain the network connectivity and, at the same time, to minimize the energy consumption is a very challenging problem. Different from many previous excellent results, we explore the topology control problem for heterogeneous wireless sensor networks. Our objective is to propose distributed topology control algorithms, where only local information is kept for all of the nodes. The experimental results show the strengths of the proposed algorithms in the average edge length and the average link length.

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.

Summary form only given. While excellent research results have been proposed for query optimization, little work has been done for the scheduling of query execution plans. We target the optimization problem of the schedule lengths of query execution plans in a symmetric multiprocessor (SMP) database system. We show the NP-hardness of the optimization problem. A critical-path-based algorithm is proposed to minimize the schedule length of a collection of query execution plans. When each query execution plan has a tree or a directed acyclic graph structure, we show that the approximation ratios of our proposed algorithm are 2 and (3 - 2/M), respectively, where M is the number of processors in the system. When the proposed algorithm is adopted for online usages, the competitive ratio of the algorithm is proven being (3 $2/M). The proposed algorithm is optimal when there is a sufficient number of processors. The performance of the proposed algorithm is evaluated based on the TPC-C benchmark.

Processes running in a multiple-disk environment may share non-preemptible resources on the processor and, at the same time, request services from disk subsystems. In this paper, we propose a methodology which is efficient and easy to implement for scheduling processes in multiple-disk environments. In other words, our methodology addresses the scheduling of real-time processes which may stop to wait for disk I/O without releasing any locked semaphores. Our proposed methodology is a variation of the well-known priority ceiling protocol to schedule processes running in multiple-disk environments. The capability of the proposed methodology is verified by a series of simulation experiments under different workloads of CPU-bound and I/O-bound processes in multiple-disk environments, for which we have some encouraging experimental results.

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system.

The emergence of Intelligent I/O (I2O) architecture provides a standard for high-performance I/O subsystems and introduces intelligence at the hardware level. With an embedded processor, I2O adaptors can offload the major I/O processing workload from the CPU and, at the same time, increase the I/O performance. This paper addresses the essential issue in the design of disk scheduling for I2O RAID-0 devices. We explore online real-time multi-disk scheduling for I2O requests and propose highly efficient algorithms to minimize the number of deadline violations and, at the same time, to improve the response times of requests. The proposed methodologies are verified by a series of experiments under realistic and randomly generated workloads.