Hybrid protocols using dynamic adjustment of serialization order for real-time concurrency control

Conclusions Time-critical scheduling in real-time database systems has two components: real-time scheduling and concurrency control. While both concurrency control and real-time scheduling are well-developed and well-understood, there is only limited knowledge about the integration of concurrency control and real-time scheduling. Though recently the problem has been studied actively, the proposed solutions are still at an initial stage. A major source of problems in integrating the two is the lack of coordination in the development. They are developed on different objectives and incompatible assumptions (Buchmann 1989).Most of the proposed work for real-time concurrency control employ a simple method to utilize one concurrency control scheme such as 2PL, TO and OCC, and to consider the priority of operations inherited from the timing constraints of transactions in operation scheduling. This method has an inherent disadvantage of being limited by the concurrency control method used as the base. Since neither of pessimistic nor optimistic concurrency control is satisfactory by itself for real-time scheduling, this simple method using only one control can hardly satisfy the timing requirements of RTDBS. Problems such as excessive blocking, wasted restarts, and priority inversion are serious in RTDBS.In this paper, we proposed two real-time transaction scheduling protocols which employ a hybrid approach, i.e., a combination of both pessimistic and optimistic approaches. These protocols make use of a new conflict resolution scheme called dynamic adjustment of serialization order, which supports priority-driven scheduling, and avoids unnecessary aborts.This work was supported in part by ONR, by NRaD, by DOE, and by IBM.     

Unconstrained seal imprint verification using attributed stroke graph matching

Seal imprint verification by human visual inspection is a serious bottleneck of office automation in Oriental countries. In this paper, we propose a new scheme^† for automatic seal imprint verification using attributed stroke graph matching. A major advantage of our scheme is that our scheme can handle seal imprints under much fewer constraints. The shape of seals can be a square, an ellipse, a circle, or any close loop. The boundary of the seal imprints is allowed to be imperfect. Furthermore, it is insensitive to the distance between the TV-camera and seal imprints. Experimental results^{, †} confirm that the proposed scheme might be feasible for practical applications.     

On Using Real-Time Static Locking Protocols for Distributed Real-Time Databases

The use of Static Two Phase Locking Protocols (S2PL) for concurrency control in real-time database systems (RTDBS) has received little attention in the past. Actually, real-time S2PL (RT-S2PL) protocols do possess some desirable features making them suitable for RTDBS, especially for distributed real-time database systems (DRTDBS) in which remote locking is required and distributed deadlock is possible. In this paper, different RT-S2PL protocols are proposed. They differ in their methods of reducing the blocking time of higher priority transactions. Their performance is studied and compared with a real-time dynamic two phase locking protocol (RT-D2PL), called Hybrid Two Phase Locking (Hb2PL). The impact of different system and workload parameters, such as mean inter-arrival time of transactions, number of remote lock requests of a transaction, communication overhead for sending messages, and database size on their performance have been examined. The performance results indicate that the RT-S2PL protocols are suitable for DRTDBS in which the proportion of local locks of a transaction is small and the communication overhead for locking is high.     

Priority Scheduling of Transactions in Distributed Real-Time Databases

One of the most important issues in the design of distributed real-time database system (DRTDBS) is transaction scheduling which consists of two parts: priority scheduling and real-time concurrency control. In the past studies, mostly, these issues are studied separately although they have a very close interaction with each other. In this paper, we propose new priority assignment policies for DRTDBS and study their impact on two typical real-time concurrency control protocols (RT-CCPs), High Priority Two Phase Locking (HP-2PL) and Optimistic Concurrency Control with Broadcast Commit (OCC-BC). Our performance results show that many factors, such as data conflict resolution, degree of data contention and transaction restarts, that are unique to database systems, have significant impact on the performance of the policies which in turn affect the performance of the real-time concurrency control protocols. OCC-BC is more affected by the priority assignment policies than HP-2PL owing to the late detection of conflict. In the design of priority assignment policies, we have found that neither the purely deadline driven policies nor data contention driven policies are suitable for DRTDBS. Our proposed policy, the Mixed Method (MM), which considers both transaction timeliness and data contention, outperforms other policies over a wide range of system parameter settings.     

Academic/industrial collaboration in a postgraduate MSc course in Software Engineering

This paper outlines the organization of an MSc in Software Engineering that has been set up as a specialist conversion course for graduates who have had some experience of computer programming. The most distinctive feature of the program is that this degree involves the participation of an industrial partner in providing some of the teaching and a period of industrial placement. Our experiences with the academic and practical aspects of such a structure have been included.^†     

Algorithm to Process Read-only Transactions in Real-time Environments

In this study, we investigate a different approach to maintaining serializability in real-time database systems (RTDBS) such that concurrency among transactions can be increased. The study is motivated by the dominance of read only transactions (ROTs) in many real-time applications. Given the knowledge about the read/write characteristics of transactions, it can be more efficient and effective to process ROTs separately from update transactions (UTs). In particular, we have devised an independent algorithm to process ROTs while a conventional concurrency control protocol such as optimistic concurrency control (OCC) can be employed to process UTs. Using a separate algorithm to process ROTs can reduce the interference between UTs and ROTs. The undesirable overhead caused by transaction restart and blocking due to concurrency control can be alleviated. Consequently, the timeliness of the system can be improved. The performance of using this approach is examined through a series of simulation experiments. The results showed that the performance of ROTs in terms of miss rate and restart rate is improved significantly while the performance of UTs is also improved slightly. As a result, separate processing of ROTs is a viable approach that achieves better performance and resource utilization than using solely the OCC protocol, one of the best performing protocols in the literature of real-time database.     

