Adaptive spin-then-block mutual exclusion in multi-threaded processing

• US 7,594,234 B1
• Filed: 06/04/2004
• Issued: 09/22/2009
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Dice, David
• Primary Examiner(s): Nguyen; Van H
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/861,729
• Time in Patent Office: 1,936 Days
• Field of Search: 718/1, 718/100, 718/102, 718/103, 718/104, 718/108, 711/130, 711/145, 711/163, 712/228, 712/229
• US Class Current: 718/108
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Adaptive modifications of spinning and blocking behavior in spin-then-block mutual exclusion include limiting spinning time to no more than the duration of a context switch. Also, the frequency of spinning versus blocking is limited to a desired amount based on the success rate of recent spin attempts. As an alternative, spinning is bypassed if spinning is unlikely to be successful because the owner is not progressing toward releasing the shared resource, as might occur if the owner is blocked or spinning itself. In another aspect, the duration of spinning is generally limited, but longer spinning is permitted if no other threads are ready to utilize the processor. In another aspect, if the owner of a shared resource is ready to be executed, a thread attempting to acquire ownership performs a “directed yield” of the remainder of its processing quantum to the other thread, and execution of the acquiring thread is suspended.

Claims

1. A computer-implemented method of acquiring ownership of a shared resource in a multi-threaded computing environment, comprising:

measuring the duration of a context switching operation within the computing environment, including in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation;

executing a spin procedure as part of an attempt by a first thread to acquire ownership of the shared resource, the spin procedure terminating upon the earlier of (i) successfully obtaining ownership of the shared resource, and (ii) reaching predetermined execution time limit equal to the measured duration of a context switching operation; and

if the spin procedure terminates by reaching the predetermined execution time limit, then executing a blocking procedure which temporarily suspends execution of the first thread.

2. A computer-implemented method according to claim 1, wherein measuring the duration of the context switching operation comprises calculating an average duration of a plurality of context switching operations.

3. A computer-implemented method according to claim 1, further comprising:

in connection with the execution of the spin procedure, determining whether the respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limiting the duration of the spin procedure to the predetermined execution time limit before executing the blocking procedure;

and if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed, then permitting the spin procedure to execute beyond the predetermined execution time limit.

4. A computer-implemented method according to claim 1, further comprising:

prior to the execution of the spin procedure, determining whether a successor flag is set to a non-null value, the non-null value of the successor flag indicating that at least one other thread waiting to acquire ownership of the shared resource is ready for execution, and if the successor flag is set to the non-null value, then executing the blocking procedure instead of the spin procedure.

5. A computer-implemented method according to claim 1, wherein multiple threads of the multi-threaded computing environment have respective priorities, and further comprising adjusting the predetermined execution time limit on a per-thread basis such that higher-priority threads have a longer execution time limit than lower-priority threads.

6. A computer-implemented method according to claim 1, wherein multiple threads of the multi-threaded computing environment have respective priorities, and further comprising adjusting respective periods of delay in respective spin loops of the threads, each period of delay starting when a respective thread observes a transition of the ownership of the shared resource and ending when the respective thread executes a test-and-set instruction in an attempt to acquire ownership of the shared resource, the periods of delay being adjusted such that lower-priority threads have delay periods greater than the delay periods of higher-priority threads.

7. A computer-implemented method by which a first thread acquires ownership of a shared resource currently owned by another thread in a multi-threaded computing environment, comprising:

determining, as part of an attempt by the first thread to acquire ownership of the shared resource, whether an execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource;

if the execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource, then executing a blocking procedure which temporarily suspends execution of the first thread;

if the execution status of the another thread does not indicate that the another thread is not progressing toward releasing its ownership of the shared resource, then executing a spin procedure during which the first thread repeatedly determines whether the shared resource is still owned by the another thread, the spin procedure terminating upon the earlier of (i) determining that the shared resource is not owned by another thread, and (ii) reaching a predetermined execution time limit; and

measuring the duration of a context switching operation within the computing environment, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation.

8. A computer-implemented method according to claim 7, wherein determining whether the execution status of the other thread indicates that the other thread is not progressing toward releasing its ownership of the shared resource comprises determining whether the other thread is blocked.

