Patent US5787243A successfully refreshed from Google Patents.
US5787243A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Main memory system and checkpointing protocol for fault-tolerant computer system
Assignee: Radisys Corp
•
Filing: 1996-07-02
•
Granted: 1998-07-28
•
Expires: 2016-07-02
Abstract
Abstract A mechanism for maintaining a consistent 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 via a memory bus. A shadow memory element, which includes a buffer memory and a main storage element, is also attached to this memory bus. During normal processing, data written to primary memory is also captured by the buffer memory of the shadow memory element. When a checkpoint is desired (thereby establishing a consistent state in main memory to which all executing applications can safely return following a fault), the data previously captured in the buffer memory is then copied to the main storage element of the shadow memory element. This structure and protocol can guarantee a consistent state in main memory, thus enabling fault-tolerant operation.
Inventors
- 👤 Jack J. Stiffler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:43
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1405; G06F11/1407
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
159 words
A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache and internal resisters and connected to a main memory system; wherein the main memory system includes: i) a primary memory element; ii) a buffer memory element connected to the primary memory element such that selected accesses to the primary memory element are captured in the buffer memory element simultaneously with the access to the primary memory element; iii) a shadow storage element connected to the buffer memory; iv) means for copying data from the buffer memory element to the shadow storage element in response to an instruction to perform such copying from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache and internal registers and means for instructing the means for copying after flushing of the cache and internal registers has completed.
Claim 2
Dependent Claim
159 words
A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache and internal resisters and connected to a main memory system; wherein the main memory system includes: i) a primary memory element; ii) a buffer memory element connected to the primary memory element such that selected accesses to the primary memory element are captured in the buffer memory element simultaneously with the access to the primary memory element; iii) a shadow storage element connected to the buffer memory; iv) means for copying data from the buffer memory element to the shadow storage element in response to an instruction to perform such copying from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache and internal registers and means for instructing the means for copying after flushing of the cache and internal registers has completed.
Claim 3
Dependent Claim
33 words
The computer system of claim 1, wherein the buffer memory element and the shadow storage element are configured as a single unit, and wherein the primary element is implemented with an identical unit.
Claim 4
Dependent Claim
52 words
The computer system of claim 2, wherein the primary memory element includes a first programmable element that configures the primary memory element as a primary memory element, and wherein the single unit includes a second programmable element that configures the single unit as a buffer memory element and a shadow storage element.
Claim 5
Dependent Claim
23 words
The computer system of claim 1, wherein the processor includes a plurality of processors, each of the plurality of processors having a cache.
Claim 6
Dependent Claim
16 words
The computer system of claim 4, further including means for initiating a flush of each cache.
Claim 7
Dependent Claim
25 words
The computer system of claim 5, wherein the means for initiating include means for initiating the flush a predetermined time subsequent to a previous flush.
Claim 8
Dependent Claim
25 words
The computer system of claim 5, wherein the means for initiating includes means for determining an amount of unused memory space within the buffer memory.
Claim 9
Dependent Claim
19 words
The computer system of claim 5, further including means for flushing data of each cache into the buffer memory.
Claim 10
Dependent Claim
25 words
The computer system of claim 8, wherein the means for flushing includes means for flushing only data that has been modified since a previous flush.
Claim 11
Dependent Claim
23 words
The computer system of claim 4, wherein each cache includes: a data cache for storing data; and an instruction cache for storing instructions.
Claim 12
Dependent Claim
18 words
The computer system of claim 4, each of the plurality of processors including means for maintaining cache coherency.
Claim 13
Dependent Claim
30 words
The computer system of claim 1, further comprising means for determining an amount of data currently stored in the buffer memory with respect to a capacity of the buffer memory.
Claim 14
Dependent Claim
27 words
The computer system of claim 1, further comprising means for determining when a copying operation from the buffer memory to the shadow storage element has been completed.
Claim 15
Dependent Claim
157 words
A memory system for use with at least two processors, each connected to the memory system and having a cache of arbitrary size and internal registers, wherein the cache and internal registers of each processor are periodically flushed by the processors in synchronization, comprising: a primary memory element; a buffer memory physically disjoint from and connected to the primary memory such that selected accesses to the primary memory element are captured in the buffer memory element simultaneously with the access to the primary memory element; a shadow storage element connected to the buffer memory and physically disjoint from the primary memory and the buffer memory; means for copying data in the buffer memory to appropriate locations in the shadow storage element when the processors complete flushing of their caches and internal registers, thereby establishing a consistent checkpoint in the memory system from which processing can resume without loss of data integrity or program continuity following a fault.
Claim 16
Dependent Claim
157 words
A memory system for use with at least two processors, each connected to the memory system and having a cache of arbitrary size and internal registers, wherein the cache and internal registers of each processor are periodically flushed by the processors in synchronization, comprising: a primary memory element; a buffer memory physically disjoint from and connected to the primary memory such that selected accesses to the primary memory element are captured in the buffer memory element simultaneously with the access to the primary memory element; a shadow storage element connected to the buffer memory and physically disjoint from the primary memory and the buffer memory; means for copying data in the buffer memory to appropriate locations in the shadow storage element when the processors complete flushing of their caches and internal registers, thereby establishing a consistent checkpoint in the memory system from which processing can resume without loss of data integrity or program continuity following a fault.
Claim 17
Dependent Claim
34 words
The computer system of claim 14, wherein the buffer memory element and the shadow storage element are configured as a single unit, and wherein the primary memory element is implemented with an identical unit.
Claim 18
Dependent Claim
52 words
The computer system of claim 15, wherein the primary memory element includes a first programmable element that configures the primary memory element as a primary memory element, and wherein the single unit includes a second programmable element that configures the single unit as a buffer memory element and a shadow storage element.
Claim 19
Dependent Claim
30 words
The memory system of claim 14, further comprising means for determining an amount of data currently stored in the buffer memory with respect to a capacity of the buffer memory.
Claim 20
Dependent Claim
27 words
The memory system of claim 14, further comprising means for determining when a copying operation from the buffer memory to the shadow storage element has been completed.
Claim 21
Dependent Claim
169 words
In a computer system having first processor with a first cache and a second processor with a second cache, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of the first and second caches to maintain a consistent state in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache such that the buffer memory and the primary memory simultaneously capture data flushed from the first cache; waiting until the second processor completes flushing of the second cache such that the buffer memory and the primary memory simultaneously capture data flushed from the second cache; instructing the buffer memory to copy data captured therein to the shadow storage element; and releasing the lock and resuming normal operations.
Claim 22
Dependent Claim
169 words
In a computer system having first processor with a first cache and a second processor with a second cache, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of the first and second caches to maintain a consistent state in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache such that the buffer memory and the primary memory simultaneously capture data flushed from the first cache; waiting until the second processor completes flushing of the second cache such that the buffer memory and the primary memory simultaneously capture data flushed from the second cache; instructing the buffer memory to copy data captured therein to the shadow storage element; and releasing the lock and resuming normal operations.
Claim 23
Dependent Claim
22 words
The method of claim 19, wherein the step of flushing includes storing only data that has been modified since a previous flush.
Claim 24
Dependent Claim
28 words
The method of claim 19, further including a step, prior to flushing the first cache, of storing a processing state of the first processor in the first cache.
Claim 25
Dependent Claim
32 words
The method of claim 19, further including a step, performed by each of the first processor and the second processor, of incrementing a flush counter when a flush operation has been completed.
Claim 26
Independent Claim
121 words
A method for checkpointing a computer system having a first processor that has a first cache and first internal registers a second processor that has a second cache and second internal registers, wherein the first and second caches hold data accessed from a primary memory by the first and second processors, and wherein the processor may modify said data, the method comprising the steps, performed by the first processor, of: sustaining execution of a process; flushing the first cache and first internal registers to copy all modified data to a primary memory; and confirming that the second processor has flushed all modified data from the second cache and second internal registers to the primary memory; and resuming execution of the process.
Claim 27
Independent Claim
121 words
A method for checkpointing a computer system having a first processor that has a first cache and first internal registers a second processor that has a second cache and second internal registers, wherein the first and second caches hold data accessed from a primary memory by the first and second processors, and wherein the processor may modify said data, the method comprising the steps, performed by the first processor, of: sustaining execution of a process; flushing the first cache and first internal registers to copy all modified data to a primary memory; and confirming that the second processor has flushed all modified data from the second cache and second internal registers to the primary memory; and resuming execution of the process.
Claim 28
Dependent Claim
136 words
A checkpoint memory element for a main memory for use in a computer system having a processor connected to the main memory wherein the main memory has a primary memory element, comprising: a buffer memory connected to the primary memory element such that the buffer memory captures selected accesses to the primary memory element simultaneously with the access to the primary memory element an having an output indicative of how full the buffer memory is; a shadow storage element connected to the buffer memory; and a memory control logic circuit, connected to the shadow storage element and the buffer memory and having outputs to control the shadow storage element and the buffer memory to copy data from the buffer memory to the shadow storage element in response to the buffer memory and instructions from the processor.
Claim 29
Dependent Claim
136 words
A checkpoint memory element for a main memory for use in a computer system having a processor connected to the main memory wherein the main memory has a primary memory element, comprising: a buffer memory connected to the primary memory element such that the buffer memory captures selected accesses to the primary memory element simultaneously with the access to the primary memory element an having an output indicative of how full the buffer memory is; a shadow storage element connected to the buffer memory; and a memory control logic circuit, connected to the shadow storage element and the buffer memory and having outputs to control the shadow storage element and the buffer memory to copy data from the buffer memory to the shadow storage element in response to the buffer memory and instructions from the processor.
Claim 30
Dependent Claim
125 words
The checkpoint memory element of claim 24, wherein the memory control logic circuit includes: a buffer memory control circuit, coupled to the buffer memory, having memory control signal outputs that control the buffer memory; a command register, coupled to the buffer memory control circuit, for storing commands; a status register, coupled to the buffer memory control circuit, for storing status information; a shadow storage control circuit, coupled to the buffer memory control circuit, having memory control signal outputs that control the shadow storage element; and an input/output interface control circuit, coupled to the buffer memory control circuit, the command register, and the status register, having outputs that control information flow among the status register, command register, buffer memory control circuit, and shadow storage control circuit.
Claim 31
Dependent Claim
31 words
The checkpoint memory element of claim 25, wherein the buffer memory control circuit includes: an output indicative of whether copying from the buffer memory to the main storage element is complete.
Claim 32
Dependent Claim
85 words
The checkpoint memory element of claim 24, further including: a data input buffer coupled to the buffer memory for temporarily storing data to be stored in the buffer memory; an address buffer memory, coupled to the memory control logic, that stores information indicative of addresses corresponding to data stored in the buffer memory; and an address input buffer, coupled to the memory control logic and the buffer memory, that provides the addresses corresponding to data stored in the buffer memory to the address buffer memory.
Claim 33
Dependent Claim
115 words
A checkpoint memory element for a main memory system for use in a computer system having a processor connected to a primary memory element comprising: a buffer memory connected to the primary memory element such that selected accesses to the primary memory element are captured in the buffer memory simultaneously with the access to the primary memory element; a shadow storage element connected to the buffer memory; means for copying data from the buffer memory to the shadow storage element in response to an instruction to perform such copying from the processor; and means for determining an amount of data currently stored in the buffer memory with respect to a capacity of the buffer memory.
Claim 34
Dependent Claim
115 words
A checkpoint memory element for a main memory system for use in a computer system having a processor connected to a primary memory element comprising: a buffer memory connected to the primary memory element such that selected accesses to the primary memory element are captured in the buffer memory simultaneously with the access to the primary memory element; a shadow storage element connected to the buffer memory; means for copying data from the buffer memory to the shadow storage element in response to an instruction to perform such copying from the processor; and means for determining an amount of data currently stored in the buffer memory with respect to a capacity of the buffer memory.
Claim 35
Dependent Claim
235 words
In a computer system having first processor with a first cache and first internal registers and a second processor with a second cache and second internal registers, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory such that selected accesses to the primary memory are captured in the buffer memory simultaneously with the access to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of caches and internal registers to maintain a consistent state of the computer system in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache and the first internal registers to the primary memory such that the buffer memory captures data flushed from the first cache and first internal registers; waiting until the second processor commences flushing of the second cache and second internal registers such that the buffer memory captures data flushed from the second cache and second internal registers; identifying which processor has written the data in the buffer memory: instructing the buffer memory to copy data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element; and releasing the lock and resuming normal operations.
Claim 36
Dependent Claim
235 words
In a computer system having first processor with a first cache and first internal registers and a second processor with a second cache and second internal registers, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory such that selected accesses to the primary memory are captured in the buffer memory simultaneously with the access to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of caches and internal registers to maintain a consistent state of the computer system in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache and the first internal registers to the primary memory such that the buffer memory captures data flushed from the first cache and first internal registers; waiting until the second processor commences flushing of the second cache and second internal registers such that the buffer memory captures data flushed from the second cache and second internal registers; identifying which processor has written the data in the buffer memory: instructing the buffer memory to copy data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element; and releasing the lock and resuming normal operations.
Claim 37
Independent Claim
147 words
A method for maintaining a consistent state of a computer system in main memory to support fault tolerance in the computer system, wherein the computer system includes a first computer having a first cache and internal registers, a second computer having a second cache and internal registers, wherein the first and second caches hold data accessed from a primary memory by the first and second processors, and wherein the processor may modify said data, and a primary memory, the method including the steps of: monitoring the primary memory to detect a data write to the primary memory; copying the data write into a buffer memory simultaneously with the data write to the primary memory; periodically flushing data from the first cache and the second cache and internal registers into the primary memory in synchronization; after flushing, copying data from the buffer memory into a shadow storage element.
Claim 38
Independent Claim
147 words
A method for maintaining a consistent state of a computer system in main memory to support fault tolerance in the computer system, wherein the computer system includes a first computer having a first cache and internal registers, a second computer having a second cache and internal registers, wherein the first and second caches hold data accessed from a primary memory by the first and second processors, and wherein the processor may modify said data, and a primary memory, the method including the steps of: monitoring the primary memory to detect a data write to the primary memory; copying the data write into a buffer memory simultaneously with the data write to the primary memory; periodically flushing data from the first cache and the second cache and internal registers into the primary memory in synchronization; after flushing, copying data from the buffer memory into a shadow storage element.
Claim 39
Dependent Claim
40 words
The method of claim 30, further including the steps of: detecting when a fault has occurred; when a fault has occurred, performing the steps of: copying data from the shadow storage element into the primary memory element; and resuming operation.
Claim 40
Dependent Claim
47 words
The method of claim 30, further including the steps of: detecting when a fault has occurred; when a fault has occurred, performing the steps of: configuring the primary memory to shadow the checkpoint storage element; and resuming operation using the shadow storage element as a primary memory.
Claim 41
Dependent Claim
49 words
The method of claim 30, wherein the step of flushing includes the steps of: setting a lock and suspending normal operation; flushing the first cache and the second cache; waiting until the first processor and the second processor have completed flushing; and releasing the lock and resuming normal operations.
References Cited (Backward Citations)
US3588829A
Cited
FR2028517A1
Cited
US4413327A
Cited
US3864670A
Cited
US3761881A
Cited
US3736566A
Cited
US3803560A
Cited
US3889237A
Cited
US3979726A
Cited
US4164017A
Cited
US4020466A
Cited
US4044337A
Cited
US4228496A
Cited
US4817091A
Cited
US4373179A
Cited
JPS5541528A
Cited
JPS55115121A
Cited
US4393500A
Cited
US4403284A
Cited
US4435762A
Cited
US4426682A
Cited
JPS5831651A
Cited
US4566106A
Cited
US4459658A
Cited
US4503534A
Cited
US4484273A
Cited
US4509554A
Cited
WO1984002409A1
Cited
US4654819A
Cited
US4819154A
Cited
US4734855A
Cited
US4905196A
Cited
US4959774A
Cited
US4751639A
Cited
US4703481A
Cited
US4819232A
Cited
US4740969A
Cited
US4941087A
Cited
EP0260625A1
Cited
FR2606184A1
Cited
US4823261A
Cited
EP0299511A2
Cited
US5123099A
Cited
US4958273A
Cited
US4965719A
Cited
US5276848A
Cited
US4924466A
Cited
US5418916A
Cited
US4912707A
Cited
US4996687A
Cited
US5301309A
Cited
US5325517A
Cited
US5239637A
Cited
US5247618A
Cited
US5235700A
Cited
EP0441087A1
Cited
US5420996A
Cited
US5271013A
Cited
US5327532A
Cited
EP0457308A2
Cited
US5263144A
Cited
US5157663A
Cited
US5530801A
Cited
DE4136729A1
Cited
US5381544A
Cited
US5214652A
Cited
US5369757A
Cited
US5408636A
Cited
US5293613A
Cited
US5495587A
Cited
US5495590A
Cited
US5269017A
Cited
US5313647A
Cited
US5325519A
Cited
US5488716A
Cited
US5363503A
Cited
US5394542A
Cited
US5448719A
Cited
US5398331A
Cited
US5485585A
Cited
US5574874A
Cited
US5408649A
Cited
US5463733A
Cited
US5418940A
Cited
US5568380A
Cited
US5504861A
Cited
US5566297A
Cited
US5583987A
Cited
US5557735A
Cited
US5649152A
Cited
US5530946A
Cited
US5644742A
Cited
US5649136A
Cited
US5630047A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-27 | 2002-01-26 | 2002-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-27 | 2006-01-26 | 2006-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-27 | 2010-01-26 | 2010-07-28 | $7700.00 | Window Closed / Lapsed |