SYSTEM AND METHOD FOR DYNAMICALLY ADAPTIVE MUTUAL EXCLUSION IN MULTI-THREADED COMPUTING ENVIRONMENT

• US 20090307707A1
• Filed: 06/09/2008
• Published: 12/10/2009
• Est. Priority Date: 06/09/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gellerich, Wolfgang, Smolinski, Holger, Schwidefsky, Martin
• Application Number:
  US12/135,616
• Publication Number:
  US 20090307707A1
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system and associated method for mutually exclusively executing a critical section by a process in a computer system. The critical section accessing a shared resource is controlled by a lock. The method measures a detection time when a lock contention is detected, a wait time representing a duration of wait for the lock at each failed attempt to acquire the lock, and a delay representing a total lapse of time from the detection time till the lock is acquired. The delay is logged and used to calculate an average delay, which is compared with a suspension overhead time of the computer system on which the method is executed to determine whether to spin or to suspend the process while waiting for the lock to be released.

Claims

1. A method for mutually exclusively executing a critical section by a process in a computer system, the method comprising:

measuring a detection time representing when a locking function detects that a lock is held by another process, and a current time representing a present time, wherein the lock permits an access to the critical section;

subsequent to said measuring, repeating at least one iteration comprising steps of determining a waiting mode of the process, and subsequently attempting to acquire the lock, wherein the waiting mode is determined such that the process in the waiting mode wastes the least amount of time while waiting for the lock pursuant to at least one delay stored in a lock delay history data structure and a suspension overhead time of the computer system;

subsequent to said repeating, acquiring the lock;

subsequent to said acquiring, calculating a delay representing a difference between a release time representing when the lock is released and the detection time; and

subsequent to said calculating, storing the calculated delay in the lock delay history data structure,

wherein said measuring, said repeating, said acquiring, said calculating, and said storing are performed by the locking function.

2. The method of claim 1, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process; and

subsequent to said determining, attempting to acquire the lock.

3. The method of claim 1, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process;

subsequent to said determining, attempting to acquire the lock;

upon said attempting, failing to acquire the lock;

subsequent to said failing, recalculating the wait time; and

subsequent to said recalculating, looping back to a next iteration of said repeating.

4. The method of claim 1, said repeating comprising:

determining the waiting mode of the process as suspend, responsive to discovering that an expected delay is greater than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of suspend stops consuming processor cycles but requires context switches of the process necessary to suspend and to resume the process; and

subsequent to said determining, suspending the process.

5. The method of claim 4, said acquiring further comprising:

measuring and storing the release time;

subsequent to said measuring, unlocking the lock such that the process acquires the lock; and

subsequent to said unlocking, resuming the suspended process,

wherein said measuring and storing, said unlocking, and said resuming are performed by an unlocking function that corresponds to the locking function.

6. The method of claim 1, said acquiring further comprising:

measuring and storing the release time; and

subsequent to said measuring, unlocking the lock such that the process acquires the lock,

wherein said measuring and storing, and said unlocking are performed by an unlocking function that corresponds to the locking function.

7. The method of claim 1, wherein the detection time, the current time, the delay, and the suspension overhead time is measured by a respective count of processor cycles of the computer system.

8. A computer program product, comprising a computer usable storage medium having a computer readable program code embodied therein, said computer readable program code containing instructions that when executed by a processor of a computer system implement a method for mutually exclusively executing a critical section by a process in a computer system, the method comprising:

measuring a detection time representing when a locking function detects that a lock is held by another process, and a current time representing a present time, wherein the lock permits an access to the critical section;

subsequent to said measuring, repeating at least one iteration comprising steps of determining a waiting mode of the process, and subsequently attempting to acquire the lock, wherein the waiting mode is determined such that the process in the waiting mode wastes the least amount of time while waiting for the lock pursuant to at least one delay stored in a lock delay history data structure and a suspension overhead time of the computer system;

subsequent to said repeating, acquiring the lock;

subsequent to said acquiring, calculating a delay representing a difference between a release time representing when the lock is released and the detection time; and

subsequent to said calculating, storing the calculated delay in the lock delay history data structure,

