实时数据库中具有时态限制的事务调度算法

在实时数据库中，事务对时态数据对象的访问在很多领域的应用日益广泛．目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性，而忽略了满足时态的一致性．本文提出了临时数据截止期的概念，以定理的形式证明了低成本的预测算法的可行性，尽可能早地终止或推迟无法满足时态一致性要求的事务的执行，节省了计算资源以供其它事务执行．在此基础上提出了新的实时数据库中具有时态限制的事务调度算法TDDBPA(Temporary Data Deadline—Based Predictive Algorithm)．通过与目前所知的有效算法比较，本算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法．     

Processing real-time transactions in a replicated database system

A database system supporting a real-time application has to provide real-time information to the executing transactions. Each real-time transaction is associated with a timing constraint, typically in the form of a deadline. It is difficult to satisfy all timing constraints due to the consistency requirements of the underlying database. In scheduling the transactions it is aimed to process as many transactions as possible within their deadlines. Replicated database systems possess desirable features for real-time applications, such as a high level of data availability, and potentially improved response time for queries. On the other hand, multiple copy updates lead to a considerable overhead due to the communication required among the data sites holding the copies. In this paper, we investigate the impact of storing multiple copies of data on satisfying the timing constraints of real-time transactions. A detailed performance model of a distributed database system is employed in evaluating the effects of various workload parameters and design alternatives on the system performance. The performance is expressed in terms of the fraction of satisfied transaction deadlines. A comparison of several real-time concurrency control protocols, which are based on different approaches in involving timing constraints of transactions in scheduling, is also provided in performance experiments. Recommended by: A. ElmagarmidThis work was initiated while the author was at the Computer Science Department, University of Illinois at Urbana-Champaign.     

基于数据时态特性的实时事务并发控制

通过对数据时态特性及其对事务调度的影响进行分析,提出了基于数据时态特性的实时事务并发控制算法.该算法根据数据截止期及事务的执行时间估算,改进了事务的验证规则,对事务的提交顺序进行调整,提高了系统的实时性能.理论分析与实验结果表明:该算法降低了事务重启个数及超截止期百分率,性能要优于已有的实时并发控制算法.     

实时数据库事务的正确性及实现算法

实时数据库系统中事务可以有定时限制（典型地为截止期）,事务超过截止期可能给系统带来灾难性后果,事务不光要满足数据库的完整性与一致性,而且要满足在时间上的正确性以及事务之间在结构上的正确性,传统的事务处理方法仅着眼于事务存取数据库的正确性,对于时间正确性与结构正确性无能为力,详细讲座了实时事务的正确性,包含结果正确性、时间正确性、行为正确性及结构正确性,已有的研究成果中大多用不央的算法及策略来保证不同的正确性要求;给出了保证实时事务正确性的一个统一的图论算法。     

分布式实时事务提交处理

由于提交处理的复杂性,分布式实时事务很难满足其截止期.提出了一种新的提交协议A2SC(主动的双空间提交),它适合于分布式实时事务提交处理的需要.分析了由于数据冲突访问而形成的各种依赖关系.当处于准备状态的事务和处于提交状态的事务发生数据冲突访问时,A2SC允许处于执行状态的事务在一种控制的方式下乐观地访问锁住的数据.当处于准备状态的事务夭折时,仅仅只有其夭折依赖集中的事务夭折.进一步提出了"没有结果的运行"的观念.当一个事务发现它是没有结果的允许时,它将主动夭折.进行了广泛的模拟实验比较A2SC和其它协议比如基准协议、PROMPT和DDCR的性能.模拟结果表明A2SC在最小化错过截止期的事务数方面较成功,因此A2SC适合于高性能分布式实时事务.     

基于挖掘具有时态限制数据语义的实时事务调度算法

在实时数据库中,事务对时态数据对象的访问在很多领域的应用日益广泛。目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性,而忽略了满足时态的一致性。论文提出了新的实时数据库中具有时态限制的事务调度算法PSBA(PredictionandSimilarity-BasedAlgorithm)。首先提出了临时数据截止期的概念,以定理的形式证明了低成本地预测算法的可行性,尽可能早地终止或推迟无法满足时态一致性要求的事务的执行,节省了计算资源以供其它事务执行。继而通过挖掘数据语义,利用数据相似性,结合预测算法,进一步提高了调度性能。与目前所知的有效算法比较,该算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法。     

关于实时数据库事务

