Method, apparatus and computer program product for locking interrelated data structures in a multi-threaded computing environment

• US 6,594,683 B1
• Filed: 09/16/1999
• Issued: 07/15/2003
• Est. Priority Date: 01/23/1998
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ohlson, Alexander R., Furlani, John L.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/398,915
• Time in Patent Office: 1,398 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/105, 709/106, 711/141, 711/145, 710/240, 710/242, 710/244
• US Class Current: 718/102
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Apparatus, methods, and computer program products are disclosed that improve the performance of multi-threaded computer applications that use objects (within an object collection) which require exclusive thread access. The invention monitors interrelationships between the objects in the object collection and provides mechanisms to lock the minimal set of these objects for the exclusive thread access. When these objects are locked, independent or unrelated objects are left unlocked and can, in turn, be locked by other threads. Because a minimal set of objects are locked other threads that access the object collection are less likely to be blocked by the lock. Thus, these other threads are more likely to be able to simultaneously access objects in the object collection.

Claims

1. A method for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such method comprising:

providing a reference lock for the collection of objects to limit access to the collection;

locking the reference lock to gain initial control of the desired object;

providing a group lock for the desired object and other objects in the collection which are interrelated with the desired object;

locking the group lock;

and unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

2. The method of claim 1 wherein lock pointers are used to link the desired and interrelated objects to the group lock.

3. The method of claim 2 further comprising modifying the lock pointers for accommodating a change of the relationship between objects.

4. The method of claim 2 further comprising modifying the lock pointers to add a previously non-interrelated object to the group of interrelated objects.

5. The method of claim 1 wherein the desired object is a directed acyclic graph (DAG) object.

6. The method of claim 5 wherein the DAG object describes an image processing operation.

7. A method for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such method comprising:

providing a reference lock for the collection of objects to limit access to the collection;

locking the reference lock to gain initial control of the desired object;

identifying other objects in the collection which are interrelated with the desired object;

providing a group lock for the desired object and the identified interrelated objects;

locking the group lock;

and unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

8. A method for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such method comprising:

providing a reference lock for the collection of objects to limit access to the collection;

locking the reference lock to gain initial control of the desired object;

providing group locks for groups of interrelated objects in the collection, one of the groups containing the desired object;

locking the group lock for the group containing the desired object;

and unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

9. The method of claim 8 wherein lock pointers are used to link the objects in the groups to their respective group locks.

10. The method of claim 9 further comprising modifying the lock pointers for accommodating changes in object relationships.

11. The method of claim 9 further comprising modifying the lock pointers to add an object to one of the groups of interrelated objects.

12. The method of claim 9 further comprising modifying the lock pointers for transferring an object from one group to another group.

13. The method of claim 8 further comprising merging two of the groups of interrelated objects, one of which includes the desired object, and providing a single group lock for the merged groups, the locking of the group lock comprising locking the single group lock for the merged group.

14. The method of claim 8 wherein the desired object is a directed acyclic graph (DAG) object.

15. The method of claim 14 wherein the DAG object describes an image processing operation.

16. A system for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such system comprising:

a reference locking mechanism for providing a reference lock for the collection of objects to limit access to the collection;

a locking mechanism for locking the reference lock to gain initial control of the desired object;

a group locking mechanism for providing a group lock for the desired object and other objects in the collection which are interrelated with the desired object;

a locking mechanism for locking the group lock;

and an unlocking mechanism for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

17. The system of claim 16 wherein lock pointers are used to link the desired and interrelated objects to the group lock.

18. The system of claim 17 further comprising a modification mechanism modifying the lock pointers for accommodating a change of the relationship between objects.

19. The system of claim 17 further comprising a modification mechanism for modifying the lock pointers to add a previously non-interrelated object to the group of interrelated objects.

20. The system of claim 16 wherein the desired object is a directed acyclic graph (DAG) object.

21. The system of claim 20 wherein the DAG object describes an image processing operation.

22. A system for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such system comprising:

a reference locking mechanism for providing a reference lock for the collection of objects to limit access to the collection;

a locking mechanism for locking the reference lock to gain initial control of the desired object;

an identifying mechanism for identifying other objects in the collection which are interrelated with the desired object;

