CAM-based wake-and-go snooping engine for waking a thread put to sleep for spinning on a target address lock

• US 8,880,853 B2
• Filed: 02/01/2008
• Issued: 11/04/2014
• 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.
• Primary Examiner(s): Huisman, David J
• Application Number:
  US12/024,327
• Publication Number:
  US 20090199189A1
• Time in Patent Office: 2,468 Days
• Field of Search: 712/220, 711/108, 711/147, 711/150, 711/152, 711/163, 718/100, 718/102, 718/104
• US Class Current: 712/220
• 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 event 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, the method comprising:

detecting, by a wake-and-go engine, that a thread is spinning on a lock associated with a target address, wherein the wake-and-go engine comprises hardware logic associated with a bus and a content addressable memory;

responsive to the wake-and-go engine detecting that the thread is spinning on the lock, storing an entry in the content addressable memory with the target address, a thread identifier associated with the thread, and a lock bit indicating the thread is spinning on the lock associated with the target address;

placing the thread in a sleep state;

snooping, by the wake-and-go engine, the bus;

responsive to the wake-and-go engine detecting a transaction on the bus associated with the target address, accessing, by the wake-and-go engine, the content addressable memory using the target address;

responsive to the wake-and-go engine finding the entry containing the target address in the content addressable memory, determining, by the wake-and-go engine, whether the thread associated with the entry is waiting for a lock-related event based on whether the lock bit is set for the entry in the content addressable memory;

responsive to the wake-and-go engine determining the thread associated with the entry is waiting for a lock-related event, determining, by the wake-and-go engine, whether the transaction causes the lock associated with the target address to be released; and

responsive to the wake-and-go engine determining the transaction causes the lock associated with the target address to be released, placing the thread in a non-sleep state.

2. The method of claim 1, wherein detecting that the thread 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 lock associated with the target address to be available.

3. The method of claim 1, wherein the bus comprises an address bus.

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

5. The method of claim 1, further comprising:

responsive to the wake-and-go engine detecting a subsequent transaction on the bus associated with a given address, accessing, by the wake-and-go engine, the content addressable memory using the given address;

responsive to the wake-and-go engine finding a given entry containing the given address in the content addressable memory, determining, by the wake-and-go engine, whether a thread associated with the given entry is waiting for a lock-related event based on whether the lock bit is set for the given entry in the content addressable memory; and

responsive to the wake-and-go engine determining the thread associated with the given entry is waiting for a non-lock-related event based on determining the lock bit is not set for the given entry, determining, by the wake-and-go engine, whether the subsequent transaction is an event for which a thread identified in the given entry is waiting.

6. The method of claim 5, further comprising:

responsive to the lock bit being set for the given entry, determining, by the wake-and-go engine, whether the subsequent transaction causes a lock associated with the given address to be released.

7. A data processing system, comprising:

a bus;

a wake-and-go engine, wherein the wake-and-go engine comprises hardware logic associated with the bus; and

a content addressable memory associated with the wake-and-go engine,

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

detect that a thread is spinning on a lock associated with a target address;

responsive to detecting that the thread is spinning on the lock, store an entry in the content addressable memory with the target address, a thread identifier associated with the thread, and a lock bit indicating the thread is spinning on the lock associated with the target address;

place the thread in a steep state;

snoop the bus;

responsive to detecting a transaction on the bus associated with the target address, access the content addressable memory using the target address;

responsive to finding the entry containing the target address in the content addressable memory, determine whether the thread associated with the entry is waiting for a lock-related event based on whether the lock bit is set for the entry in the content addressable memory;

responsive to determining the thread associated with the entry is waiting for a lock-related event, determine whether the transaction causes the lock associated with the target address to be released; and

responsive to determining the transaction causes the lock associated with the target address to be released place the thread in a non-sleep state.

8. The data processing system of claim 7, wherein detecting that the thread 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 lock associated with the target address to be available.

9. The data processing system of claim 7, wherein the bus comprises an address bus.

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

11. The data processing system of claim 7, wherein the wake-and-go engine is further configured to:

responsive to detecting a subsequent transaction on the bus associated with a given address, access the content addressable memory using the given address;

responsive to finding a given entry containing the given address in the content addressable memory, determine whether a thread associated with the given entry is waiting for a lock-related event based on whether the lock bit is set for the given entry in the content addressable memory; and

responsive to determining the thread associated with the given entry is waiting for a non-lock-related event based on determining the lock bit is not set for the given entry, determine whether the subsequent transaction is an event for which a thread identified in the given entry is waiting.

12. The data processing system of claim 11, wherein the wake-and-go engine is further configured to:

responsive to determining the lock bit is set for the given entry, determine whether the subsequent transaction causes a lock associated with the given address to released.

13. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored thereon, 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 associated with a target address;

responsive to detecting that the thread is spinning on the lock, store entry in a content addressable memory with the target address, a thread identifier associated with the thread, and a lock bit indicating the thread is spinning on the lock associated with the target address;

place the thread in a sleep state;

snoop a bus;

responsive to detecting a transaction on the bus associated with the target address, access the content addressable memory using the target address;

responsive to finding the entry containing the target address in the content addressable memory, determine whether the thread associated with entry is waiting for a lock-related event based on whether the lock bit is set for in the content addressable memory;

responsive to determining the thread associated with the entry is waiting for a lock-related event, determine whether the transaction causes the lock associated with the target address to released; and

responsive to determining the transaction causes the lock associated with the target address to be released, place the thread in a non-sleep state.

14. The computer program product of claim 13, wherein detecting that the thread is spinning on the lock comprises detecting a programming idiom within an instruction stream of the thread that causes the thread to wait a lock associated with the target address to be available.

15. The computer product of claim 13, wherein the bus comprises an address bus and wherein responsive to a transaction that writes a date value to a given address, the content addressable memory returns a storage address at which the given address is stored within the content addressable memory.

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

responsive to detecting a subsequent transaction on the bus associated with a given address, access the content addressable memory using the given address;

responsive to finding a given entry containing the given address in the content addressable memory, determine whether a thread associated with the given entry is waiting for a lock-related event based on whether the lock bit is set for the given entry in the content addressable memory; and

responsive to determining the thread associated with the given entry is waiting for a non-lock-related event based on determining the lock bit is not set for the given entry, determine whether the subsequent transaction is an event for which a thread identified in the given entry is waiting.

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

responsive to determining the lock bit is set for the given entry, determine whether the subsequent transaction causes a lock associated with the given address to be released.