Real-Time Access Control and Reservation on B-Tree Indexed Data

This paper proposes methodologies to control the access of B⁺-tree-indexed data in a batch and firm real-time fashion. Algorithms are proposed to insert, query, delete, and rebalance B⁺-tree-indexed data based on the non-real-time algorithms proposed in Kerttu, Eljas, and Tatu (1996) and the idea of priority inheritance. We propose methodologies to reduce the number of disk I/O to improve the system performance without introducing more priority inversion. When the schedulability of requests with critical timing constraints is highly important, we propose a mechanism for data reservation based on the idea of preemption level and the Stack Resource Policy. The performance of our methodologies was evaluated by a series of experiments, from which we have obtained encouraging results.