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

1. AGM88a.Robert Abbot and Hector Garcia-Molina. Schedufing real-time transactions. SIGMOD RECORD, 17(1):71-81, 1988.
2. AGM88b.Robert Abbot and Hector Garcia-Molina. Scheduling real-time transactions: a performance evaluation. In Proceedings of the 14th VLDB, pages 1-12. ACM, 1988.
3. AGM89.Robert Abbot and Hector Garcia-Molina. Scheduling real-time transactions with disk resident data. In Proceedings of the 15th VLDB, pages 385-396. ACM, 1989.
4. BMH89.A. Buchmann, D.R. McCarthy, and M. Hsu. Time-critical database scheduling: A framework for integrating real-time scheduling and concurrency control. In Proceedings of the Fifth Conference on Data Engineering, pages 470-480, Feb 1989.
5. 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.
6. Fis92.Paul A. Fishwick. SIMPACK:C.based Stmu. lat,on Tool Package Versson 2.University of Florida, 1992.
7. Har91.Jayant Ramaswamy Haritsa.Transaction scheduling in firm real-time database systems. Technical Report TR1036, University of Wisconsin-Madison, 1991.
8. HCL90.Jayant R. Haritsa, Michael J. Carey, and Miron Livny. On being optimistic about real-time constraints. A CM SIGMOD, 1990.
9. HSRT91.Jiandong Hyang, John A. St#nkovic, Krithi Ramamritham, and Don Towsley. Experimental evaluation of real-time optimistic concurrency control schemes. In Proceedings of the 17th VLDB, pages 35-46. ACM, 1991.
10. LL73.C.L. Liu and J.W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM, pages 46-61, 1973.
11. Sha88.Lui Sha. Concurrency control for distributed real-time databases. SIGMOD RECORD, 17(1 ):82-98, 1988.
12. SRSC91.Lui Sha, Ragunathan Rajkumar, Sang Hyuk Son, and Chun-Hyun Chang. A real-time locking protocol IEEE Transact,ons on Computers, 40(7):793-800, 1991.
13. SZ88.John A. Stankovic and Wei Zhao. On real-time transactions. SIGMOD RECORD, 17(1):4-18, 1988.
14. XP90.Jia Xu and David R. Parnas. Scheduling processes with release times, deadlines, precedence, and exclusion relations. IEEE Transactions on Software Engineering, 16(3):360-369, 1990.
15. ZRS87a.Wei Zhao, Krithi Ramamritham, and John A. Stankovic. Preemptive scheduling under time and resource constraints. 1EEE Transactions on Computers, 36(8):949-960, 1987.
16. ZRS87b.Wei Zhao, Krithi Ramamritham, and John A. Stankovic. Scheduling tasks with requirement in hard real-time systems. IEEE Transactions on Software Engzneering, 13(5):225-236, 1987.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation support systems

      • Simulation environments

• Information systems

  • Data management systems

    • Database management system engines

      • Database transaction processing

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making