A decomposition solution to the queueing network model of the centralized DBMS with static locking

ABSTRACT

The effect of concurrency control methods on the performance of computer systems is analyzed in the context of a centralized database with a static lock request policy, i.e., database transactions should acquire all locks before their activation. In the lock conflict model the L locks required by each transaction are uniformly distributed over the N locks in the database. The computer system is modelled as a queueing network. Two scheduling policies for transaction activation are considered: FCFS with and without skip. In each case the scheduling overhead for scanning the blocked transactions is taken into account. The number of transactions to be scanned is limited by a window size parameter. The system is analyzed using a hierarchical decomposition method, where the highest level model yields the mean user response time. The results of the approximate solution are validated using a detailed simulation, which shows that the analysis based on no resampling of locks is quite accurate and outperforms the simplified analysis with resampling of locks in accuracy. The effect of varying the values of parameters such as transaction size, granularity of locking, scheduling discipline for transaction activation, scheduling overhead, and window size on system performance is investigated.

REFERENCES

• 1: R. M. Brown , J. C. Browne , K. M. Chandy, Memory management and response time, Communications of the ACM, v.20 n.3, p.153-165, March 1977 [doi>10.1145/359436.359443]
• 2: Courtois, P.J.; Decomposability; Queueing and Computer System Applications, Academic Press, 1977.
• 3: Joao Eduardo De Rezende Dantas, Performance analysis of distributed database systems, 1980
• 4: C. J. Date, An Introduction to Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 5: 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]
• 6: Galler, B.I. "Concurrency control performance issues," Technical Report CSRG-147, Computer Systems Research Group, University of Toronto, Sept. 1982.
• 7: 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]
• 8: Annie W. Shum , Andrew M. Langer, The distribution of granule accesses made by database transactions, Communications of the ACM, v.25 n.11, p.831-832, Nov 1982 [doi>10.1145/358690.358714]
• 9: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 10: Menasce, D.A.; and Nakanishi, T. "Optimistic versus pessimistic concurrency control mechanisms in database management systems," Information Systems 7, 1(1982), 13-27.
• 11: Molina, H.G. "Performance of update algorithms for replicated data in a distributed database," Ph.D. Dissertation, Computer Science Dept., Stanford University, June 1979.
• 12: Nakanishi, T.; and Menasce, D.A. "Correctness and performance evaluation of a two-phase commit based protocal for DDBS," Technical Report DB 078102, Departamento de Informatica, Pontificia Universidade Catolica do Rio de Janeiro, Brasil, 1981.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: Ryu, I.K. "Performance modelling of database systems," Ph.D. Thesis in progress, Dept. EE-Systems, University of Southern California.
• 17: Sevcik, K.C. "Database system performance predication using an analytical model," in Proc. Seventh Int'l Conf. on Very Large Data Bases, Cannes, France, Sept. 1981, pp. 182-198.
• 18: Shum, A.W.; and Spirakis, P.G. "Performance analysis of concurrency control methods in database systems," in Performance '81, F.J. Kylstra (ed.), North-Holland, 1981, pp. 1-19.
• 19: 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]
• 20: Thomesian, A. "The performance of a transaction processing system with static locking," submitted for publication.
• 21: Thomasian, A. "An iterative solution to the queueing network model of a DBMS with dynamic locking," in Proc. 13th Computer Measurement Group Conference, San Diego, CA, Dec. 1982, pp 252-261.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Centralization/decentralization

General Terms:
Performance, Theory