Queueing network models for concurrent transaction processing in a database system

ABSTRACT

This paper presents two queueing network models which correspond to different implementations of the lock management algorithm for concurrent transaction processing in a database system. These models are developed to investigate the effects of varying the granularity of locks and the degree of multiprogramming on the performance of a database system. A numerical example is presented for a set of apparently realistic parameters and its results are discussed. In addition to other conclusions, these results also confirm the result of Ries and Stonebraker, using a simulation model [9], that a relatively coarse granularity is sufficient to allow enough parallelism for efficient resource utilization. In contrast with simulation models, the queueing network models presented in this paper allow us to examine more closely the cause-effect relationships of concurrent transaction processing in a database system at less cost.

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: Berstein, P.A., et al. "The Concurrency Control Mechaniśm of SDD-1: A System for Distributed Databases (The Fully Redundant Case)", IEEE Transactions on Software Engineering, Vol. SE-4, No. 3, May 1978, pp. 154--168.
• 3: Jeffrey P. Buzen, Computational algorithms for closed queueing networks with exponential servers, Communications of the ACM, v.16 n.9, p.527-531, Sept. 1973 [doi>10.1145/362342.362345]
• 4: 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]
• 5: Gray, J.N., et al. "Granularity of Locks and Degree of Consistency in a Shared Data Base", in Modelling in Database Management Systems, G.M. Nijssen (ed.) North-Holland, 1976.
• 6: King, P.F. and Collmeyer, A.J. "Database Sharing --- an Efficient Mechanism for Supporting Concurrent Processes", Proc. AFIPS 1973, NCC, Vol.42, pp. 271--276.
• 7: Kleinrock, L. "Queueing Systems --- Vol.2: Computer Applications" John Wiley and Sons, New York, 1976.
• 8: 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]
• 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 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]
• 11: Johnny Wai-Nang Wong, Queueing network models for computer systems., 1975