ACCELERATING MUTUAL EXCLUSION LOCKING FUNCTION AND CONDITION SIGNALING WHILE MAINTAINING PRIORITY WAIT QUEUES

• US 20100100889A1
• Filed: 10/16/2008
• Published: 04/22/2010
• Est. Priority Date: 10/16/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: LABRIE, ROBERT G., MYERS, JAMES J.
• Application Number:
  US12/252,938
• Publication Number:
  US 20100100889A1
• Time in Patent Office: Days
• US Class Current: 718/106
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A synchronization library of mutex functions and condition variable functions for threads which are compatible with pthread library functions conforming to a (POSIX) standard. The library can utilize a mutex data structure and a condition variable data structure both including lockwords and queuing anchors. In the library, Compare Swap (CS) instruction processing can be used to protect shared resource. The synchronization library can support priority queuing of threads and can have an ability to yield control when CS spin lock iterations exceed a set limit.

Claims

1. A software library comprising:

a synchronization library of functions for threads which are compatible with pthread library functions conforming to a Portable Operating System Interface (POSIX) standard excepting the pthread synchronization library functions, where the synchronization library functions are configured to be used in place of existing pthread synchronization library functions, wherein said synchronization library functions comprise mutex functions and condition variable functions;

a mutex data structure configured to be used with the mutex functions of the synchronization library, wherein the mutex data structure comprises fields for a lockword, for an owner, and queuing anchors for threads waiting to acquire an instance of the mutex data structure;

a condition variable data structure configured to be used with the condition variable functions of the synchronization library, wherein the condition variable data structure comprises fields for a lockword and for queuing anchors for threads waiting to acquire an instance of the condition variable data structure, wherein the synchronization library is stored in a storage medium, and wherein the synchronization library is configured to utilize Compare Swap (CS) instruction processing to protect shared resources, wherein the Compare Swap (CS) instruction processing operates against a lockword of a mutex data structure instance and a lockword of a condition variable data structure instance.

2. The software library of claim 1, wherein the synchronization library permits pthread to possess at least two priority states, wherein the synchronization library is configured such that when threads are added to a queue of threads waiting on a mutex data structure instance, threads associated with a greater priority state are placed in the queue above pre-existing threads associated with a lesser priority state, wherein the synchronization library is configured such that threads placed in the queue having equivalent priority states are processed in a first-in-first-out (FIFO) manner.

3. The software library of claim 1, wherein the synchronization library is configured such that spin locked threads yield control while waiting for a mutex data structure instance when a number of cycles waited exceeds a configurable and previously established threshold.