Methods, apparatus, and product for distributed garbage collection

• US 6,816,875 B2
• Filed: 06/19/2003
• Issued: 11/09/2004
• Est. Priority Date: 10/11/1996
• Status: Expired due to Term

• Current Assignee: Ann W. Wollrath, James H. Waldo, Roger Riggs
• Original Assignee: Ann W. Wollrath, James H. Waldo, Roger Riggs
• Inventors: Waldo, James H., Riggs, Roger, Wollrath, Ann W.
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/464,562
• Publication Number:
  US 20030208512A1
• Time in Patent Office: 509 Days
• Field of Search: 707/203, 707/104.1, 707/202, 707/103.R, 707/103.Y, 707/206, 707/10, 707/201, 709/201, 709/203, 709/226, 709/104
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 9/4411 Configuring for operating with peripheral devices; Loading of device drivers
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/547 Remote procedure calls [RPC]; Web services
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 : Recoverability
• CPC Class Codes: Y10S 707/99957 : Garbage collection

Abstract

In accordance with the present invention a process is provided for allocating and deallocating resources in a distributed processing system having a requester platform and a server platform. The process involves receiving a request from the requestor platform referring to a system resource and specifying a requested lease period, permitting shared access to the system resource for a lease period, sending a return call to the requestor platform advising of the lease period, and deallocating the system resource when the lease period expires.

Claims

1. A method in a system including a first machine having a first invocation component and a second machine having a second invocation component that manages access to a resource, the method performed by the second invocation component comprising:

receiving, from the first invocation component, a request for a lease to the resource for a requested time interval;

providing, to the first invocation component, an indication of a granted lease for a lease period; and

managing access to the resource during the granted lease period such that the resource is reclaimed based on one of (i) a determination that the lease period expired, or (ii) the first machine no longer requires access to the resource; and

allowing the first machine to regain access to the resource when the lease period expires and another machine holds a reference to the resource.

2. The method of claim 1, wherein the second invocation component determines that the first machine no longer requires access to the resource based on an indication that the first machine dropped a reference to the resource.

3. The method of claim 2, wherein managing access includes:

decrementing a reference count when the first machine drops the reference to the resource.

4. The method of claim 3, wherein the resource is reclaimed when the reference count indicates that no machine currently accesses the resource.

5. The method of claim 1, further including:

extending the lease period based on a request received from the first invocation component.

6. The method of claim 1, wherein the granted lease period is for a duration different than a duration of the requested time interval.

7. The method of claim 1, wherein managing access includes:

incrementing a reference count corresponding to the resource.

8. A system including:

a first machine including a first invocation component that manages access to a resource; and

a second machine holding a reference to the resource, including a second invocation component that is configured to request a lease to the resource for a specified period of time, facilitate access to the resource during a respective granted lease period provided by the first invocation component, request an extension to the respective granted lease period, and provide an indication to the first invocation component dropping a reference to the resource,

wherein the first invocation component monitors one or more references to the resource and reclaims the resource when either no more references exist for the resource or all granted lease periods to the resource have expired.

9. The system of claim 8, wherein the first machine grants the extension to the granted lease period.

10. The system of claim 8, wherein the first invocation component allows the second machine to regain access to the resource after the second machine drops the reference to the resource.

11. The system of claim 10, wherein the first invocation component allows the second machine to regain access to the resource when another machine holds a reference to the resource.

12. The system of claim 11, wherein the second machine regains access to the resource following expiration of the granted lease period.

13. The system of claim 8, wherein the first invocation component increments a reference count each time the resource is accessed by a respective machine.

14. The system of claim 8, wherein the first invocation component decrements a reference count each time a machine drops a reference to the resource.

15. The system of claim 14, wherein the first invocation component reclaims the resource when the reference count indicates there are no more references for the resource.

16. The system of claim 8, wherein the second invocation component provides the indication to the first invocation component when the second machine no longer requires access to the resource.

17. A method of managing a resource, comprising:

granting one or more leases to the resource based on respective lease requests including a requested lease period;

determining whether one or more clients hold a reference to the resource;

determining whether a latest agreed lease period for any of the granted one or more leases has expired; and

reclaiming the resource based on the determinations.

18. The method of claim 17, wherein reclaiming the resource includes:

reclaiming the resource when the latest agreed lease period has expired and there are no more references for the resource.

19. The method of claim 17, wherein determining whether one or more clients hold a reference to the resource includes:

monitoring the resource to determine whether the one or more clients no longer require access to the resource.

20. The method of claim 17, wherein determining whether one or more clients hold a reference to the resource includes:

monitoring a reference count reflecting a number of outstanding references to the resource.

21. The method of claim 17, further including:

allowing a first client to regain access to the resource after the first client drops a reference to the resource based on the determinations.

22. The method of claim 17, further including:

receiving from a first client a request to renew a granted lease period.

23. A system comprising:

a plurality of machines, wherein each machine has a first invocation component;

a first resource managing component associated with a first one of the machines configured to grant a first lease to a first resource for a first granted lease period and reclaim the first resource based on a determination that either no more references exist for the first resource or a latest granted lease period to the first resource has expired, and

