Browse Prior Art Database

Method for Reserving Resources in a Multiprocessor Computer System Disclosure Number: IPCOM000234986D
Publication Date: 2014-Feb-21
Document File: 2 page(s) / 31K

Publishing Venue

The Prior Art Database


A method is disclosed for reserving one or more resource elements of a resource array in a computer system having two or more processors operating concurrently. The method reserves the one or more resource elements in the resource array by allowing at least one of the two or more processors to start scanning the one or more resource elements at an index different from an index at which the scan was started by another processor of the two or more processors.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 49% of the total text.

Page 01 of 2

Method for Reserving Resources in a Multiprocessor Computer System

In the existing art, the allocation of resources in a multiprocessor computing system consisting of P concurrently executing processors (CPUs) poses a number of problems. More specifically, in the multiprocessing computing system there exists a number R of discrete instances of resources of a given common type T, wherein each instance is

identified by an integer i in the range i=[0..R-1]. The problem can be solved by building a data structure and algorithm so that the P processors can allocate and release instances of T with small likelihood of serializing with one another. The P processors can also allocate and release instances with small likelihood of memory contention on the data structure that holds the use information pertaining to the R resource instances.

A first solution to the problem is to build an array of R elements and place control

information to represent instance i into an i'th array element. A permission to scan the

data structure to find a free instance is controlled by acquiring a conventional lock. The conventional lock can be at least one of a spin lock and a defer lock, both of which are

well known in the art. To scan the array, a processor p uses a protocol that first acquires the conventional lock and then serially scans the array to find a free instance. The protocol then marks the found free instance as in-use by the processor p and then releases the conventional lock. Thus, the P processors can allocate and release resource instances without colliding, thereby assuring integrity.

A drawback of the first solution is that only one processor p can scan the array at a

time. When there is high contention for resource instances, the rate at which P processors can acquire the lock, scan the data structure, and release the lock can be a limiter on the performance of the system. Thus, the first solution is useful only when P is small and when use of the R resource instances is not frequent.

A second solution to the problem is again to use the array of R elements by enabling

the P processors to manipulate the array without a lock for the array. Instead of using the conventional lock, each array element i is equipped with a small lock of its own that can be manipulated through an interlocked instruction such as Test and Set or Compare and Swap. Such interlocked instructions give each processor p a way to attempt to reserve instance i and then check whether the attempt succeeded. A

processor p looks for a free instance by serially scanning the array elements, typically starting at the first element. When processor p visits array element i, the processor can first simply read array element i's lock field to see whether instance i is in use. If so, processor p simply advances to the next array element. But if the lock field expresses that instance i is not in-use, processor p can attempt an interlocked instruction for acquiring permission to use inst...