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

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

实时数据库系统中时态一致性的维护

实时数据库系统(RTDBS)的一个重要问题是维护实时事务和时态数据时态一致性.讨论了实时数据库中事务和数据的时间特性,给出了事务的绝对时态一致性和相对时态一致性的定义;探讨了时态数据给实时事务调度策略带来的影响;提出了一种既保证事务的时态一致性,又减少更新事务执行数量的方法.     

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。     

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

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

实时数据库管理系统—实时事务调度与并发控制子系统的设计与实现

实时数据库管理系统(RTDBMS)是建立在UNIX环境下,以关系数据模型为基础,借鉴实时系统管理特征而实现的数据库管理系统。RTDBMS包括内存数据库管理、触发器管理、实时事务调度与并发控制、数据操纵、用户接口与数据说明等五个子系统。实时事务调度与并发控制子系统(简称实时事务调度子系统)是其中之一。 本文主要介绍了实时事务调度子系统为实现RTDBMS的最终目标——对数据与事务的定时限制而必须具备的功能,如事务的优先数分配、并发控制、冲突处理、按原则调度事务等。这些功能模块的实现,使得对事务的“时间识别”处理,即:既满足数据的一致性(逻辑一致,绝对一致,相对一致),又满足事务的时限要求成为现实。     

一种支持时态数据的实时数据模型

实时数据库系统不但包括事务的定时限制,还包括数据的定时限制。本文讨论了实时数据库中数据的时间特性,给出了数据的绝对时态一致性和相对时态一致性的定义;针对时态数据的特征,提出了一种实时关系数据模型。     

一种动态调整串行化顺序的实时并发控制协议

实时并发控制协议用来控制并发事务间的相互作用,已满足实时数据库的一致性.本文提出一种四阶段实时并发控制协议HTRCC-DASO,协议在读或等待阶段基于事务优先级动态调整串行化顺序,通过阻塞或及早重启低优先级事务,使高优先级事务率先提交并降低事务重启开销.在验证阶段检查事务读写集合的外部一致性和相互一致性并调整活动事务的时间戳间隔,确保满足事务时态一致性和调度冲突可串行化.通过引入相似性概念,提出了HTRCC-DASO的改进版本:SHTRCC-DASO,性能测试结果显示,SHTRCC-DASO协议能保证良好的实时性能.     

移动实时事务的相对时间正确性及其实现

随着移动通信技术的迅速发展,人们提出了新的应用要求：在移动环境下处理实时事务．而移动通信的带宽有限性引起较大的数据访问延迟,有时甚至由于网络传输的断接而使得事务得不到所需访问的数据,这些严重影响了移动环境下实时事务截止期的满足．实时事务的时间要求(典型地为截止性)的满足通常比事务执行的逻辑结果的完全正确更为重要．该文提出了移动环境下实时事务的“相对”时间正确性标准,只要事务访问的数据的陈旧度(staleness)在控制的范围内,就不一定要求实时事务访问的数据在事务提交时是有效的．文中提出了移动实时事务的相对时间正确性标准、保证事务相对时间正确性标准的算法及移动实时事务执行模型．所有这些策略一方面降低了移动实时事务的并发控制代价,另一方面以牺牲事务的“绝对”时间正确换取事务截止期的满足,这与实时数据库“宁愿要部分正确但及时的结果而不愿要绝对正确但过时的结果”的系统目标是相一致的．实验表明：相对时间正确性标准的提出及相应的事务执行模型能提高系统中满足截止期事务的比率,从而提高了系统性能．     

基于可延迟调度提升实时数据对象时序一致性服务质量算法

