US5819299A — Process for distributed garbage collection

Claim 1

Independent Claim 285 words

In a distributed computer system having a plurality of concurrently active processes that have instantiated a plurality of objects in a memory associated with the distributed computer system, a method of operating the distributed computer system comprising the steps of: selecting a suspect object from the plurality of objects for testing to determine whether said suspect object is garbage; identifying an inverse reference graph for said suspect object wherein each object of a subset of objects of the plurality of objects referentially coupled to said suspect object are represented as nodes on said inverse reference graph and wherein each edge between a pair of nodes defines a referential relationship between a pair of objects of said subset of the plurality of objects; testing each branch of said inverse graph coupled from a suspect node associated with said suspect object to a referring node associated with a referring object to determine whether any branch of said inverse reference graph is relevant to establish whether said suspect object is garbage; wherein said testing step comprises the steps of: generating an identifier; transmitting a root request message, tagged with said identifier, to each object of a plurality of referring objects of said suspect object as identified by branches of said inverse reference graph originating from said suspect object wherein each branch receives a separate root request message tagged with said identifier; and receiving a reply message, tagged with said identifier, from each branch, each said reply message from any particular branch indicating whether said particular branch is to be disregarded for determining whether said suspect object is garbage; and identifying said suspect node as garbage when no branch is relevant to establish whether said suspect node is garbage.

Claim 2

Dependent Claim 285 words

In a distributed computer system having a plurality of concurrently active processes that have instantiated a plurality of objects in a memory associated with the distributed computer system, a method of operating the distributed computer system comprising the steps of: selecting a suspect object from the plurality of objects for testing to determine whether said suspect object is garbage; identifying an inverse reference graph for said suspect object wherein each object of a subset of objects of the plurality of objects referentially coupled to said suspect object are represented as nodes on said inverse reference graph and wherein each edge between a pair of nodes defines a referential relationship between a pair of objects of said subset of the plurality of objects; testing each branch of said inverse graph coupled from a suspect node associated with said suspect object to a referring node associated with a referring object to determine whether any branch of said inverse reference graph is relevant to establish whether said suspect object is garbage; wherein said testing step comprises the steps of: generating an identifier; transmitting a root request message, tagged with said identifier, to each object of a plurality of referring objects of said suspect object as identified by branches of said inverse reference graph originating from said suspect object wherein each branch receives a separate root request message tagged with said identifier; and receiving a reply message, tagged with said identifier, from each branch, each said reply message from any particular branch indicating whether said particular branch is to be disregarded for determining whether said suspect object is garbage; and identifying said suspect node as garbage when no branch is relevant to establish whether said suspect node is garbage.

Claim 3

Dependent Claim 30 words

The distributed computer operating method of claim 1 wherein said identifying step establishes said suspect node as garbage when all said reply messages indicate all branches are to be disregarded.

Claim 4

Dependent Claim 54 words

The distributed computer operating method of claim 2 further comprising the step of replying with a disregard message to every transmitting object that transmits to a particular referring object a root request message having said identifier while said referring object is resolving a previously received root request message that is tagged with said identifier.

Claim 5

Dependent Claim 23 words

The distributed computer operating method of claim 3 wherein a particular branch is relevant when any object in said particular branch is rooted.

Claim 6

Dependent Claim 36 words

The distributed computer operating method of claim 4 wherein said identifying step identifies said suspect object as garbage whenever each reply message from each branch in response to said root request message is a disregard message.

Claim 7

Dependent Claim 252 words

In a distributed computer system having a plurality of concurrently active processes that have instantiated a plurality of objects in a memory associated with the distributed computer system, a method of operating the distributed computer system comprising the steps of: establishing a suspect list of a subset of said plurality of objects wherein said subset of objects are candidates for garbage collection; selecting a first object from said suspect list; defining an inverse reference graph for said first object wherein each object of said plurality of objects referentially coupled to said first object is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects; generating an identifier; transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by said inverse reference graph; receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage; and identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects indicates any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage.

Claim 8

Dependent Claim 252 words

In a distributed computer system having a plurality of concurrently active processes that have instantiated a plurality of objects in a memory associated with the distributed computer system, a method of operating the distributed computer system comprising the steps of: establishing a suspect list of a subset of said plurality of objects wherein said subset of objects are candidates for garbage collection; selecting a first object from said suspect list; defining an inverse reference graph for said first object wherein each object of said plurality of objects referentially coupled to said first object is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects; generating an identifier; transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by said inverse reference graph; receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage; and identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects indicates any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage.

Claim 9

Dependent Claim 56 words

The distributed computer operating method of claim 6 further comprising the step of: replying with a disregard message from said first object, prior to said identifying step and in response to a particular root request message tagged with said identifier and received from a second one object of said plurality of objects, to said second object.

Claim 10

Dependent Claim 30 words

The distributed computer operating method of claim 6 further comprising the step of: collecting, after said identifying step, said first object from said memory when said first object is garbage.

Claim 11

Dependent Claim 100 words

The distributed computer operating method of claim 6 wherein a first referring object of said subset of said plurality of referring objects is instantiated in a first portion of said memory that is associated with a first process of the plurality of concurrently active processes that is active in a first machine and wherein a second referring object of said subset of said plurality of referring objects is instantiated in a second portion of said memory associated with a second process of the plurality of concurrently active processes that is active in a second machine different from said first machine.

Claim 12

Dependent Claim 238 words

A computer system, comprising: a multiplicity of concurrently active processes executing on a plurality of machines for instantiating a plurality of objects; a memory, coupled to said plurality of machines, for storing said plurality of objects; and garbage identification means, coupled to said memory, for: maintaining a suspect list of a subset of said plurality of objects that are candidates for garbage collection; selecting a first object from said suspect list; generating an identifier; transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by an inverse reference graph, wherein each object of said plurality of objects is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects; receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage; and identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects, indicates any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage.

Claim 13

Dependent Claim 238 words

A computer system, comprising: a multiplicity of concurrently active processes executing on a plurality of machines for instantiating a plurality of objects; a memory, coupled to said plurality of machines, for storing said plurality of objects; and garbage identification means, coupled to said memory, for: maintaining a suspect list of a subset of said plurality of objects that are candidates for garbage collection; selecting a first object from said suspect list; generating an identifier; transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by an inverse reference graph, wherein each object of said plurality of objects is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects; receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage; and identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects, indicates any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-10-05	2002-04-06	2002-10-06	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-10-05	2006-04-06	2006-10-06	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-10-05	2010-04-06	2010-10-06	$7700.00	Window Closed / Lapsed

Process for distributed garbage collection

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag