Method and system for speeding up mutual exclusion

Abstract

In a multiprocessor computer system, a lock operation is maintained with a thread using non-atomic instructions. Identifiers are assigned to each thread. Flags in conjunction with the thread identifiers are used to determine the continuity of the lock with a thread. However, in the event continuity of the lock with the thread ceases, a compare-and-swap operation is executed to reset the lock with the same thread or another thread. Similarly, in the event there has been a collision between two or more threads requesting the lock, a compare-and-swap operation is executed to assign the lock to one of the requesting threads. Accordingly, prolonged ownership of a lock operation by a thread is encouraged to mitigate use of atomic operations in granting of the lock to a non-owning thread.

1 . A method for managing a multithreaded computer system comprising: 
 determining through a non-atomic operation if ownership of a lock by a first thread has been discontinued; and    assigning ownership of said lock to a thread executing a compare-and-swap operation in response to a determination that said ownership of said lock by said first thread has been discontinued.    
     
     
         2 . The method of  claim 1 , wherein the step of determining discontinuity of a lock operation includes comparison of thread identifiers of said first thread with a thread identifier of a second thread.  
     
     
         3 . The method of  claim 2 , further comprising setting a first flag in response to a positive comparison of said thread identifiers.  
     
     
         4 . The method of  claim 3 , further comprising setting a second flag in response to confirmation of continuity of said lock operation by said first thread.  
     
     
         5 . The method of  claim 1 , further comprising detecting collision of execution of said lock operation by two or more threads in response to a determination of discontinuity of a lock operation by said first thread.  
     
     
         6 . The method of  claim 5 , further comprising resetting lock ownership with a compare-and-swap operation in response to said collision.  
     
     
         7 . A computer system comprising: 
 a lock manager adapted to determine through a non-atomic operation if ownership of a lock by a first thread has been discontinued;    said manager adapted to assign ownership of said lock to a thread executing a compare-and-swap operation in response to a determination by said manager of discontinuation of ownership of said lock by said first thread.    
     
     
         8 . The system of  claim 7 , further comprising a thread manager adapted to compare a thread identifier of said first thread with a thread identifier of a second thread.  
     
     
         9 . The system of  claim 8 , further comprising a first flag adapted to be set in response to a positive comparison by said thread manager.  
     
     
         10 . The system of  claim 9 , further comprising a second flag adapted to be set in response to confirmation of continuity of said lock ownership by said first thread.  
     
     
         11 . The system of  claim 7 , further comprising a thread manager adapted to detect collision of execution of a lock operation by two or more threads in response to a determination of discontinuity of a lock operation by said first thread.  
     
     
         12 . The system of  claim 11 , further comprising a compare-and-swap operation adapted to reset lock ownership to a requesting thread in response to detection of a collision by said thread manager.  
     
     
         13 . An article comprising: 
 a computer-readable signal-bearing medium;    means in the medium for determining through a non-atomic operation if ownership of a lock by a first thread has been discontinued; and    means in the medium for assigning ownership of said lock to a thread executing a compare-and-swap operation in response to a determination that said ownership of said lock by said first thread has been discontinued.    
     
     
         14 . The article of  claim 13 , wherein said medium is selected from a group consisting of: a recordable data storage medium, and a modulated carrier signal.  
     
     
         15 . The article of  claim 13 , wherein the means for determining discontinuity of a lock operation includes comparison of thread identifiers of said first thread with a thread identifier of a second thread.  
     
     
         16 . The article of  claim 15 , further comprising means in the medium for setting a first flag in response to a positive comparison of said thread identifiers.  
     
     
         17 . The article of  claim 16 , further comprising means in the medium for repeating setting a second flag in response to confirmation of continuity of said lock operation by said first thread.  
     
     
         18 . The article of  claim 13  further comprising means in the medium for detecting collision of execution of said lock operation by two or more threads in response to a determination of discontinuity of a lock operation by said first thread.  
     
     
         19 . The article of  claim 18 , further comprising means in the medium for resetting lock ownership with a compare-and-swap operation in response to said collision.