Granted Patent B2

US 10,430,111 · App. 15/360,934 · Granted Oct 1, 2019

Inventors: Luis F. Stevens (San Jose, CA); Hrishikesh Vivek Prabhune (Columbus, IN); Pallav Agrawal (Edison, NJ); Vincent Schiavone (Berwyn, PA)

Assignee: UDA, LLC

G06F3/0652G06F3/0604G06F3/0608G06F3/0631G06F3/0683G06F16/24568G06F16/9024G06K9/00G06Q50/01

Abstract

Claims (63)

1. A method for accessing a plurality of sequential memory slots of a shared non-circular memory array by multiple processes without using software-based locking techniques, the method comprising:

assigning an index number to each memory slot of the shared memory array by masking portions of the physical address of each memory slot;

allocating a first memory slot and writing, using a producer process, data to the first memory slot, wherein the first memory slot is associated with a producer index number;

reading, using a consumer process, data from a second memory slot, wherein the second memory slot is associated with a consumer index number; and

de-allocating, using a garbage collector process, data from a third memory slot having a second index number, wherein the garbage collector and the third memory slot are associated with a garbage collector index number;

wherein the writing, reading and de-allocating are performed using atomic instructions.

2. The method of claim 1 , further comprising:

in accordance with a determination that a difference between the producer index number and the garbage collector index number does not exceed a maximum queue length threshold, writing, using the producer process, data to a fourth memory slot, wherein the fourth memory slot is subsequent to the first memory slot in the sequential non-circular array; and

in accordance with a determination that a difference between the producer index number and the garbage collector index number exceeds a maximum queue length threshold, refraining from writing, using the producer process, data to the fourth memory slot.

3. The method of claim 1 , further comprising:

in accordance with a determination that the consumer index number does not equal or exceed the producer index number, reading, using the consumer process, data from a fifth memory slot, wherein the fifth memory slot is subsequent to the second memory slot in the sequential non-circular array; and

in accordance with a determination that the consumer index number does equal the producer index number, refraining from reading, using the consumer process, data from the fifth memory slot.

4. The method of claim 1 , further comprising:

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, de-allocating, using the garbage collector process, data from a sixth memory slot, wherein the sixth memory• slot is subsequent to the third memory slot in the sequential non-circular array; and

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, refraining from de-allocating, using the garbage collector process, data from the sixth memory slot.

5. The method of claim 1 wherein the allocating includes:

retrieving a word from a bitmap, wherein the bitmap identifies whether a state record for a queue thread state is allocated;

determining, using a single atomic instruction, whether the word includes a bit that indicates that a memory block is available for allocation;

if the word includes a bit that indicates that a memory block is available for allocation, performing a series of atomic instructions, per bit, to identify the bit that indicates that the memory block is available for allocation by the producer process;

after identifying the bit, allocating the memory block to correspond to the first memory slot in the memory array; and

de-allocating the memory block by identifying the global word position in the bitmap and subsequently identifying a bit position in the identified word that corresponds to the previously-identified memory block.

6. A system for accessing a plurality of sequential memory slots of a shared non-circular memory array, the system including one or more processors and memory storing one or more programs to be executed by the one or more processors, the one or more programs including instructions for:

assigning an index number to each memory slot of the shared memory array by masking portions of the physical address of each memory slot;

allocating a first memory slot and writing, using a producer process, data to the first memory slot, wherein the first memory slot is associated with a producer index number;

reading, using a consumer process, data from a second memory slot, wherein the second memory slot is associated with a consumer index number; and

de-allocating, using a garbage collector process, data from a third memory slot having a second index number, wherein the garbage collector and the third memory slot are associated with a garbage collector index number;

wherein the writing, reading and de-allocating are performed using atomic instructions.

7. The system of claim 6 , the one or more programs further including instructions for:

in accordance with a determination that a difference between the producer index number and the garbage collector index number does not exceed a maximum queue length threshold, writing, using the producer process, data to a fourth memory slot, wherein the fourth memory slot is subsequent to the first memory slot in the sequential non-circular array; and

in accordance with a determination that a difference between the producer index number and the garbage collector index number exceeds a maximum queue length threshold, refraining from writing, using the producer process, data to the fourth memory slot.

