Analysis of locking policies in database management systems

ABSTRACT

Consistency control has to be enforced in database management systems (DBMS) where several transactions may concurrently access the database. This control is usually achieved by dividing the database into locking units or granules, and by specifying a locking policy which ensures integrity of the information. However, a drawback of integrity enforcement through locking policies is the degradation of the global system performance. This is mainly due to the restriction imposed by the locking policies to the access of transactions to the database, and to the overheads involved with the management of locks. A framework for the quantitative analysis of the impact of these factors on the performance of DBMS is presented in this paper. In a first step, the main factors which determine the behavior of these systems are pointed out and analyzed independently. The results hereby obtained are aggregated in a second step to yield a global performance evaluation. Throughout this hierarchical modeling approach various analytical techniques are used and the results are illustrated by numerical examples. The paper concludes by pointing out the final results' sensitivity to some basic assumptions concerning transaction behavior and the need for more experimental studies in this area.

REFERENCES

• 1: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 2: Mike Blasgen , Jim Gray , Mike Mitoma , Tom Price, The convoy phenomenon, ACM SIGOPS Operating Systems Review, v.13 n.2, p.20-25, April 1979 [doi>10.1145/850657.850659]
• 3: K. Mani Chandy , Charles H. Sauer, Approximate Methods for Analyzing Queueing Network Models of Computing Systems, ACM Computing Surveys (CSUR), v.10 n.3, p.281-317, Sept. 1978 [doi>10.1145/356733.356737]
• 4: Denning, P.J., Kahn, K.C., Leroudier, J., Potier, D., and Suri, R. Optimal multiprogramming. Acta Inform. 7, 2 (1976), 197-216.
• 5: D. C. Gilbert, Modeling spin locks with queuing networks, ACM SIGOPS Operating Systems Review, v.12 n.1, p.29-42, January 1978 [doi>10.1145/775323.775327]
• 6: Merle, D., Potier, D., and Veran, M. A tool for computer system performance analysis. Proc. Internat. Conf. on Performance of Comptr. Installations 1978, North-Holland Pub. Co., Amsterdam, 1978, pp. 195-214.
• 7: 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]
• 8: Riordan, J. An Introduction to Combinatorial Analysis. John Wiley and Sons, N.Y., 1958.
• 9: Daniel R. Ries , Michael Stonebraker, Effects of locking granularity in a database management system, ACM Transactions on Database Systems (TODS), v.2 n.3, p.233-246, Sept. 1977 [doi>10.1145/320557.320566]
• 10: Daniel R. Ries , Michael R. Stonebraker, Locking granularity revisited, ACM Transactions on Database Systems (TODS), v.4 n.2, p.210-227, June 1979 [doi>10.1145/320071.320078]
• 11: Rodriguez-Rosell, J. Empirical data reference behaviour in database systems. Computer 9, 11 (Nov. 1976), 9-13.
• 12: Rodriguez-Rosell, J., and Hildebrand, D. A framework for evaluation of database management system. Proc. Internat. Comptng. Symp. 1975, E. Gelenbe and D. Potier, Eds., North-Holland Pub. Co., Amsterdam, 1975.
• 13: Alan Jay Smith, Sequentiality and prefetching in database systems, ACM Transactions on Database Systems (TODS), v.3 n.3, p.223-247, Sept. 1978 [doi>10.1145/320263.320276]
• 14: William J. Stewart, A comparison of numerical techniques in Markov modeling, Communications of the ACM, v.21 n.2, p.144-152, Feb. 1978 [doi>10.1145/359340.359350]
• 15: Tuel, W.G., and Rodriguez-Rosell, J. A methodology for evaluation of database systems. Res. Rep. RJ 1688, IBM Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y., 1976.
• 16: Veran, M. QNAP description language. Res. Rep., Antenne Scientifique CII-Honeywell-Bull, Grenoble, France, 1979.

INDEX TERMS

Keywords:
concurrency, consistency, database management, performance modeling, queueing models, queueing networks