wherein said measuring, said repeating, said acquiring, said calculating, and said storing are performed by the locking function.

9. The computer program product of claim 8, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process; and

subsequent to said determining, attempting to acquire the lock.

10. The computer program product of claim 8, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process;

subsequent to said determining, attempting to acquire the lock;

upon said attempting, failing to acquire the lock;

subsequent to said failing, recalculating the wait time; and

subsequent to said recalculating, looping back to a next iteration of said repeating.

11. The computer program product of claim 8, said repeating comprising:

determining the waiting mode of the process as suspend, responsive to discovering that an expected delay is greater than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of suspend stops consuming processor cycles but requires context switches of the process necessary to suspend and to resume the process; and

subsequent to said determining, suspending the process.

12. The computer program product of claim 11, said acquiring further comprising:

measuring and storing the release time;

subsequent to said measuring, unlocking the lock such that the process acquires the lock; and

subsequent to said unlocking, resuming the suspended process,

wherein said measuring and storing, said unlocking, and said resuming are performed by an unlocking function that corresponds to the locking function.

13. The computer program product of claim 8, said acquiring further comprising:

measuring and storing the release time; and

subsequent to said measuring, unlocking the lock such that the process acquires the lock,

wherein said measuring and storing, and said unlocking are performed by an unlocking function that corresponds to the locking function.

14. The computer program product of claim 8, wherein the detection time, the current time, the delay, and the suspension overhead time is measured by a respective count of processor cycles of the computer system.

15. A computer system comprising a processor and a computer readable memory unit coupled to the processor, said memory unit containing instructions that when executed by the processor implement a method for mutually exclusively executing a critical section by a process in a computer system, the method comprising:

measuring a detection time representing when a locking function detects that a lock is held by another process, and a current time representing a present time, wherein the lock permits an access to the critical section;

subsequent to said measuring, repeating at least one iteration comprising steps of determining a waiting mode of the process, and subsequently attempting to acquire the lock, wherein the waiting mode is determined such that the process in the waiting mode wastes the least amount of time while waiting for the lock pursuant to at least one delay stored in a lock delay history data structure and a suspension overhead time of the computer system;

subsequent to said repeating, acquiring the lock;

subsequent to said acquiring, calculating a delay representing a difference between a release time representing when the lock is released and the detection time; and

subsequent to said calculating, storing the calculated delay in the lock delay history data structure,

wherein said measuring, said repeating, said acquiring, said calculating, and said storing are performed by the locking function.

16. The computer system of claim 15, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process; and

subsequent to said determining, attempting to acquire the lock.

17. The computer system of claim 15, said repeating comprising:

determining the waiting mode of the process as busy-wait, responsive to discovering that an expected delay is less than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of busy-wait continues consuming processor cycles but requires no context switch of the process;

subsequent to said determining, attempting to acquire the lock;

upon said attempting, failing to acquire the lock;

subsequent to said failing, recalculating the wait time; and

subsequent to said recalculating, looping back to a next iteration of said repeating.

18. The computer system of claim 15, said repeating comprising:

determining the waiting mode of the process as suspend, responsive to discovering that an expected delay is greater than the suspension overhead time, wherein the expected delay is a difference between an average delay and a wait time, wherein the average delay represents an average value of said at least one delay stored in the lock delay history, wherein the wait time represents a difference between the current time and the detection time, wherein the suspension overhead time represents the amount of time that is wasted for context switches of the process necessary to suspend and to resume the process, wherein the process in the waiting mode of suspend stops consuming processor cycles but requires context switches of the process necessary to suspend and to resume the process; and

subsequent to said determining, suspending the process.

19. The computer system of claim 18, said acquiring further comprising:

measuring and storing the release time;

subsequent to said measuring, unlocking the lock such that the process acquires the lock; and

subsequent to said unlocking, resuming the suspended process,

wherein said measuring and storing, said unlocking, and said resuming are performed by an unlocking function that corresponds to the locking function.

20. The computer system of claim 15, said acquiring further comprising:

measuring and storing the release time; and

subsequent to said measuring, unlocking the lock such that the process acquires the lock,

wherein said measuring and storing, and said unlocking are performed by an unlocking function that corresponds to the locking function.