a group locking mechanism for providing a group lock for the desired object and the identified interrelated objects;

a locking mechanism for locking the group lock;

and an unlocking mechanism for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

23. A system for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such system comprising:

a reference locking mechanism for providing a reference lock for the collection of objects to limit access to the collection;

a locking mechanism for locking the reference lock to gain initial control of the desired object;

a group locking mechanism for providing group locks for groups of interrelated objects in the collection, one of the groups containing the desired object;

a locking mechanism for locking the group lock for the group containing the desired object;

and an unlocking mechanism for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

24. The system of claim 23 wherein lock pointers are used to link the objects in the groups to their respective group locks.

25. The system of claim 24 further comprising a modification mechanism for modifying the lock pointers for accommodating changes in object relationships.

26. The system of claim 24 further comprising a modification mechanism for modifying the lock pointers to add an object to one of the groups of interrelated objects.

27. The system of claim 24 further comprising a modification mechanism for modifying the lock pointers for transferring an object from one group to another group.

28. The system of claim 23 further comprising a group merging mechanism for merging two of the groups of interrelated objects, one of which includes the desired object, and providing a single group lock for the merged groups, the locking of the group lock comprising locking the single group lock for the merged group.

29. The system of claim 23 wherein the desired object is a directed acyclic graph (DAG) object.

30. The system of claim 29 wherein the DAG object describes an image processing operation.

31. A computer program product comprising:

a computer usable storage medium having computer readable code for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such computer readable code comprising;

computer readable code for providing a reference lock for the collection of objects to limit access to the collection;

computer readable code for locking the reference lock to gain initial control of the desired object;

computer readable code for providing a group lock for the desired object and other objects in the collection which are interrelated with the desired object;

computer readable code for locking the group lock;

and computer readable code for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

32. The computer program product of claim 31 wherein lock pointers are used to link the desired and interrelated objects to the group lock.

33. The computer program product of claim 32 further comprising computer readable code for modifying the lock pointers for accommodating a change of the relationship between objects.

34. The computer program product of claim 32 further comprising computer readable code for modifying the lock pointers to add a previously non-interrelated object to the group of interrelated objects.

35. The computer program product of claim 31 wherein the desired object is a directed acyclic graph (DAG) object.

36. The computer program product of claim 35 wherein the DAG object describes an image processing operation.

37. A computer program product comprising:

a computer usable storage medium having computer readable code for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such computer readable code comprising;

computer readable code for providing a reference lock for the collection of objects to limit access to the collection;

computer readable code for locking the reference lock to gain initial control of the desired object;

computer readable code for identifying other objects in the collection which are interrelated with the desired object;

computer readable code for providing a group lock for the desired object and the identified interrelated objects;

computer readable code for locking the group lock;

and computer readable code for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

38. A computer program product comprising:

a computer usable storage medium having computer readable code for locking a desired object in a collection of objects for a period of time while locking objects in the collection which are not interrelated with the desired object for a lesser period of time, such computer readable code comprising;

computer readable code for providing a reference lock for the collection of objects to limit access to the collection;

computer readable code for locking the reference lock to gain initial control of the desired object;

computer readable code for providing group locks for groups of interrelated objects in the collection, one of the groups containing the desired object;

computer readable code for locking the group lock for the group containing the desired object;

and computer readable code for unlocking the reference lock to enable access to objects in the collection which are not interrelated with the desired object.

39. The computer program product of claim 38 wherein lock pointers are used to link the objects in the groups to their respective group locks.

40. The computer program product of claim 39 further comprising computer readable code for modifying the lock pointers for accommodating changes in object relationships.

41. The computer program product of claim 39 further comprising computer readable code for modifying the lock pointers to add an object to one of the groups of interrelated objects.

42. The computer program product of claim 39 further comprising computer readable code for modifying the lock pointers for transferring an object from one group to another group.

43. The computer program product of claim 38 further comprising computer readable code for merging two of the groups of interrelated objects, one of which includes the desired object, and providing a single group lock for the merged groups, the locking of the group lock comprising locking the single group lock for the merged group.

44. The computer program product of claim 38 wherein the desired object is a directed acyclic graph (DAG) object.

45. The computer program product of claim 44 wherein the DAG object describes an image processing operation.