System and Method for Implementing Shared Scalable Nonzero Indicators

• US 20090125548A1
• Filed: 11/13/2007
• Published: 05/14/2009
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Moir, Mark S., Lev, Yosef, Luchangco, Victor M., Dice, David
• Granted Patent: US 8,909,601 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A Scalable NonZero Indicator (SNZI) object in a concurrent computing application may include a shared data portion (e.g., a counter portion) and a shared nonzero indicator portion, and/or may be an element in a hierarchy of SNZI objects that filters changes in non-root nodes to a root node. SNZI objects may be accessed by software applications through an API that includes a query operation to return the value of the nonzero indicator, and arrive (increment) and depart (decrement) operations. Modifications of the data portion and/or the indicator portion may be performed using atomic read-modify-write type operations. Some SNZI objects may support a reset operation. A shared data object may be set to an intermediate value, or an announce bit may be set, to indicate that a modification is in progress that affects its corresponding indicator value. Another process or thread seeing this indication may “help” complete the modification before proceeding.

Claims

1. A computer-implemented method, comprising:

writing a value to a shared data object;

determining whether said writing changed a summary value associated with the shared data object; and

in response to determining that said writing changed the summary value associated with the shared data object, modifying a value of a shared indicator object to reflect the changed summary value.

2. The method of claim 1, wherein the shared data object comprises a plurality of Boolean values, the summary value represents a logical OR of the plurality of Boolean values, and the shared indicator comprises a Boolean value indicating whether the summary value is true.

3. The method of claim 1, wherein the summary value comprises a value of zero if the value of the shared data object is zero and nonzero if the value of the shared data object is nonzero;

wherein said determining comprises determining whether the summary value changed from zero to nonzero or from nonzero to zero; and

wherein the shared indicator object comprises a Boolean nonzero indicator object that indicates whether the summary value is zero or nonzero.

4. The method of claim 3, wherein, in response to determining that said writing changed the summary value from zero to nonzero, said modifying comprises incrementing the value of the shared indicator object.

5. The method of claim 3, wherein, in response to determining that said writing changed the summary value from nonzero to zero, said modifying comprises decrementing the value of the shared indicator object.

6. The method of claim 1, wherein the shared data object comprises a shared counter and wherein the shared indicator object comprises a second shared counter.

7. The method of claim 6, further comprising:

determining whether said modifying the second shared counter changed a summary value associated with the second shared counter; and

in response to determining that said modifying the second shared counter changed the summary value associated with the second shared counter, modifying a value of a second shared indicator object to reflect the changed summary value associated with the second shared counter.

8. The method of claim 1, further comprising:

writing another value to the shared data object;

determining whether said writing another value changed the summary value associated with the shared data object; and

in response to determining that said writing another value did not change the summary value associated with the shared data object, preserving a current value of the shared indicator object.

9. The method of claim 1, wherein the shared data object comprises a reference counter or ownership record corresponding to a shared resource, the method further comprising releasing the shared resource in response to determining that the shared indicator object indicates that the summary value is zero or false.

10. The method of claim 1, wherein at least one of said writing and said modifying are performed using an atomic read-modify-write type operation.

11. The method of claim 1, further comprising reading the value of the shared indicator object to determine the summary value, wherein said writing and said reading are performed by different threads executing on one or more processors.

12. The method of claim 1, wherein said writing a value to a shared data object comprises writing an intermediate value to the shared data object, the method further comprising, in response to determining that the value of the shared data object is equal to the intermediate value, initiating writing another value to the shared data object, wherein said writing a value and said writing another value are performed by different threads executing on one or more processors.

13. The method of claim 1, wherein said writing a value to a shared data object comprises:

initiating modification of the value of the shared data object on behalf of a first thread;

setting an announce indicator on behalf of the first thread;

on behalf of a second thread, determining whether the announce indicator is set; and

in response to determining that the announce indicator is set, initiating another modification of the value of the shared data object on behalf of the first thread; and

initiating modification of the value of the shared data object on behalf of the second thread.

14. A system comprising:

one or more processors; and

a memory coupled to the one or more processors;

wherein the memory comprises;

a shared data object accessible by a plurality of threads executing on the one or more processors; and

a shared indicator object accessible by the plurality of threads;

wherein the memory further comprises program instructions executable by the one or more processors to implement;

one of the plurality of threads writing a value to the shared data object;

determining whether said writing changed a summary value associated with the shared data object; and

in response to determining that said writing changed the summary value associated with the shared data object, modifying a value of a shared indicator object to reflect the changed summary value.

15. The system of claim 14, wherein the shared data object comprises a plurality of Boolean values, the summary value represents a logical OR of the plurality of Boolean values, and the shared indicator comprises a Boolean value indicating whether the summary value is true.

16. The system of claim 14,

wherein the summary value comprises a value of zero if the value of the shared data object is zero and nonzero if the value of the shared data object is nonzero, and wherein said determining comprises determining whether the summary value changed from zero to nonzero or from nonzero value to zero;

wherein the program instructions are further configured to implement;

in response to determining that said writing changed the summary value from zero to nonzero, said modifying comprises incrementing the value of the shared indicator object; and

in response to determining that said writing changed the summary value from nonzero to zero, said modifying comprises decrementing the value of the shared indicator object.

17. The system of claim 14, wherein the shared indicator object comprises a Boolean nonzero indicator object that indicates whether the summary value is zero or nonzero.

18. The system of claim 14, wherein the shared object comprises an identifier of a current epoch, wherein the program instructions are further executable by the one or more processors to implement:

prior to said writing, determining if an epoch specified by said one of the plurality of threads during said writing is equal to the current epoch, wherein said writing is performed in response to the epoch specified during said writing being equal to the current epoch;

returning without performing said writing in response to determining that the epoch specified during said writing is not equal to the current epoch; and

in response to one of the plurality of threads invoking a reset operation, setting the current epoch identifier to a new epoch value.

19. A computer-readable storage medium comprising program instructions computer-executable to implement:

one of a plurality of threads executing on one or more processors writing a value to a shared data object;

determining whether said writing changed a summary value associated with the shared data object;

in response to determining that said writing changed the summary value from zero to nonzero, setting the value of a shared Boolean indicator object to true; and

in response to determining that said writing changed the summary value from nonzero to zero, setting the value of the shared Boolean indicator object to false.

20. The storage medium of claim 19, wherein the program instructions are further computer-executable to implement:

an application programming interface comprising a query operation configured to return the value of the shared Boolean indicator object; and

one of the plurality of threads executing the query operation to determine the value of the shared Boolean indicator object.