Method and system for managing lock contention in a computer system

• US 6,845,504 B2
• Filed: 02/08/2001
• Issued: 01/18/2005
• Est. Priority Date: 02/08/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Walehiane, Nasr-Eddine, Olszewski, Bret R., Srinivas, Mysore S., Hua, Hong L.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Ali, Syed J
• Application Number:
  US09/779,369
• Publication Number:
  US 20020107854A1
• Time in Patent Office: 1,440 Days
• Field of Search: 718/100, 718102-104, 707/8, 710/200
• US Class Current: 718/104
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system and method for efficiently managing lock contention for a central processing unit (CPU) of a computer system. The present invention uses both spinning and blocking (or undispatching) to manage threads when they are waiting to acquire a lock. In addition, the present invention intelligently determines when the program thread should spin and when the program thread should become undispatched. If it is determined that the program thread should become undispatched, the present invention provides efficient undispatching of program threads that improves throughput by reducing wait time to acquire the lock. A lock contention management system includes a dispatcher for managing the execution of threads on CPUs as well as threads that are currently ready to run but not executing because they are waiting for an available CPU, a dispatch management module that determines when a program thread should become undispatched to wait on a lock and when the program thread should spin, and low-priority execution module for undispatching the program thread. The present invention also includes a lock contention management method using the above system.

Claims

1. A lock contention management method, comprising:

determining whether a code module has failed to acquire access to a lock to keep other code modules from accessing a resource;

allowing a higher-priority code module to access the lock first by changing from an original priority of the code module to a lower priority if the code module should continually request access to the lock, and allowing the code module to continue to request access at the lower priority if it is determined that there are no other code modules waiting to run; and

restoring the code module to its original priority after the code module either obtains the lock or is forced to sleep after some fixed period of time.

2. The method of claim 1, wherein:

the code module continually requests access to the lock when the resource has other tasks to run; and

the code module stops requesting access to the lock when the resource has no other tasks to run.

3. The method of claim 1, further comprising determining that there are multiple processor run queues and having the code module stop requesting access to the lock if there are other code modules in the multiple processor run queues waiting to access the lock and having the code module continually request access to the lock if there are not.

4. The method of claim 1, further comprising determining that there is a single processor run queue and having the code module stop requesting access to the lock if there are other code modules in the single processor run queue waiting to access the lock and having the code module continually request access to the lock if there are not.

5. The method of claim 1, wherein the code module stops requesting access to the lock using a low-priority execution technique that lowers a priority of the code module.

6. The method of claim 5, wherein the low-priority execution technique allows a higher-priority code module to access the lock first.

7. The method of claim 6, wherein the lowered-priority code module continually requests access to the lock if no higher-priority code modules are available.

8. A lock contention management system, comprising:

a dispatch management module that undispatches a code module when the code module has failed to acquire access to a lock to keep other code modules from accessing a resource, and other code modules are waiting to run; and

a low-priority execution module that lowers a priority of the code module when the code module becomes undispatched;

wherein, if the code module continually requests access to the lock, and if there are no other code modules waiting to run, allowing a higher-priority code module to access the lock first by changing from an original priority of the code module to the lower priority with the low-priority execution module, dispatching the code module with the dispatch management module and allowing the code module to spin at the lower priority;

wherein the code module is restored to its original priority after the code module either obtains the lock or is forced to sleep after some fixed period of time.

9. The lock contention management system of claim 8, wherein the dispatch management module determines that the code module should spin when a processor has no other tasks to perform.

10. The lock contention management system of claim 8, wherein the dispatch management module determines that the code module should become undispatched when a processor has other tasks to perform.

11. The lock contention management system of claim 8, wherein the code module is a program thread.

12. The lock contention management system of claim 8, wherein the low-priority execution module reduces an original priority of the code module to a lowered priority.

13. The lock contention management system of claim 12, wherein the low-priority execution module allows higher-priority code modules to acquire the lock before the lower priority code module.

14. A method of acquiring a lock to allow execution of a program thread by a computer processor, comprising:

undispatching the program thread when the program thread has failed to acquire a lock and other program threads are waiting to run;

lowering a priority of the program thread before spinning or undispatching;

dispatching the program thread and allowing a higher-priority code module to access the lock first by changing from an original priority of the program thread to the lower priority if the program thread continually requests access to the lock and if there are no other program threads waiting to run and allowing the code module to spin at the lower priority; and

restoring the program thread to its original priority after the program thread either obtains the lock or is forced to sleep after some fixed period of time.

15. The method of claim 14, wherein the program thread is allowed to spin if there are no other program threads waiting to access the lock and if the computer processor does not have other processing to perform.

16. The method of claim 14, wherein the program thread becomes undispatched if there are other program threads waiting to access the lock and if the computer processor has other processing to perform.