SCALABLE THREAD LOCKING WITH CUSTOMIZABLE SPINNING

• US 20140189699A1
• Filed: 03/04/2014
• Published: 07/03/2014
• 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.
• Granted Patent: US 8,997,101 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• 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 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 for implementing a method for implementing a customized spin for a selected processing thread based on the thread'"'"'s turn, the computer program product comprising one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by one or more processors of the computing system, cause the computing system to perform the method, 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 selected processing thread; and

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

2. The computer program product of claim 1, further comprising determining that the lock is unavailable.

3. The computer program product of claim 2, wherein one of the plurality of threads increments the selected thread'"'"'s waiting count by two.

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

5. The computer program product of claim 4, 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.

6. The computer program product of claim 4, 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.

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

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

9. The computer program product of claim 8, 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.

10. The computer program product of claim 8, 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.

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

12. 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 a selected processing thread; and

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

13. The computer system claim 12, further comprising determining that the lock is unavailable, wherein one of the plurality of threads increments the selected thread'"'"'s waiting count by two.

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

15. The computer system of claim 14, 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.

16. The computer system of claim 14, 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.

17. At a computer system including at least one processor and system memory, a computer-implemented method for 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 selected processing thread; and

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

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

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

20. The computer-implemented method of claim 19, 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.