Evaluation of the Bitstring Algorithm
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
A resource allocation technique based on an alternative data representation to the list structure, i.e. the bitvector, is discussed in this paper. The data structure provides for implicit collapsing of available resources, and the algorithm, called Bitstring, can be applied to any type of resource without performance loss. An optimized implementationof Bitstring is compared with a corresponding list structure algorithm Firstfit. Two bitvector algorithms for special resource allocation environments, Exactstring and Quickstring, are presented. The implementation of Bitstring in microcode on a PDP-1140E and the resulting performance improvement relative to the assembly code implementation are discussed.
- Computer Programming and Software
- Computer Hardware