面向混合实时数据库系统的调度与并发控制

在航天测量与控制系统中，访问实时数据库的实时事务对时间限制的要求是不一致的，该文在分析了这些事务特征的基础上，提出了混合实时数据库系统的概念，并设计了相应的优先级分派算法——事务的紧迫度和终止时间优先和并发控制协议——扩展的有条件优先级继承。     

Two individual computer workstations

This article describes two workstations to operate at under $10,000 and designed to provide the computer capabilities for a number of art- and design-related tasks. The article questions whether one computer graphic system and workstation is really suitable for all computer graphic tasks at least at the low and middle ranges of computer equipment and software.^† Implications for education in the arts are discussed and a range of options for the artist as well as the art educator are presented. Practical options and concerns for the purchase of computer hardware and software and video-related equipment are also discussed.     

Transaction Scheduling in Distributed Real-Time Systems

Inthis paper, we study the performance of using optimistic approachto concurrency control in distributed real-time database systems(RTDBS). The traditional optimistic approach suffers from theproblem of unnecessary restarts. Transaction restarts can significantlyincrease the system workload and intensify resource and datacontention. In distributed environments, the complexity of thesystem and the high communication overhead exacerbate the problem.Therefore, the number of unnecessary restarts is the determinantfactor that affects the performance of optimistic approach indistributed RTDBS. When optimistic approach is extended to distributedenvironments, a number of issues resulting from the increasedcomplexity and communication overhead have to be resolved. Inthis paper, a new real-time distributed optimistic concurrencycontrol (DOCC) protocol with dynamic adjustment of serializationorder (DASO), called DOCC-DA is proposed. This protocol can avoidunnecessary transaction restarts by dynamically adjusting theserialization order of the conflicting transactions. Therefore,resources can be saved and more transactions can meet their deadlines.In the DOCC-DA protocol, a new distributed circular validationscheme is included to facilitate transaction validation in distributedenvironments. The performance of the DOCC-DA protocol has beenexamined in detail by simulation. The results showed that theperformance of the DOCC-DA protocol is consistently better thanthat of other protocols.     

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

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

并行数据库实时多版本并发控制协议性能研究

随着对实时数据库事务处理性能要求的不断提高 ,将并行数据库和实时数据库相结合的并行实时数据库将成为新的发展方向 .然而通常的实时多版本并发控制协议不适合并行数据库的无共享结构 .比较了几种并发控制协议在无共享结构下的性能 ,该文提出了一种并行实时多版本并发控制协议 .它能有效地减少事务的重启 ,降低事务的错过率 .在长短事务混合的情况下 ,它的性能比其它的并发控制协议更好 .同时 ,它具有更好的可扩展性 .作者利用仿真模型对该协议进行了性能测试 ,与其它协议进行了比较 ,并分析了实验结果 ,仿真实验结果表明该协议性能良好     

Classification of paint on metallic surfaces using spatial domain analysis of laser images

In this paper a classification method is described for painted surfaces using laser image clarity meter (LIC)^†. In this method extracted features from reflected images of size (512 × 512 × 8 bits) from painted surfaces are used for classification purpose. The distance measured between the features of the test samples and the reference sample, which is smooth black glass, determines the deviation of the test sample from the reference. In comparing the result of 500 of the painted panels classified by the proposed method with the result of visual inspection, we have shown that this method is quite effective.     

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

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

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.     

Analysis of global pressure relaxation for flows with strong interaction and separation

A global or pressure relaxation formulation for the reduced form of the Navier-Stokes equations, frequently referred to as semi-elliptic or partially parabolized or just “parabolized” Navier-Stokes (PNS),^‡ is presented. Difference procedures and relaxation solutions for the (u, v, p) system are described. The continuity equation is satisfied exactly at each grid point and a poisson pressure equation is not required explicitly. Several model problems, e.g. finite flat plate, trough, boattail and airfoil, are considered. Strong pressure interaction is evident in each case and axial flow separation occurs for several of the problems. The questions of accuracy, stability, convergence rate, and implied difference forms of the pressure and vorticity equations are addressed. Solutions for laminar and turbulent modelling are presented.     

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.     

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.     

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.     

Real-time concurrency control in a multiprocessor environment

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system     

并行实时数据库系统中的一种自适应并发控制模式

根据事务的实时性及关键性分类,事务分为硬实时、固实时、软实时和非实时事务。传统的并发控制仅考虑其中一到两种事务,且将固／软实时事务统一为软实时事务考虑,带有很大的不精确性,这将降低系统吞吐率。为此,本文提出了一种自适应并发控制模式。该模式采用两级并发控制体系,一级是主并发控制器,探测不同类事务间可能存在
在的类间数据冲突;二级是从并发控制器,探测同类事务间可能存在的类内数据冲突,由四类从并发控制器实现。根据各类事务的不同特征,各控制器采用的策略不同,因而具有极大的自适应性并能最终提高系统的吞吐率,但需要增加额外的硬件开销。