Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-03
2001-11-27
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S201000, C709S238000, C709S243000, C711S159000, C711S160000
Reexamination Certificate
active
06324549
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a distributed system, a memory management device and method, and to a storage medium, and in particular to memory management for distributed computing.
2. Description of the Related Art
An automatic memory management device and memory management method for distributed computing is considered with the purpose of realizing automatic memory management and garbage collection, not in one single memory space, but in a plurality of memory spaces in a distributed system.
In a paper by D. I. Bevan, “Distributed Garbage Collection Using Reference Counting” (Springer Verlag, LN CS 259, June 1987, pages 176-187), an automatic memory management device that uses a weighted reference counting method manages memory by adding a “reference weight,” a numerical value, to objects that reference, i.e., that remote-reference, objects in a different memory space.
In a case in which an object is created that has a remote reference to another object, an initial value of a numerical value (exponentiation of 2) particular to an object and referred to as “total reference weight” is set to the referenced object that is remotely referenced; and a numerical value particular to remote referencing to a referenced object, which is referred to as “partial reference weight,” is set to the referencing object that remote-references. Remote reference is thus “created.”
In
FIG. 1
, for example, if the initial value for total reference weight is “64,” referenced object
11
holds a total reference weight of “64” and reference object
10
that remote-references referenced object
11
has a partial reference weight of “64” with respect to referenced object
11
.
In a case in which a reference object that remotely references an object gives information of the referenced object to a third object by means of a communication message, the reference object subtracts half of its own partial reference weight and updates its new partial reference weight as half. The reference object includes the other half of the reference weight in the communication message to the third object.
The third object accepts the reference weight contained in this communication message and stores the received reference weight as its own partial reference weight. In this way, a reference object can make a reference to a referenced object, and remote reference can be “distributed” from a reference object to a third object.
A difference exists between the “distribution” of remote reference and the “creation” of remote reference in that a third object that receives “distribution” of reference resides in a different memory space than the memory space of the reference object that distributes weight and the memory space of the referenced object. In “distribution” of remote reference, moreover, the total reference weight is constant, and the total reference weight is therefore always equal to the sum of the partial reference weights belonging to reference objects and the sum of reference weight pertaining to objects contained in all communication messages that flow in a distributed system.
For example, in a case in which reference object
10
from the state in
FIG. 1
transfers the information of referenced object
11
to object
12
, reference object
10
decreases its own partial reference weight “64” by half to “32” as shown in FIG.
2
. Reference object
10
includes its decreased weight “32” in a communication message and sends this to object
12
. Upon accepting this communication message, object
12
makes its own partial reference weight “32” and becomes a reference object as shown in FIG.
3
.
When a reference object is no longer necessary in the memory space in which it resides, it transmits to a referenced object a reference deletion message containing information of it own partial reference weight. This “deletion” of remote referencing enables reclamation of unneeded memory region and reuse.
In
FIG. 4
, for example, when it is determined that reference object
10
having a partial reference weight of “32” is no longer necessary, a reference deletion message containing the reference weight “32” is transmitted to referenced object
11
, which is the reference destination. Upon receiving this reference deletion message, referenced object
11
updates by subtracting the received reference weight “32” from the total reference weight, as shown in FIG.
5
. When the total reference weight of a referenced object becomes “0,” it can be determined that there are no longer any objects referencing the object from other memory spaces. If there is no referencing from the memory region in which the referenced object itself resides, the regions of that referenced object can be reclaimed.
A reference object having a partial reference weight that has become “1” cannot “distribute” remote referencing. In such a case, the reference object creates a new indirect object that indirectly remote-references and causes the created indirect object to indirectly remote-reference.
In
FIG. 6
, for example, when reference object
20
having a partial reference weight that has become “1” “distributes” remote referencing to object
22
, reference object
20
creates indirect object
23
as shown in FIG.
7
. Indirect object
23
takes over the partial reference weight of “1” of reference object
20
. Indirect object
23
maintains the reference to referenced object
21
and stores a total reference weight of “64.” Reference object
20
updates remote referencing from referenced object
21
to indirect object
23
, and makes the partial reference weight “64.”
Reference object
20
distributes the reference weight by sending a message containing weight “32” to object
22
. After accepting this reference weight, object
22
can remote-reference indirect object
23
with a partial reference weight of “32” as shown in FIG.
8
.
Nevertheless, the automatic memory management device of the above-described prior art (hereinafter referred to as “the prior art”) has the following problems.
First, the prior art cannot realize memory management when the data region of, for example, an object, is migrated between computers.
In recent years, a method referred to as “agent” is being studied in which the execution of an object is resumed or the execution environment of an object is migrated from a particular execution environment to a different execution environment in a network.
In an agent method, the data region itself of an object, or the memory region itself that is occupied by the agent, changes its execution environment, i.e., the region migrates.
In a distributed system in which an agent or an object region accompanying this agent migrates in this way, automatic memory management is necessary to enable an object that referenced an object before migration to continue to reference the object after migration, despite the migration of the referenced object.
In the prior art, however, it was assumed that data regions of, for example, objects, are stationary in the memory space in which they were created. The prior art therefore did not consider even the existence of migrating objects, and memory management of such objects was therefore impossible.
A second problem in the prior art is the increase in the amount of communication in the network.
In a distributed system made up of a wide range of networks such as the Internet, objects increasingly reference data regions of different computers from remote computers. This trend is further increased by the agent migration and object migration described in regard to the first problem.
In addition, due to agent migration and object migration, the situation frequently occurs that the actual data do not reside at the reference destination of maintained data, but can only be referenced after tracing yet another reference destination.
To reference data regions on a computer at a remote site, a reference request communication message must be sent to the computer of the reference destination to have the requested data sent back. A multi-step exchange of communication
Fujita Satoru
Gomi Hidehito
Alam Hosain T.
Ly Anh
McGinn & Gibb PLLC
NEC Corporation
LandOfFree
Distributed system and memory management device, method, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed system and memory management device, method, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed system and memory management device, method, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612476