Real-time index concurrency control

Real time database systems are expected to rely heavily on indexes to speed up data access and thereby help more transactions meet their deadlines. Accordingly, high performance index concurrency control (ICC) protocols are required to prevent contention for the index from becoming a bottleneck. We develop real time variants of a representative set of classical B-tree ICC protocols and, using a detailed simulation model, compare their performance for real time transactions with firm deadlines. We also present and evaluate a real time ICC protocol called GUARD-link that augments the classical B-link protocol with a feedback based admission control mechanism. Both point and range queries, as well as the undos of the index action transactions are included in the study. The performance metrics used in evaluating the ICC protocols are the percentage of transactions that miss their deadlines and the fairness with respect to transaction type and size. Experimental results show that the performance characteristics of the real time version of an ICC protocol could be significantly different from the performance of the same protocol in a conventional (nonreal time) database system. In particular, B-link protocols, which are reputed to provide the best overall performance in conventional database systems, perform poorly under heavy real time loads. The new GUARD-link protocol, however, although based on the B-link approach, delivers the best performance (with respect to all performance metrics) for a variety of real time transaction workloads, by virtue of its admission control mechanism. GUARD-link provides close to ideal fairness in most environments     

Analysis of hybrid concurrency control schemes for a high datacontention environment

Analytical models are developed to study hybrid CC (concurrency control) schemes which employ a different CC scheme to handle rerun transactions, since their characteristics are different from the first run of transactions. These include switching to static or dynamic locking during rerun (referred to as static and dynamic hybrid OCC (optimistic concurrency control) schemes, respectively), and switching to broadcast OCC during rerun, while doing pure OCC for the first run. In a high data contention environment where locking is inferior to OCC, analysis shows that the performance can be substantially improved by using this hybrid approach and the authors study the tradeoff of the different hybrid CC schemes. The analytic models are based on a decomposition approach and use a mean-value-type analysis. The accuracy of the analysis is validated through simulations     

Real-time segmentation of video on a multiprocessor platform

This paper presents a multiprocessor implementation of a segmentation algorithm for video streams. The segmentation procedure is part of an augmented-reality telepresence prototype. It has been implemented on a multiprocessor computer, equipped with specialized hardware for real-time graphics and video processing. The goal of this paper is to assess our experience in implementing an image processing procedure intended to meet the prototype's real-time requirements rather than present a new image processing technique.     

Advanced concurrency control in Java

Developing concurrent applications is not a trivial task. As programs grow larger and become more complex, advanced concurrency control mechanisms are needed to ensure that application consistency is not compromised. Managing mutual exclusion on a per‐object basis is not sufficient to guarantee isolation of sets of semantically‐related actions. In this paper, we consider ‘atomic blocks’, a simple and lightweight concurrency control paradigm that enables arbitrary blocks of code to access multiple shared objects in isolation. We evaluate various strategies for implementing atomic blocks in Java, in such a way that concurrency control is transparent to the programmer, isolation is preserved, and concurrency is maximized. We discuss these concurrency control strategies and evaluate them in terms of complexity and performance. Copyright © 2002 John Wiley & Sons, Ltd.     

Asynchronous operations in distributed concurrency control

Distributed locking is commonly adopted for performing concurrency control in distributed systems. It incorporates additional steps for handling deadlocks. This activity is carried out by methods based on wait-for-graphs or probes. The present study examines detection of conflicts based on enhanced local processing for distributed concurrency control. In the proposed "edge detection" approach, a graph-based resolution of access conflicts has been adopted. The technique generates a uniform wait-for precedence order at distributed sites for transactions to execute. The earlier methods based on serialization graph testing are difficult to implement in a distributed environment. The edge detection approach is a fully distributed approach. It presents a unified technique for locking and deadlock detection exercises. The technique eliminates many deadlocks without incurring message overheads.     

Syntactic control of concurrency

