Performance Evaluation of Cautious Waiting.

Meichun Hsu, Bin Zhang: Performance Evaluation of Cautious Waiting. ACM Trans. Database Syst. 17(3): 477-512(1992)

@article{DBLP:journals/tods/HsuZ92,
  author    = {Meichun Hsu and
               Bin Zhang},
  title     = {Performance Evaluation of Cautious Waiting},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {3},
  year      = {1992},
  pages     = {477-512},
  ee        = {http://doi.acm.org/10.1145/132271.132275, db/journals/tods/HsuZ92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1925 KB]

References

[1]: Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[2]: Rakesh Agrawal, Michael J. Carey, Lawrence W. McVoy: The Performance of Alternative Strategies for Dealing with Deadlocks in Database Management Systems. IEEE Trans. Software Eng. 13(12): 1348-1363(1987) BibTeX
[3]: R. Balter, P. Berard, Paul Decitre: Why Control of the Concurrency Level in Distributed Systems is More Fundamental Than Deadlock Management. PODC 1982: 183-193 BibTeX
[4]: Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX
[5]: Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118 BibTeX
[6]: A. Chesnais, Erol Gelenbe, Isi Mitrani: On the Modeling of Parallel Access to Shared Data. Commun. ACM 26(3): 196-202(1983) BibTeX
[7]: Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) BibTeX
[8]: Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[9]: Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[10]: Keki B. Irani, Hing-Lung Lin: Queuing Network Models for Concurrent Transaction Processing in a Database System. SIGMOD Conference 1979: 134-142 BibTeX
[11]: ...
[12]: H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[13]: Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[14]: Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
[15]: Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
[16]: ...
[17]: Y. C. Tay, Rajan Suri, Nathan Goodman: A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. J. ACM 32(3): 618-651(1985) BibTeX
[18]: Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985) BibTeX
[19]: ...

Referenced by

Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
Alexander Thomasian: A Performance Comparison of Locking Methods with Limited Wait Depth. IEEE Trans. Knowl. Data Eng. 9(3): 421-434(1997)
Alexander Thomasian: Two-Phase Locking Performance and Its Thrashing Behavior. ACM Trans. Database Syst. 18(4): 579-625(1993)
Peter A. Franaszek, John T. Robinson, Alexander Thomasian: Concurrency Control for High Contention Environments. ACM Trans. Database Syst. 17(2): 304-345(1992)
Alexander Thomasian: Performance Limits of Two-Phase Locking. ICDE 1991: 426-435

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]