Data Structures for Parallel Resource Management.

The problem of resource management for many processor architectures can be viewed as the problem of simultaneously updating data structures that hold system state. Consistency requirements of strict data structures introduce serialization in the resource management functions thereby leading to performance bottlenecks in highly parallel systems. Our approach is to examine the possibility of using structures with weakened specifications. Specifically, this paper introduces data structures that weaken the specification of a priority queue permitting it to be updated simultaneously by multiple processes. Two structures are proposed, the concurrent heap and the software banyan along with their associated algorithms for update. The algorithms are shown to possess attractive properties of simultaneous update and throughput. The results of simulation and actual implementations show that such data structures can improve the execution times of parallel algorithms quite significantly. These structures are proposed as possible basic building blocks for implementation of resource allocation in operating systems. [ABSTRACT FROM AUTHOR]