We consider a finitary procedural programming language (finite data-types, no recursion) extended with parallel composition and binary semaphores. Having first shown that may-equivalence of second-order open terms is undecidable we set out to find a framework in which decidability can be regained with minimum loss of expressivity. To that end we define an annotated type system that controls the number of concurrent threads created by terms and give a fully abstract game semantics for the notion of equivalence induced by typable terms and contexts. Finally, we show that the semantics of all typable terms, at any order and in the presence of iteration, has a regular-language representation and thus the restricted observational equivalence is decidable.     

用SQL实现工作流的并发控制

工作流技术在信息系统的应用中，并发控制机制的设计是经常要面临的问题。给出一种基于将工作流中数据和任务分离的工作流并发控制机制，在保证工作流正确性的前提下，引入“数据约束”和“任务约束”的概念来提高工作流的工作性能和降低工作流设计的复杂性，并用数据库中SQL语言强有力的约束控制加以实现。     

Supervisory control of a rapid thermal multiprocessor

An application of supervisory control theory to a piece of semiconductor manufacturing equipment is presented. The approach allows the flexible design and reliable update of processing recipes to accommodate frequently changing manufacturing requirements. An input-output interpretation of supervisory control theory is given. This interpretation leads to a generic implementation scheme for manufacturing systems. A synthesis fixpoint algorithm implementation using binary decision diagrams enables the design of supervisors of realistic size. A sample synthesis for an oxide growth recipe is performed on a state space of the order of 10⁶ states. The actual implementation of the logic sequencing control software for the application under investigation is described     

Integrated concurrency control in shared B-trees

The traditional approach to concurrency control in sharedB-trees is based on locking. Recently new methods have been proposed called optimistic methods. In contrast to locking these methods achieve correct operations on theB-tree by a restart mechanism. In this paper we present a new approach to concurrency control, which integrates locking and the optimistic method. Practical applications are pointed out in which this approach can be expected to be superior to either locking or the optimistic method.     

Asymptotic analysis of a heterogeneous multiprocessor system in arandomly changing environment

