Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-05-21
2001-08-28
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C711S110000, C711S217000, C711S218000, C711S219000
Reexamination Certificate
active
06282700
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This application relates in general to flash, non-volatile memory, and in specific to a mechanism that maintains multiple updates of an object in the memory without regard to a number of updates of the object by using a cyclic tagging mechanism.
BACKGROUND OF THE INVENTION
Flash memory, or memory which can be electronically erased and reprogrammed, is also known as EEPROM. Flash memory, which unlike ordinary RAM, does not lose the stored information upon a power off condition. Many products or designs maintain objects, and their revisions, including program code, login data, operating parameters, usage settings, and firmware, in flash memory, to allow these objects to be changed during use, but retained after loss of power. Flash memory is typically used in PC BIOS initialization operations. Most products that embed such objects offer facilities for replacing or modifying their contents. For example, the operating firmware for a given device, such as a magnetic disk, may be updated.
A problem arises during a flash update, in that the update process may not complete. Thus, the updated revision may be incomplete, and unusable. If the system only maintains a single copy in a single allocated storage area, meaning that no prior versions exist, then the system can suffer loss of state if an error occurs while the object is being replaced.
A prior art alternative to the single copy mechanism is to maintain prior versions of the object. However, updating these objects can cause multiple revisions of objects to be present, and thus requires a mechanism to determine which object is valid and should be used. Typically, a version is considered valid if it is the most recent, complete version. The second mechanism has a larger storage area, in which multiple revisions of the object may be maintained, where only one is active, usually the valid version. The prior art assigns each version a tag which is incremented via a counter after each assignment. During initialization of the system, a software algorithm examines the tags, and thus determines which object to activate.
However, such implementations that store multiple revisions using a finite revision tags have problems when the revision tag reaches its maximal value. The next tag value is then the lowest tag, and thus, the most recent version is tagged with the lowest value tag, and since applications assume that the highest tag value represents the most recent version, the most recent version will not be used during system operations. This is known as rollover effects. Note that the tags are represented by a fixed field, and the tag is usually an index or revision number, or a date code. These tag fields are limited in that they have an inherent maximum value, due to the physical size of the storage allocated for maintaining the tag field. The consequence of this bounded tags and rollover effects is that revision management algorithms may generate indeterminate, and hence incorrect, results.
Therefore, there is a need in the art for a mechanism that will allow multiple versions of objects to be stored in a non-volatile memory without the rollover limitations of bounded tags.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which uses a cyclic tagging mechanism or state mechanism that permits the location of the latest object revision, (as well as its predecessors) and eliminates boundary condition constraints.
The inventive state mechanism uses a particular number of predetermined tags, which are recycled as they are assigned to new versions of the object. If there are a total of N versions or revisions to be stored in N storage areas, then N+2 tags are required. One tag is used a null or uninitialized tag. The remaining tags are assigned in a particular precedence order to revisions of the object as they arrive. Thus, each assigned tag, except the null tag, has both a unique predecessor as well as a unique successor tag. This forms the cyclic relationship. Note that this inventive mechanism assumes that a finite number of object revisions can be stored at any one time, such that storage areas associated with the objects are not infinite in nature.
The inventive state mechanism is used by a memory management controller in assigning the tags to the revisions. The state mechanism determines the tag that is to be assigned to the next revision. The precedence order of the tags allows the memory management controller to determine which revision is the most current revision. For example, if there are two storage areas, then four tags are required. One tag is used for the null state, and the remaining tags are assigned to the revisions. With only two revision stored at any one time, one tag is unused. The unused tag is used to determine the subsequent tag and the precedent tag. The subsequent tag of the sequence which would be used for the next revision is the unused tag. The tag with the highest precedence of the two assigned tags, is the tag lower in precedence to the unused tag. Another way of viewing this mechanism is that a review of the assigned tags will reveal the object tag whose successor tag is not currently assigned (i.e., unused). The object tagged in this manner is the current revision. Similarly, a tagged object that has no currently assigned predecessor is the oldest revision. Revising objects is a process of deactivating the oldest object and its tag, replacing its contents, and then assigning it the next successor tag in the cycle. The previously assigned object tag is then reclaimed, and by convention and design, represents the next unused tag in the cycle of succession.
Therefore, it is a technical advantage of the invention to allow multiple revisions of an object to be stored with a limited number of tags and not incurring problems from counter overflows or rollover of tags.
It is another technical advantage of the invention to store multiple revisions and thereby eliminate the problems associated with storing a single version of the object, such as loss of state during an update.
It is a further technical advantage of the invention to apply an unbounded, cyclic code tag to each object revision stored in memory.
It is a further technical advantage of the invention to determine the most recent, valid revision of a known memory object based on the cyclic code tag.
It is a further technical advantage of the invention to generate the next cyclic tag in sequence to apply to a new revision of a memory object based on the current tag.
It is a further technical advantage of the invention that object revisions can be rolled back to arbitrary points, without losing any versions.
It is a further technical advantage of the invention that the size of the tag field can be significantly smaller than the prior art indexed or time-stamp mechanisms. Note that the maximum tag field size is that which will support the maximum tag value.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis or modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.
REFERENCES:
patent: 5043871 (1991-08-01), Nishigaki et al.
patent: 5606660 (1997-02-01), Estakhri et al.
patent: 5640592 (1997-06-01), Rao
patent: 5640608 (1997-06-01), Dockter et al.
patent: 5987575 (1999-11-01), Yamaguchi
Cormen et al., Introduction to Algorithms, MIT Press, Mar. 1990.*
Goodman-Miller, A Programmer's View of Computer A
Grover Rajiv K.
Keaveny Thomas A.
Hewlett -Packard Company
Nguyen-Ba Hoang-Vu Anthony
Powell Mark R.
LandOfFree
Mechanism for maintaining revisions of objects in flash memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for maintaining revisions of objects in flash memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for maintaining revisions of objects in flash memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472313