Parallel Lock Spinning Using Wake-and-Go Mechanism

• US 20090199189A1
• Filed: 02/01/2008
• Published: 08/06/2009
• Est. Priority Date: 02/01/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Ravi K., Sharma, Satya P., Swanberg, Randal C.
• Granted Patent: US 8,880,853 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A wake-and-go mechanism is provided for a data processing system. The wake-and-go mechanism recognizes a programming idiom that indicates that a thread is spinning on a lock. The wake-and-go mechanism updates a wake-and-go array with a target address associated with the lock and sets a lock bit in the wake-and-go array. The thread then goes to sleep until the lock frees. The wake-and-go array may be a content addressable memory (CAM). When a transaction appears on the symmetric multiprocessing (SMP) fabric that modifies the value at a target address in the CAM, the CAM returns a list of storage addresses at which the target address is stored. The wake-and-go mechanism associates these storage addresses with the threads waiting for an even at the target addresses, and may wake the thread that is spinning on the lock.

Claims

1. A method, in a data processing system, for performing a wake-and-go operation in response to detecting a thread spinning on a lock, the method comprising:

detecting that a thread is spinning on a lock at a target address;

responsive to detecting the thread spinning on the lock, populating a wake-and-go storage array with the target address and placing the thread in a sleep state; and

responsive to an event associated with the target address, placing the thread in a non-sleep state.

2. The method of claim 1, wherein detecting a thread that is spinning on a lock comprises detecting a programming idiom within an instruction stream of the thread that causes the thread to wait for a data value to be written to a target address.

3. The method of claim 2, wherein the wake-and-go storage array is a content addressable memory and an address appearing on an address bus is used to address the content addressable memory.

4. The method of claim 3, wherein responsive to an event that writes the data value to the target address, the content addressable memory returns a storage address at which the target address is stored within the content addressable memory.

5. The method of claim 1, further comprising:

setting a lock bit in the wake-and-go storage array, wherein the lock bit indicates that the thread is spinning on a lock at the target address.

6. The method of claim 5, further comprising:

responsive to an event that modifies a given address, determining whether the given address is stored in the wake-and-go storage array;

responsive to the given address being stored in the wake-and-go storage array, determining whether the lock bit is set for the given address; and

responsive to the lock bit being set for the given address, placing a thread corresponding to the given address in a non-sleep state.

7. The method of claim 6, further comprising:

responsive to the lock bit not being set for the given address, determining whether to wake the thread corresponding to the given address.

8. A data processing system, comprising:

a wake-and-go mechanism; and

a wake-and-go storage array,

wherein the wake-and-go mechanism is configured to;

detect that a thread is spinning on a lock at a target address;

responsive to detecting the thread spinning on the lock, populate the wake-and-go storage array with the target address and place the thread in a sleep state; and

responsive to an event associated with the target address, placing the thread in a non-sleep state.

9. The data processing system of claim 8, wherein detecting a thread that is spinning on a lock comprises detecting a programming idiom within an instruction stream of the thread that causes the thread to wait for a data value to be written to a target address.

10. The data processing system of claim 9, wherein the wake-and-go storage array is a content addressable memory and an address appearing on an address bus is used to address the content addressable memory.

11. The data processing system of claim 10, wherein responsive to an event that writes the data value to the target address, the content addressable memory returns a storage address at which the target address is stored within the content addressable memory.

12. The data processing system of claim 9, wherein the wake-and-go mechanism is further configured to a lock bit in the wake-and-go storage array, wherein the lock bit indicates that the thread is spinning on a lock at the target address.

13. The data processing system of claim 12, wherein the wake-and-go mechanism is configured to:

responsive to an event that modifies a given address, determine whether the given address is stored in the wake-and-go storage array;

responsive to the given address being stored in the wake-and-go storage array, determine whether the lock bit is set for the given address; and

responsive to the lock bit being set for the given address, place a thread corresponding to the given address in a non-sleep state.

14. The data processing system of claim 13, wherein the wake-and-go mechanism is configured to:

responsive to the lock bit not being set for the given address, determine whether to wake the thread corresponding to the given address.

15. A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program, when executed on a computing device, causes the computing device to:

detect that a thread is spinning on a lock at a target address;

responsive to detecting the thread spinning on the lock, populate a wake-and-go storage array with the target address and place the thread in a sleep state; and

responsive to an event associated with the target address, place the thread in a non-sleep state.

16. The computer program product of claim 15, wherein detecting a thread that is spinning on a lock comprises detecting a programming idiom within an instruction stream of the thread that causes the thread to wait for a data value to be written to a target address.

17. The computer program product of claim 15, wherein the wake-and-go storage array is a content addressable memory and wherein responsive to an event that writes the data value to the target address, the content addressable memory returns a storage address at which the target address is stored within the content addressable memory.

18. The computer program product of claim 15, wherein the computer readable program further causes the computing device to:

set a lock bit in the wake-and-go storage array, wherein the lock bit indicates that the thread is spinning on a lock at the target address.

19. The computer program product of claim 18, wherein the computer readable program further causes the computing device to:

responsive to an event that modifies a given address, determine whether the given address is stored in the wake-and-go storage array;

responsive to the given address being stored in the wake-and-go storage array, determine whether the lock bit is set for the given address; and

responsive to the lock bit being set for the given address, place a thread corresponding to the given address in a non-sleep state.

20. The computer program product of claim 19, wherein the computer readable program further causes the computing device to:

responsive to the lock bit not being set for the given address, determine whether to wake the thread corresponding to the given address.