Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2002-05-24
2004-07-20
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06766432
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 freeing memory within a computing device, such as a smart card, which includes both volatile and non-volatile memory.
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 large 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 can reside in writeable non-volatile memory, such as electrically erasable programmable read only memory (EEPROM) or flash memory. (Within this specification the term “EEPROM” refers to both “EEPROM” and “flash memory.”)
Existing garbage collection techniques are not suitable for EEPROM because individual memory elements in EEPROM 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. Moreover, the process of performing write operations to EEPROM 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-described problems of writeable non-nonvolatile memory. However, the amount of RAM is often extremely limited. Hence, it is not possible to store a complete image of EEPROM in RAM; even a bitmap representing blocks of EEPROM would take up too much space in RAM.
The garbage collection process operates by first deleting unused objects from memory. Once the objects are deleted, the memory space formerly occupied by the objects must somehow be reclaimed. In conventional computing systems, this reclamation process is typically accomplished by performing a compaction operation to eliminate “holes” in memory that arise as a consequence of deleting objects. However, a compaction operation typically involves rewriting a significant portion of memory, which tends to reduce the life expectancy of the EEPROM.
Hence, what is needed is a method and an apparatus for reclaiming memory without requiring the large number of write operations involved in performing a compaction operation.
Furthermore, in computing devices that include both EEPROM and RAM, it is possible to define “transient objects,” which include a portion defined in EEPROM and a portion defined in RAM. In order to support such hybrid objects, what is needed is a method and an apparatus that reclaims memory used by these hybrid objects.
SUMMARY
One embodiment of the present invention provides a system for freeing memory within a computing device. During operation, the system receives a command to free a given segment of memory within the computing device, wherein the command specifies the location of the given segment and the size of the given segment. In response to the command, the system adds the given segment to a free segment table that contains entries for free segments of memory within the computing device. During this process, if the given segment is contiguous with an existing segment in the free segment table, the given segment is concatenated with the existing segment by adding the given segment to an entry for the existing segment in the free segment table.
In a variation on this embodiment, if the given segment is not contiguous with any existing segments in the free segment table, adding the given segment to the free segment table involves adding a new entry for the given segment to the free segment table.
In a variation on this embodiment, if the free segment table is full and the given segment cannot be added to an existing entry in the free segment table, adding the given segment to the free segment table involves allocating an additional free segment table to accommodate the given segment.
In a variation on this embodiment, if the given segment is contiguous with two existing segments in the free segment table, so that the given segment bridges the two existing segments, the system concatenates the given segment and the two existing segments into a single segment and updates the free segment table accordingly.
In a variation on this embodiment, the system additionally allocates a new segment from the free segment table using a “best fit” technique that allocates the smallest segment that is large enough to accommodate the new segment.
In a variation on this embodiment, prior to freeing the given segment, the system deletes an object that occupying the given segment.
In a variation on this embodiment, the memory within the computing device includes writeable non-volatile memory that can only be written to a limited number of times, and is hence not suited for a memory management system that performs compaction because of the large number of write operations involved in a compaction operation.
In a variation on this embodiment, 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 telephone.
REFERENCES:
patent: 5625819 (1997-04-01), Hoffer, Jr.
patent: 5784699 (1998-07-01), McMahon et al.
patent: 6505283 (2003-01-01), Stoney
patent: 6643754 (2003-11-01), Challenger et al.
patent: 6687687 (2004-02-01), Smadja
Ellis Kevin L.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Memory management system supporting object deletion in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management system supporting object deletion in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management system supporting object deletion in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234629