Lock mechanism to reduce waiting of threads to access a shared resource by selectively granting access to a thread before an enqueued highest priority thread

• US 8,607,239 B2
• Filed: 12/31/2009
• Issued: 12/10/2013
• Est. Priority Date: 12/31/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Anand, Vaijayanthimala K., Hepkin, David A., Michel, Dirk, Olszewski, Bret R.
• Primary Examiner(s): To, Jennifer
• Assistant Examiner(s): Zhao, Bing
• Application Number:
  US12/651,294
• Publication Number:
  US 20110161539A1
• Time in Patent Office: 1,440 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Two or more processors that each provides a specified thread to access a shared resource that can only be accessed by one thread at a given time. A locking mechanism enables one of the threads to access the shared resource while other threads are retained in a waiting queue. Responsive to an additional thread that is not one of the specified threads being provided access the shared resource during an identified time period, and responsive to a first criterion an a second criterion being met, the additional thread accesses the shared resource before the other threads in the waiting queue.

Claims

1. In association with a plurality of processors including two or more processors that each provides one of a set of specified threads to access a shared resource, wherein the shared resource can only be accessed by one thread at a given time, a locking mechanism enables a first one of the set of specified threads to access the shared resource while each of the other specified threads is retained in a waiting queue, and a second one of the specified threads occupies a position of highest priority in the queue, a method comprising the steps of:

identifying a time period between a time when the first specified thread releases access to the shared resource, and a later time when the second specified thread becomes enabled to access the shared resource;

responsive to an additional thread that is not one of the specified threads being provided by a processor to access the shared resource during the identified time period, determining whether a first prespecified criterion pertaining to the specified threads retained in said queue has been met, said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than a number which is determined from a specified relationship of the number of threads in the queue to the number of processors in said configuration of processors;

responsive to said first criterion being met, determining whether a second prespecified criterion has been met, wherein said second criterion is that the number of specified threads in said queue has not decreased since a specified prior time; and

responsive to said second criterion being met before said second specified thread acquires said lock, enabling said additional thread to access the shared resource before the second specified thread accesses the shared resource.

2. The method of claim 1, wherein:

responsive to either or both of the first prespecified criterion or the second prespecified criterion not being met, placing said additional thread into said queue.

3. The method of claim 1, wherein:

said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than one.

4. The method of claim 1, wherein:

said locking mechanism comprises a handoff lock mechanism that provides a lock, wherein the lock is sequentially acquired by different threads, and a thread becomes enabled to access the shared resource upon acquiring said lock.

5. The method of claim 4, wherein:

said second criterion is that the number of specified threads in said queue has not decreased since the last time the lock was acquired by a thread.

6. The method of claim 5, wherein:

a first counter is continually updated to show the current number of waiting threads in said queue at a given time, a second counter is continually updated to show the number of waiting threads each time the lock is acquired by a thread, and the contents of said first and second counters are selectively compared with each other to determine whether said second criterion has been met.

7. The method of claim 1, wherein:

each processor of said configuration comprises a virtual processor.

8. The method of claim 1, wherein:

each processor of said configuration comprises a real processor.

9. In association with a plurality of processors including two or more processors that each provides a specified thread to access a shared resource, wherein the shared resource can only be accessed by one thread at a given time, a locking mechanism enables a first one of the specified threads to access the shared resource while each of the other specified threads is retained in a waiting queue, and a second one of the specified threads occupies a position of highest priority in the queue, a computer program product executable in a non-transitory computer readable storage medium comprising:

instructions for identifying a time period between a time when the first specified thread releases access to the shared resource, and a later time when the second specified thread becomes enabled to access the shared resource;

instructions for responsive to an additional thread that is not one of the specified threads being provided by a processor to access the shared resource during the identified time period, for determining whether a first prespecified criterion pertaining to the specified threads retained in said queue has been met, said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than a number which is determined from a specified relationship of the number of threads in the queue to the number of processors in said configuration of processors;

instructions for responsive to said first criterion being met, for determining whether a second prespecified criterion has been met, wherein said second criterion is that the number of specified threads in said queue has not decreased since a specified prior time; and

instructions for responsive to said second criterion being met before said second specified thread acquires said lock, for enabling said additional thread to access the shared resource before the second specified thread accesses the shared resource.

10. The computer program product of claim 9, wherein:

responsive to deciding not to enable said additional thread to access the shared resource before the second specified thread, said additional thread is placed into said queue.

11. The computer program product of claim 9, wherein:

said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than one.

12. The computer program product of claim 9, wherein:

said locking mechanism comprises a handoff lock mechanism that provides a lock, wherein the lock is sequentially acquired by different threads, and a thread becomes enabled to access the shared resource upon acquiring said lock.

13. The computer program product of claim 12, wherein:

said second criterion is that the number of specified threads in said queue has not decreased since the last time the lock was acquired by a thread.

14. In association with a plurality of processors including two or more processors that each provides a specified thread to access a shared resource, wherein the shared resource can only be accessed by one thread at a given time, a locking mechanism enables a first one of the specified threads to access the shared resource while each of the other specified threads is retained in a waiting queue, and a second one of the specified threads occupies a position of highest priority in the queue, a computer comprising:

a memory having computer usable instructions encoded thereon;

a bus connecting the memory to a processor; and

a processor wherein the processor executes the computer usable instructions;

to identify a time period between a time when the first specified thread releases access to the shared resource, and a later time when the second specified thread becomes enabled to access the shared resource;

responsive to an additional thread that is not one of the specified threads being provided by a processor to access the shared resource during the identified time period, to determine whether a first prespecified criterion pertaining to the specified threads retained in said queue has been met, said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than a number which is determined from a specified relationship of the number of threads in the queue to the number of processors in said configuration of processors;

responsive to said first criterion being met, to determine whether a second prespecified criterion has been met, wherein said second criterion is that the number of specified threads in said queue has not decreased since a specified prior time; and

responsive to said second criterion being met before said second specified thread acquires said lock, to enable said additional thread to access the shared resource before the second specified thread accesses the shared resource.

15. The apparatus of claim 14, wherein:

responsive to deciding not to enable said additional thread to access the shared resource before the second specified thread, said additional thread is placed into said queue.

16. The apparatus of claim 14, wherein:

said first prespecified criterion is that the number of threads retained in said queue during said identified time period is greater than one.

17. The apparatus of claim 14, wherein:

said locking mechanism comprises a handoff lock mechanism that provides a lock, wherein the lock is sequentially acquired by different threads, and a thread becomes enabled to access the shared resource upon acquiring said lock.

18. The apparatus of claim 17, wherein:

said second criterion is that the number of specified threads in said queue has not decreased since the last time the lock was acquired by a thread.