实时数据库事务显示了与传统数据库事务的很大不同．这些不同主要表现在事务的复杂结构、定时特性、相关性和正确性方面．本文先分析了实时数据库事务的应用特征与需求，并给出了一个复杂事务结构的框架，然后着重讨论实时事务间的相关性：结构相关、数据相关、行为相关，以及实时事务的结果、结构、行为及时间正确性．     

Real-time transaction scheduling in database systems

A database system supporting a real-time application, which can be called “a real-time database system (RTDBS)”, has to provide real-time information to the executing transactions. Each RTDB transaction is associated with a timing constraint, usually in the form of a deadline. Efficient resource scheduling algorithms and concurrency control protocols are required to schedule the transactions so as to satisfy both timing constraints and data consistency requirements. In this paper,^† we concentrate on the concurrency control problem in RTDBSs. Our work has two basic goals: real-time performance evaluation of existing concurrency control approaches in RTDBSs, and proposing new concurrency control protocols with improved performance. One of the new protocols is locking-based, and it prevents the priority inversion problem^{, †} by scheduling the data lock requests based on prioritizing data items. The second new protocol extends the basic timestamp-ordering method by involving real-time priorities of transactions in the timestamp assignment procedure. Performance of the protocols is evaluated through simulations by using a detailed model of a single-site RTDBS. The relative performance of the protocols is examined as a function of transaction load, data contention (which is determined by a number of system parameters) and resource contention. The protocols are also tested under various real-time transaction processing environments. The performance of the proposed protocols appears to be good, especially under conditions of high transaction load and high data contention.     

Databases with deadline and contingency constraints

Real-time database systems associate the concept of deadlines with transaction executions. Previous approaches use “best effort” techniques to schedule a given set of transactions to meet the deadlines as well as to ensure the consistency of the database. However, such approaches are inadequate for target applications which have “hard” real-time deadlines that need to be met in the event of crisis situations. In such cases, it is important to obtain contingency plans that may be invoked with guaranteed execution time characteristics. This paper presents an alternative model for real-time database systems in which deadlines are associated with “contingency” constraints rather than directly with transactions. Our approach leads to a predicate-based model that intrinsically incorporates both triggering and relative timing constraints regarding the transaction executions. We exhibit that selecting contingency plans with respect to various optimality criteria has inherent computational inefficiencies. We study the issues in scheduling of the selected plans with the focus on the contention among the transactions for data resources. Our results exhibit that the data contention, by itself, has a severe adverse impact on the schedulability of the deadline-constrained transactions. We discuss some of the practical implications of our results, and we suggest some counter-measures to handle the computational complexities     

Real-Time Transaction Scheduling: A Framework for Synthesizing Static and Dynamic Factors

Real-time databases are poised to be an important component of complex embedded real-time systems. In real-time databases (as opposed to real-time systems), transactions must satisfy the ACID properties in addition to satisfying the timing constraints specified for each transaction (or task). Although several approaches have been proposed to combine real-time scheduling and database concurrency control methods, to the best of our knowledge, none of them provide a framework for taking into account the dynamic cost associated with aborts, rollbacks, and restarts of transactions. In this paper, we propose a framework in which both static and dynamic costs of transactions can be taken into account. Specifically, we present: i) a method for pre-analyzing transactions based on the notion of branch-points for data accessed up to a branch point and predicting expected data access to be incurred for completing the transaction, ii) a formulation of cost that includes static and dynamic factors for prioritizing transactions, iii) a scheduling algorithm which uses the above two, and iv) simulation of the algorithm for several operating conditions and workload. Our dynamic priority assignment policy (termed the cost conscious approach or CCA) adapts well to fluctuations in the system load without causing excessive numbers of transaction restarts. Our simulations indicate that i) CCA performs better than the EDF-HP algorithm for both soft and firm deadlines, ii) CCA is more fair than EDF-HP, iii) CCA is better than EDF-CR for soft deadline, even though CCA requires and uses less information, and iv) CCA is especially good for disk-resident data.     

Scheduling Value-Based Nested Transactions in Distributed Real-Time Database Systems

Many noticeable studies have focussed on scheduling flat transactions in a distributed real-time database system (RTDBS). However, a nested transaction model has been widely adopted in many real-life applications such as Internet stock trading systems and telecommunications. This work concerns efficiently scheduling real-time nested transactions in a distributed RTDBS. A new real-time scheduler called flexible high reward for nested transactions (FHRN) is proposed. FHRN consists of (1) FHRN_p ¹ policy to schedule real-time nested transactions and (2) 2PL_HPN to resolve the concurrent data-accessing problem among interleaved nested transactions. Simulation results show that FHRN outperforms these existent real-time schedulers such as random priority (RP), earliest deadline (ED), highest value (HV), hierarchical earliest deadline (HED), and highest reward and urgency (HRU) when an application requires a nested transaction model.     