An asymptotic queuing theoretic approach is proposed to analyze the performance of an FCFS (first-come, first-served) heterogeneous multiprocessor computer system with a single bus operating in a randomly changing environment. All stochastic times in the system are considered to be exponentially distributed and independent of the random environment, while the access and service rates of the processors are subject to random fluctuations. It is shown under the assumption of `fast' arrivals that the busy period length of the bus converges weakly, under appropriate normalization, to an exponentially distributed random variable. As a consequence, main steady-state performance measures such as system throughput, mean delay time, expected waiting time, and mean number of active processors can be approximately determined. The reliability of the proposed method is validated by comparing the new approximations with known exact results     

The optimisation of higher order resampling methods in a multiprocessor environment

The processing of images obtained from satellites often involves highly repetitive calculations on very large amounts of data. This processing is extremely time consuming when these calculations are performed on sequential machines. Parallel computers are well suited to handling computationally expensive operations such as higher order interpolations on large data sets. This paper decribes work undertaken to develop parallel implementations of a set of resampling procedures on an Alliant VFX/4. Each resampling procedure implemented has been optimised in three stages. First, the algorithm has been restructured, where two-dimensional resampling is performed by two one-dimensional resampling operations. Second, each procedure has been reprogrammed in such a way that the autoparallelisation provided by the FX/Fortran compiler has been exploited. Thirdly, data dependent analysis of each procedure has been performed in order to achieve full optimization of each procedure; each procedure has been restructured where appropriate to circumvent vectorisation and concurrency inhibiting data dependencies. The nature and extent of the code optimization achieved for each procedure is presented in this paper. The original code for the most computationally expensive procedure, as targeted at a sequential machine, was found to have an execution time of 4900 seconds on the Alliant VFX/4 when compiled with regular compiler optimization options. Following algorithmic redesigning and reprogramming of the code, as indicated in stage 1 and stage 2, the execution time was reduced to 248 seconds. Restructuring of the code following data dependency analysis indicated in stage 3 in order to avoid data dependencies and allow concurrency and vectorisation, further reduced execution time to 162 seconds. The consequence of this work is that higher-order resampling methods which had not previous been practical are now routinely performed on the Alliant VFX/4 at the University of Dundee.     

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.     

一种多粒度锁的事务并发控制算法

研究了一种基于多粒度锁的并发控制算法,包括其多粒度锁锁、锁表数据结构及锁操作的算法步骤。算法可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。在验证算法有效性时,通过测试类对内存数据库记录的插入速度、索引查找的速度、记录的删除速度三方面的性能进行了测试,结果表明,事务并发控制优化算法对内存数据库性能的提升是有效可行的。     

Checkpointing for optimistic concurrency control methods

Restart-oriented concurrency control (CC) methods, such as optimistic CC, outperform blocking-oriented methods, such as standard two-phase locking in a high data contention environment, but this is at the cost of wasted processing due to restarts. Volatile savepoints are considered in this study as a method to reduce this wasted processing and to improve response time. There is the usual tradeoff between the checkpointing overhead and the wasted processing when a transaction is restarted. Our study shows that in a system where objects are accessed and updated uniformly during the lifetime of transactions, significant improvement in performance at high data conflict levels are attainable only when the checkpointing cost is low. This implies few optimally placed checkpoints per transaction. It is observed that checkpointing may result in a significant improvement in performance when access to database hot-spots are deferred to the final steps of transaction execution. The parametric studies reported in this paper are facilitated by closed-form analytic solutions expressing system performance, as well as an iterative solution which takes into account hardware resource contention in addition to data contention     

一种面向多租户中间件的应用级并发控制方法

针对在多租户中间件上存在的租户隔离、资源侵占的问题,提出一种面向多租户中间件的应用级并发控制方法。首先分析了现有并发控制方法的局限性,然后介绍了一种基于工作管理器的多租户请求处理模型的原理及设计,进一步给出了基于该模型的应用级并发控制方法的设计与实现,最后通过实验测试方法的性能开销,并设计了一个多租户性能隔离方法来验证方法的应用效果。实验结果验证了方法的有效性。     

Observations on optimistic concurrency control schemes

Optimistic concurrency control schemes allow uncontrolled access to shared data objects during transaction processing under the explicit assumption that read and write conflicts among transactions are rare events. Before a transaction commits, the DBMS has to validate that no conflict has occurred. Conflict resolution mainly relies on transaction abort.Two different optimistic concurrency control schemes are introduced and compared to each other. The problems of implementing such schemes and their implications on DBMS processing is investigated in some detail. A number of general properties of optimistic concurrency control schemes is derived, and their advantages and drawbacks w.r.t. two-phase locking approaches are discussed.     

Optimal control of a resource-sharing multiprocessor with periodic maintenance

Shared resources and the processes that control them play a critical role in the functioning of concurrent systems. The article analyzes the production control of a workstation producing a number of products concurrently. The workstation is periodically stopped for maintenance. The objective of the production control is to minimize inventory and backlog costs over an infinite time horizon. Using the maximum principle and under the so-called agreeable cost structure, we derive the optimal production control. We prove that under this cost structure, the problem can be solved in polynomial time.     

Learning control of mobile robots using a multiprocessor system

A real-time multiprocessor system is proposed for the solution of the tracking problem of mobile robots operating in a real context with environmental disturbances and parameter uncertainties. The proposed control scheme utilizes multiple models of the robot for its identification in an adaptive and learning control framework. Radial Basis Function Networks (RBFNs) are considered for the multiple models in order to exploit the net non-linear approximation capabilities for modeling the kinematic behavior of the vehicle and for reducing unmodeled contributions to tracking errors. The training of the nets and the tests of the achieved control performance have been done in a real experimental setup. The proposed control architecture improves the robot tracking performance achieving fast and accurate control actions in presence of large and time-varying uncertainties in dynamical environments. The experimental results are satisfactory in terms of tracking errors and computational efforts.     

Two fully distributed concurrency control algorithms

Two new concurrency control algorithms are introduced for partially replicated distributed databases. They both maintain two values of a data item, and differ in that one requires all locks to be granted at one time, whereas the other does not. They are based on locking, and avoid deadlocks by using timestamps to establish an execution order when conflicts arise. Since they both proceed without any communication among schedulers, but only communication between the originating site and all participating sites, we say they are fully distributed