Meichun Hsu
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.
- 1 AGRAWAL, R., CAREY, M. J., AND LIVNY, M. Concurrency control performance modeling: Alternatives and implications. ACM Trans. Database Syst. 12, 4 (Dec. 1987). Google Scholar
- 2 AGRAWAL, R., AND CAREY, M. J. Performance of alternative strategies for dealing with deadlocks in DBMSs. Submitted for publication.Google Scholar
- 3 BALTER, R., BERARD, P., AND DECITRE, P. Why control of concurrency level in distributed systems is more fundamental than deadlock management. In Proceedings of the ACM PODC (Ottawa, Aug. 1982), pp. 183 193. Google Scholar
- 4 BERNSTEIN, P. A., SHIPMAN, D. W., AND ROTHNIE, J.B. Concurrency control in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 5, 1 (Mar. 1980), 18-51. Google Scholar
- 5 CAREY, M., AND STONEBRAKER, M. The performance of concurrency control algorithms for database management systems. In Proeeedtngs of the lOth VLDB (Singapore, Aug. 1984). Google Scholar
- 6 CHBSNAIS, A., GELENBE, E., AND MITRANI, I. On the modeling of parallel access to shared data. Commun. ACM 26, 3 (Mar. 1983), 196 202. Google Scholar
- 7 FRANASZEK, P., AND ROBINSON, J.T. Limitations of concurrency in transaction processing. ACM Trans. Database Syst. 10, 1 (Mar. 1985), 1-28. Google Scholar
- 8 ESWARAN, K. P., GRAY, J. N, LORIE, R. A., AND TRA1GER, I.L. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633. Google Scholar
- 9 GRAY, J. N. Notes on database operating systems. In Operating Systems--An Advanced Course. R. Bayer, R. M. Graham, B. G. Seegmuller, Eds. Springer-Verlag, New York, 1978, pp. 393-481. Google Scholar
- 10 IRANI, K., AND LIN, H. Queuing network models for concurrent transaction processing in a database system. In Proceedings of the ACM-SYGMOD. ACM, New York, 1979. Google Scholar
- 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.Google Scholar
- 12 KUNG, H. T., AND ROBINSON, J. On optimistic methods for concurrency control. ACM Trans. Database Syst. 6, 2 (June 1981). Google Scholar
- 13 PAPADIMI~RIOU, C. The serializability of concurrent database updates. J. ACM 26, 4 (Oct. 1979). Google Scholar
- 14 POTIER, D., AND LEBLANC, P. Analysis of locking policies in database management systems. Commun. ACM 23, 10 (Oct. 1980). Google Scholar
- 15 ROSENKRANTZ, D. J., STEARNS, R. E., AND LEWIS, P.M. System level concurrency control for distributed database systems. ACM Trans Database Syst. 3, 2 (June 1978), 178 198 Google Scholar
- 16 TAY, Y.C. A mean value performance model for locking in databases. Ph.D. thesis, Harvard Univ., Cambridge, Mass, Feb. 1984. Google Scholar
- 17 TAY, Y. C, Sum, R., AND GOODMAN, N. A mean value performance model for locking in databases: The no waiting case. J. ACM 32, 3 (July 1985), 618-651. Google Scholar
- 18 TAY, Y. C., Sum, R., AND GOODMAN, N. Locking performance in centralized databases. ACM Trans. Database Syst. 10, 4, (Dec. 1985), 415-462. Google Scholar
- 19 THOMASIAN, A., AND RYU, I. A decomposition solution to the queuing network model of the centrahzed DBMS with statm locking. In Proceedzngs of the ACM-SIGMETRICS Conference on Measurement and Modeling of Computer systems (Minneapohs, Aug. 1983). Google Scholar
Index Terms
- Performance evaluation of cautious waiting
Recommendations
Performance Analysis of Dynamic Locking with the No-Waiting Policy
A transaction processing system with two-phase dynamic locking with the no waiting policy (DLNW) for concurrency control is considered. In this method, transactions making conflicting lock requests are aborted and restarted rather than blocked, thereby ...
Multiversion Cautious Schedulers for Database Concurrency Control
Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence ...
Performance Analysis of Two-Phase Locking
A straightforward analytic solution method is developed which takes into account the variability of transaction size (the number of lock requests). The authors first obtain analytic expressions for the probability of lock conflict, probability of ...
Comments