Method and system for speeding up mutual exclusion

• US 20060090168A1
• Filed: 09/28/2004
• Published: 04/27/2006
• Est. Priority Date: 09/28/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Ogasawara, Takeshi, Koseki, Akira, Kawachiya, Kiyokuni, Onodera, Tamiya
• Application Number:
  US10/952,142
• Publication Number:
  US 20060090168A1
• Time in Patent Office: Days
• 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:

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.