Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2002-05-24
2004-05-11
Ellis, Kevin L. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S103000
Reexamination Certificate
active
06735680
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to the process of managing memory in a computer system. More specifically, the present invention relates to a method and an apparatus for deleting objects from memory in a computing device, such as a smart card.
2. Related Art
Dramatic advances in computer technology presently make it possible to integrate a significant amount of computing power onto a “smart card”. This increased computing power enables smart cards to support larger numbers of applications. However, unlike conventional computing systems, smart card-based computing systems do not presently provide a mechanism for reclaiming memory occupied by objects that are no longer in use. This process of reclaiming unused memory is often referred to as “garbage collection”.
Garbage collection can be performed in conventional computing systems using a number of well-known techniques. However, smart card-based computing systems are different than conventional computing systems because objects (or portions of objects) can reside in writeable non-volatile memory, such as electrically erasable programmable read only memory (EEPROM) or flash memory.
Existing garbage collection techniques are not suitable for EEPROM or flash memory because individual memory elements in EEPROM and flash memory can only be written to a limited number of times. Hence, existing garbage collection techniques, which operate by frequently marking objects in memory, can dramatically reduce the life expectancy of EEPROM or flash memory. Moreover, the process of performing write operations to EEPROM or flash memory is typically very slow, which can significantly degrade system performance.
Smart cards often contain a small amount of volatile random access memory (RAM), which does not suffer from the above-mentioned problems of writeable non-nonvolatile memory. However, the amount of RAM that is available on a smart card is often limited. Hence, it is not possible to store a complete image of EEPROM or flash memory in RAM; even a bitmap representing blocks of EEPROM or flash memory would take up too much space in RAM. Moreover, commonly used recursive techniques mark objects take up too much stack space in RAM.
Hence, what is needed is a method and an apparatus for deleting objects from memory within a computing device, such as a smart card, without the problems described above.
SUMMARY
One embodiment of the present invention provides a system for deleting objects from a memory in a computing device, wherein the memory includes both a volatile memory and a non-volatile memory that is writeable. During operation, the system receives a request to perform an object deletion operation, which locates and deletes unused objects from the memory. In response to this request, the system performs the object deletion operation by first performing a marking operation that marks objects that are reachable in the non-volatile memory. This marking operation does not directly mark the objects in the non-volatile memory, but instead marks data values in the volatile memory that are associated with the objects. In this way, unnecessary write operations to non-volatile memory are avoided. Next, the system performs a sweep operation that deletes unmarked objects from the non-volatile memory.
In a variation on this embodiment, the request to perform the object deletion operation is received from an application program.
In a variation on this embodiment, the object deletion operation takes place during a time interval between requests from the application program.
In a variation on this embodiment, performing the marking operation involves first identifying roots within the memory, and then marking objects that are directly or indirectly reachable through references from the roots. Note that the roots can be located by examining static variables that point to objects, or by examining an applet table that contains references to applet objects.
In a variation on this embodiment, the data values in the volatile memory are stored as a bitmap in the volatile memory. This bitmap includes a bit corresponding to each object located within the non-volatile memory. Space for this bitmap can be allocated from unused stack space within the volatile memory.
In a variation on this embodiment, the marking operation is performed through an iterative process that does not use unbounded recursion. This avoids the need for a large amount of stack space to perform an unbounded recursive marking operation.
Note that the computing device can be located within a smart card that can be part of, an identification card, a client loyalty card, or an electronic wallet, or can be located within a cellular phone, or a data card.
Furthermore, the non-volatile memory that is writeable can include: an electrically erasable read only memory (EEPROM), a flash memory, or a magnetic memory device.
REFERENCES:
patent: 5933847 (1999-08-01), Ogawa
patent: 6604168 (2003-08-01), Ogawa
Ellis Kevin L.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for deleting objects from memory within... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for deleting objects from memory within..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for deleting objects from memory within... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239195