Energy And Workload Efficient Strategies For Real-time Database Systems

Real-Time DataBase System (abbreviated as RTDBS) is a combination product of database technology and real-time system, it integrates theories and techniques of both real-time systems and database systems. In recent years, RTDBS has been widely used in defense and civilian real-time information services such as power and data network man-agement, radar tracking, industrial process control and securities transactions, etc., where the applications need to access data regularly or access "temporary" data. Although the ap-plication of RTDBS has achieved great success, the same as many other computing systems, RTDBS also experiences the problem of excessive energy consumption. Excessive energy consumption has a huge impact on the system Quality of Service (including the service time, the stability and reliability, etc.). In some specific environments (e.g., the embedded envi-ronment), RTDBS typically relies on battery-power to work, the cost of replenishing system energy is too expensive. Sometimes the RTDBS even cannot be replenished in quite a long time due to environmental constraints. Moreover, in the foreseeable future, the battery life limitations are difficult to be completely resolved. At this point, saving energy consumption and thus extending the service time of RTDBS becomes particularly important.Different from data stored in traditional databases, a real-time data object is only valid in a given time period, which is defined as its temporal validity interval. In order to maintain temporal validity (a.k.a. temporal consistency), each real-time data object must be refreshed by a sensor update transaction before its temporal validity interval expires, or else the RT-DBS cannot respond to environmental changes in a timely manner. Since the computing resources in RTDBS are usually limited (especially in embedded environment), how to de-termine the sampling periods and deadlines for sensor update transactions so that temporal consistency can be maintained while the resulting processor workload is minimized has be-come one important issue in designing RTDBS.In RTDBS, a transaction usually executes in a non-preemptive manner, due to that the time cost of locking tables and checking the consistency of the database is much greater than that of executing the transaction itself. However, most of the past work on energy-aware scheduling are based on preemptive task set. Although there also exist energy-aware studies for partially non-preemptive task set, directly applying them to a fully non-preemptive task set may lead to slowdown factors (normalized task execution speeds) higher than necessary, and thus cannot get the best energy savings. In view of this, we propose a new slowdown calculation algorithm namely ISA for fully non-preemptive task set. By conducting a more accurate analysis on the execution times of higher priority tasks, ISA can derive lower slow-down factors. Combining with the frequency inheritance (Fl) policy, the slowdown factors computed by ISA can guarantee all task deadlines while achieving considerable energy sav-ings. Observing that there is no need to always use the Fl policy to guarantee task deadlines, we further propose a selective frequency inheritance (SFI) policy, which can achieve more energy savings. Moreover, considering that tasks may experience different execution times which are usually less than their worst case execution times, based on ISA, we design a dynamic slack reclamation algorithm namely ISA-DR, which can obtain additional energy savings. The experimental results show that the proposed ISA algorithm along with the re-lated strategies can obtain considerably more (20%-30% on average) energy savings than other solutions with comparable quality.The period and deadline assignment problem for periodic sensor update transactions has been well studied for fixed-priority systems on uniproccssor systems. However, there is comparatively less work addressing the same problem from the perspective of dynamic priority scheduling. Existing algorithms either obtain a too high processor workload, or have a very low runtime efficiency, hence it is an urgent need to design a method which is able to quickly obtain a relatively low workload. This thesis proposes a new two-phase algorithm gεEDF.The first phase of gεEDF has a linear time complexity and hence can be use to derive a solution very efficiently. It has been proved that the solution obtained by this phase has the minimum workload when the assignment order is fixed to be shortest validity first (SVF). When the first phase fails, the second phase is proposed based on an exact feasibility test. Since the second phase has a pseudo-polynomial time complexity, we introduce several techniques to reduce the scheduling points and iteration steps when conducting feasibility test, and thus can reduce the computation cost significantly, which in turn can improve the efficiency of the algorithm. The experimental results demonstrate that gεEDF can quickly derive a solution with CPU workload lower than that of existing solutions.In the past, while there has been much work devoted to the temporal consistency scheduling problem, almost all of them focus on uniprocessor systems. As far as we know, none work has been conducted on the temporal consistency scheduling problem upon multiprocessor platforms. We take a first step to address the workload-aware temporal consistency maintenance problem on multiprocessor platforms. We formally prove that the problem of partitioning transactions on multiprocessor platforms with the goal of minimiz-ing processor workload is NP-hard. In view of the intractability of the problem, we first only consider the feasibility aspect of the workload-aware transaction assignment problenf by proposing a polynomial-time partitioning algorithm, Temporal Consistency Partition (TCP), and formally show that the resource augmentation bound of TCP is 3-1/m. We then address the workload-efficient transaction-to-processor assignment problem globally by characterizing it as a density factor balance problem. Based on the observation that "a more density factor balanced partitioning tends to result in a lower processor workload" we propose a polynomial time heuristic, Density factor Balancing Fit (DBF), and prove that the resource augmentation bound of DBF is also 3-1/m. The experimental results show that DBF has better feasibility/workload performance than other heuristics with comparable quality.