Probabilistic Models and Asymptotic Results for Concurrent Processing with Exclusive and Non-Exclusive Locks
Debasis Mitra · SIAM Journal on Computing · 1985
We give a probabilistic model for conflicts among transactions in a database. We extend recent work (Mitra and Weinberger, J. Assoc. Comput. Mach., 31 (1984), pp. 855–878) by allowing two kinds of locks for concurrency control, exclusive and non-exclusive. Thus read locks allow shared access and are therefore non-exclusive, while write locks are exclusive. An arriving transaction is blocked if it conflicts with any of the transactions already undergoing processing; otherwise, it is accepted for concurrent processing. Our treatment, which has probabilistic, combinatorial and analytic components, yields exact formulas for performance measures, such as mean concurrency and throughput. For large databases special formulas are derived and proven to be asymptotically exact. These formulas are simple and also fit well to the exact formulas. What are non-exclusive locks worth? A succinct answer is given for this important design question.