Method of reducing contention of a highly contended lock protecting multiple data items

• US 7,065,763 B1
• Filed: 09/29/2000
• Issued: 06/20/2006
• Est. Priority Date: 09/29/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Martin, Brian James, Ryan, Michael
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Tang, Kenneth
• Application Number:
  US09/675,396
• Time in Patent Office: 2,090 Days
• Field of Search: 718 1-108
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Featured is a method or process for reducing contention of a highly contended software lock(s) that is protecting multiple data items, where the software has a plurality of code paths accessing the data items. The method includes creating additional partition locks to protect subsets of the data items protected by the existing global lock. Such a method further includes acquiring all partition locks and the global lock, wherever a global lock would have been acquired to protect data. The method also includes identifying one or more heavily used code paths and determining which data items are touched by the identified one or more heavily used code paths. These data items are then moved into a partition, if they were not partitioned earlier. The locking requirements for each of the identified one or more heavily used code paths are optimized to match the reduced locking requirements because of the partitioned data items. In other words the locking requirements are reduced so only the locks for the partitions including the data items that touch the code path are acquired. In more specific embodiments, the so-modified software is evaluated to determine if there is an acceptable increase in overall system performance resulting from the optimization of the locking requirements. If the modified system'"'"'s performance is not acceptable, then the next most heavily used code path is identified and the locking requirements for this code path are optimized. Such optimization is continued until the system exhibits an acceptable overall system performance or all code paths are optimized.

Claims

1. A method for reducing contention of a highly contended software lock protecting data items of a data set, all of the data items being stored in a system memory of a multi-processor computer system, said method comprising the steps of:

defining partitions within the data set;

creating N partition locks, one for each partition, where N>

2;

identifying one code path from one or more code paths of a software program that access one or more of the data items;

determining which data items of the data set are accessible by the identified code path;

partitioning at least a portion of the data items that are accessible by the identified code path into the partitions; and

optimizing locking requirements of the identified code path so the locks being acquired and released in the identified code path are those associated with the data items being accessible by the identified code path, wherein the identified code path includes a plurality of branches, and wherein said optimizing includes optimizing the locking requirements of the identified code path so the locks being acquired and released in the code path are those associated with the data items being accessible by each branch of identified code path.

2. The method according to claim 1, further comprising the step of modifying the locking requirements of the one or more code paths of the software program that access one or more of the data items so as to acquire all N partition locks and a global lock where the global lock would have been acquired prior to accessing of the one or more data items and so as to release all N partition locks and the global lock where a global lock would have been released after accessing of the one or more data items.

3. The method according to claim 1, wherein said optimizing includes optimizing the locking requirements of each branch of the identified code path so the locks being acquired and released in each branch are those associated with the data items being touched accessible by said each branch.

4. The method according to claim 1, further comprising the step of evaluating the software program after said optimizing the locking requirements so as to determine if overall performance of the software program is acceptable, wherein the overall system performance is based on reducing contention of the highly contended software lock.

5. The method according to claim 4, wherein in the case where said evaluating determines that the overall performance of the software program is not acceptable, then said method includes identifying another code path of the one or more code paths and repeating said steps of determining, partitioning, optimizing, and evaluating for the another identified code path.

6. The method according to claim 5, wherein the code path first identified is the heaviest used code path and wherein the another code path and subsequent code paths are identified sequentially in the direction from the heaviest used code path to a lesser used path.

7. The method according to claim 1, further comprising the step of first determining a methodology for partitioning the data set.

8. The method according to claim 1, wherein the code path first identified is the heaviest used code path.

9. The method according to claim 1, wherein there is one of a plurality or a multiplicity of code paths that access one or more of the data items.

10. A method for reducing contention of a highly contended software lock protecting data items of a data set, all of the data items being stored in a system memory of a multi-processor computer system, said method comprising the steps of:

first determining a methodology for partitioning the data set into partitions;

creating N partition locks, one for each partition, where N>

2;

modifying locking requirements of each of one or more code paths of a software program that access one or more of the data items so as to acquire all N partition locks and a global lock where the global lock would have been acquired prior to accessing of the one or more data items and so as to release all N partition locks and the global lock where the global lock would have been released after accessing of the one or more data items;

identifying one code path from the one or more code paths of the software program that access one or more of the data items, wherein the code path first identified is the heaviest used code path and wherein the another code path and subsequent code paths are identified sequentially in the direction from the heaviest used code path to a lesser used path;

next determining which data items of the data set are accessible by the identified code path;

partitioning at least one of the data items that are accessible by the identified code path; and

optimizing the locking requirements of the identified code path so the locks being acquired and released in the identified code path are those associated with the data items being accessible by the identified code path;

