System and method for reducing serialization in transactional memory using gang release of blocked threads

• US 8,789,057 B2
• Filed: 12/03/2008
• Issued: 07/22/2014
• Est. Priority Date: 12/03/2008
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Dice, David, Moir, Mark S.
• Primary Examiner(s): LI, AIMEE J
• Application Number:
  US12/327,659
• Publication Number:
  US 20100138836A1
• Time in Patent Office: 2,057 Days
• Field of Search: 718/102, 718/104, 718/107, 718/101, 711/150, 711/152
• US Class Current: 718/101
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

Transactional Lock Elision (TLE) may allow multiple threads to concurrently execute critical sections as speculative transactions. Transactions may abort due to various reasons. To avoid starvation, transactions may revert to execution using mutual exclusion when transactional execution fails. Because threads may revert to mutual exclusion in response to the mutual exclusion of other threads, a positive feedback loop may form in times of high congestion, causing a “lemming effect”. To regain the benefits of concurrent transactional execution, the system may allow one or more threads awaiting a given lock to be released from the wait queue and instead attempt transactional execution. A gang release may allow a subset of waiting threads to be released simultaneously. The subset may be chosen dependent on the number of waiting threads, historical abort relationships between threads, analysis of transactions of each thread, sensitivity of each thread to abort, and/or other thread-local or global criteria.

Claims

1. A computer-implemented method, comprising:

detecting that execution of a plurality of threads is blocked due to the plurality of threads waiting to acquire a given lock in a multi-threaded, transactional memory system, wherein each of the plurality of threads includes a respective section that is dependent on the given lock;

in response to said detecting;

determining a subset of the plurality of threads for which to attempt execution of their respective sections as speculative transactions, wherein the subset comprises two or more of the plurality of threads; and

releasing the subset of threads from a waiting pool associated with the given lock; and

subsequent to said releasing, attempting to execute the respective section of at least one of the threads in the subset transactionally without acquiring the given lock.

2. The method of claim 1, wherein the subset comprises all of the plurality of threads.

3. The method of claim 1, wherein said determining a subset is dependent, at least in part, on one or more of:

a number of threads waiting on the given lock;

a number of previous unsuccessful attempts to execute one of the plurality of threads transactionally;

a historical abort relationship between two or more of the plurality of threads;

or

program instructions to be executed by the plurality of threads.

4. The method of claim 1, further comprising:

subsequent to said releasing, introducing an other thread of the plurality of threads into the subset; and

the other thread attempting to execute transactionally without acquiring the given lock.

5. The method of claim 4, wherein said introducing is performed in response to one or more threads in the subset completing an attempt to execute transactionally.

6. The method of claim 1, further comprising:

subsequent to said releasing, one of the plurality of threads that is not included in the subset acquiring the lock.

7. The method of claim 6, wherein said acquiring is performed in response to one or more threads in the subset completing an attempt to execute transactionally.

8. A system comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions executable by one or more processors to implement;

detecting that execution of a plurality of threads is blocked due to the plurality of threads waiting to acquire a given lock in a multi-threaded, transactional memory system, wherein each of the plurality of threads includes a respective section that is dependent on the given lock;

in response to said detecting;

determining a subset of the plurality of threads for which to attempt execution of their respective sections as speculative transactions, wherein the subset comprises two or more of the plurality of threads; and

releasing the subset of threads from a waiting pool associated with the given lock; and

subsequent to said releasing, attempting to execute the respective section of at least one of the threads in the subset transactionally without acquiring the given lock.

9. The system of claim 8, wherein the subset comprises all of the plurality of threads.

10. The system of claim 8, wherein said determining a subset is dependent, at least in part, on one or more of:

a number of threads waiting on the given lock;

a number of previous unsuccessful attempts to execute one of the plurality of threads transactionally;

a historical abort relationship between two or more of the plurality of threads or program instructions to be executed by the plurality of threads.

11. The system of claim 8, wherein the program instructions are further executable to implement:

subsequent to said releasing, introducing an other thread of the plurality of threads into the subset; and

the other thread attempting to execute transactionally without acquiring the given lock.

12. The system of claim 11, wherein said introducing is performed in response to one or more threads in the subset completing an attempt to execute transactionally.

13. The system of claim 8, wherein the program instructions are further executable to implement:

subsequent to said releasing, one of the plurality of threads that is not included in the subset acquiring the lock.

14. The system of claim 13, wherein said acquiring is performed in response to one or more threads in the subset completing an attempt to execute transactionally.

15. A computer readable storage medium storing program instructions computer-executable to implement:

detecting that execution of a plurality of threads is blocked due to the plurality of threads waiting to acquire a given lock in a multi-threaded, transactional memory system, wherein each of the plurality of threads includes a respective section that is dependent on the given lock;

in response to said detecting;

determining a subset of the plurality of threads for which to attempt execution of their respective sections as speculative transactions, wherein the subset comprises two or more of the plurality of threads; and

releasing the subset of threads from a waiting pool associated with the given lock; and

subsequent to said releasing, attempting to execute the respective section of at least one of the threads in the subset transactionally without acquiring the given lock.

16. The storage medium of claim 15, wherein the subset comprises all of the plurality of threads.

17. The storage medium of claim 15, wherein said determining a subset is dependent, at least in part, on one or more of:

a number of threads waiting on the given lock;

a number of previous unsuccessful attempts to execute one of the plurality of threads transactionally;

a historical abort relationship between two or more of the plurality of threads or program instructions to be executed by the plurality of threads.

18. The storage medium of claim 15, wherein the program instructions are further executable to implement:

subsequent to said releasing, introducing an other thread of the plurality of threads into the subset; and

the other thread attempting to execute transactionally without acquiring the given lock.

19. The storage medium of claim 18, wherein said introducing is performed in response to one or more threads in the subset completing an attempt to execute transactionally.

20. The storage medium of claim 15, wherein the program instructions are further executable to implement:

subsequent to said releasing, one of the plurality of threads that is not included in the subset acquiring the lock.