RUI: "Splay Trees" as Operating System Ready Queues

点击翻译按钮获取中文摘要

This research is designed to modify the algorithms for the "splay tree" data structure developed by Sleator and Tarjan so as to use the splay tree for ready queue implementations in concurrent real-time operating systems. In particular, alternate heuristics for the "dequeue" and "enqueue" procedures will be developed to take advantage of, and to meet the demands of, the concurrency in a tightly-coupled multiprocessor environment. The modified data structure will then be implemented in a developmental operating system in order to make comparisons between the newly developed algorithms and those for the linked list.