a second resource managing component associated with the first machine configured to request a second lease to a second resource managed by a second invocation component included in a second machine, request an extension to a second granted lease to the second resource that is granted by the second invocation component, and provide an indication to the second invocation component reflecting that the application dropped a reference to the second resource.

24. The system of claim 23, wherein the first resource managing component of the first machine communicates with a second resource managing component of the second machine to manage access to the resource.

25. The system of claim 23, wherein the first resource managing component maintains a reference count reflecting a number of references held for the resource by one or more of the plurality of machines.

26. The system of claim 25, wherein the first resource managing component increments the reference count each time it receives an indication that an application in one of the machines obtains access to the resource.

27. The system of claim 25, wherein the first resource managing component decrements the reference count each time it determines that an application in one of the machines drops a reference to the resource.

28. The system of claim 23, wherein the invocation managing component grants the first lease for a respective granted lease period based on at least one of a requested lease period and granted lease periods for the resource.

29. A method performed by an object included in a first machine comprising:

receiving a lease to a resource managed by a second machine for a lease period;

accessing the resource during the lease period;

providing an indication to the second machine that the object has dropped a reference to the resource during the lease period; and

regaining access to the resource following the providing step when at least one of the lease period has not expired and the second machine has not reclaimed the resource.

30. The method of claim 29, wherein the object may regain access to the resource following expiration of the lease period when the second machine has not reclaimed the resource.

31. The method of claim 30, wherein following the providing step, the second machine does not reclaim the resource when a third machine holds a reference to the resource.

32. The method of claim 29, wherein receiving the lease includes:

sending a request for the lease, the request including a requested lease period.

33. The method of claim 29, wherein object drops the reference to the resource when the first machine no longer requires access to the resource.

34. The method of claim 29, wherein accessing the resource includes:

requesting an extension for the lease period; and

receiving an indication of a granted lease period extension.

35. A method performed by an object included in a first machine comprising:

receiving, from a second machine, a request for a lease to a resource managed by the object;

granting the lease for a lease period;

managing access to the resource by the second machine during the lease period;

receiving an indication that the second machine has dropped a reference to the resource during the lease period;

receiving a request to regain access to the resource by the second machine; and

preventing access to the resource by the second machine when one of the lease period has expired or the object has reclaimed the resource.

36. The method of claim 35, wherein the object reclaims the resource when either all leases to the resource have expired or no references to the resource exist.

37. The method of claim 35, wherein receiving an indication includes:

monitoring the resource to determine whether the second machine no longer requires access to the resource.

38. The method of claim 35, wherein managing access to the resource includes:

receiving a request for an extension to the lease period; and

granting the extension request based on at least one of the request and other granted leases to the resource.

39. The method of claim 35, wherein the request to regain access is received following receiving the indication that the second machine has dropped the reference.

40. The method of claim 35, further including:

granting a second lease to the resource during the lease period; and

allowing the second machine to regain access to the resource after the second machine has dropped the reference while the second lease still exists.

41. A computer-executable component included within a first machine that performs a method for managing a resource, when executed by the first machine, the method comprising:

granting one or more leases to the resource in response to one or more lease requests from one or more second machines that hold a respective reference to the resource;

managing access by the one or more second machines to the resource during the respective one or more leases; and

reclaiming the resource when all of the one or more leases have expired or all references to the resource no longer exist.

42. A computer-executable component included in a machine that performs a method for managing a resource when executed by the machine, the method comprising:

requesting a lease to a resource managed by a remote machine;

accessing the resource during a lease period granted by the remote machine; and

managing access to the resource, wherein managing includes;

sending an indication to the remote machine that the machine no longer requires access to the resource,

requesting an extension to the lease period, and

regaining access to the resource after the sending of the indication when either the lease period has not expired or another machine holds a reference to the resource.

43. A computer-readable medium including instructions for performing a method, when executed by a processor, in a system including a first machine having a first invocation component and a second machine having a second invocation component that manages access to a resource, the method performed by the second invocation component comprising:

receiving, from the first invocation component, a request for a lease to the resource for a requested time interval;

providing, to the first invocation component, an indication of a granted lease for a lease period; and

managing access to the resource during the granted lease period such that the resource is reclaimed based on one of (i) a determination that the lease period expired, or (ii) the first machine no longer requires access to the resource; and

allowing the first machine to regain access to the resource when the lease period expires and another machine holds a reference to the resource.

44. The computer-readable medium of claim 43, wherein the second invocation component determines that the first machine no longer requires access to the resource based on an indication that the first machine dropped a reference to the resource.

45. The computer-readable medium of claim 44, wherein managing access includes:

decrementing a reference count when the first machine drops the reference to the resource.

46. The computer-readable medium of claim 45, wherein the resource is reclaimed when the reference count indicates that no machine currently accesses the resource.

47. The computer-readable medium of claim 43, wherein the method further includes:

extending the lease period based on a request received from the first invocation component.

48. The computer-readable medium of claim 43, wherein the granted lease period is for a duration different than a duration of the requested time interval.

