Method and system for speeding up mutual exclusion

• US 8,473,969 B2
• Filed: 07/15/2008
• Issued: 06/25/2013
• Est. Priority Date: 09/28/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ogasawara, Takeshi, Koseki, Akira, Komatsu, Hideaki, Kawachiya, Kiyokuni, Onodera, Tamiya
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Huaracha, Willy W
• Application Number:
  US12/173,551
• Publication Number:
  US 20080276256A1
• Time in Patent Office: 1,806 Days
• Field of Search: 718/1, 718/101, 718/102, 718/104, 718/107, 718/100, 719/320, 710/200, 710/240, 711/150, 711/152
• US Class Current: 719/320
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

Claims

1. A method for managing a multithreaded computer system comprising:

a second thread requesting ownership of a lock for a shared memory resource owned by a first thread;

determining discontinuity of lock ownership by the first thread, including a first comparison of a thread identifier of the first thread with a thread identifier of the second thread, and setting a first flag in response to a determination of discontinuity of lock ownership;

extending continuity of lock ownership and setting a second flag in response to confirmation of continuity of said lock operation by the first thread; and

assigning ownership of the lock to the second thread by executing a first compare-and-swap operation in response to a determination that ownership of the lock by the first thread has been discontinued, including waiting until a thread denied lock ownership has passed a critical section prior to assigning ownership to the second thread, wherein a second compare-and-swap operation is initiated responsive to a changed lock ownership following the first comparison, but prior to setting a second flag, to clear the first flag and enable a lock reset.

2. The method of claim 1, further comprising detecting collision of execution of the lock operation by two or more threads in response to a determination of discontinuity of a lock operation by the first thread.

3. The method of claim 2, further comprising resetting lock ownership with a compare-and-swap operation in response to the collision.

4. A computer system comprising:

a processor with two or more threads to execute a process, a second thread requesting ownership of a lock for a shared memory resource owned by a first thread;

a lock manager in communication with the processor to determine discontinuity of ownership of a lock by the first thread;

a thread manager in communication with the lock manager for a first comparison to compare identifiers of the first and second threads to determine discontinuity of lock ownership;

the thread manager adapted to set a first flag in response to a determination of discontinuity of lock ownership;

the thread manager adapted to extend continuity of lock ownership and to set a second flag in response to confirmation of continuity of said lock operation by the first thread; and

the lock manager adapted to assign ownership of the lock to the second thread by execution of a first compare-and-swap operation in response to a determination of discontinuation of ownership of the lock by the first thread, including waiting until a thread denied lock ownership has passed a critical section prior to assigning ownership to the second thread, wherein a second compare-and-swap operation is initiated responsive to a changed lock ownership following the first comparison, but prior to setting a second flag, to clear the first flat and enable a lock reset.

5. The system of claim 4, further comprising the thread manager 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 the first thread.

6. The system of claim 5, further comprising the compare-and-swap operation to reset lock ownership to a requesting thread in response to detection of a collision by the thread manager.

7. An article comprising:

a non-transitory computer-readable data storage medium tangibly embodying instructions including;

instructions in the medium for a second thread requesting ownership of a lock for a shared memory resource owned by a first thread;

instructions in the medium for determining discontinuity of lock ownership by the first thread, including a first comparison of a thread identifier of the first thread with a thread identifier of the second thread;

instructions in the medium for setting a first flag in response to a determination of discontinuity of lock ownership;

instructions in the medium for extending continuity of lock ownership and setting a second flag in response to confirmation of continuity of said lock operation by the first thread; and

instructions in the medium for assigning ownership of the lock to the second thread by executing a compare-and-swap operation in response to a determination that the ownership of the lock by the first thread has been discontinued, including waiting until a thread denied lock ownership has passed a critical section prior to assigning ownership to the second thread, wherein a second compare-and-swap operation is initiated responsive to a changed lock ownership following the first comparison, but prior to setting a second flag, to clear the first flag and enable a lock reset.

8. The article of claim 7 further comprising instructions in the medium for detecting collision of execution of the lock operation by two or more threads in response to a determination of discontinuity of a lock operation by the first thread.

9. The article of claim 8, further comprising instructions in the medium for resetting lock ownership with a compare-and-swap operation in response to the collision.