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.     

一种新的实时数据库的乐观并发控制协议

针对一些并发控制协议中由于过多的事务重启动造成资源浪费,提出了一种新的乐观并发控制协议(Optimistic Concurrency Control),通过向后调整不严重冲突事务的动态串行化顺序,许多不必要的事务重启动可以避免。在一个事务的读阶段不用记录事务冲突和串行化限制,各种优先级冲突解决方法可以很方便地加入到该协议中,根据需要选择使用了优先级-中止-50机制。     

混合的实时嵌套事务并发控制协议

嵌套事务作为扩展事务模型的一种,提供了事务内部的并行性和更好的失败恢复选择,具有较为广泛的应用,然而却给事务并发控制带来了更高的复杂性,尤其在实时数据库中事务具有时间限制.针对实时嵌套事务模型,提出了一种混合并发控制协议,对同一事务树内的子事务采用锁协议,对不同事务树之间的事务采用基于动态调整串行化顺序的乐观并发控制协议,提高了事务的成功率,最后证明了协议的正确性.     

Secure one snapshot protocol for concurrency control in real-time stock trading systems

To prevent any data from being accessed by unauthorized users, it is necessary for stock trading systems (STS) to use multilevel secure database management systems in controlling concurrent executions among multiple transactions. In STS, analytical transactions as well as mission critical transactions are executed concurrently, which makes it difficult to use traditional secure real-time transaction management schemes for STS environment. In this paper, we propose the read-down relationship-based secure one snapshot protocol (SOS) that is devised for the secure real-time transaction management in STS. By maintaining an additional one snapshot as well as working database, SOS blocks covert-channels without causing the priority inversion phenomenon. We introduce the process of SOS protocol with some examples, present the proofs of devised protocol, and then evaluate the performance gains by means of simulation method.     

一种新的混合实时事务并发控制算法

单一的实时事务并发控制策略因为对事务性能以及事务对数据的访问方式有着特殊限制而无法满足不同类型事务同时并存的混合实时数据库的要求.针对不同类型实时事务特征,提出了一种新的混合实时事务并发控制算法,对不同类型实时事务采用不同并发控制策略,具有极强的针对性和自适应性,算法同时通过分析数据的相关语义,利用数据相似性定义,合理放宽可串行化的正确性标准,在优先考虑硬实时事务的前提下,尽可能增加软实时事务成功提交的比例以提高系统整体性能.仿真实验结果证明MRTT_CC算法性能良好.     

MIRROR: a state-conscious concurrency control protocol for replicated real-time databases

Data replication can help database systems meet the stringent temporal constraints of current real-time applications, especially Web-based directory and electronic commerce services. A prerequisite for realizing the benefits of replication, however, is the development of high-performance concurrency control mechanisms. In this paper, we present managing isolation in replicated real-time object repositories (MIRROR), a concurrency control protocol specifically designed for firm-deadline applications operating on replicated real-time databases. MIRROR augments the classical O2PL concurrency control protocol with a novel state-based real-time conflict resolution mechanism. In this scheme, the choice of conflict resolution method is a dynamic function of the states of the distributed transactions involved in the conflict. A feature of the design is that acquiring the state knowledge does not require inter-site communication or synchronization, nor does it require modifications to the two-phase commit protocol.Using a detailed simulation model, we compare MIRROR's performance against the real-time versions of a representative set of classical replica concurrency control protocols for a range of transaction workloads and system configurations. Our performance studies show that (a) the relative performance characteristics of these protocols in the real-time environment can be significantly different from their performance in a traditional (non-real-time) database system, (b) MIRROR provides the best performance in both fully and partially replicated environments for real-time applications with low to moderate update frequencies, and (c) MIRROR's simple to implement conflict resolution mechanism works almost as well as more sophisticated strategies.     

基于多版本的安全实时并发控制协议

安全实时数据库必须同时满足安全性和实时性,然而这两者有时可能相互冲突.为了解决这种冲突,提出了基于多版本的安全实时并发控制协议.协议为每个数据对象提供两个版本:工作版本和只读版本,根据事务和数据对象的安全级为事务提供不同的数据版本,有效地解决了实时性与安全性之间的冲突,最后给出了协议的正确性证明.     

A non-two-phase locking protocol for global concurrency control indistributed heterogeneous database systems

