US5751939A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Main memory system and checkpointing protocol for fault-tolerant computer system using an exclusive-or memory
Assignee: Radisys Corp
•
Filing: 1995-11-29
•
Granted: 1998-05-12
•
Expires: 2015-11-29
Abstract
Abstract A mechanism for returning a computer system to a consistent, periodically updated state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In a typical computer system, a processor and input/output elements are connected to a main memory subsystem that includes a primary memory. A checkpoint memory element which may include one or more buffer memories, including a read buffer and a write buffer, and an exclusive-or memory block, is also appended to this main memory subsystem. The exclusive-or memory block is a block of memory corresponding in size to one block of the primary memory that can fail as a unit. The exclusive-or memory block contains an exclusive-or of the contents of the primary memory at a previous checkpoint state. During normal processing, both or either a pre-image and/or a post image of data written to primary memory may be captured by the checkpoint memory element. In one embodiment, a write operation is converted to a read-then-write operation to store pre-image data in a FIFO. An exclusive-or of pre-image and post-image data is exclusive-or'ed into the exclusive-or memory. When a fault occurs in the computer system, the data stored in the buffer memories, along with the contents of the exclusive-or memory block, are used to ensure that the primary memory is restored to a previous checkpointed state from which the computer system can recover. This structure and protocol can guarantee a consistent state in the primary memory, thus enabling fault-tolerant operation.
Inventors
- 👤 Jack J. Stiffler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 17:52
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1004; G06F11/14; G06F11/1402; G06F11/1405; G06F11/1407
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
86 words
A computer system comprising: a processor; a main memory subsystem, coupled to the processor, including: an exclusive-or memory for storing an exclusive-or checkpoint state; a buffer that monitors accesses of the main memory subsystem by the processor and stores data related to the accesses; and means, using the data from the buffer and the exclusive-or memory, for ensuring the existence of a consistent checkpoint state in the main memory subsystem to which processing can resume without loss of data integrity or program continuity following a fault.
Claim 2
Dependent Claim
86 words
A computer system comprising: a processor; a main memory subsystem, coupled to the processor, including: an exclusive-or memory for storing an exclusive-or checkpoint state; a buffer that monitors accesses of the main memory subsystem by the processor and stores data related to the accesses; and means, using the data from the buffer and the exclusive-or memory, for ensuring the existence of a consistent checkpoint state in the main memory subsystem to which processing can resume without loss of data integrity or program continuity following a fault.
Claim 3
Dependent Claim
65 words
The computer system of claim 1, wherein the processor has a corresponding input/output subsystem which provides input/output events initiated by the processor, wherein the processor has means for queuing input/output events between checkpoints and means for flushing the queued events to the primary memory element when a checkpoint is to be established, whereby input/output events are captured in checkpoint data in the main memory subsystem.
Claim 4
Dependent Claim
64 words
The computer system of claim 1, wherein a read-then-write operation is performed when the processor performs a write operation to the main memory subsystem, and further comprising means for storing a pre-image in a FIFO, means for performing an exclusive-or operation on pre-image and post-image data of the write operation and means for storing the result of the exclusive-or operation in the exclusive-or memory.
Claim 5
Dependent Claim
158 words
A computer system comprising: a processor having a cache that is periodically flushed to establish a checkpoint; an input/output port; a main memory subsystem coupled to the processor and to the input/output port, including: a read buffer, coupled to the processor and external port, that stores a pre-image of data to be written to the main memory subsystem; a write buffer, coupled to the processor and external port, that stores data written to the main memory subsystem; an exclusive-or memory; and an exclusive-or stage, coupled to the read and write buffers and to the exclusive-or memory; wherein after the cache of the processor is flushed, the exclusive-or stage reads data from the read buffer, the write buffer, and the exclusive-or stage, performs an exclusive-or operation on the data read by the exclusive-or stage, and stores a result of the exclusive-or operation in the exclusive-or memory thereby establishing a backup of the main memory subsystem in the exclusive-or memory.
Claim 6
Dependent Claim
158 words
A computer system comprising: a processor having a cache that is periodically flushed to establish a checkpoint; an input/output port; a main memory subsystem coupled to the processor and to the input/output port, including: a read buffer, coupled to the processor and external port, that stores a pre-image of data to be written to the main memory subsystem; a write buffer, coupled to the processor and external port, that stores data written to the main memory subsystem; an exclusive-or memory; and an exclusive-or stage, coupled to the read and write buffers and to the exclusive-or memory; wherein after the cache of the processor is flushed, the exclusive-or stage reads data from the read buffer, the write buffer, and the exclusive-or stage, performs an exclusive-or operation on the data read by the exclusive-or stage, and stores a result of the exclusive-or operation in the exclusive-or memory thereby establishing a backup of the main memory subsystem in the exclusive-or memory.
Claim 7
Dependent Claim
62 words
The computer system of claim 4, wherein the main memory subsystem includes a plurality of memory blocks each having equal storage capacity and each capable of failing independently from other memory blocks of the plurality of memory blocks, and wherein the exclusive-or memory has a storage capacity substantially equal to the storage capacity of any one of the plurality of memory blocks.
Claim 8
Dependent Claim
112 words
The computer system of claim 4, wherein, upon occurrence of a fault in one of the plurality of memory blocks of the main memory, the main memory is restored to a state at a previous checkpoint using contents of the exclusive-or memory and the read buffer, and the exclusive-or stage reads all data contained within the main memory except for data of the failed block, performs an exclusive-or operation of the data read from the main memory with data contained within the exclusive-or memory, and stores a result of the exclusive-or operation in the exclusive-or memory, the result representing the data of the failed memory block at the time of the fault.
Claim 9
Independent Claim
137 words
A method for providing fault tolerance in a computer system having a processor with a cache, an external port, a main memory subsystem, a read buffer memory, a write buffer memory, and an exclusive-or memory, the method comprising steps of: capturing a pre-image of data that is to be written to the main memory subsystem; storing the pre-image data in the read buffer; capturing write data written to the main memory subsystem; storing the write data in the write buffer; reading the read data from the read buffer; reading the write data from the write buffer; performing an exclusive-or operation on the write data, the read data and the data contained within the exclusive-or memory to obtain an exclusive-or result; and storing the exclusive-or result in the exclusive-or memory to establish a checkpoint in the exclusive-or memory.
Claim 10
Independent Claim
137 words
A method for providing fault tolerance in a computer system having a processor with a cache, an external port, a main memory subsystem, a read buffer memory, a write buffer memory, and an exclusive-or memory, the method comprising steps of: capturing a pre-image of data that is to be written to the main memory subsystem; storing the pre-image data in the read buffer; capturing write data written to the main memory subsystem; storing the write data in the write buffer; reading the read data from the read buffer; reading the write data from the write buffer; performing an exclusive-or operation on the write data, the read data and the data contained within the exclusive-or memory to obtain an exclusive-or result; and storing the exclusive-or result in the exclusive-or memory to establish a checkpoint in the exclusive-or memory.
Claim 11
Dependent Claim
163 words
The method of claim 7, wherein the main memory subsystem includes a plurality of memory blocks each having equal storage capacity, wherein the exclusive-or memory has a storage capacity equal to the storage capacity of any one of the plurality of memory blocks, and wherein the method further includes steps of: detecting a failed memory block of the plurality of memory blocks; copying data stored in the read buffer memory to the main memory subsystem to restore the main memory, except the failed memory block, to a previous checkpoint state; reading data contained within the plurality of memory blocks of the main memory except data contained within the failed memory block; reading data contained within the exclusive-or memory; performing an exclusive-or operation on the data read from the plurality of memory blocks and the data read from the exclusive-or memory to obtain an exclusive-or result; and storing the exclusive-or result in back into one of the exclusive-or memory and a spare memory block.
Claim 12
Dependent Claim
26 words
The method of claim 8, further comprising a step of: storing the exclusive-or result in the failed memory block after it has recovered from the failure.
References Cited (Backward Citations)
US3588829A
Cited
US4413327A
Cited
US3761881A
Cited
US3736566A
Cited
US3803560A
Cited
US3889237A
Cited
US3979726A
Cited
US4164017A
Cited
US4020466A
Cited
US4044337A
Cited
US4228496A
Cited
US4373179A
Cited
JPS5541528A
Cited
JPS55115121A
Cited
US4393500A
Cited
US4403284A
Cited
US4435762A
Cited
US4426682A
Cited
JPS5831651A
Cited
US4566106A
Cited
US4459658A
Cited
US4484273A
Cited
US4819154A
Cited
US4654819A
Cited
US4734855A
Cited
US4905196A
Cited
US4751639A
Cited
US4819232A
Cited
US4740969A
Cited
US4941087A
Cited
US4958273A
Cited
US4965719A
Cited
US5276848A
Cited
US4924466A
Cited
US5418916A
Cited
US4964126A
Cited
US5325517A
Cited
US5247618A
Cited
US5239637A
Cited
US5327532A
Cited
US5263144A
Cited
US5157663A
Cited
US5214652A
Cited
US5369757A
Cited
US5269017A
Cited
US5313647A
Cited
US5325519A
Cited
US5488719A
Cited
US5418940A
Cited
US5633635A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-11 | 2001-11-10 | 2002-05-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-11 | 2005-11-10 | 2006-05-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-11 | 2009-11-10 | 2010-05-12 | $7700.00 | Window Closed / Lapsed |