Method and apparatus to advise spin and yield decisions

• US 9,223,637 B1
• Filed: 07/31/2007
• Issued: 12/29/2015
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Kessler, Peter B.
• Primary Examiner(s): Patel, Hiren
• Application Number:
  US11/831,292
• Time in Patent Office: 3,073 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/528 by using speculative mechanisms
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

Methods and apparatus provide for a busy resource encoder to allow for a finer control of spin versus yield decisions. Specifically, the busy resource encoder allows for the execution a first thread, where the first thread is using a particular resource. Additionally, the busy resource encoder allows for the execution of a second thread, where the second thread requires use of the resource which is locked due to first thread execution. The busy resource encoder creates a busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread. The second thread can then read the busy code to determine to execute one of a spin and a yield routine by the second thread.

Claims

1. A method, comprising:

executing a first thread, the first thread using a resource;

executing a second thread, the second thread requiring use of the resource which is locked due to first thread execution;

creating a busy code to indicate progress of the execution of the first thread in relation to use of the resource by the first thread, including assigning a value to a variable according to a measure of completeness of the execution of the first thread in relation to use of the resource, wherein, when the resource is locked, the variable includes a yield value or a spin value, the yield value indicating to the second thread to execute a yield routine to cause the second thread to be notified when the resource is available, the spin value specifying, based on the measure of completeness, a number of spin-loop cycles of a spin routine to be executed by the second thread to wait for the resource to be available before attempting to read the busy code again, the spin value providing information from the first thread regarding when the resource is likely to be available;

reading the busy code to determine whether the variable advises to execute the spin routine or the yield routine; and

in response to determining that the variable includes the spin value, executing one of the spin routine or the yield routine by the second thread based on the value of the variable and a maximum spin cycle count defined for the second thread, the maximum spin cycle count specifying a count of spin-loop cycles of the spin routine, such that when the spin value exceeds the maximum spin cycle count, the second thread executes the yield routine despite the value of the variable advising to execute the spin routine.

2. The method as in claim 1, further comprising:

updating the busy code to reflect a current state of progress of the execution of the first thread in relation to use of the resource by the first thread; and

reading the updated busy code.

3. The method as in claim 2, wherein reading the updated busy code include:

determining to execute at least one of the following;

i) the spin routine by at least one of the second thread and another thread;

ii) the yield routine by at least one of the second thread and another thread;

iii) a spin routine currently in progress by the second thread;

or

iv) a yield routine currently in progress by the second thread.

4. The method as in claim 1, wherein creating the busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread includes updating the value of the variable, the variable corresponding to the resource and indicating an availability of the resource with respect to the progress of the executing of the first thread.

5. The method as in claim 4, wherein updating the value of the variable includes:

monitoring execution of the first thread in relation to use of the resource;

as a result of monitoring the execution of the first thread, producing the measure of completeness of the execution of the first thread in relation to use of the resource; and

changing the value of the variable according to the measure of completeness of the execution of the first thread in relation to use of the resource.

6. The method as in claim 5, wherein changing the value of the variable according to the measure of completeness of the execution of the first thread in relation to use of the resource includes assigning the variable a predetermined access value to indicate to the second thread that the progress of the execution of the first thread in relation to use of the resource by the first thread is complete and the resource is unlocked and available to the second thread.

7. The method as in claim 1, further comprising processing the busy code according to a consideration of at least one of a machine state metric, a second thread metric, and a resource metric.

8. The method of claim 1, wherein a lower order bit of the variable of the busy code indicates whether the busy code is an access value specifying a forwarding pointer to the resource in an unlocked state or the spin value specifying the number of spin-loop cycles of the spin routine to be executed by the second thread.

9. The method of claim 1, wherein the number of spin-loop cycles of the spin routine represents a count of spin-loop cycles until the resource will be available.

10. A non-transitory computer readable medium comprising computer executable instructions encoded thereon, the instructions operable on a computerized device to perform processing and comprising instructions for:

executing a first thread, the first thread using a resource;

executing a second thread, the second thread requiring use of the resource which is locked due to first thread execution;

creating a busy code to indicate progress of the execution of the first thread in relation to use of the resource by the first thread, including assigning a value to a variable according to a measure of completeness of the execution of the first thread in relation to use of the resource, wherein, when the resource is locked, the variable includes a yield value or a spin value, the yield value indicating to the second thread to execute a yield routine to cause the second thread to be notified when the resource is available, the spin value specifying, based on the measure of completeness, a number of spin-loop cycles of a spin routine to be executed by the second thread to wait for the resource to be available before attempting to read the busy code again, the spin value providing information from the first thread regarding when the resource is likely to be available;

