×

zbMATH — the first resource for mathematics

Probabilistic models and asymptotic results for concurrent processing with exclusive and non-exclusive locks. (English) Zbl 0582.68062
We give a probabilistic model for conflicts among transactions in a database. We extend recent work [D. Mitra and P. J. Weinberger, J. Assoc. Comput. Mach. 31, 855-878 (1984)] 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.

MSC:
68P20 Information storage and retrieval of data
68N25 Theory of operating systems
PDF BibTeX XML Cite
Full Text: DOI