Scalable thread locking with customizable spinning

• US 8,997,101 B2
• Filed: 03/04/2014
• Issued: 03/31/2015
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Omara, Emad A., Duffy, John J.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, SISLEY NAHYUN
• Application Number:
  US14/196,398
• Publication Number:
  US 20140189699A1
• Time in Patent Office: 392 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Embodiments described herein are directed to dynamically controlling the number of spins for a selected processing thread among a plurality of processing threads. A computer system tracks both the number of waiting processing threads and each thread'"'"'s turn, wherein a selected thread'"'"'s turn comprises the total number of waiting processing threads after the selected thread'"'"'s arrival at the processor. Next, the computer system determines, based on the selected thread'"'"'s turn, the number of spins that are to occur before the selected thread checks for an available thread lock. The computer system also, based on the selected thread'"'"'s turn, changes the number of spins, such that the number of spins for the selected thread is a function of the number of waiting processing threads and processors in the computer system.

Claims

1. A computer program product comprising the following:

one or more computer-readable hardware storage devices having stored thereon computer-executable instructions that, when executed by one or more processors of the computing system, cause the computing system to perform a methodfor implementing a customized spin for a selected processing thread based on the thread'"'"'s turn, the method comprising;

an act of initializing a single integer variable configured to keep track of the following;

the status of a lock bit indicating whether a lock has been acquired or not, a number of waiting threads, and the status of a thread tracking flag;

an act of checking the lock bit to determine whether the lock is available for a the selected processing thread;

upon determining that the lock is available, an act of assigning the lock to the selected processing thread; and

upon determining that the lock is unavailable, an act of one of said number of waiting threads incrementing the selected thread'"'"'s waiting count by two.

2. The computer program product of claim 1, further comprising an act of calculating the selected thread'"'"'s turn, wherein the turn is calculated by dividing the updated waiting count by two.

3. The computer program product of claim 2, wherein upon determining that the updated waiting count divided by two is less than the number of processors, an act of spinning the selected processing thread based on the selected thread'"'"'s turn.

4. The computer program product of claim 2, wherein upon determining that the updated waiting count divided by two is more than the number of processors, an act of foregoing any spinning and directing the selected thread to begin yielding.

5. The computer program product of claim 3, wherein the selected processing thread spins until a predefined number of spinning iterations have been completed.

6. The computer program product of claim 5, wherein, upon finishing the predefined number of spinning iterations without acquiring the lock, the selected processing thread begins yielding.

7. The computer program product of claim 6, wherein the yielding comprises a first phase that includes placing the selected processing thread at the end of a scheduling queue for a current processor and placing another, higher priority thread at the top of the scheduling queue for the current processor.

8. The computer program product of claim 6, wherein the yielding comprises a second phase that includes placing the selected processing thread at the end of a scheduling queue for each of the processors in the computer system and placing another, higher priority thread at the top of the scheduling queue for the processors of the computer system.

9. The computer program product of claim 8, wherein the yielding comprises a third phase that includes putting the selected processing thread in a sleep state for a variable, customizable amount of time.

10. A computer system comprising the following:

one or more processors;

system memory;

one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform a method for implementing a customized spin for a selected processing thread based on the thread'"'"'s turn, the method comprising the following;

an act of initializing a single integer variable configured to keep track of the following;

the status of a lock bit indicating whether a lock has been acquired or not, a number of waiting threads, and the status of a thread tracking flag;

an act of checking the lock bit to determine whether the lock is available for the selected processing thread;

upon determining that the lock is available, an act of assigning the lock to the selected processing thread; and

upon determining that the lock is unavailable, an act of one of said number of waiting threads incrementing the selected thread'"'"'s waiting count by at least two.

11. The computer system claim 10, wherein the selected thread'"'"'s waiting count is incremented by three.

12. The computer system of claim 11, further comprising an act of calculating the selected thread'"'"'s turn, wherein the turn is calculated by dividing the updated waiting count by two.

13. The computer system of claim 12, wherein upon determining that the updated waiting count divided by two is less than the number of processors, an act of spinning the selected processing thread based on the selected thread'"'"'s turn.

14. The computer system of claim 12, wherein upon determining that the updated waiting count divided by two is more than the number of processors, an act of foregoing any spinning and directing the selected thread to begin yielding.

15. A method comprising the following:

implementing a customized spin for a selected processing thread based on the thread'"'"'s turn at a computer system including at least one processor and system memory, wherein implementing the customized spin is performed by;

an act of initializing a single integer variable configured to keep track of the following;

the status of a lock bit indicating whether a lock has been acquired or not, a number of waiting threads, and the status of a thread tracking flag;

an act of checking the lock bit to determine whether the lock is available for the selected processing thread;

upon determining that the lock is available, an act of assigning the lock to the selected processing thread; and

upon determining that the lock is unavailable, an act of one of said number of waiting threads incrementing the selected thread'"'"'s waiting count by at least two.

16. The computer-implemented method of claim 15, wherein the selected processing thread spins until a predefined number of spinning iterations have been completed.

17. The computer-implemented method of claim 16, wherein, upon finishing the predefined number of spinning iterations without acquiring the lock, the selected processing thread begins yielding.

18. The computer-implemented method of claim 17, wherein the yielding comprises a first phase that includes placing the selected processing thread at the end of a scheduling queue for a current processor and placing another, higher priority thread at the top of the scheduling queue for the current processor, and wherein the yielding comprises a second phase that includes placing the selected processing thread at the end of a scheduling queue for each of the processors in the computer system and placing another, higher priority thread at the top of the scheduling queue for the processors of the computer system.

19. The computer-implemented method of claim 15, wherein the selected thread'"'"'s waiting count is incremented by three.

20. The computer-implemented method of claim 19, wherein the computer system comprises a number of processors, and wherein the method further comprises determining if the incremented waiting count divided by two is more than the number of processors in the computer system, the selected thread yields directly and does not spin.