reading the busy code to determine whether the variable advises to execute the spin routine or the yield routine; and

in response to determining that the variable includes the spin value, executing one of the spin routine or the yield routine by the second thread based on the value of the variable and a maximum spin cycle count defined for the second thread, the maximum spin cycle count specifying a count of spin-loop cycles of the spin routine, such that when the spin value exceeds the maximum spin cycle count, the second thread executes the yield routine despite the value of the variable advising to execute the spin routine.

11. The computer readable medium as in claim 10, the computer executable instructions further comprising instructions for:

updating the busy code to reflect a current state of progress of the execution of the first thread in relation to use of the resource by the first thread; and

reading the updated busy code, which include instructions for determining to execute at least one of the following;

i) the spin routine by at least one of the second thread and another thread;

ii) the yield routine by at least one of the second thread and another thread;

iii) a spin routine currently in progress by the second thread;

or

iv) a yield routine currently in progress by the second thread.

12. The computer readable medium as in claim 10, wherein the instructions for creating the busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread include instructions for updating the value of the variable, the variable corresponding to the resource and indicating an availability of the resource with respect to the progress of the executing of the first thread.

13. The computer readable medium as in claim 12, wherein the instructions for updating the value of the variable include instructions for:

monitoring execution of the first thread in relation to use of the resource;

producing at least one measure of completeness of the execution of the first thread in relation to use of the resource, as a result of monitoring the execution of the first thread; and

changing the value of the variable according to the measure of completeness of the execution of the first thread in relation to use of the resource.

14. The computer readable medium as in claim 13, wherein the instructions for changing the value of the variable according to the measure of completeness of the execution of the first thread in relation to use of the resource include instructions for assigning the variable a predetermined access value to indicate to the second thread that the progress of the execution of the first thread in relation to use of the resource by the first thread is complete and the resource is unlocked and available to the second thread.

15. The computer readable medium as in claim 10, wherein the instructions further include instructions for processing the busy code according to a consideration of at least one of a machine state metric, a second thread metric, and a resource metric.

16. A computer system comprising:

a processor;

a memory unit that stores instructions associated with an application executed by the processor; and

an interconnect coupling the processor and the memory unit, enabling the processor to execute the application and perform operations of;

executing a first thread, the first thread using a resource;

executing a second thread, the second thread requiring use of the resource which is locked due to first thread execution;

creating a busy code to indicate progress of the execution of the first thread in relation to use of the resource by the first thread, including assigning a value to a variable according to a measure of completeness of the execution of the first thread in relation to use of the resource, wherein, when the resource is locked, the variable includes a yield value or a spin value, the yield value indicating to the second thread to execute a yield routine to cause the second thread to be notified when the resource is available, the spin value specifying, based on the measure of completeness, a number of spin-loop cycles of a spin routine to be executed by the second thread to wait for the resource to be available before attempting to read the busy code again, the spin value providing information from the first thread regarding when the resource is likely to be available;

reading the busy code to determine whether the variable advises to execute the spin routine or the yield routine; and

in response to determining that the variable includes the spin value, executing one of the spin routine or the yield routine by the second thread based on the value of the variable and a maximum spin cycle count defined for the second thread, the maximum spin cycle count specifying a count of spin-loop cycles of the spin routine, such that when the spin value exceeds the maximum spin cycle count, the second thread executes the yield routine despite the value of the variable advising to execute the spin routine.

17. The computer system of claim 16, wherein the processor performs the further operations of:

updating the busy code to reflect a current state of progress of the execution of the first thread in relation to use of the resource by the first thread; and

reading the updated busy code.

18. The computer system of claim 17, wherein the operation of reading the updated busy code includes the operation of:

determining to execute at least one of the following;

i) the spin routine by at least one of the second thread and another thread;

ii) the yield routine by at least one of the second thread and another thread;

iii) a spin routine currently in progress by the second thread;

or

iv) a yield routine currently in progress by the second thread.

19. The computer system of claim 17, wherein the operation of creating the busy code to indicate the progress of the execution of the first thread in relation to use of the resource by the first thread includes the operation of updating the value of the variable, the variable corresponding to the resource and indicating an availability of the resource with respect to the progress of the executing of the first thread.

20. The computer system of claim 19, wherein the operation of updating the value of the variable includes the operations of:

monitoring execution of the first thread in relation to use of the resource;

as a result of monitoring the execution of the first thread, producing the measure of completeness of the execution of the first thread in relation to use of the resource; and

changing the value of the variable according to the measure of completeness of the execution of the first thread in relation to use of the resource.