Performance evaluation of cautious waiting

ABSTRACT

We study a deadlock-free locking-based concurrency control algorithm, called cautious waiting, which allows for a limited form of waiting. The algorithm is very simple to implement. We present an analytical solution to its performance evaluation based on the mean-value approach proposed by Tay et al. [18]. From the modeling point of view, we are able to do away with a major assumption used in Tay's previous work, and therefore capture more accurately both the restart and the blocking rates in the system. We show that to solve for this model we only need to solve for the root of a polynomial. The analytical tools developed enable us to see that the cautious waiting algorithm manages to achieve a delicate balance between restart and blocking, and therefore is superior (i.e., has higher throughput to both the no-waiting (i.e., immediate restart) and the general waiting algorithms under a wide range of system parameters. The study substantiates the argument that balancing restart and blocking is important in locking systems.

REFERENCES

• 1: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 2: AGRAWAL, R., AND CAREY, M. J. Performance of alternative strategies for dealing with deadlocks in DBMSs. Submitted for publication.
• 3: 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]
• 4: Philip A. Bernstein , David W. Shipman , James B. Rothnie, Jr., Concurrency control in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.18-51, March 1980 [doi>10.1145/320128.320131]
• 5: Michael J. Carey , Michael Stonebraker, The Performance of Concurrency Control Algorithms for Database Management Systems, Proceedings of the 10th International Conference on Very Large Data Bases, p.107-118, August 27-31, 1984
• 6: 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]
• 7: Peter Franaszek , John T. Robinson, Limitations of concurrency in transaction processing, ACM Transactions on Database Systems (TODS), v.10 n.1, p.1-28, March 1985 [doi>10.1145/3148.3160]
• 8: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 9: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 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: KUMAR, V. An analysis of the roll-back and blocking operations of three concurrency control mechanisms. In Procee&ngs of Natzonal Computer Conference. 1987.
• 12: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 13: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 14: D. Potier , Ph. Leblanc, Analysis of locking policies in database management systems, Communications of the ACM, v.23 n.10, p.584-593, Oct. 1980 [doi>10.1145/359015.359021]
• 15: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 16: Yong Chiang Tay, A mean value performance model for locking in databases, 1984
• 17: Y. C. Tay , Rajan Suri , Nathan Goodman, A mean value performance model for locking in databases: the no-waiting case, Journal of the ACM (JACM), v.32 n.3, p.618-651, July 1985 [doi>10.1145/3828.3831]
• 18: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]
• 19: Alexander Thomasian , In Kyung Ryu, A decomposition solution to the queueing network model of the centralized DBMS with static locking, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.82-92, August 29-31, 1983, Minneapolis, Minnesota, United States [doi>10.1145/800040.801397]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

General Terms:
Algorithms, Management, Performance

Keywords:
cautious waiting, concurrency control