# US 8,789,057 B2 · System and method for reducing serialization in transactional memory using gang release of blocked threads > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,789,057 B2 - Document ID: US8789057B2 - Status: Granted - Kind: B2 - Application number: 12/327,659 - Filed: 2008-12-03 - Published: 2010-06-03 - Granted: 2014-07-22 - Earliest claimed: 2008-12-03 - Assignees: Oracle America, Inc. - Applicants: David Dice; Mark S. Moir - Inventors: David Dice; Mark S. Moir - Web page: https://patentgrep.com/patent/US8789057B2 ## CPC - G06F 9/466: {Transaction processing} - G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores - G06F 9/528: {by using speculative mechanisms} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the subset comprises all of the plurality of threads. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 6) 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. ### Claim 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. ### Claim 9 (depends on 8) The system of claim 8, wherein the subset comprises all of the plurality of threads. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 8) 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 8) 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. ### Claim 14 (depends on 13) 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. ### Claim 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. ### Claim 16 (depends on 15) The storage medium of claim 15, wherein the subset comprises all of the plurality of threads. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 15) 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.