针对保证实时数据对象时序一致性调度算法在软实时数据库系统环境下的应用问题,提出了一种基于概率统计的可延迟优化(SDS-OPT)算法。首先,分析和比较了现有算法在可调度性、服务质量(QoS)以及工作负载方面的特征与不足,指出优化现有算法的必要性;然后,利用最速下降法提升作业的执行时间筛选基准值,进而增加实时更新事务可调度的作业数量,以确保实时数据对象的时序一致性服务质量(QoS)最大化;最后,从工作负载和服务质量两个方面对所提算法和现有算法的性能进行对比分析。仿真实验结果表明,相对于已有的针对固定优先级可延迟调度算法(DS-FP)和统计性的非确定性可延迟调度算法(DS-PS),所提算法能够保证实时数据对象的时序一致性,同时降低工作负载,服务质量提升明显。     

主动实时数据库的事务处理

现在越来越多的研究关注于主动实时数据库。提出了主动实时数据库下的事务概念模型，这个模型是专门用在实时环境下的嵌套事务模型；介绍了一个事务执行模型的执行原理及该模型各个模块的功能；最后提出了一个事务调度算法，并在此基础上与别的常见的算法进行了性能分析。     

Chronological scheduling of transactions with temporal dependencies

Database applications often impose temporal dependencies between transactions that must be satisfied to preserve data consistency. The extant correctness criteria used to schedule the execution of concurrent transactions are either time independent or use strict, difficult to satisfy real-time constraints. On one end of the spectrum, serializability completely ignores time. On the other end, deadline scheduling approaches consider the outcome of each transaction execution correct only if the transaction meets its real-time deadline. In this article, we explore new correctness criteria and scheduling methods that capture temporal transaction dependencies and belong to, the broad area between these two extreme approaches. We introduce the concepts ofsuccession dependency andchronological dependency and define correctness criteria under which temporal dependencies between transactions are preserved even if the dependent transactions execute concurrently. We also propose achronological scheduler that can guarantee that transaction executions satisfy their chronological constraints. The advantages of chronological scheduling over traditional scheduling methods, as well as the main issues in the implementation and performance of the proposed scheduler, are discussed.     

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.

On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

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.     

A neural-based concurrency control algorithm for database systems

Concurrency control (CC) algorithms guarantee the correctness and consistency criteria for concurrent execution of a set of transactions in a database. A precondition that is seen in many CC algorithms is that the writeset (WS) and readset (RS) of transactions should be known before the transaction execution. However, in real operational environments, we know the WS and RS only for a fraction of transaction set before execution. However, optional knowledge about WS and RS of transactions is one of the advantages of the proposed CC algorithm in this paper. If the WS and RS are known before the transaction execution, the proposed algorithm will use them to improve the concurrency and performance. On the other hand, the concurrency control algorithms often use a specific static or dynamic equation in making decision about granting a lock or detection of the winner transaction. The proposed algorithm in this paper uses an adaptive resonance theory (ART)-based neural network for such a decision making. In this way, a parameter called health factor (HF) is defined for transactions that is used for comparing the transactions and detecting the winner one in accessing the database objects. HF is calculated using ART2 neural network. Experimental results show that the proposed neural-based CC (NCC) algorithm increases the level of concurrency by decreasing the number of aborts. The performance of proposed algorithm is compared with strict two-phase locking (S2PL) algorithm, which has been used in most commercial database systems. Simulation results show that the performance of proposed NCC algorithm, in terms of number of aborts, is better than S2PL algorithm in different transaction rates.     

On scheduling transactions in a grid processing system considering load through Ant Colony Optimization

Load balanced transaction scheduling problem is an important issue in distributed computing environments including grid system. This problem is known to be NP-hard and can be solved by using heuristic as well as any meta-heuristic method. We ponder over the problem of the load balanced transaction scheduling in a grid processing system by using an Ant Colony Optimization for load balancing. The problem that we consider is to achieve good execution characteristics for a given set of transactions that has to be completed within their given deadline. We propose a transaction processing algorithm based on Ant Colony Optimization (ACO) for load balanced transaction scheduling. We modify two meta-heuristic along with ACO and three heuristic scheduling algorithms for the purpose of comparison with our proposed algorithm. The results of the comparison show that the proposed algorithm provides better results for the load balanced transaction scheduling in the grid processing system.     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。