ADAPTIVE SPIN-THEN-BLOCK MUTUAL EXCLUSION IN MULTI-THREADED PROCESSING
First Claim
1. A computer-implemented method of acquiring ownership of a shared resource in a multi-threaded computing environment, comprising:
- (1) 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, and (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; and
(2) periodically adjusting the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. A computer-implemented method of acquiring ownership of a shared resource in a multi-threaded computing environment, comprising:
-
(1) 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, and (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; and
(2) periodically adjusting the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 18, 19, 20)
-
-
9. 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, 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 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. - View Dependent Claims (10, 11, 12)
-
-
13. 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 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 remainder of the N 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. - View Dependent Claims (14, 15, 16)
-
-
17. 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, 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 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 periodically adjust the value of N based on the extent to which at least one recent execution of the spin procedure has terminated successfully.
-
Specification