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 inse rt, 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 (Sha, Rajkumar, and Lehoczky, 1990). We propose metho dologies to reduce the number of disk I/O to improve the system performance without introducing more priority inversion. When the schedulability of re quests with critical timing constraints is highly important, we propose a m echanism for data reservation based on the idea of preemption level and the Stack Resource Policy (Baker, 1990). The performance of our methodologies was evaluated by a series of experiments, from which we have obtained encou raging results.