Multi-lane concurrent bag for facilitating inter-thread communication

• US 8,689,237 B2
• Filed: 09/22/2011
• Issued: 04/01/2014
• Est. Priority Date: 09/22/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Dice, David, Otenko, Oleksandr
• Primary Examiner(s): Anya, Charles E
• Assistant Examiner(s): SEYE, ABDOU K
• Application Number:
  US13/241,015
• Publication Number:
  US 20130081061A1
• Time in Patent Office: 922 Days
• Field of Search: None
• US Class Current: 719/314
• CPC Class Codes: G06F 13/22 using successive scanning, e.g. polling G06F13/24 takes precedence
• CPC Class Codes: G06F 2205/067 Bidirectional FIFO, i.e. system allowing data transfer in two directions
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 2213/2806 Space or buffer allocation for DMA transfers
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A method, system, and medium are disclosed for facilitating communication between multiple concurrent threads of execution using a multi-lane concurrent bag. The bag comprises a plurality of independently-accessible concurrent intermediaries (lanes) that are each configured to store data elements. The bag provides an insert function executable to insert a given data element into the bag by selecting one of the intermediaries and inserting the data element into the selected intermediary. The bag also provides a consume function executable to consume a data element from the bag by choosing one of the intermediaries and consuming (removing and returning) a data element stored in the chosen intermediary. The bag guarantees that execution of the consume function consumes a data element if the bag is non-empty and permits multiple threads to execute the insert or consume functions concurrently.

Claims

1. A non-transient, computer-readable storage medium storing program instruction executable by a processor to implement:

a concurrent multi-lane bag data structure comprising;

a plurality of independently-accessible concurrent intermediaries configured to store data elements;

an insert function executable to insert a given data element into the bag by selecting a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary selected by an execution of the insert function, and inserting the data element into the selected intermediary; and

a consume function executable to consume a data element from the bag by choosing a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary chosen by an execution of the consume function, and removing and returning the data element from the chosen intermediary;

wherein;

the bag guarantees that an execution of the consume function consumes a data element if the bag is non-empty; and

the bag enables multiple threads to execute the insert function or the consume function concurrently.

2. The medium of claim 1, wherein:

the insert function is configured such that successive executions select successive intermediaries in a predefined order; and

the consume function is configured such that successive executions choose successive intermediaries in the same predefined order.

3. The medium of claim 2, wherein the ordering is defined by respective positions of the intermediaries within an array.

4. The medium of claim 2, wherein the ordering is defined by respective positions of the intermediaries within a linked list.

5. The medium of claim 1, wherein one or more of the intermediaries is a concurrent blocking queue or a concurrent blocking bag.

6. The medium of claim 1, wherein the consume function is further executable to invoke a consume function of the chosen intermediary, wherein the consume function of the chosen intermediary is configured to block the executing thread if the intermediary stores no data element.

7. The medium of claim 1, wherein the program instructions are further executable to implement multi-thread communication comprising:

multiple producer threads configured to concurrently insert data elements into the bag; and

multiple consumer threads configured to concurrently consume the data elements from the bag.

8. The medium of claim 1, wherein the program instructions are further executable to use the bag to implement a resource pool or a semaphore.

9. A method, comprising:

providing, by a computer system, a multi-lane concurrent bag to a plurality of threads, wherein the bag comprises;

a plurality of independently-accessible concurrent intermediaries configured to store data elements;

an insert function executable to insert a given data element into the bag by selecting a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary selected by an execution of the insert function, and inserting the data element into the selected intermediary;

and a consume function executable to consume a data element from the bag by choosing a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary chosen by an execution of the consume function, and removing and returning the data element from the chosen intermediary;

wherein;

the bag guarantees that an execution of the consume function consumes a data element if the bag is non-empty; and

the bag enables multiple threads to execute the insert function or the consume function concurrently; and

executing, by the computer system, the plurality of concurrent threads, wherein the executing comprises;

the threads communicating with one another using the bag by inserting data elements into the bag by executing the insert function and consuming those data elements from the bag by executing the consume function.

10. The method of claim 9, wherein:

the insert function is configured such that successive executions select successive intermediaries in a predefined order; and

the consume function is configured such that successive executions choose successive intermediaries in the same predefined order.

11. The method of claim 10, wherein the ordering is defined by respective positions of the intermediaries within an array or within a linked list.

12. The method of claim 9, wherein one or more of the intermediaries is a concurrent blocking queue or a concurrent blocking bag.

13. The method of claim 9, wherein executing the consume function, by at least one of the threads, comprises:

determining that the chosen intermediary stores no data elements; and

in response, blocking the thread executing the consume function until a data element is inserted into the chosen intermediary.

14. The medium of claim 9, wherein the threads communicate via the bag to implement a resource pool or a semaphore.

15. A system, comprising:

a processor;

a memory coupled to the processor and storing program instructions executable by the processor to implement a concurrent multi-lane bag data structure comprising;

a plurality of independently-accessible concurrent intermediaries configured to store data elements;

an insert function executable to insert a given data element into the bag by selecting a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary selected by an execution of the insert function, and inserting the data element into the selected intermediary, wherein the insert function is configured such that successive executions select successive intermediaries in a predefined order; and

a consume function executable to consume a data element from the bag by choosing a successive one of the intermediaries, at least in part, by atomically reading and modifying an indication of the most recent intermediary chosen by an execution of the consume function, and removing and returning the data element from the chosen intermediary, wherein the consume function is configured such that successive executions choose successive intermediaries in the predefined order;

wherein;

the bag guarantees that an execution of the consume function consumes a data element if the bag is non-empty; and

the bag enables multiple threads to execute the insert function or the consume function concurrently.

16. The system of claim 15, wherein the ordering is defined by respective positions of the intermediaries within an array or within a linked list.

17. The system of claim 15, wherein one or more of the intermediaries is a concurrent blocking queue or a concurrent blocking bag.

18. The system of claim 15, wherein the consume function is further executable to invoke a consume function of the chosen intermediary, wherein the consume function of the chosen intermediary is configured to block the executing thread if the intermediary stores no data element.