Browse Prior Art Database

Contiguous Resource Management

IP.com Disclosure Number: IPCOM000121916D
Original Publication Date: 1991-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 74K

Publishing Venue

IBM

Related People

Schwendiman, CA: AUTHOR [+2]

Abstract

Disclosed is an algorithm for searching for contiguous free resources, and then marking those resources as in use or free. The heart of the algorithm makes use of the CNTLZ (Count Leading Zeroes) instruction of the RISC System/6000* instruction set.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Contiguous Resource Management

      Disclosed is an algorithm for searching for contiguous
free resources, and then marking those resources as in use or free.
The heart of the algorithm makes use of the CNTLZ (Count Leading
Zeroes) instruction of the RISC System/6000* instruction set.

      This algorithm is designed to provide an efficient alternative
to resource management in code paths where performance is critical.
A typical use would be in a device driver that has to manage a pool
of resources, with the requirement that the resources be contiguous.

      The CNTLZ instruction counts the number of leading zero bits in
a 32-bit word.  The advantage of this new algorithm is that up to 32
(because of 32-bit word) contiguous resources can be found in one
instruction cycle, as well as up to 32 resources marked as in use or
free in one instruction cycle.  To manage the resources, a list of
32-bit words is initialized to 0xFFFFFFFF, where a bit set to 1
represents 1 free resource.  The number of 32-bit words needed is a
function of the number of resources managed divided by 32.  When
resources are allocated, a bit mask is created for the first and last
32-bit words that were used to fulfill the request for contiguous
resources.  The bit mask for any 32-bit word inbetween the first and
last words used is obviously 0xFFFFFFFF.  The masks for the first and
last words consist of the bits corresponding to the newly allocated
resources. The flowchart in the figure describes the algorithm in
detail.
      Following is a simple example of the algorithm:
      Total Number of resources = 128
      Number of 32-bit Words    =   4
      F...