Lock-free scalable free list

Patent metadata

Field	Value
Publication number	US-9892031-B2
Application number	US-201113290912-A
Country	US
Kind code	B2
Filing date	Nov 7, 2011
Priority date	Nov 7, 2011
Publication date	Feb 13, 2018
Grant date	Feb 13, 2018

Abstract

A plurality of free list data structures are maintained in a multi-processor computing system that each correspond to one processor of the multi-processor computing system and that each comprise an ordered queue of processor-specific items. Thereafter, a number of processor-specific items allocated to each free list data structure is calculated. Processor-specific items allocated to a first of the free list data structures are moved to a second of the free list data structures when the number of calculated processor-specific items in the first free data structure exceeds a first threshold. In addition, processor-specific items allocated to the second of the free list data structures are moved to the first of the free list data structures when the number of calculated processor-specific items in the first free data structure is below a second threshold. Related apparatus, systems, techniques and articles are also described.

First claim

What is claimed is:

1. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
maintaining, in a multi-processor computing system, a plurality of free list data structures implemented in a dynamic memory, each free list data structure being striped by, and corresponding to, a different processor of the multi-processor computing system, each free list data structure comprising an ordered queue of processor-specific items assigned to a corresponding processor of the multi-processor computing system, wherein each processor has a primary free list data structure and a secondary free list data structure;
calculating a number of processor-specific items allocated to each free list data structure;
moving processor-specific items allocated to a first of the free list data structures to a second of the free list data structures, when the number of calculated processor-specific items in the first free data structure exceeds a first threshold; and
moving processor-specific items allocated to the second of the free list data structures to the first of the free list data structures, when the number of calculated processor-specific items in the first free data structure is below a second threshold;
the first and second thresholds being determined based on a number of items in each free list data structure;
maintaining a global free list data structure;
wherein
upon determination that a first item is present in the first primary free list data structure, then the first item is allocated;
upon determination that the first item is not present in the first primary free list data structure and the first secondary free list data structure includes at least two processor-specific items, at least a portion of the processor-specific items in a corresponding first secondary free list data structure are moved to the first primary free list data structure, wherein at least one item from the global list data structure queue of items is moved to the first primary free list data structure when the first secondary free list data structure includes a number of processor-specific items below the first threshold, wherein at least one item in the global list data structure is selectively allocated to all of the primary free list data structures to effect load-balancing; and
upon determination, for a second of the free list data structure pairs, that a corresponding second primary free list data structure includes a number of processor-specific items exceeding the second threshold, at least one of the processor-specific items in the second primary free list data structure having the number of processor-specific items exceeding the first threshold is moved to a corresponding second secondary free list data structure, wherein a new item is pushed into the second primary free list data structure, wherein at least a portion of processor-specific items in the second secondary free list data structure is moved to the global free list data structure.

2. A computer program product as in claim 1 , wherein the operations further comprise:
moving to the global free list processor-specific items allocated to the first of the free list data structures, when the number of calculated processor-specific items in the first free data structure exceeds half of the first threshold; and
moving to the global free list processor-specific items allocated to the second of the free list data structures, when the number of calculated processor-specific items in the second free data structure exceeds half of the second threshold.

3. A computer program product as in claim 1 , wherein the items in the free list data structures represent free blocks in memory allocation algorithms.

4. A computer program product as in claim 1 , wherein the items in the free list data structures comprise arbitrary objects.

5. A computer program product as in claim 1 , wherein each free list data structure comprises a last-in-first-out (LIFO) queue.

6. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
maintaining, in a multi-processor computing system, a plurality of free list data structures implemented in a dynamic memory, each free list data structure corresponding to a different processor of the multi-processor computing system, each free list data structure comprising an ordered queue of processor-specific items assigned to a corresponding processor of the multi-processor computing system, wherein each processor has a primary free list data structure and a secondary free list data structure;
calculating a number of processor-specific items allocated to each free list data structure;
moving processor-specific items allocated to the free list data structures to a global free list queue when a number of processor-specific items within a corresponding free list data structure exceeds a first threshold; and
re-assigning items in the global free list queue to free list data structures having a number of processor-specific items below a second threshold;
the first and second thresholds being determined based on a number of items in each free list data structure;
wherein
upon determination that a first item is present in the first primary free list data structure, then the first item is allocated;
upon determination that the first item is not present in the first primary free list data structure and the first secondary free list data structure includes at least two processor-specific items, at least a portion of the processor-specific items in a corresponding first secondary free list data structure are moved to the first primary free list data structure, wherein at least one item from a global list data structure queue of items is moved to the first primary free list data structure when the first secondary free list data structure includes a number of processor-specific items below the first threshold, wherein at least one item in the global list data structure is selectively allocated to all of the primary free list data structures to effect load-balancing; and
upon determination, for a second of the free list data structure pairs, that a corresponding second primary free list data structure includes a number of processor-specific items exceeding the second threshold, at least one of the processor-specific items in the second primary free list data structure having the number of processor-specific items exceeding the first threshold is moved to a corresponding second secondary free list data structure, wherein a new item is pushed into the second primary free list data structure, wherein at least a portion of processor-specific items in the second secondary free list data structure is moved to the global free list data structure.

7. A computer program product as in claim 6 , wherein the items in the free list data structures represent (i) free blocks in memory allocation algorithms, (ii) free internal state objects of job worker queues, and/or (iii) free I/O control blocks of an I/O subsystems.

8. A computer program product as in claim 6 , wherein the items in the free list data structures comprise arbitrary objects.

9. A computer program product as in claim 6 , wherein each free list data structure comprises a last-in-first-out (LIFO) queue.

10. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
maintaining, in a multi-processor computing system

Assignees

• Schreter Ivan
• Booss Daniel
• Sap Se

Inventors

• Schreter Ivan
• Booss Daniel

Classifications

• G06F12/023 Primary

  Free address space management · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F12/0284

  Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163) · CPC title

• G06F9/5016

  the resource being the memory · CPC title