Real-time transaction scheduling: a cost conscious approach

ABSTRACT

Real-time databases are an important component of embedded real-time systems. In a real-time database context, transactions must not only maintain the consistency constraints of the database but must also satisfy the timing constraints specified for each transaction. Although several approaches have been proposed to integrate real-time scheduling and database concurrency control methods, none of them take into account the dynamic cost of scheduling a transaction. In this paper, we propose a new cost conscious real-time transaction scheduling algorithm which considers dynamic costs associated with a transaction. Our dynamic priority assignment algorithm adapts to changes in the system load without causing excessive numbers of transaction restarts. Our simulations show its superiority over EDF-HP algorithm.

REFERENCES

• AGM88a: Robert Abbott , Hector Garcia-Molina, Scheduling real-time transactions, ACM SIGMOD Record, v.17 n.1, p.71-81, March, 1988 [doi>10.1145/44203.44209]
• AGM88b: 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
• AGM89: 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
• BMH89: Alejandro P. Buchmann , Dennis R. McCarthy , M. Hsu , Umeshwar Dayal, Time-Critical Database Scheduling: A Framework For Integrating Real-Time Scheduling and Concurrency Control, Proceedings of the Fifth International Conference on Data Engineering, p.470-480, February 06-10, 1989
• C+89: S. Chakravarthy et al. HiPAC: A Research Project in Active, Time-Constrained Database Management, Final Report. Technical Report XAIT-89-02, Xerox Advanced Information Technology, Cambridge, MA, Aug. 1989.
• Fis92: Paul A. Fishwick. SIMPACK:C.based Stmu. lat,on Tool Package Versson 2.University of Florida, 1992.
• Har91: Jayant Ramaswamy Haritsa.Transaction scheduling in firm real-time database systems. Technical Report TR1036, University of Wisconsin-Madison, 1991.
• HCL90: 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]
• HSRT91: Jiandong Huang , John A. Stankovic , Krithi Ramamritham , Donald F. Towsley, Experimental Evaluation of Real-Time Optimistic Concurrency Control Schemes, Proceedings of the 17th International Conference on Very Large Data Bases, p.35-46, September 03-06, 1991
• LL73: 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]
• Sha88: Lui Sha , Ragunathan Rajkumar , John P. Lehooczky, Concurrency control for distributed real-time databases, ACM SIGMOD Record, v.17 n.1, p.82-98, March, 1988 [doi>10.1145/44203.44210]
• SRSC91: Lui Sha , Sang Hyuk Son , Ragunathan Rajkumar , Chun-Hyon Chang, A Real-Time Locking Protocol, IEEE Transactions on Computers, v.40 n.7, p.793-800, July 1991 [doi>10.1109/12.83617]
• SZ88: John A. Stankovic , Wei Zhao, On real-time transactions, ACM SIGMOD Record, v.17 n.1, p.4-18, March, 1988 [doi>10.1145/44203.44204]
• XP90: Jia Xu , David Parnas, Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations, IEEE Transactions on Software Engineering, v.16 n.3, p.360-369, March 1990 [doi>10.1109/32.48943]
• ZRS87a: W. Zhao , K. Ramamritham , J. A. Stanovic, Preemptive scheduling under time and resource constraints, IEEE Transactions on Computers, v.36 n.8, p.949-960, Aug. 1987 [doi>10.1109/TC.1987.5009518]
• ZRS87b: W. Zhao , K. Ramamritham , J. A. Stankovic, Scheduling tasks with resource requirements in hard real-time systems, IEEE Transactions on Software Engineering, v.13 n.5, p.564-577, May 1987 [doi>10.1109/TSE.1987.233201]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems
          Subjects: Environments

General Terms:
Algorithms, Design, Performance, Theory, Verification