8. The system of claim 6 , the one or more programs further including instructions for:

in accordance with a determination that the consumer index number does not equal or exceed the producer index number, reading, using the consumer process, data from a fifth memory slot, wherein the fifth memory slot is subsequent to the second memory slot in the sequential non-circular array; and

in accordance with a determination that the consumer index number does equal the producer index number, refraining from reading, using the consumer process, data from the fifth memory slot.

9. The system of claim 6 , the one or more programs further including instructions for:

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, de-allocating, using the garbage collector process, data from a sixth memory slot, wherein the sixth memory• slot is subsequent to the third memory slot in the sequential non-circular array; and

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, refraining from de-allocating, using the garbage collector process, data from the sixth memory slot.

10. The system of claim 6 wherein the instructions for allocating further include instructions for:

retrieving a word from a bitmap, wherein the bitmap identifies whether a state record for a queue thread state is allocated;

determining, using a single atomic instruction, whether the word includes a bit that indicates that a memory block is available for allocation;

if the word includes a bit that indicates that a memory block is available for allocation, performing a series of atomic instructions, per bit, to identify the bit that indicates that the memory block is available for allocation by the producer process;

after identifying the bit, allocating the memory block to correspond to the first memory slot in the memory array; and

de-allocating the memory block by identifying the global word position in the bitmap and subsequently identifying a bit position in the identified word that corresponds to the previously-identified memory block.

11. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system, the one or more programs including instructions for:

assigning an index number to each memory slot of the shared memory array by masking portions of the physical address of each memory slot;

allocating a first memory slot and writing, using a producer process, data to the first memory slot, wherein the first memory slot is associated with a producer index number;

reading, using a consumer process, data from a second memory slot, wherein the second memory slot is associated with a consumer index number; and

de-allocating, using a garbage collector process, data from a third memory slot having a second index number, wherein the garbage collector and the third memory slot are associated with a garbage collector index number;

wherein the writing, reading and de-allocating are performed using atomic instructions.

12. The non-transitory computer readable storage medium of claim 11 , the one or more programs further including instructions for:

in accordance with a determination that a difference between the producer index number and the garbage collector index number does not exceed a maximum queue length threshold, writing, using the producer process, data to a fourth memory slot, wherein the fourth memory slot is subsequent to the first memory slot in the sequential non-circular array; and

in accordance with a determination that a difference between the producer index number and the garbage collector index number exceeds a maximum queue length threshold, refraining from writing, using the producer process, data to the fourth memory slot.

13. The non-transitory computer readable storage medium of claim 11 , for the one or more programs further including instructions for:

in accordance with a determination that the consumer index number does not equal or exceed the producer index number, reading, using the consumer process, data from a fifth memory slot, wherein the fifth memory slot is subsequent to the second memory slot in the sequential non-circular array; and

in accordance with a determination that the consumer index number does equal the producer index number, refraining from reading, using the consumer process, data from the fifth memory slot.

14. The non-transitory computer readable storage medium of claim 11 , the one or more programs further including instructions for:

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, de-allocating, using the garbage collector process, data from a sixth memory slot, wherein the sixth memory• slot is subsequent to the third memory slot in the sequential non-circular array; and

in accordance with a determination that the garbage collector index number does not meet or exceed the consumer index number, refraining from de-allocating, using the garbage collector process, data from the sixth memory slot.

15. The non-transitory computer readable storage medium of claim 11 wherein the instructions for allocating further include instructions for:

retrieving a word from a bitmap, wherein the bitmap identifies whether a state record for a queue thread state is allocated;

determining, using a single atomic instruction, whether the word includes a bit that indicates that a memory block is available for allocation;

if the word includes a bit that indicates that a memory block is available for allocation, performing a series of atomic instructions, per bit, to identify the bit that indicates that the memory block is available for allocation by the producer process;

after identifying the bit, allocating the memory block to correspond to the first memory slot in the memory array; and

de-allocating the memory block by identifying the global word position in the bitmap and subsequently identifying a bit position in the identified word that corresponds to the previously-identified memory block.

Assignments (1)

Continuity (11)

Cited By (1)

US 12,216,913