US4459658A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique for enabling operation of a computer system with a consistent state of a linked list data structure after a main memory failure
Assignee: NCR Voyix Corp
•
Filing: 1982-02-26
•
Granted: 1984-07-10
•
Expires: 2002-02-26
Abstract
Abstract Operation of a computer system after a main memory failure is enabled by storing a read-only access shadow copy of its data structures in another memory having an independent failure mode. The shadow copy is periodically updated at a series of checkpoints. Where the data structure is a linked list, updating without recopying is enabled by prelinking the list item in the read-only list to the beginning of a second read/write list, which is appended to the first list at the next checkpoint.
Inventors
- 👤 John D. Gabbe
- 👤 Matthew S. Hecht
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:18
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1446; G06F11/1448; G06F11/1451
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
178 words
A method of restoring the memory of a computer system to a recent consistent state after a memory failure including the steps of: (a) forming a read-only shadow copy of a data structure in said computer memory, said structure including information stored in a first series of linked pages, each page of said first series other than the last page containing a pointer to the next page in the series, (b) storing said read-only shadow copy in a second memory having a failure mode independent of the failure mode of the main memory of said computer, and (c) periodically constructing a new read-only shadow copy to replace the previous shadow copy, said new copy incorporating additional information accumulated since the previous shadow copy was formed, characterized in that (d) said forming step includes inserting a pointer on said last page of said first series of pages to the first page of a second series of pages containing said additional information, and (e) said constructing step includes appending said second series of pages to said first series of pages.
Claim 2
Independent Claim
178 words
A method of restoring the memory of a computer system to a recent consistent state after a memory failure including the steps of: (a) forming a read-only shadow copy of a data structure in said computer memory, said structure including information stored in a first series of linked pages, each page of said first series other than the last page containing a pointer to the next page in the series, (b) storing said read-only shadow copy in a second memory having a failure mode independent of the failure mode of the main memory of said computer, and (c) periodically constructing a new read-only shadow copy to replace the previous shadow copy, said new copy incorporating additional information accumulated since the previous shadow copy was formed, characterized in that (d) said forming step includes inserting a pointer on said last page of said first series of pages to the first page of a second series of pages containing said additional information, and (e) said constructing step includes appending said second series of pages to said first series of pages.
Claim 3
Dependent Claim
73 words
The method defined in claim 1 wherein said information stored in said first series of linked pages includes a first list of the addresses of free pages in said second memory which are available for use at the time said read-only shadow copy is formed, and said additional information includes a second list of the addresses of pages in said second memory which become free for use after said shadow copy is formed.
Claim 4
Dependent Claim
48 words
The method defined in claim 2 further including the steps of: allocating free pages for use in the operation of said computer system from addresses obtained from the beginning of said first list, and adding addresses of newly freed memory pages at the end of said second list.
Claim 5
Dependent Claim
61 words
The method defined in claim 3 wherein said method further includes: computing the number of free pages in said first list, comparing said number of free pages to a preselected threshold, and wherein said constructing step occurs when said number of free pages in said first list is below said preselected threshold, or at a predetermined time interval, whichever occurs sooner.
Claim 6
Independent Claim
158 words
A method of enabling the operation of a computer system after a main memory failure including the steps of: (a) forming a read-only shadow copy of a linked list data structure in a memory having a failure mode independent of said main memory, said linked list data structure including information stored in a first series of linked pages, each page of said first series other than the last page containing a pointer to the next page in the series, and (b) periodically constructing a read-only shadow copy to replace the previous shadow copy by appending to said first series of pages additional information from a second linked series of pages, said additional information being accumulated since the previous shadow copy was formed, characterized in that said forming step includes (c) inserting a pointer on said last page of said first series of pages, prelinking said last page to the first page of said second linked series of pages.
Claim 7
Independent Claim
158 words
A method of enabling the operation of a computer system after a main memory failure including the steps of: (a) forming a read-only shadow copy of a linked list data structure in a memory having a failure mode independent of said main memory, said linked list data structure including information stored in a first series of linked pages, each page of said first series other than the last page containing a pointer to the next page in the series, and (b) periodically constructing a read-only shadow copy to replace the previous shadow copy by appending to said first series of pages additional information from a second linked series of pages, said additional information being accumulated since the previous shadow copy was formed, characterized in that said forming step includes (c) inserting a pointer on said last page of said first series of pages, prelinking said last page to the first page of said second linked series of pages.
Claim 8
Dependent Claim
74 words
The method defined in claim 5 wherein said information stored in said first series of pages represents a list of the addresses of free pages in said independent failure mode memory at the time of said constructing step, and said additional information stored in said second series of pages represents a list of the addresses of pages in said independent failure mode memory freed for use since the last occurrence of said constructing step.
Claim 9
Dependent Claim
30 words
The method defined in claim 6 wherein said constructing step is performed when the number of said addresses in said list of addresses of free pages reaches a preset minimum.
Claim 10
Dependent Claim
67 words
The method defined in claim 7 wherein said inserting step includes: (a) obtaining the address of a free page from the beginning of said list of addresses of free pages (b) storing information representing said address in a preselected location on said last page, and (c) modifying a pointer indicating the beginning of said free page list to point to the next address of a free page.
Claim 11
Independent Claim
161 words
A method of performing checkpoints to preserve a recent consistent state of a data structure in a computer memory and enable its recovery after a memory failure, said data structure including a series of pages each of which is linked to the next page, said method including the step of: (a) updating information on a system page stored during the previous checkpoint to reflect subsequent changes in said data structure, (b) storing the updated information in a memory having a failure mode independent of the failure mode of said main memory, and (c) repeating steps (a) and (b), characterized in that said series of pages includes a read-only portion, and an append-only portion and said updating step includes: (1) appending information stored in said append-only portion which reflects said subsequent changes to said read-only portion to form the next read-only portion, and (2) prelinking the last page of said next read-only portion to the first page of the next append-only portion.
Claim 12
Independent Claim
161 words
A method of performing checkpoints to preserve a recent consistent state of a data structure in a computer memory and enable its recovery after a memory failure, said data structure including a series of pages each of which is linked to the next page, said method including the step of: (a) updating information on a system page stored during the previous checkpoint to reflect subsequent changes in said data structure, (b) storing the updated information in a memory having a failure mode independent of the failure mode of said main memory, and (c) repeating steps (a) and (b), characterized in that said series of pages includes a read-only portion, and an append-only portion and said updating step includes: (1) appending information stored in said append-only portion which reflects said subsequent changes to said read-only portion to form the next read-only portion, and (2) prelinking the last page of said next read-only portion to the first page of the next append-only portion.
Claim 13
Dependent Claim
19 words
The method defined in claim 9 wherein said updating step further includes inserting a time-indication on said system page.
Claim 14
Dependent Claim
27 words
The method defined in claim 9 wherein said information stored on said system page includes pointers to the beginning and end of said read-only and append-only portions.
Claim 15
Dependent Claim
29 words
The method defined in claim 9 wherein said prelinking step includes inserting an indication of the address of said first page in a predetermined location on said last page.
Claim 16
Dependent Claim
54 words
The method defined in claim 9 further including the steps of: (a) writing the addresses of unused pages of said independent failure mode memory in said read-only portion, and (b) writing the addresses of pages of said independent failure mode memory which have become free since the last updating step in said append-only portion.
Claim 17
Dependent Claim
50 words
The method defined in claim 13 further including the steps of allocating unused pages for use in the operation of said computer system in accordance with addresses obtained from the beginning of said read-only portions, and adding addresses of newly freed memory pages at the end of said append-only portion.
Claim 18
Dependent Claim
61 words
The method defined in claim 14 wherein said method further includes the step of: comparing the number of addresses of unused pages in said read-only portion to a preselected number, and wherein said updating and storing steps are repeated at periodic intervals, or sooner if said number of unused page addresses remaining in said read-only portion falls below said preselected minimum.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-07-10 | 1988-01-09 | 1988-07-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-07-10 | 1992-01-09 | 1992-07-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-07-10 | 1996-01-09 | 1996-07-10 | $7700.00 | Window Closed / Lapsed |