49. The computer-readable medium of claim 43, wherein managing access includes:

incrementing a reference count corresponding to the resource.

50. A computer-readable medium including instructions for performing, when executed by a processor, a method of managing a resource, the method comprising:

granting one or more leases to the resource based on respective lease requests including a requested lease period;

determining whether one or more clients hold a reference to the resource;

determining whether a latest agreed lease period for any of the granted one or more leases has expired; and

reclaiming the resource based on the determinations.

51. The computer-readable medium of claim 50, wherein reclaiming the resource includes:

reclaiming the resource when the latest agreed lease period has expired and there are no more references for the resource.

52. The computer-readable medium of claim 50, wherein determining whether one or more clients hold a reference to the resource includes:

monitoring the resource to determine whether the one or more clients no longer require access to the resource.

53. The computer-readable medium of claim 50, wherein determining whether one or more clients hold a reference to the resource includes:

monitoring a reference count reflecting a number of outstanding references to the resource.

54. The computer-readable medium of claim 50, further including:

allowing a first client to regain access to the resource after the first client drops a reference to the resource based on the determinations.

55. The computer-readable medium of claim 50, further including:

receiving from a first client a request to renew a granted lease period.

56. A computer-readable medium including instructions for performing a method, when executed by an object included in a first machine, the method comprising:

receiving a lease to a resource managed by a second machine for a lease period;

accessing the resource during the lease period;

providing an indication to the second machine that the object has dropped a reference to the resource during the lease period; and

regaining access to the resource following the providing step when at least one of the lease period has not expired and the second machine has not reclaimed the resource.

57. The computer-readable medium of claim 56, wherein the object may regain access to the resource following expiration of the lease period when the second machine has not reclaimed the resource.

58. The computer-readable medium of claim 57, wherein following the providing step, the second machine does not reclaim the resource when a third machine holds a reference to the resource.

59. The computer-readable medium of claim 56, wherein receiving the lease includes:

sending a request for the lease, the request including a requested lease period.

60. The computer-readable medium of claim 56, wherein object drops the reference to the resource when the first machine no longer requires access to the resource.

61. The computer-readable medium of claim 56, wherein accessing the resource includes:

requesting an extension for the lease period; and

receiving an indication of a granted lease period extension.

62. A computer-readable medium including instructions for performing a method, when executed by an object included in a first machine, the method comprising:

receiving, from a second machine, a request for a lease to a resource managed by the object;

granting the lease for a lease period;

managing access to the resource by the second machine during the lease period;

receiving an indication that the second machine has dropped a reference to the resource during the lease period;

receiving a request to regain access to the resource by the second machine; and

preventing access to the resource by the second machine when one of the lease period has expired or the object has reclaimed the resource.

63. The computer-readable medium of claim 62, wherein the object reclaims the resource when either all leases to the resource have expired or no references to the resource exist.

64. The computer-readable medium of claim 62, wherein receiving an indication includes:

monitoring the resource to determine whether the second machine no longer requires access to the resource.

65. The computer-readable medium of claim 62, wherein managing access to the resource includes:

receiving a request for an extension to the lease period; and

granting the extension request based on at least one of the request and other granted leases to the resource.

66. The computer-readable medium of claim 62, wherein the request to regain access is received following receiving the indication that the second machine has dropped the reference.

67. The computer-readable medium of claim 62, wherein the method further includes:

granting a second lease to the resource during the lease period; and

allowing the second machine to regain access to the resource after the second machine has dropped the reference while the second lease still exists.

68. A system including:

a first machine having a first invocation component; and

a second machine having a second invocation component that manages access to a resource, the second invocation component comprising;

means for receiving, from the first invocation component, a request for a lease to the resource for a requested time interval,

means for providing, to the first invocation component, an indication of a granted lease for a lease period, and

means for managing access to the resource during the granted lease period such that the resource is reclaimed based on one of (i) a determination that the lease period expired, or (ii) the first machine no longer requires access to the resource; and

means for allowing the first machine to regain access to the resource when the lease period expires and another machine holds a reference to the resource.

69. A system for managing a resource, comprising:

means for granting one or more leases to the resource based on respective lease requests including a requested lease period;

means for determining whether one or more clients hold a reference to the resource;

means for determining whether a latest agreed lease period for any of the granted one or more leases has expired; and

means for reclaiming the resource based on the determinations.

70. A first machine including an object comprising:

means for receiving a lease to a resource managed by a second machine for a lease period;

means for accessing the resource during the lease period;

means for providing an indication to the second machine that the object has dropped a reference to the resource during the lease period; and

means for regaining access to the resource following the provision of the indication when at least one of the lease period has not expired and the second machine has not reclaimed the resource.

71. A first machine including an object comprising:

means for receiving, from a second machine, a request for a lease to a resource managed by the object;

means for granting the lease for a lease period;

means for managing access to the resource by the second machine during the lease period;

means for receiving an indication that the second machine has dropped a reference to the resource during the lease period;

means for receiving a request to regain access to the resource by the second machine; and

means for preventing access to the resource by the second machine when one of the lease period has expired or the object has reclaimed the resource.