Scheduling transactions with temporal constraints: exploiting data semantics

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant transaction scheduling policies are proposed. Informally, data-deadline is a deadline assigned to a transaction due to the temporal constraints of the data accessed by the transaction. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in realtime database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.     

Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints

In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n ² N ³) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.     

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.

Improving Predictability of Transaction Execution Times in Real-time Databases

We present a design for multi-versionconcurrency control and recovery in a main memory database, anddescribe logical and physical versioning schemes that allowread-only transactions to execute without obtaining data itemlocks or system latches. Our schemes enable a system to providethe guarantee that updaters will never interfere with read-onlytransactions, and read-only transactions will not be delayeddue to data contention. Consequently, transaction executionsbecome more predictable—this partially alleviates a majorproblem in real-time database system (RTDBS) scheduling, namely,significant unpredictability in transaction execution times.As a result, in addition to a transaction's deadline, a moreaccurate estimate of its execution time can also be taken intoaccount, thus facilitating better scheduling decisions. Our contributionsinclude several space saving techniques for the main-memory implementation,including improved methods for logical aging of data items andthe introduction of physical aging for low-level structures.Some of these schemes have been implemented on a widely-usedsoftware platform within Lucent, and the full scheme is implementedin the Dalí main-memory storage manager.     

Correctness of a distributed transaction system

A distributed transaction system manages information that is dispersed over a number of storage devices. This paper deals with an experimental transaction system designed to satisfy real-time constraints through distributed control of the executions of transactions. Of interest is the correctness of the algorithm for distributed control. Demonstrating the correctness involves showing that the algorithm guarantees the consistency of distributed data, and equally importantly, that every transaction will eventually terminate. Proof of consistency is based on the notion of serializability of transactions while proof of termination is based on the conflict resolution and failure recovery strategies employed by the transaction system.     

嵌入式实时数据库ARTs-EDB事务调度实现技术

着重讨论了嵌入式实时数据库系统ARTs-EDB中事务调度实现技术。给出了ARTs-EDB中事务的执行模型、状态及状态变迁；设计了一个考虑事务类型和截止期的多层动态可调整优先级分派方法；给出了一个优先级驱动可抢占的实时事务调度策略，以保证更多事务满足截止期要求。     

An effective fixed priority co-scheduling algorithm for periodic update and application transactions

An important function of many cyber-physical systems (CPS) is to provide a close monitoring of the operation environment to be able to adapt to changing situations effectively. One of the commonly applied techniques for that is to invoke time-constrained periodic application transactions to check the status of the operation environment. The status of the environment is represented by the values of the physical entities in the operation environment which are maintained as real-time data objects in a real-time database. Unfortunately, meeting the deadlines of application transactions and maintaining the quality of real-time data objects are conflicting with each other, because they compete for the same computation resources. To address this problem of update and application transactions co-scheduling problem, in this paper, we propose a fixed priority co-scheduling algorithm called periodic co-scheduling (PCS). PCS uses periodic update transactions to maintain the temporal validity of real-time data objects. It judiciously decides the priority orders among all the update and application transactions so that the constructed schedule can satisfy the deadline constraints of all the application transactions and at the same time maximize the qualities of the real-time data objects to ensure the correct execution of application transactions. The effectiveness of the algorithm is validated through extensive simulation experiments.     

实时数据库的事务调度研究

实时数据库系统的事务调度一般只考虑事务的截止期,但是,在很多情况下,它还与数据截止期直接相关。对不同类型调度策略能否充分考虑数据截止期进行了具体分析,对其中存在的规律进行了归纳总结,并且在全面估算事务运行时间的基础上,给出了基于数据截止期和事务截止期的事务处理策略。     

Optimistic priority-based concurrency control protocol for firm real-time database systems

This paper presents an optimistic priority-based concurrency control protocol that schedules active transactions accessing firm deadline real-time database systems. This protocol combines the forward and backward validation processes in order to control concurrent transactions with different priorities more effectively. For a transaction in the validation phase, it can be committed successfully if the serialization order is adjusted in favour of the transactions with higher priority and aborted otherwise. Thus, this protocol establishes a priority ordering technique whereby a serialization order is selected and transaction execution is forced to obey this order. This priority-based protocol addresses the problem of satisfying data consistency, with the goal being to increase the number of transactions that commit by their deadlines. In addition, for desirable real-time conflict resolution, this protocol intends to meet more deadlines of higher priority transactions then lower priority transactions.