evaluating the software program after said optimizing the locking requirements so as to determine if overall performance of the software program is acceptable, wherein the overall system performance is based on reducing contention of the highly contended software lock; and

in the case where said evaluating determines that the overall performance of the software program is not acceptable, then identifying another code path of the one or more code paths and repeating said steps of determining, partitioning, optimizing and evaluating for the another identified code path.

11. The method according to claim 10, wherein the identified code path includes a plurality of branches, and wherein said optimizing includes optimizing the locking requirements of the identified code path so the locks being acquired and released in the code path are those associated with the data items being accessible by each branch of identified code path.

12. The method according to claim 11, wherein said optimizing includes optimizing the locking requirements of each branch of the identified code path so the locks being acquired and released in each branch are those associated with the data items being accessible by said each branch.

13. A method for reducing contention of a highly contended software lock protecting data items of a data set, all of the data items being stored in a system memory of a multi-processor computer system, said method comprising the steps of:

defining partitions within the data set;

creating N partition locks, one for each partition, where N>

2;

partitioning at least one of the data items into the partitions; and

modifying locking requirements of all code paths of the one or more code paths of a software program that access one or more of the data items so that the locks being acquired and released in each of said all code paths are those associated with the accessible data items of each respective partition, wherein one code path of said all code paths includes a plurality of branches, and wherein said modifying includes modifying the locking requirements of each branch of said one code path so the locks being acquired and released in each branch are those associated with the data accessible by said each branch.

14. The method according to claim 13, further comprising the step of evaluating the software program after said modifying the locking requirements so as to determine if the overall performance of the software program is acceptable.

15. The method according to claim 14, wherein in the case where said evaluating determines that the overall performance of the software program is not acceptable, then said method includes partitioning more data items and repeating said steps of modifying and evaluating.

16. The method according to claim 13, further comprising the step of first determining a methodology for partitioning the data set.

17. The method according to claim 13, wherein there is one of a plurality or a multiplicity of code paths that access one or more of the data items.

18. A method for reducing contention of a highly contended software lock protecting data items of a data set, all of the data items being stored in a system memory of a multi-processor computer system, said method comprising the steps of:

first determining a methodology for partitioning the data set;

defining partitions within the data set based upon the methodology;

creating N partition locks, one for each partition, where N>

2;

partitioning a plurality of the data items into the partitions;

modifying locking requirements of all code paths of the one or more code paths of a software program that access one or more of the data items so that the locks being acquired and released in each of said all code paths are those associated with accessible data items, wherein the code path first modified is the heaviest used code path and wherein the another code path and subsequent code paths are modified sequentially in the direction from the heaviest used code path to a lesser used path; and

evaluating the software program after said modifying the locking requirements so as to determine if overall performance of the software program is acceptable, wherein the overall system performance is based on reducing contention of the highly contended software lock, wherein in the case where said evaluating determines that the overall performance of the software program is not acceptable, then said method includes partitioning more data items and repeating said steps of modifying and evaluating.

19. A method for accessing one or more data items in a data set by a software program, all of the data items being stored in a system memory of a multi-processor computer system, said method comprising the steps of:

defining partitions within the data set;

creating N partition locks, one for each partition, where N>

2;

identifying one code path from one or more code paths of the software program that access one or more of the data items;

determining which data items of the data set are touched by the identified code path;

partitioning at least one of the data items that are accessible by the identified code path;

optimizing locking requirements of the identified code path so the locks being acquired and released in the identified code path are those associated with the data items being accessible by the identified code path;

locking the data items of the data set that are touched by the identified code path while keeping unlocked the data items of the data set that are not being accessible by the identified code path;

accessing one or more of the locked data items;

modifying the locking requirements of the one or more code paths of the software program that access one or more of the data items so as to acquire all N partition locks and a global lock where the global lock would have been acquired prior to accessing of the one or more data items and so as to release all N partition locks and the global lock where a global lock would have been released after accessing of the one or more data items; and

releasing the locks associated with the locked data.

20. The method according to claim 19, wherein in the case where accessing data in the one or more code paths in which all N partition locks and the global lock are acquired and released, said method further comprising the steps of:

acquiring all N partition locks and the global lock;

accessing the data being protected by the acquired N partition locks and the global lock; and

releasing all N partition locks and the global lock.

21. The method according to claim 19, wherein the identified code path is the heaviest used code path that accesses data items.

22. The method according to claim 19, wherein locking requirements for a plurality of code paths are optimized, and wherein said acquiring, accessing and releasing are selectively effected in any one of the plurality of code paths provided that the data items to be locked in said any one code path are not locked in any other of the plurality of code paths.