Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-09
2001-08-07
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C711S154000, C711S173000, C711S166000, C370S354000, C370S522000, C235S380000, C235S382000
Reexamination Certificate
active
06272504
ABSTRACT:
TECHNICAL FIELD
The invention concerns a novel approach for the identification and collection of ‘garbage’ (memory sections that contain information not needed anymore). This approach is well suited for use in systems with memory of limited size, such as integrated circuit cards (e.g. smartcards).
BACKGROUND OF THE INVENTION
Object-based application programs (written in Java, C++, or the like) usually operate on directed graphs. These graphs comprise root objects and regular objects which are interconnected by means of pointers. During the execution of an object-based application program the graph dynamically changes as objects and/or pointers are added, modified or removed.
Object-based execution environments often support the application developer in one of the most tedious and error-prone tasks in programming, namely memory handling. In many systems, objects are only allocated by the application program, but never explicitly de-allocated. In these systems it is the task of a so-called garbage collector (GC) to determine which objects are no longer needed. Furthermore, the GC frees-up the respective memory and returns it to the heap of unused memory. A GC must, every once in a while, clean up wasted memory. In addition, the GC might be used to compact memory by eliminating the gaps created by fragmentation.
Cleaning up the garbage in memory is usually done in two steps, referred to as marking and sweeping. The current SUN Java garbage collector also uses the mark-and-sweep approach according to which every root object in the system is marked initially. Then one follows all the object references inside those objects to other objects not yet marked, and so on, recursively. Finally, when there are no more references to follow, all the unmarked objects are deleted.
Current GC schemes are not well suited for use in resource constrained systems because these GC schemes require more volatile memory which than usually available in these kind of systems.
An integrated circuit card (ICC), more widely known as smartcard, is one example of such a resource constrained system. Other examples are: mobile and/or hand held devices, such as cellular phones, pagers, personal digital assistants, personal area network devices, and so forth.
In the following, we will focus mainly on ICCs and smartcards in particular. The smartcard concept began in Europe prior to 1985, and is today being used in telephone systems, toll roads, game parlors, and personal computers, just to mention some applications.
In the following, the term integrated circuit card will be used, because ISO uses the term to encompass all those devices where an integrated circuit is contained within a card-size piece of plastic, or the like.
Typical ICCs comprise a microprocessor (central processing unit, CPU), a read-only memory (ROM), a volatile random-access memory (RAM), and some type of non-volatile, programmable memory, such as an EEPROM (electrically erasable programmable read only memory). In addition, an ICC usually comprises some kind of a bus (such as a serial bus) and I/O ports for interconnection to a card terminal.
The contents of the ROM type of memory is fixed and can not be changed once manufactured by the semiconductor company. This is a low cost memory, in that it occupies minimum space on the substrate. It is a disadvantage of a ROM that it cannot be changed and that it takes several months to be produced. As opposed to this, an EEPROM is erasable by the user and can be rewritten many times. ROMs and EEPROMs are non volatile. In other words, when the power is removed they still retain their contents.
A RAM is a volatile memory and as soon as the power is removed the data content is lost. A RAM, however, has the advantage that it is much faster than ROMs and EEPROMs. On the other hand, a RAM is more expensive in terms of die size. Usually, the RAM is relatively small. RAM is not used at all for any type of operation involving data that has to be kept permanent and consistent. Unfortunately, always using non-volatile memory has a couple of serious drawbacks. One is the extreme performance penalty that has to be paid as every memory write access is roughly 500 to thousand times slower when using EEPROM instead of RAM. An even more serious problem is the limitation on the amount of guaranteed write cycles (100000 times for EEPROM).
It is an object of the present invention to provide a novel garbage identification and garbage collection scheme, and in particular garbage identification and garbage collection scheme which is well suited for use in resource constrained systems.
It is an object of the present invention to provide a solution for garbage collection in resource constrained systems, such as an integrated circuit cards.
SUMMARY OF THE INVENTION
The present invention concerns a scheme for the distinguishing of reachable objects and non-reachable objects used by an object-based application in a system with volatile memory of limited size. The object-based application operates on n objects whereby Z thereof are root objects. The following steps are carried out for each root object
traversing from said root object to any other object that can be reached from said root object,
marking all objects that were reached from said root object and storing, while marking, in said volatile memory a description of the path from said root object to the currently visited object,
if the marking phase reaches an object and the respective path does not fit into said volatile memory,
then this object is not marked but identified as an object which has to be processed later,
continuing the marking phase until all root objects and all objects identified as objects which have to be processed later are processed.
The inventive scheme minimizes the amount of state needed to perform a garbage collection. Furthermore, the inventive allows for a flexible tradeoff between execution time and runtime space requirements. The scheme is well suited for use in systems with constrained resources.
REFERENCES:
patent: 4989132 (1991-01-01), Mellender et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5535390 (1996-07-01), Hilderbrandt
patent: 5577246 (1996-11-01), Priddy et al.
patent: 5659736 (1997-08-01), Hasegawa et al.
patent: 5799185 (1998-08-01), Watanabe
patent: 6098089 (2000-08-01), O'Connor et al.
patent: 6199075 (2001-03-01), Ungar et al.
Huelsbergen, Lorenz et al., “Very Concurrent Mark-&-Sweep Garbage Collection without Fine-Grain Synchronization”, Bell Labs, Lucent Technologies, Murray Hill, NJ; ACM, Oct. 1998, pp. 166-175.*
Lieberman, Henry et al., “A Real-Time Garbage Collector Based on the Lifetimes of Objects”, Communications of the ACM, Jun. 1983, vol. 26, No. 6, pp. 419-429.*
Persson, Patrik et al., “An Interactive Environment for Real-Time Software Development”, Proceedings of the 33rd International Conference on Technology of Object-Oriented Languages, 2000, TOOLS. Jun. 5-8, 2000, pp. 57-68.*
Siebert, Fridtjof, “Hard real-time garbage collection in the Jamaica Virtual Machine”, Sixth International Conference on Real-Time Computing Systems and Applications, 1999 RTCSA, Dec. 13-15, 1999, pp. 96-102.
Baentsch Michael
Buhler Peter
Eirich Thomas
Hoering Frank
Oestreicher Marcus
Alam Hosain T.
Alam Shahid
August Casey P.
International Business Machines - Corporation
LandOfFree
Flexibly deleting objects in a resource constrained environment does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexibly deleting objects in a resource constrained environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexibly deleting objects in a resource constrained environment will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2461686