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

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.

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.

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.