Managing memory for real-time queries

ABSTRACT

The demanding performance objectives that real-time database systems (RTDBS) face necessitate the use of priority resource scheduling. This paper introduces a Priority Memory Management (PMM) algorithm that is designed to schedule queries in RTDBS. PMM attempts to minimize the number of missed deadlines by adapting both its multiprogramming level and its memory allocation strategy to the characteristics of the offered workload. A series of simulation experiments confirms that PMM's admission control and memory allocation mechanisms are very effective for real-time query scheduling.

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
• Abbo90: R. Abbott, H. Garcia-Molina, "Scheduling I/O Requests with Deadlines, A Performance Evaluation", Proc. 1990 RTSS Syrup.
• Bitt88: D. Bitton, J. Gray, "Disk Shadowing", Proc. 1989 VLDB Conf.
• Brow93: Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
• 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
• Chen91: S. Chen, J.A. Stankovlc, J.F, Kurose, D. Towsley, "Performance Evaluation of Two New Disk Scheduling Algorithms for Real- Time Systems", Real-Time Systems Journal 3(3), 1991
• Corn89: D. W. Cornell , Ph.S. Yu, Integration of buffer management and query optimization in relational database environment, Proceedings of the 15th international conference on Very large data bases, p.247-255, July 1989, Amsterdam, The Netherlands
• Devo91: J.L. Devore, Probability and Stattstics for Engmeering and the Sciences, Brooks/Cole Pub. Co., 1991, pp. 283-301,326-335.
• Drap81: N.R Draper, H. Smith, Apphed Regresston Analysis, John Wiley & Sons, Inc., 1981, pp. 70-136.
• Hari90: Jayant R. Haritsa , Michael J. Carey , Miron Livny, On being optimistic about real-time constraints, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-343, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298585]
• Huan89: J. Huang, J.A. Stankovic, D. Towsley, K. Ramamritham, "Experimental Evaluation of Real-Time Transaction Processing", Proc. 1989 RTSS Symp.
• Kim91: W. Kim, J. Srivastava, "Enhancing Real-Time DBMS Performance with Multiversion Data and Priority Based Disk Scheduling", PrQ#,, 1991 RTSS S_ymp.
• Liu73: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• Livn90: M. Livny, "DeNet User's Guide, Version 1.5", Computer Sclences Department. University of Wisconsin, Madison, 1990
• Pang93a: Hwee Hwa Pang , Michael J. Carey , Miron Livny, Partially preemptible hash joins, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.59-68, May 25-28, 1993, Washington, D.C., United States
• Pang93b: HweeHwa Pang , Michael J. Carey , Miron Livny, Memory-Adaptive External Sorting, Proceedings of the 19th International Conference on Very Large Data Bases, p.618-629, August 24-27, 1993
• Sarg76: Robert G. Sargent, Statistical analysis of simulation output data, Proceedings of the 4th symposium on Simulation of computer systems, p.39-50, August 10-12, 1976, Boulder, Colorado, United States
• Shap86: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• Yu93: Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993 [doi>10.1007/BF01231797]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Performance