A mean value performance model for locking in databases: the waiting case

ABSTRACT

An earlier paper introduced a simple performance model for studying the behaviour of locking. That paper treats a highly simplified form of locking, called the no waiting case, in which transactions restart when they request locks that are already held by others. This analysis is now extended to the more realistic waiting case, in which transactions are allowed to wait for conflicting locks, and restart only if there is a deadlock. The analysis begins with a system that has uniform access and exclusive locks only. The model's predictions for this base system agree well with simulation results. Next, a system with nonuniform access and another with shareable locks are each shown to be reducible to the base system. A comparison of the waiting and no waiting cases yields a surprising result: the throughput for the no waiting case is often better than for the waiting case, and never much worse.

REFERENCES

• 1: R. Balter , P. Berard , P. Decitre, Why control of the concurrency level in distributed systems is more fundamental than deadlock management, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.183-193, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806696]
• 2: {B0} Beeri, C. and Obermarck, R. A resource class independent deadlock detection algorithm. Proc. International Conference on Very Large Databases, Cannes, France (Sept. 1981), 166-178.
• 3: A. Chesnais , E. Gelenbe , I. Mitrani, On the modeling of parallel access to shared data, Communications of the ACM, v.26 n.3, p.196-202, March 1983 [doi>10.1145/358061.358073]
• 4: Joao Eduardo De Rezende Dantas, Performance analysis of distributed database systems, 1980
• 5: {DKLPS} Denning, P.J., Kahn, K.C., Leroudier, J., Potier, D., and Suri, R. Optimal multiprogramming. Acta Informatica 7, 2 (1976), 197-216.
• 6: {G} Galler, B.I. Concurrency control performance issues. Technical Report CSRG-147, Computer Systems Research Group, University of Toronto (Sept. 1982).
• 7: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 8: Jim Gray, A Transaction Model, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.282-298, July 14-18, 1980
• 9: Nathan Goodman , Rajan Suri , Y. C. Tay, A simple analytic model for performance of exclusive locking in database systems, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588084]
• 10: Keki B. Irani , Hing-Lung Lin, Queueing network models for concurrent transaction processing in a database system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582116]
• 11: {K} Kleinrock, L. Queveing systems, Vol 1: Theory. John Wiley & Sons, New York (1975).
• 12: {LN} Lin, W.K., and Nolte, J. Performance of two phase locking. Proc. 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Feb. 1982) 131-160.
• 13: R. Munz , G. Krenz, Concurrency in database systems: a simulation study, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509421]
• 14: Debasis Mitra , Peter J. Weinberger, Some Results on Database Locking: Solutions, Computational Algorithms and Asymptotics, Proceedings of the International Workshop on Computer Performance and Reliability, p.373-386, September 26-30, 1983
• 15: R Suri , G W Diehl, A variable buffer-size model and its use in analyzing closed queueing networks with blocking, Management Science, v.32 n.2, p.206-224, Feb. 1986 [doi>10.1287/mnsc.32.2.206]
• 16: {SS} Shum, A.W. and Spirakis, P.G. Performance analysis of concurrency control methods in database systems. Performance '81, F.J. Kylstra (ed.), North Holland (1981), 1-19.
• 17: {T} Thornasian, A. An iterative solution to the queueing network model of a DBMS with dynamic locking. Proc. 13th Computer Measurement Group Conference, San Diego, CA (Dec. 1982) 252-261.
• 18: {TSG 1} Tay, Y.C., Suri, R. and Goodman, N. A mean value performance model for locking in databases: the no waiting case. Technical Report TR-16-83, Aiken Computation Laboratory, Harvard University (May 1983).
• 19: {TSG 2} Tay, Y.C., Suri, R. and Goodman, N. A mean value performance model for locking in databases: the waiting case. Technical Report TR-29-83, Aiken Computation Laboratory, Harvard University (Dec 1983).