Fault tolerant distributed garbage collection system and method for collecting network objects

• US 5,446,901 A
• Filed: 06/30/1993
• Issued: 08/29/1995
• Est. Priority Date: 06/30/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Owicki, Susan S., Wobber, Edward P., Birrell, Andrew D., Nelson, Charles G.
• Primary Examiner(s): Heckler, Thomas M.
• Assistant Examiner(s): BACKENSTOSE, JONATHAN
• Application Number:
  US08/085,407
• Time in Patent Office: 790 Days
• Field of Search: 395/650, 395/700, 364/228.7, 364/228.8, 364/280, 364/281.1, 364/284, 364/284.3, 364/284.4
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

A distributed computer system includes a multiplicity of concurrently active processes. Each object is owned by one process. Objects are accessible to processes other than the object'"'"'s owner. Each process, when it receives a handle to an object owned by any other process, sends a first "dirty" message to the object'"'"'s owner indicating that the object is in use. When a process permanently ceases use of an object handle, it sends a second "clean" message to the object'"'"'s owner indicating that the object is no longer in use. Each object'"'"'s owner receives the first and second messages concerning usage of that object, stores data for keeping track of which other processes have a handle to that object and sends acknowledgement messages in return. The receiver of an object handle does not use the handle until its first message is acknowledged. Periodically, the object'"'"'s owner sends status request messages to other processes with outstanding handles to that object to determine if any of those processes have terminated and updates its stored object usage data accordingly. A garbage collection process collects objects for which the usage data indicates that no process has a handle. The first and second messages include sequence numbers, wherein the sequence numbers sent by any process change in value monotonically in accordance with when the message is sent. Object owners ignore any message whose sequence number indicates that it was sent earlier than another message for the same object that previously received from the same process.

Claims

1. In a computer system having a multiplicity of concurrently active processes, a method of operating the distributed computer system comprising the steps of:

storing objects in at least one computer memory, each object being owned by one of said multiplicity of processes;

for each of a plurality of said objects, distributing handles for accessing said each object to processes other than the process that owns said each object;

each process further performing the steps of;

upon receiving a handle to an object owned by any other process, sending a first message to the other process that owns said object, wherein said first message identifies said object and the process which received said handle;

upon releasing a handle to an object owned by any other process, sending a second message to the process that owns said object, wherein said second message identifies said object and the process which released said handle;

receiving ones of said first message for objects owned by said each process and storing object usage data indicating which other processes have a handle to each object owned by said each process;

receiving ones of said second message for objects owned by said each process and deleting corresponding portions of said object usage data;

sending status request messages to said other processes that said stored object usage data indicates have handles to objects owned by said each process to determine if any of said other processes have terminated, and deleting portions of said object usage data corresponding to those of said other processes determined to have terminated; and

garbage collecting objects owned by said each process for which said usage data indicates that no process has a handle.

2. The method of claim 1, each process further performing the steps of:

upon receiving said ones of said first message, sending an acknowledgement of said first message to the process that sent said first message;

after sanding said first message, waiting to use said received handle until said acknowledgement has been received from the owner of the object corresponding to said received handle.

3. The method of claim 1, wherein

said steps of sending said first message and sanding said second message include sending a sequence number with each of said first and second messages, wherein said sequence numbers sent by any process change in value monotonically in accordance with when said process sent each corresponding message;

and

said receiving steps including ignoring said received message when said sequence number sent with said received message indicates that it was sent earlier than another message previously received from the same process that sent said received message.

4. A method of operating a computer system, comprising the steps of:

concurrently running a multiplicity of processes, including a server process and a plurality of client processes;

each process running in a distinct address space;

storing objects owned by the server process in the address space of said server process;

distributing to ones of said client processes handles for accessing each of a plurality of said objects owned by said server process;

each client process, upon receiving a handle to an object owned by said server process, sending a first message to said server process, wherein said first message identifies said object and said each client process;

each client process releases said received handle to said object owned by said server process, and sending a second message to said server process, wherein said second message identifies said object for which said received handle was released and further identifies said client process which released said handle;

said server process receiving ones of said first message and storing object usage data indicating which client processes have a handle to each object owned by said server process;

said server process receiving ones of said second message and deleting corresponding portions of said object usage data;

said server process sending status request messages to those of said client processes that said stored object usage data indicates have handles to objects owned by said client process to determine if any of said client processes have terminated, and deleting portions of said object usage data corresponding to those of said client processes determined to have terminated; and

said server process garbage collecting objects for which said usage data indicates that no process has a handle.

5. The method of claim 4, further including the steps of:

said server process, upon receiving each said first message, sending an acknowledgement of said first message to the client process that sent said each first message;

each client process, after sending said first message, waiting to use said received handle to the object identified in said first message until said acknowledgement has been received from said server process.

6. The method of claim 4, wherein

said steps of sending said first message and sending said second message include sending a sequence number with each of said first and second messages, wherein said sequence numbers sent by any client process change in value monotonically in accordance with when said client process sent each corresponding message;

and

said receiving steps including ignoring said received message when said sequence number sent with said received message indicates that it was sent earlier than another message previously received from the same process that sent said received message.

7. A computer system, comprising:

a multiplicity of concurrently active processes;

memory means for storing objects, each object being owned by one of said multiplicity of processes;

handles, held by various ones of said processes, for each of a plurality of said objects, each handle enabling access to a corresponding object by a process other than the process that owns said each object;

each process including;

first message sending means for sending a first message, upon receiving a handle to an object owned by any other process, said first message being sent to the other process that owns said object, wherein said first message identifies said object and the process which received said handle;

second message means for sending a second message, upon releasing a handle to an object owned by any other process, said second message being sent to the process that owns said object, wherein said second message identifies said object and the process which released said handle;

object usage tracking means for receiving ones of said first message for objects owned by said each process and for storing object usage data indicating which other processes have a handle to each object owned by said each process;

said object usage tracking means including means for receiving ones of said second message for objects owned by said each process and deleting corresponding portions of said object usage data;

status checking means for sending status request messages to said other processes that said stored object usage data indicates have handles to objects owned by said each process to determine if any of said other processes have terminated, and for deleting portions of said object usage data corresponding to those of said other processes determined to have terminated; and

garbage collection means for garbage collecting objects owned by said each process for which said usage data indicates that no process has a handle.

8. The computer system of claim 7,

said object usage tracking means including means, responsive to receiving said ones of said first message, for sending an acknowledgement of said first message to the process that sent said first message;

each said process including means for preventing, after sending said first message, use of said received handle until said acknowledgement has been received from the owner of the object corresponding to said received handle.

9. The computer system of claim 7, wherein

said first message sending means and said second message sending means include means for sending a sequence number with each of said first and second messages, wherein said sequence numbers sent by any process change in value monotonically in accordance with when said process sent each corresponding message;

and

said object usage tracking means including means for ignoring said received message when said sequence number sent with said received message indicates that it was sent earlier than another message previously received from the same process that sent said received message.