9. A computer-implemented method according to claim 7, wherein determining whether the execution status of the other thread indicates that the other thread is not progressing toward releasing its ownership of the shared resource comprises determining whether the other thread is spinning.

10. A computer-implemented method according to claim 7, further comprising:

in connection with the execution of the spin procedure, determining whether respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limiting the duration of the spin procedure to the predetermined execution time limit before executing the blocking procedure; and

if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed, then permitting the spin procedure to execute beyond the predetermined execution time limit.

11. A computer-implemented method by which a first thread acquires ownership of a shared resource currently owned by another thread in a multi-threaded computing environment, comprising:

in connection with the execution of a spin procedure by which the first thread attempts to acquire ownership of the shared resource, determining whether respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limiting the duration of the spin procedure to a predetermined execution time limit before executing a blocking procedure which temporarily suspends execution of the first thread; and

if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed, then permitting the spin procedure to execute beyond the predetermined execution time limit; and

measuring a duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, and wherein the predetermined execution time limit is made equal to the measured duration of a context switching operation.

12. A computer-implemented method by which a first preemptible thread acquires ownership of a shared resource currently owned by another preemptible thread in a multi-threaded computing environment, comprising:

in connection with the execution of a spin-then-block procedure by which the first preemptible thread attempts to acquire ownership of the shared resource, determining whether an execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed;

if the execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed, then (i) yielding the remainder of a processing quantum for the first thread to the another preemptible thread, and (ii) suspending execution of the first preemptible thread; and

if the execution status of the another preemptible thread indicates that the another preemptible thread is not ready to be executed, then continuing the execution of the spin-then-block procedure by the first preemptible thread; and

measuring a duration of a context switching operation within the computing environment, including,

in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, and wherein the spin-then-block procedure has a spinning portion employing a predetermined execution time limit equal to the measured duration of the context switching operation.

13. A computer-implemented method according to claim 12, further comprising:

in connection with the execution of a spinning portion of the spin-then-block procedure, determining whether respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limiting the duration of the spin portion to the predetermined execution time limit before executing a blocking portion which temporarily suspends execution of the first thread; and

if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed, then permitting the spin portion to execute beyond the predetermined execution time limit.

14. A computerized system, comprising:

a shared resource; and

control circuitry including a set of one or more processors operative to execute a mutual exclusion mechanism, the mutual exclusion mechanism including a computer-implemented method of acquiring ownership of the shared resource, the method including;

measuring a duration of a context switching operation within the computing environment, including, in a first measuring thread marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation;

executing a spin procedure as part of an attempt by a first thread to acquire ownership of the shared resource, the spin procedure terminating upon the earlier of (i) successfully obtaining ownership of the shared resource, and (ii) reaching a predetermined execution time limit equal to the measured duration of a context switching operation; and

if the spin procedure terminates by reaching the predetermined execution time limit, then executing a blocking procedure which temporarily suspends execution of the first thread.

15. A computerized system, comprising:

a shared resource; and

control circuitry including a set of one or more processors operative to execute a mutual exclusion mechanism in a multi-threaded computing environment, the mutual exclusion mechanism including a computer implemented method by which a first thread acquires ownership of the shared resource,

the shared resource being currently owned by another thread, the method including;

determining, as part of an attempt by the first thread to acquire ownership of the shared resource, whether an execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource;

if the execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource, then executing a blocking procedure which temporarily suspends execution of the first thread;

if the execution status of the another thread does not indicate that the another thread is not progressing toward releasing, its ownership of the shared resource, then executing a spin procedure during which the first thread repeatedly determines whether the shared resource is still owned by the another thread, the spin procedure terminating upon the earlier of (i) determining that the shared resource is not owned by another thread, and (ii) reaching a predetermined execution time limit; and

measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation.

16. A computerized system, comprising:

a shared resource; and

control circuitry including a set of one or more processors operative to execute a mutual exclusion mechanism in a multi-threaded computing environment, the mutual exclusion mechanism including a computer-implemented method by which a first thread acquires ownership of the shared resource, the shared resource being currently owned by another thread, the method including;

