On being optimistic about real-time constraints

ABSTRACT

Performance studies of concurrency control algorithms for conventional database systems have shown that, under most operating circumstances, locking protocols outperform optimistic techniques. Real-time database systems have special characteristics - timing constraints are associated with transactions, performance criteria are based on satisfaction of these timing constraints, and scheduling algorithms are priority driven. In light of these special characteristics, results regarding the performance of concurrency control algorithms need to be re-evaluated. We show in this paper that the following parameters of the real-time database system - its policy for dealing with transactions whose constraints are not met, its knowledge of transaction resource requirements, and the availability of resources - have a significant impact on the relative performance of the concurrency control algorithms. In particular, we demonstrate that under a policy that discards transactions whose constraints are not met, optimistic concurrency control outperforms locking over a wide range of system utilization. We also outline why, for a variety of reasons, optimistic algorithms appear well-suited to real-time database systems.

REFERENCES

• Abbo88: Robert K. Abbott , Hector Garcia-Molina, Scheduling Real-time Transactions: a Performance Evaluation, Proceedings of the 14th International Conference on Very Large Data Bases, p.1-12, August 29-September 01, 1988
• Abbo89: R. Abbott , H. Garcia-Molina, Scheduling real-time transactions with disk resident data, Proceedings of the 15th international conference on Very large data bases, p.385-395, July 1989, Amsterdam, The Netherlands
• Agra87: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• Care88: Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988
• Care89: M. J. Carey , R. Jauhari , M. Livny, Priority in DBMS resource scheduling, Proceedings of the 15th international conference on Very large data bases, p.397-410, July 1989, Amsterdam, The Netherlands
• Eswa76: 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]
• Kung81: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• Livn88: Livny, M., DeNet User's Guide, Version 1.0, Comp. Sei. Dept., Univ. of Wisconsin, Madison, 1988.
• Mena82: Menasce, D., and Nakanishi, T., "Optimistic versus Pessimistic Concurrency Control Mechanisms in Database Management Systems," Information Systems, vol. 7-I, 1982.
• Robi82: John Timothy Robinson, Design of concurrency controls for transaction processing systems, 1982
• Sha87: Sha, L., Rajkumar, R., and Lehoczl~, J., "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," Tech. Report No. CMU-CS-87-181, Carnegie Mellon University, Dec. 1987.
• Jack63: Jackson, J.R., "Jobshop-like Queuing Systems," Management Science, No. 10-1, Oct. 1963.
• Klei75: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory