SYSTEM AND METHOD FOR LOAD-ADAPTIVE MUTUAL EXCLUSION WITH WAITING PROCESS COUNTS

• US 20090320028A1
• Filed: 06/18/2008
• Published: 12/24/2009
• Est. Priority Date: 06/18/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gellerich, Wolfgang, Smolinski, Holger, Schwidefsky, Martin
• Granted Patent: US 8,839,253 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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 to determine whether to spin or to suspend the process while waiting for the lock to be released. The number of processes waiting for the lock and the number of processes suspended are respectively counted to optimize the method.

Claims

1. A method for mutually exclusively executing a critical section by a process in a computer system, wherein a lock permits the process an access to the critical section, the method comprising:

upon detecting that the lock is held by another process, adding one (1) to a waiter count that represents the number of processes waiting for the lock, measuring a detection time that represents the time of said detecting, and measuring a current time representing a present time;

subsequent to said adding, 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 for the process;

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

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

subsequent to said storing, subtracting one (1) from the waiter count,

wherein said adding, said repeating, said acquiring, said calculating, said storing, and said subtracting are performed by a locking function invoked by the process.

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;

responsive to said determining, adding one (1) to a sleeper count that represents the number of suspended processes waiting for the lock;

subsequent to said adding, suspending the process; and

subsequent to said suspending, upon the process being resumed by an unlocking function that corresponds to the locking function, subtracting one (1) from the sleeper count.

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock;

subsequent to said unlocking, confirming that the sleeper count is greater than zero (0); and

responsive to said confirming, resuming the process from said suspending,

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

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock; and

subsequent to said unlocking, confirming that the sleeper count is equal to zero (0),

wherein said determining, said measuring and storing, said unlocking, and said confirming 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, wherein a lock permits the process an access to the critical section, the method comprising:

upon detecting that the lock is held by another process, adding one (1) to a waiter count that represents the number of processes waiting for the lock, measuring a detection time that represents the time of said detecting, and measuring a current time representing a present time;

subsequent to said adding, 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 for the process;

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

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

subsequent to said storing, subtracting one (1) from the waiter count,

wherein said adding, said repeating, said acquiring, said calculating, said storing, and said subtracting are performed by a locking function invoked by the process.

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;

responsive to said determining, adding one (1) to a sleeper count that represents the number of suspended processes waiting for the lock;

subsequent to said adding, suspending the process; and

subsequent to said suspending, upon the process being resumed by an unlocking function that corresponds to the locking function, subtracting one (1) from the sleeper count.

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock;

subsequent to said unlocking, confirming that the sleeper count is greater than zero (0); and

responsive to said confirming, resuming the process from said suspending,

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

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock; and

subsequent to said unlocking, confirming that the sleeper count is equal to zero (0),

wherein said determining, said measuring and storing, said unlocking, and said confirming 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, wherein a lock permits the process an access to the critical section, the method comprising:

upon detecting that the lock is held by another process, adding one (1) to a waiter count that represents the number of processes waiting for the lock, measuring a detection time that represents the time of said detecting, and measuring a current time representing a present time;

subsequent to said adding, 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 for the process;

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

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

subsequent to said storing, subtracting one (1) from the waiter count,

wherein said adding, said repeating, said acquiring, said calculating, said storing, and said subtracting are performed by a locking function invoked by the process, and 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.

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;

responsive to said determining, adding one (1) to a sleeper count that represents the number of suspended processes waiting for the lock;

subsequent to said adding, suspending the process; and

subsequent to said suspending, upon the process being resumed by an unlocking function that corresponds to the locking function, subtracting one (1) from the sleeper count.

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock;

subsequent to said unlocking, confirming that the sleeper count is greater than zero (0); and

responsive to said confirming, resuming the process from said suspending,

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

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

determining that the waiter count is greater than zero (0);

responsive to said determining, measuring and storing the release time;

subsequent to said measuring, unlocking the lock; and

subsequent to said unlocking, confirming that the sleeper count is equal to zero (0),

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