Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-29
2001-11-27
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06324550
ABSTRACT:
FOREIGN APPLICATION PRIORITY DATA
This application takes priority under 35 U.S.C. §119 from Australian Provisional Patent Application No. TQ4125, filed Nov. 18, 1999, and from Australian Provisional Patent Application No. PQ2441, filed Aug. 25, 1999.
The present invention relates to a data object removal system and, more particularly, to such a system particularly suited, although not exclusively, for the identification of and subsequent removal of unused or unusable data objects in a memory system of a computer system, thereby to free up system resources and, more particularly, memory resources.
BACKGROUND
All computer operating systems utilise memory systems for the storage and manipulation of data. During usage it typically occurs that portions of memory contain data which is no longer required. The system needs to be made aware that these memory portions have become available for further use. In one sense it can be said that these memory portions now contain “garbage” and there is a requirement to collect the “garbage” so as to free up the memory resources for further system-use.
In an “object oriented” form of computer system the system can be thought of as producing and using objects, the “objects” being data objects having data fields which either contain data values or pointers to objects.
FIG. 1
illustrates a generalised object oriented system
301
containing a first data object
302
and a second data object
303
. The first data object
302
comprises a single data record having a number of different data fields, one of which is a pointer field
304
containing data which points to (that is, contains the memory location of) a data field
305
containing numbers in second data object
303
.
In such a system memory resources can become unavailable where, for example, data objects come to point back to each other forming an island
306
.
In order to get rid of this “garbage” thereby to free unused system resources most systems use some form of garbage collection.
Two commonly used current forms are “reference counting” and “mark/sweep”.
Problems with current systems include inability to locate islands, a requirement that the operating system suspend processing while garbage is being collected and a general inability to consistently and comprehensively first identify and then remove unwanted or unused data objects (garbage).
It is an object of the present invention, in at least some preferred embodiments, to address or ameliorate one or more of the abovementioned problems.
BRIEF DESCRIPTION OF INVENTION
Accordingly, in accordance with one aspect one broad form of the invention there is provided a method of identification of unused data blocks in a computer system; said computer system performing computer functions by way of a plurality of tasks; each data block having a unique reference; said method comprising the steps of:
(a) designating a special purpose task as a cleaner task which identifies unused data blocks;
(b) each task adapted to indicate to the cleaner task the identity of a unique reference which it has displaced.
Preferably said cleaner task, during execution, takes into account the identity of those unique references which are indicated as having been displaced.
In accordance with a further aspect of the invention there is provided, in a computer system which includes objects with references between objects forming an at least first directed graph; said computer system performing computing functions by way of a plurality of tasks each of which operate with or on said objects and at least one of which tasks is designated as a cleaner task; the system having the property that it is possible for the cleaner task to discover all objects and all starting points; each of said tasks adapted to indicate to the cleaner task the identify of any handle which has been displaced;
a method of identification of unused ones of said objects, said method comprising the steps of, in order:
(a) initiating said cleaner task, said cleaner task defining a set of unused objects which comprises initially all objects in said system;
(b) said cleaner task traversing said directed graphs commencing at the respective initial starting points of said graphs; during traverse, removing from said set of unused objects the handle of each said object encountered during the traverse;
(c) said cleaner task traversing all graphs for which the starting point is any handle which has been identified as displaced during execution of step b; and, during traverse, removing from said set of unused objects the handle of each said object encountered during the traverse.
In accordance with a further aspect of the invention there is provided a method of removal or release of unused objects from a computer system of the type described above; said method comprising the steps of:
(a) following the above described method of identification in order to identify a set of unused objects,
(b) making available to said system for re-use the memory locations occupied by said set of unused objects.
In accordance with a further aspect of the invention there is provided a data object identification system operating according to the above described method.
In accordance with a further aspect of the invention there is provided a data object identifier and removal system operating according to any one of the above described methods and wherein said cleaner task makes available to said computer system for reuse data objects which have been identified as unused data objects.
In accordance with a further aspect of the invention there is provided a computer architecture which supports a cleaner task; said architecture arranged, in an at least first mode of operation to take and store elsewhere a value immediately prior to said value being over-written.
Preferably said value which is stored elsewhere is accessible to a cleaner task.
In one preferred form the computer architecture is implemented in hardware.
In an alternative preferred form the computer architecture is implemented in software.
In yet an alternative preferred form the computer architecture is implemented in microcode.
In yet a further aspect of the invention there is provided a method of identification of unused data blocks in a computer system implemented as a cleaner task which can run concurrently with other tasks performed by the computer system; each data block having a unique reference; said method comprising the steps of:
(a) designating a special purpose task as said cleaner task which identifies unused data blocks;
(b) each task adapted to indicate to the cleaner task that it has caused a unique reference to be overwritten.
Preferably said cleaner task, during execution, takes into account the identity of those unique references which are indicated as having been displaced.
REFERENCES:
patent: 5274804 (1993-12-01), Jackson et al.
patent: 5355483 (1994-10-01), Serlet
patent: 5398334 (1995-03-01), Topka et al.
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5561785 (1996-10-01), Blandy et al.
patent: 5692185 (1997-11-01), Nilsen et al.
patent: 225755 (1987-06-01), None
patent: 288146 (1988-10-01), None
patent: 0 395 606 (1994-10-01), None
patent: 0 881 576 A1 (1998-12-01), None
Black Thomas
Bullant Technology Pty Ltd
Mills John G.
Stetina Brunda Garred & Brucker
LandOfFree
Data object identification and removal system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data object identification and removal system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data object identification and removal system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617449