in connection with the execution of a spin procedure by which the first thread attempts to acquire ownership of the shared resource, determining whether respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limiting the duration of the spin procedure to a predetermined execution time limit before executing a blocking procedure which temporarily suspends execution of the first thread; and

if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed, then permitting the spin procedure to execute beyond the predetermined execution time limit; and

measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation.

17. A computerized system, comprising:

a shared resource; and

control circuitry including a set of one or more processors operative to execute a mutual exclusion mechanism in a multi-threaded computing environment, the mutual exclusion mechanism including a computer-implemented method by which a first preemptible thread acquires ownership of the shared resource, the shared resource being currently owned by another preemptible thread, the method including;

in connection with the execution of a spin-then-block procedure by which the first preemptible thread attempts to acquire ownership of the shared resource, determining whether an execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed;

if the execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed, then (i) yielding the remainder of a processing quantum for the first preemptible thread to the another preemptible thread, and (ii) suspending execution of the first preemptible thread;

if the execution status of the another preemptible thread indicates that the another preemptible thread is not ready to be executed, then continuing the execution of the spin-then-block procedure by the first preemptible thread; and

measuring a duration of a context switching operation within the computing environment, including

in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, and wherein the spin-then-block procedure has a spinning portion employing a predetermined execution time limit equal to the measured duration of the context switching operation.

18. A computerized system including at least a central processor running a multi-threaded computing environment in which a first thread acquires ownership of a shared resource from another thread, comprising:

means, executed by the processor, for measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation;

means, executed by the processor, for executing a spin procedure as part of an attempt by the first thread to acquire ownership of the shared resource, the spin procedure terminating upon the earlier of (i) successfully obtaining ownership of the shared resource, and (ii) reaching predetermined execution time limit equal to the measured duration of the context switching operation; and

means for executing a blocking procedure if the spin procedure terminates by reaching the predetermined execution time limit, the blocking procedure temporarily suspending execution of the first thread.

19. A computerized system including at least a central processor running a multi-threaded computing environment in which a first thread acquires ownership of a shared resource from another thread, comprising:

means, executed by the processor, for determining, as part of an attempt by the first thread to acquire ownership of the shared resource, whether an execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource;

means, executed by the processor, for executing a blocking procedure if the execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource, the blocking procedure temporarily suspending execution of the first thread;

means, executed by the processor, for executing a spin procedure if the execution status of the another thread does not indicate that the another thread is not progressing toward releasing its ownership of the shared resource, the spin procedure repeatedly determining whether the shared resource is owned by another thread, the spin procedure terminating upon the earlier of (i) determining that the shared resource is not owned by another thread, and (ii) reaching a predetermined execution time limit; and

means, executed by the processor, for measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation.

20. A computerized system including at least a central processor running a multi-threaded computing environment in which a first thread acquires ownership of a shared resource from another thread, comprising:

means, executed by the processor, for determining, in connection with the execution of a spin procedure by which the first thread attempts to acquire ownership of the shared resource, whether respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

means, executed by the processor, for then limiting the duration of the spin procedure if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, the duration of the spin procedure being limited to a predetermined execution time limit before executing a blocking procedure which temporarily suspends execution of the first thread; and

means for permitting the spin procedure to execute beyond the predetermined execution time limit if the respective execution statuses of the other threads indicate that none of the other threads is ready to be executed;

means, executed by the processor, for measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation.

21. A computerized system including at least a central processor running a multi-threaded computing environment in which a first preemptible thread acquires ownership of a shared resource from another preemptible thread, comprising:

means, executed by the processor, for determining, in connection with the execution of a spin-then-block procedure by which the first preemptible thread attempts to acquire ownership of the shared resource, whether an execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed;

means, executed by the processor, operative if the execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed, for (i) yielding the remainder of a processing quantum for the first preemptible thread to the another preemptible thread, and (ii) suspending execution of the first preemptible thread;

means, executed by the processor, for continuing the execution of the spin-then-block procedure by the first preemptible thread if the execution status of the another preemptible thread indicates that the another preemptible thread is not ready to be executed; and

means, executed by the processor for measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation.