A concurrency control method is proposed for global transactions in a distributed heterogeneous database system. This method is applicable when the database sites are interconnected in a rooted tree fashion. It guarantees deadlock freedom in addition to serializability. A general architecture of a heterogeneous system is given. The global transaction manager (GTM) decomposes the global transactions initiated at a site and the subtransactions received from other sites into smaller subtransactions, some of which are sent to the GTMs of the other sites, and those remaining, called g-local transactions, are to be executed by the local transaction manager (LTM) at that site. A concurrency control mechanism ensures serializability among: the local transactions (including the g-local transactions of the global ones) at each site, the global transactions and the global and local transactions together     

A nonrestrictive concurrency control protocol for object-oriented databases

We propose an algorithm for executing transactions in object-oriented databases. The object-oriented database model generalizes the classical model of database concurrency control by permitting accesses toclass andinstance objects, by permittingarbitrary operations on objects as opposed to traditional read and write operations, and by allowingnested execution of transactions on objects. In this paper, we first develop a uniform methodology for treating both classes and instances. We then develop a two-phase locking protocol with a new relationship between locks calledordered sharing for an object-oriented database. Ordered sharing does not restrict the execution of conflicting operations. Finally, we extend the protocol to handle objects that execute methods on other objects thus resulting in the nested execution of transactions. The resulting protocol permits more concurrency than other known locking-based protocols.     

Prescheduling policy for real-time concurrency control: A performance evaluation

A new priority management policy, aprescheduling policy, is proposed. This policy can be applied on any conventional concurrency control protocol to schedule a real-time transaction. Costly preemption is avoided by the prescheduling policy, and parsing dataset of a transaction is not needed. Three widely used conventional concurrency control protocols (dynamic two-phase locking, basic timestamp ordering, and optimistic) are incorporated with the prescheduling policy to form three real-time concurrency control protocols. Performance of the three protocols is evaluated from three different viewpoints: database management systems, protocols, and transaction. From a database management system viewpoint, we show the prescheduling policy can improve the performance of protocols by raising thevalid ratio and reducingrestart counts. In general, two-phase locking with the prescheduling policy performs the best in most cases and yields the best choice for concurrency control in a real-time application. Deciding factors that affect performance of each protocol are identified from protocol viewpoint. Some suggestions are given for writing a timely transaction from the aspect of transaction viewpoint.     

Evaluation of concurrency control strategies for mixed soft real-time database systems

Previous research in real-time concurrency control mainly focuses on the schedulability guarantee of hard real-time transactions and the reduction of the miss rate of soft real-time transactions. Although many new database applications have significant response time requirements, not much work has been done in the joint scheduling of traditional non-real-time transactions and soft real-time transactions. In this paper, we study the concurrency control problems in mixed soft real-time database systems, in which both non-real-time and soft real-time transactions exist simultaneously. The objectives are to identify the cost and the performance tradeoff in the design of cost-effective and practical real-time concurrency control protocols, and to evaluate their performance under different real-time and non-real-time supports. In particular, we are interested in studying the impacts of different scheduling approaches for soft real-time transactions on the performance of non-real-time transactions. Instead of proposing yet another completely new real-time concurrency control protocol, our objective is to design an efficient integrated concurrency control method based on existing techniques. We propose several methods to integrate the well-known two phase locking and optimistic concurrency control with the aims to meet the deadline requirements of soft real-time transactions and, at the same time, to minimize the impact on the performance of non-real-time transactions. We have conducted a series of experiments based on a sanitized version of stock trading systems to evaluate the performance of both soft real-time and non-real-time transactions under different real-time supports in the system.     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

A concurrency control model for PDM systems

In today's manufacturing environment, enterprises having work groups geographically dispersed are not uncommon. A product data management (PDM) system is therefore required for controlling the distribution and maintaining the integrity of the product data throughout its entire lifecycle; the efficiency of a PDM system is greatly affected by the concurrency control method it adopts. The paper proposes a concurrent control model for PDM that can also caters for version management and product architecture. The paper discusses how granularity and versioning are being embedded into a lock-based concurrency control model. The concurrent accessibility of an example product data is explained to illustrate the adjustability according to the actions taken by the users and the architecture of the corresponding entities.     

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.     

Gria: an efficient deterministic concurrency control protocol

