DATA-STRUCTURES FOR PARALLEL RESOURCE-MANAGEMENT

The problem of resource management for many processor architectures ca n be viewed as the problem of simultaneously updating data structures that hold system state. Consistency requirements of strict data struct ures introduce serialization in the resource management functions ther eby leading to performance bottlenecks in highly parallel systems. Our approach is to examine the possibility of using structures with weake ned specifications. Specifically, this paper introduces data structure s that weaken the specification of a priority queue permitting it to b e updated simultaneously by multiple processes. Two structures are pro posed, the concurrent heap and the software banyan along with their as sociated algorithms for update. The algorithms are shown to possess at tractive properties of simultaneous update and throughput. The results of simulation and actual implementations show that such data structur es can improve the execution times of parallel algorithms quite signif icantly. These structures are proposed as possible basic building bloc ks for implementation of resource allocation in operating systems.