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

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