SYSTEMS AND METHODS FOR S-LIST PARTITIONING

• US 20130290667A1
• Filed: 04/27/2012
• Published: 10/31/2013
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dixit, Amol Dilip, Waters, Bradley Michael
• Granted Patent: US 9,652,289 B2
• Time in Patent Office: Days
• US Class Current: 711/173
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Systems and techniques of the management of the allocation of a plurality of memory elements stored within a plurality of lockless list structures are presented. These lockless list structures (such as Slists) may be made accessible within an operating system environment of a multicore processor—and may be partitioned within the system. Memory elements may also be partitioned among these lockless list structures. When a core processor (or other processing element) makes a request for allocating a memory element to itself, the system and/or method may search among the lockless list structures for an available memory element. When a suitable and/or available memory element is found, the system may allocate the available memory element to requesting core processor. Dynamically balancing of memory elements may occur according to a suitable balancing metric, such as maintain substantial numerical equality of memory elements or avoid over-allocation of resources.

Claims

1. A method for managing the allocation of a plurality of memory elements stored within one or more lockless list structures, said lockless list structures accessible within an operating system environment of a multicore processor, the steps of said method comprising:

partitioning said one or more lockless list structures;

initially partitioning said plurality of memory elements among said one or more lockless list structures;

upon a request for allocating a memory element to a core processor, searching said one or more lockless list structures for an available memory element;

upon finding said available memory element, allocating said available memory element to said core processor; and

dynamically balancing said memory elements among said one or more said lockless list structures according to a suitable balancing metric.

2. The method of claim 1 wherein said memory elements comprise one of a group, said group comprising fixed size buffers and variable size buffers.

3. The method of claim 2 wherein said lockless list structure comprises Slist structures.

4. The method of claim 3 wherein the step of partitioning said one or more lockless list structures further comprises partitioning said one or more lockless list structures into a first data structure.

5. The method of claim 4 wherein said first data structure is one of a group, said group comprising:

a hash structure and a dynamic list swapping data structure.

6. The method of claim 5 wherein said hash structure is keyed according to the multicore processor architecture.

7. The method of claim 6 wherein said hash structure is keyed according to processor index.

8. The method of claim 6 wherein said hash structure is keyed according to NUMA node number.

9. The method of claim 5 wherein said dynamic list swapping data structures further comprises a pop lockless list structure and a push lockless list structure, wherein said step of partitioning said one or more lockless list structure further comprises swapping pointers between said pop lockless list structures and said push lockless list structure, according to a metric to balance memory resources.

10. The method of claim 1 wherein said suitable balancing metric is to maintain substantially numerical equality of memory elements among the lockless list structures.

11. The method of claim 1 wherein said suitable balancing metric is to avoid over-allocation of memory resources.

12. A system for managing the allocation of a plurality of memory elements stored within one or more lockless list structures, said lockless list structures accessible within an operating system environment of a multicore processor, said system comprising:

a plurality of core processors, said core processors partitioned into a set of processor sockets;

a set of shared memory, said shared memory being accessible with at least one of said processor sockets;

communications pathways between at least two said processor sockets;

a set of one or more lockless list structures, each said lockless list structure capable of storing at least one memory element, said set of one or more lockless list structures capable of being partitioned to allow allocation of said memory elements to said core processors upon a request for memory element allocations;

an allocation module, said allocation module capable of receiving requests for memory element allocations from said plurality of core processors; and

wherein said allocation module is capable of dynamically adjusting memory elements between said set of one or more lockless list structure according to a suitable balancing metric.

13. The system of claim 12 wherein said allocation module is capable of executing on one of said core processors.

14. The system of claim 12 wherein said suitable balancing metric is one of a group, said group comprising:

maintain substantially numerical equality of memory elements among the lockless list structures and avoid over-allocation of memory resources.

15. The system of claim 12 wherein said at least one memory element comprises a fixed size buffer.

16. The system of claim 12 wherein said at least one memory element comprises a variable size buffer.

17. A computer readable storage medium that is not a transient signal, said computer readable storage medium having computer-executable instructions stored thereon that, when executed by a processor, cause said processor to execute:

a method for managing the allocation of a plurality of memory elements stored within one or more lockless list structures, said lockless list structures accessible within an operating system environment of a multicore processor, the steps of said method comprising the step of;

partitioning said one or more lockless list structures;

initially partitioning said plurality of memory elements among said one or more lockless list structures;

upon a request for allocating a memory element to a core processor, searching said one or more lockless list structures for an available memory element;

upon finding said available memory element, allocating said available memory element to said core processor; and

18. The computer readable storage medium of claim 17 wherein said memory elements comprise one of a group, said group comprising:

fixed size buffers and variable sized buffers; and

wherein said lockless list structure comprises Slist structures.

19. The computer readable storage medium of claim 18 wherein the step of partitioning said one or more lockless list structures further comprises partitioning said one or more lockless list structures into a first data structure.

20. The computer readable storage medium of claim 19 wherein said first data structure is one of a group, said group comprising:

a hash structure and a dynamic list swapping data structure.