System and Method for Reducing Serialization in Transactional Memory Using Gang Release of Blocked Threads

• US 20100138836A1
• Filed: 12/03/2008
• Published: 06/03/2010
• Est. Priority Date: 12/03/2008
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Moir, Mark S., Dice, David
• Granted Patent: US 8,789,057 B2
• Time in Patent Office: Days
• 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 one or more threads is blocked due to the one or more threads waiting to acquire a given lock in a multi-threaded, transactional memory system;

determining a subset of the one or more threads;

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

at least one of the threads in the subset attempting to execute transactionally without acquiring the given lock.

2. The method of claim 1, wherein the subset comprises all of the one or more 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 one or more threads transactionally;

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

or

program instructions to be executed by the one or more threads.

4. The method of claim 1, further comprising:

subsequent to said releasing, introducing an other thread of the one or more 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 one or more threads 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 one or more threads is blocked due to the one or more threads waiting to acquire a given lock in a multi-threaded, transactional memory system;

determining a subset of the one or more threads;

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

at least one of the threads in the subset attempting to execute transactionally without acquiring the given lock.

9. The system of claim 8, wherein the subset comprises all of the one or more 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 one or more threads transactionally;

a historical abort relationship between two or more of the one or more threads or

program instructions to be executed by the one or more 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 one or more 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 one or more threads 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 one or more threads is blocked due to the one or more threads waiting to acquire a given lock in a multi-threaded, transactional memory system;

determining a subset of the one or more threads;

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

at least one of the threads in the subset attempting to execute transactionally without acquiring the given lock.

16. The storage medium of claim 15, wherein the subset comprises all of the one or more 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 one or more threads transactionally;

a historical abort relationship between two or more of the one or more threads or

program instructions to be executed by the one or more 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 one or more 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 one or more threads not included in the subset acquiring the lock.