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.