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

• US 8,046,758 B2
• Filed: 09/04/2009
• Issued: 10/25/2011
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Dice, David
• Primary Examiner(s): An; Meng
• Assistant Examiner(s): Arcos; Caroline H
• Application Number:
  US12/554,116
• Publication Number:
  US 20090328053A1
• Time in Patent Office: 781 Days
• Field of Search: None
• US Class Current: 718/100
• 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:

for each set of multiple sets of N successive attempts by a first thread acquire ownership of the shared resource;

for each of a predetermined number of the N attempts of the set, executing 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) successfully obtaining ownership of the shared resource, or (ii) reaching a predetermined execution time limit; and

for a remainder of the N attempts of the set, determining whether the shared resource is owned by the another thread, and if so then executing a blocking procedure which temporarily suspends execution of the first thread;

periodically adjusting the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully; and

measuring the duration of a context switching operation within the computing environment, and wherein the predetermined execution time limit is made substantially equal to the measured duration of the context switching operation.

2. A computer-implemented method according to claim 1, wherein (i) the value of N is decreased if it is greater than a minimum permissible value and the most recent execution of the spin procedure has terminated successfully, and (ii) the value of N increased if it is less than a maximum permissible value and the most recent execution of the spin procedure has not terminated successfully.

3. A computer-implemented method according to claim 1, wherein the predetermined number of attempts in which the spin procedure is executed for each set is one.

4. 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 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.

5. 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.

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 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.

7. 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.

8. 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:

(1) for each set of multiple sets of N successive attempts by a first thread to acquire ownership of the shared resource;

for each of a predetermined number of the N attempts of the set, less than N, execute a spin procedure during which the first thread repeatedly determines whether the shared resource is owned by the another thread, the spin procedure terminating upon the earlier of (i) successfully obtaining ownership of the shared resource, and (ii) reaching a predetermined execution time limit; and

for a non-zero remainder of the N attempts of the set, determine whether the shared resource is owned by another thread, and if so then executing a blocking procedure which temporarily suspends execution of the first thread; and

(2) periodically adjust the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully.

9. A computer program product according to claim 8, wherein the predetermined number of attempts in which the spin procedure is executed for each set is one.

10. A computer program product according to claim 8, wherein, when the instructions are carried out by the computerized system, the computerized system is further caused to:

prior to the execution of the spin procedure, determine 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, execute the blocking procedure instead of the spin procedure.

19. A computer program product according to claim 8, wherein (i) the value of N is decreased if it is greater than a minimum permissible value and the most recent execution of the spin procedure has terminated successfully, and (ii) the value of N increased if it is less than a maximum permissible value and the most recent execution of the spin procedure has not terminated successfully.

11. 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;

(1) for each set of multiple sets of N successive attempts by a first thread to acquire ownership of the shared resource;

for each of a predetermined number of the N attempts of the set less than N, executing 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) successfully obtaining ownership of the shared resource, and (ii) reaching a predetermined execution time limit; and

for the non-zero remainder of a N attempts of the set, determining whether the shared resource is owned by the another thread, and if so then executing a blocking procedure which temporarily suspends execution of the first thread; and

(2) periodically adjusting the value of N based on the extent to which least one recent execution of the spin procedure has terminated successfully.

12. The computerized system according to claim 11, wherein (i) the value of N is decreased if it is greater than a minimum permissible value and the most recent execution of the spin procedure has terminated successfully, and (ii) the value of N increased if it is less than a maximum permissible value and the most recent execution of the spin procedure has not terminated successfully.

13. The computerized system according to claim 11, wherein the predetermined number of attempts in which the spin procedure is executed for each set is one.

14. The computerized system according to claim 11, 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.

15. 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 executing a spin procedure for each of a predetermined number M of N attempts to acquire 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) successfully obtaining ownership of the shared resource, and (ii) reaching a predetermined execution time limit;

means, executed by the processor, for determining, for a non-zero remainder of the N-M attempts, whether the shared resource is owned by the another thread, and if so then executing a blocking procedure which temporarily suspends execution of the first thread;

means, executed by the processor, for repeating the execution of the spin procedure and the blocking procedure for subsequent sets of N attempts to acquire ownership of the shared resource; and

means, executed by the processor, for periodically adjusting the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully.

16. The computerized system according to claim 15, wherein (i) the value of N is decreased if it is greater than a minimum permissible value and the most recent execution of the spin procedure has terminated successfully, and (ii) the value of N increased if it is less than a maximum permissible value and the most recent execution of the spin procedure has not terminated successfully.

17. The computerized system according to claim 15, wherein the predetermined number of attempts in which the spin procedure is executed for each set is one.

18. The computerized system according to claim 15, 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.