22. A computer program product that includes a computer readable storage medium having instructions stored thereon for accessing a shared resource of a computerized system, such that the instructions, when carried out by the computerized system, cause the computerized system to:

measure the duration of a context switching operation within the computing environment, including, in a first measuring thread, marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation;

execute a spin procedure as part of an attempt by a first thread to acquire ownership of the shared resource, the spin procedure terminating upon the earlier of (i) successfully obtaining ownership of the shared resource, and (ii) reaching a predetermined execution time limit equal to the measured duration of the context switching operation; and

if the spin procedure terminates by reaching the predetermined execution time limit, then execute a blocking procedure which temporarily suspends execution of the first thread.

23. A computer program product that includes a computer readable storage medium having instructions stored thereon for accessing a shared resource of a computerized system, such that the instructions, when carried out by the computerized system, cause the computerized system to:

determine, as part of an attempt by the first thread to acquire ownership of the shared resource, whether an execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource;

if the execution status of the another thread indicates that the another thread is not progressing toward releasing its ownership of the shared resource, then execute a blocking procedure which temporarily suspends execution of the first thread;

if the execution status of the another thread does not indicate that the another thread is not progressing toward releasing its ownership of the shared resource, then execute a spin procedure during which the first thread repeatedly determines whether the shared resource is owned by another thread, the spin procedure terminating upon the earlier of (i) determining that the shared resource is not owned by another thread, and (ii) reaching a predetermined execution time limit; and

measuring the duration of a context switching operation within the computing environment, including, in a first measuring thread marking an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generating a request to wake up the first measuring thread; and

in the first measuring thread, marking a finish time at which it is awakened by the request of the second thread, and calculating one-half the difference of the finish and initial times to determine the duration of the context switching operation, wherein the predetermined execution time limit is made equal to the measured duration of the context switching operation.

24. A computer program product that includes a computer readable storage medium having instructions stored thereon for accessing a shared resource of a computerized system, such that the instructions, when carried out by the computerized system, cause the computerized system to:

in connection with the execution of a spin procedure by which the first thread attempts to acquire ownership of the shared resource, determine whether the respective execution statuses of other threads indicate that any of the other threads is ready to be executed;

if the respective execution statuses of the other threads indicate that any of the other threads is ready to be executed, then limit the duration of the spin procedure to a predetermined execution time limit before executing a blocking procedure which temporarily suspends execution of the first thread; and

if the respective execution statuses of the other threads indicate that none o of the other threads is ready to be executed, then permit the spin procedure to execute beyond the predetermined execution time limit; and

measure a duration of a context switching operation within the computing environment, including,

in a first measuring thread, mark an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generate a request to wake up the first measuring thread; and

in the first measuring thread, mark a finish time at which it is awakened by the request of the second thread, and calculate one-half the difference of the finish and initial times to determine the duration of the context switching operation, and wherein the spin-then-block procedure has a spinning portion employing a predetermined execution time limit equal to the measured duration of the context switching operation.

25. A computer program product that includes a computer readable storage medium having instructions stored thereon for accessing a shared resource of a computerized system, such that the instructions, when carried out by the computerized system, cause the computerized system to:

in connection with the execution of a spin-then-block procedure by which the first thread attempts to acquire ownership of the shared resource, determine whether an execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed;

if the execution status of the another preemptible thread indicates that the another preemptible thread is ready to be executed, then (i) yield the remainder of a processing quantum for the first preemptible thread to the another preemptible thread, and (ii) suspend execution of the first preemptible thread; and

if the execution status of the another preemptible thread indicates that the another preemptible thread is not ready to be executed, then continue the execution of the spin-then-block procedure by the first preemptible thread; and

measure a duration of a context switching operation within the computing environment, including,

in a first measuring thread, mark an initial time at which a request is generated to wake up a second measuring thread, the first measuring thread entering a sleeping state after the wake-up request is generated;

in the second measuring thread upon being awakened, generate a request to wake up the first measuring thread; and

in the first measuring thread, mark a finish time at which it is awakened by the request of the second thread, and calculate one-half the difference of the finish and initial times to determine the duration of the context switching operation, and wherein the spin-then-block procedure has a spinning portion employing a predetermined execution time limit equal to the measured duration of the context switching operation.