Scalable method for producer and consumer elimination

• US 20060123156A1
• Filed: 01/04/2006
• Published: 06/08/2006
• Est. Priority Date: 01/11/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Nussbaum, Daniel S., Moir, Mark S., Shavit, Nir N., Shalev, Ori
• Granted Patent: US 7,779,165 B2
• Time in Patent Office: Days
• US Class Current: 710/33
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Producers and consumer processes may synchronize and transfer data using a shared data structure. After locating a potential transfer location that indicates an EMPTY status, a producer may store data to be transferred in the transfer location. A producer may use a compare-and-swap (CAS) operation to store the transfer data to the transfer location. A consumer may subsequently read the transfer data from the transfer location and store, such as by using a CAS operation, a DONE status indicator in the transfer location. The producer may notice the DONE indication and may then set the status location back to EMPTY to indicate that the location is available for future transfers, by the same or a different producer. The producer may also monitor the transfer location and time out if no consumer has picked up the transfer data.

Claims

1. A computer-implemented method, comprising:

a producer process atomically storing a data value to a transfer location;

the producer process setting a status indicator for the transfer location to indicate a non-empty status;

wherein the producer process atomically stores the data value to the transfer location and sets the status indicator for the transfer location as a single atomic operation; and

the producer process setting the status indicator for the transfer location to indicate an empty status in response to a consumer process setting the status indicator to indicate a done status.

2. The method of claim 1, further comprising:

a consumer process reading the stored data value from the transfer location in response to the producer process setting the status indicator for the transfer location to indicate a non-empty status; and

the consumer process atomically setting the status indicator for the transfer location to indicate a done status.

3. The method of claim 1, further comprising a consumer process setting the status indicator for the transfer location to indicate a waiting status, wherein said atomically storing a data value to the transfer location is in response to said setting the status indicator for the transfer location to indicate a waiting status.

4. The method of claim 3, further comprising the producer process setting a privacy indication for the transfer location to indicate that the data value is intended only for the consumer process that set the status indicator to a waiting status.

5. The method of claim 1, further comprising the producer process setting the status indicator for the transfer location to indicate an empty status in response to determining that no consumer process has set the status indicator to indicate a done status within a predetermined amount of time.

6. The method of claim 1, wherein the status indicator and the data value are stored at a single location in the transfer location and wherein said atomically storing a data value to the transfer location comprises said setting the status indicator to indicate a non-empty status.

7. The method of claim 1, wherein said atomically storing a data value to the transfer location comprises storing a pointer referencing a portion of shared memory storing the data value, wherein the portion of share memory is accessible to both the producer process and the consumer process.

8. The method of claim 7, wherein said setting the status indicator for the transfer location to indicate a done status comprises storing a pointer in the transfer location, wherein the pointer references a portion of shared memory indicating to a done status indication.

9. The method of claim 1, wherein the single atomic operation comprises an atomic compare-and-swap operation.

10. The method of claim 1, further comprising the producer process selecting the transfer location randomly from among a plurality of potential transfer locations.

11. A system, comprising:

a processor; and

a memory, wherein the memory comprising program instruction executable by the processor to implement;

a consumer process; and

a producer process, wherein the producer process is configured to;

atomically store a data value to a transfer location;

set a status indicator for the transfer location to indicate a non-empty status;

wherein the producer process is configured to atomically store the data value to the transfer location and to set the status indicator for the transfer location as a single atomic operation; and

set the status indicator for the transfer location to indicate an empty status in response to the consumer process setting the status indicator to indicate a done status.

12. The system of claim 11 where the consumer process is configured to:

read the stored data value from the transfer location in response to the producer process setting the status indicator for the transfer location to indicate a non-empty status; and

atomically set the status indicator for the transfer location to indicate a done status.

13. The system of claim 11, where the consumer process is configured to set the status indicator for the transfer location to indicate a waiting status, wherein the processor is configured to perform said atomically storing a data value to the transfer location in response to the consumer process setting the status indicator for the transfer location to indicate a waiting status.

14. The system of claim 13, wherein the producer process is further configured to set a privacy indication for the transfer location to indicate that the data value is intended only for the consumer process.

15. The system of claim 11, wherein the producer process is configured to set the status indicator for the transfer location to indicate an empty status in response to determining that the consumer process has not set the status indicator to indicate a done status within a predetermined amount of time.

16. The system of claim 11, wherein the status indicator and the data value are stored at a single location in the transfer location and wherein said atomically storing a data value to the transfer location comprises said setting the status indicator to indicate a non-empty status.

17. The system of claim 11, wherein in atomically storing a data value to the transfer location, the producer process is configured to store a pointer referencing a portion of shared memory storing the data value, wherein the reference portion of shared memory is accessible to both the producer process and the consumer process.

18. The system of claim 11, wherein the single atomic operation comprises an atomic compare-and-swap operation.

19. The system of claim 11, wherein the producer process is further configured to select the transfer location randomly from among a plurality of potential transfer locations.

20. A computer accessible medium, comprising program instructions computer executable to implement:

a producer process atomically storing a data value to a transfer location;

the producer process setting a status indicator for the transfer location to indicate a non-empty status;

wherein the producer process atomically stores the data value to the transfer location and sets the status indicator for the transfer location as a single atomic operation; and

the producer process setting the status indicator for the transfer location to indicate an empty status in response to a consumer process setting the status indicator to indicate a done status.