Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-12-10
2004-07-27
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S159000, C711S161000, C711S162000
Reexamination Certificate
active
06769053
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory means comprising at least one set of data in a memory area. The memory means may be implemented with volatile RAM devices or with non-volatile silicon devices, such as EEPROM. Flash-EPROM or ROM. Usually, such memory stores operating system software modules, application programs and application data. In areas where such computer systems according to the invention may be particularly applicable, some or all of the operating system software modules are stored in ROM.
DESCRIPTION OF PRIOR ART
In some applications, typically financial transaction processes, storing must be done very safely. Such safe storage applications are known as requiring “Atomicity of Update” in “persistent” storage means. In order to carry out such safe updating, the use of update logs is known from the prior art. Such update logs register which parts of a set of data has to be changed during an update session. Only when the set of data together with its updated parts has been stored in memory, all references to the former version of the set of data may be removed.
OBJECT OF THE INVENTION
The object of the present invention is to support persistent application-data storage by providing a mechanism for atomicity of update for data stored in non-volatile memory devices, especially in silicon storage devices such as EEPROM or Flash-EEPROM.
SUMMARY OF THE INVENTION
Aspects of the invention are directed to methods and computer arrangements for storing a data structure for supporting the persistent storage of a set of data. In one aspect of the invention, a method is provided that stores, in the data structure, at least an oldest version of the set of data and a first tag identifying the oldest version in a first memory area. Further, the method includes storing, in the data structure, at least a most recently updated version of the set of data and a second tag identifying the most recently updated version in a second memory area. The method may also include deallocating the first memory area following the storing of the most recently updated version provided there are at least two versions of the set of data in the data structure.
The application of such unique tags related to the different memory areas allows to uniquely identify which one of the versions are older versions. Moreover, the application of such tags allows for identifying which versions relate to the same original set of data. Thus, in a memory, different versions of different sets of data may be present at the same time. Moreover, during updating the most recently updated version the older versions, as well as the most recently updated version, are not removed from memory. Only after an update action of the most recently updated version has been entirely completed the oldest version of the set of data may be removed from memory.
When the updating is interrupted during an update action, the most recently updated version is still present in the memory, thus guaranteeing the presence of at least one valid version of the set of data. Thus, “Atomicity of Update” is performed that guarantees either a complete replacement of the data or a complete unaltered copy of the original data, even if the update operation is disrupted.
In one embodiment, each of the versions of the set of data are stored in one or more memory pages, and each of the memory pages includes one tag, each tag comprising references to the set of data, a version number and a page number.
A page is defined as a memory area of consecutive memory locations which are dealt with as a unity such as appropriate for the storage technology concerned. Each page may correspond to one word line, thus facilitating memory unit read and write operations. Version numbers are assigned to the different generations of the set of data. Thus, different version numbers relate to different generations. Different page numbers refer to different pages within the same generation of the set of data.
The invention also relates to a computer arrangement including a processor and at least one computer-readable medium as defined above.
Preferably, the processor is arranged to write tags with redundancy as to the content and, after having read tags from the memory means, to analyze from the redundancy whether or not write errors have occurred. Such a redundancy can be used as an indication whether or not the tags concerned and the set of data to which the tags refer have valid values.
Preferably, the most recently updated version comprises a plurality of pages, each page having a unique tag, and the processor is arranged for updating said most recently updated version of said set of data and to write a predetermined tag of a predetermined one of said plurality of pages into said memory means as a last step of said updating. The predetermined tag, which is written last, can be read by the processor. If the processor detects the presence of this predetermined tag in the memory means, the processor can conclude that the updating action has been completed entirely.
The application of such tags provides for several new options. For instance, at least one of the tags may include additional data as to indicate ownership and use-rights, the processor being arranged to recognize ownership and use-rights from these additional data.
The use-rights may differ for different parts of the set of data and the processor may be arranged to recognize these different use-rights for these different parts.
Preferably, the processor is arranged to analyze tag values and is only allowed to access the versions of the set of data by reference through the tag values. Thus, access to the different versions of the set of data is not controlled by a usual program counter but by the tag values. In other words, the memory has become content addressable memory.
In the latter embodiment, the processor preferably comprises a central processing unit and a distinct memory managing unit, where the tag values are only known to the memory managing unit. Then, the physical address space of the memory means is not included in the address space of the central processing unit, especially not in the address space where application program or operating system software instructions are stored. In this manner, additional protection against “probing” can be obtained. To realize this potential protection, the memory managing unit may provide to the central processing unit additional interface functionality with a tag-size address register.
In order to increase the safety of stored data, the memory managing unit may encode tags with a cryptographic key prior to writing them into the memory, the cryptographic key being only known to the memory managing unit. Such a cryptographic key may relate to a cryptographic one-way function.
The present invention also relates to a method for supporting persistent storage of a set of data, comprising the steps of:
(a) storing an oldest version of said set of data in a first memory area, wherein said first memory area includes a first tag for uniquely identifying said oldest version, and
(b) storing a most recently updated version of said set of data in a second distinct memory area, wherein said second memory area includes a second tag for, uniquely identifying said most recently updated version.
REFERENCES:
patent: 4425642 (1984-01-01), Moses et al.
patent: 4921278 (1990-05-01), Shiang et al.
patent: 4930129 (1990-05-01), Takahira
patent: 4953160 (1990-08-01), Gupta
patent: 5057997 (1991-10-01), Chang et al.
patent: 5148546 (1992-09-01), Blodgett
patent: 5204663 (1993-04-01), Lee
patent: 5204897 (1993-04-01), Wyman
patent: 5283885 (1994-02-01), Hollerbauer
patent: 5404377 (1995-04-01), Moses
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5452431 (1995-09-01), Bournas
patent: 5469559 (1995-11-01), Parks et al.
patent: 5481715 (1996-01-01), Hamilton et al.
patent: 5544246 (1996-08-01), Mandelbaum et al.
patent: 5594227 (1997-01-01), Deo
patent: 5649118 (1997-07-01), Carlisle et al.
patent: 5657379 (1997-08-01), Honda et al.
patent: 5721781 (1998-02-01), Deo et al
Bos Jurjen Norbert Eelco
De Jong Eduard Karel
Belle Gate Investment B.V.
Elmore Reba I.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
LandOfFree
Arrangement storing different versions of a set of data 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 Arrangement storing different versions of a set of data in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangement storing different versions of a set of data in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213106