Deterministic databases are able to reduce coordination costs in a replication. This property has fostered a significant interest in the design of efficient deterministic concurrency control protocols. However, the state-of-the-art deterministic concurrency control protocol Aria has three issues. First, it is impractical to configure a suitable batch size when the read-write set is unknown. Second, Aria running in low-concurrency scenarios, e.g., a single-thread scenario, suffers from the same conflicts as running in high-concurrency scenarios. Third, the single-version schema brings write-after-write conflicts. To address these issues, we propose Gria, an efficient deterministic concurrency control protocol. Gria has the following properties. First, the batch size of Gria is auto-scaling. Second, Gria’s conflict probability in low-concurrency scenarios is lower than that in high-concurrency scenarios. Third, Gria has no write-after-write conflicts by adopting a multi-version structure. To further reduce conflicts, we propose two optimizations: a reordering mechanism as well as a rechecking strategy. The evaluation result on two popular benchmarks shows that Gria outperforms Aria by 13x.     

A conditional abortable priority ceiling protocol for scheduling mixed real-time tasks

Priority Ceiling Protocol (PCP) is a well-known resource access protocol for hard real-time systems. However, it has a problem of ceiling blocking which imposes a great hindrance to task scheduling in mixed real-time systems where tasks may have different criticality. In this paper, a new resource access protocol called the Conditional Abortable Priority Ceiling Protocol (CA-PCP) is proposed. It resolves the problem of ceiling blocking by incorporating a conditional abort scheme into the PCP. The new protocol inherits all the desirable properties of the PCP and the Ceiling Abort Protocol (CAP) which is yet another modification of the PCP. In the proposed protocol, a condition is defined to control the abort of a job so that the schedulability of the system will not be affected. Performance study has been done to compare the CA-PCP with the PCP. The results indicate that CA-PCP can significantly improve the performance of a system if the lengths of the abortable critical sections are well chosen.     

A multi-granularity locking model for concurrency control inobject-oriented database systems

A locking model adopting a multi-granularity approach is proposed for concurrency control in object-oriented database systems. The model is motivated by a desire to provide high concurrency and low locking overhead in accessing objects. Locking in schemas and locking in instances are developed separately and then are integrated. Schema changes and composite objects are also taken into account. A dual queue scheme for efficient scheduling of lock requests is developed. The model consists of a rich set of lock modes, a compatibility matrix, and a locking protocol. Characteristic query examples on single class, class lattice, and composite objects are used to illustrate the comparison between the ORION model and the proposed model. It is shown that our locking model has indeed made some improvements and is suitable for concurrency control in object-oriented databases     

实时控制系统中优先级反转问题的解决方法

以实时操作系统μC/OS-Ⅱ为例,分析了产生优先级反转的原因,提出了解决该问题的2种方法,即互斥信号量(Mutex)和实现时间片轮番调度法。在保证共享资源互斥访问的前提下,将优先级反转的发生有效地限制在一个层次上,降解了优先级反转现象的发生。     

A hybrid distributed optimistic concurrency control method for high-performance real-time transaction processing

The conventional lock scheme tends to suffer from a cascade of blockings,while the optimistic concurrency control(OCC) scheme may suffer from wasting resources.To overcome these problems,some researchers have proposed a combination of OCC and lock in transaction processing.Using this method,Thomasian proposed the hybrid method for conventional distributed transaction processing,and Lam proposed the DOCC-DA protocol for distributed realtime databased system based on forward validation.This paper proposes a new protocol,called Hybrid Distributed Optimistic Concurrency COntrol Embedded in two-Phase Commit,which is based on back validation.The new protocol makes use of access invariance and runtime inforbased on back validation.The new protocol makes use of access invariance and runtime infor mation which can guarantee a rerun transaction to meet its deadline and abort the fruitless run transactions as early as possible.A series of simulation experiments have been done to investigate the performance of the new protocol.The results show that its performance is consitently better than that of other protocols.     

Object-based semantic real-time concurrency control with boundedimprecision

The paper describes a concurrency control technique for real-time object-oriented databases that supports logical consistency and temporal consistency, as well as bounded imprecision that results from their trade-offs. The concurrency control technique uses a semantic locking mechanism within each object and user-defined conditional compatibility over the methods of the object. The semantics can specify when to sacrifice precise logical consistency to meet temporal consistency requirements. It can also specify accumulation and bounding of any resulting logical imprecision. The authors show that this technique, under certain general restrictions, can preserve global correctness and bound imprecision by proving it can guarantee a form of epsilon serializability specialized for object-oriented databases