EP0381644A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Multi-processor system and method for maintaining the reliability of shared data structures
Assignee: International Business Machines Corp
•
Filing: 1990-01-15
•
Granted: —
•
Expires: 2010-01-15
Abstract
Abstract A system for maintaining the reliability of shared data structures, such as message queues, in a multi-processor data processing system is disclosed. The system includes a plurality of virtual memory- type processor units (10) in which the processors share virtual memory and can access each one of a plurality of virtual memory segments by the same virtual memory address. The system assures the reliability of system-wide shared data structures in the event of a failure of one of the processors by maintaining at least two copies of each data structure and by maintaining two copies of a table used in locating such data structures. The system updates copies of such shared data structures that are stored in at least two different processing units with the results of a specified data processing transaction, which may have affected the information in such data structures, in a manner to insure that either identical updates occur or no update occurs. The system further insures that any changes that might have occurred in the information stored in the data structure prior to the end of an aborted transaction is returned to the initial state to permit the transaction to be retried.
Inventors
- 👤 Marion Lee Blount
- 👤 Stephen Paul Morgan
- 👤 Katalin Anna Veronica Rader
- 👤 Robert Kent Rader
- 👤 Amal Ahmed Shaheen-Gouda
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 22:49
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/202; G06F11/2043; G06F11/14; G06F11/2097; G06F2201/00; G06F2201/825; G11; G11C; G11C29/00; G11C29/70; G11C29/74; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99955
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
81 words
A system for maintaining the reliability of shared data structures, including a plurality of processors (10) interconnected by a communication link (12), comprising: virtual storage shareable by each of said plurality of processors, the virtual storage having a plurality of virtual storage segments, each accessible by a same virtual addresse from anyone of the processors, means for maintaining at least two copies of each data structure, and means for maintaining two copies of a table used in locating such data structures.
Claim 2
Independent Claim
81 words
A system for maintaining the reliability of shared data structures, including a plurality of processors (10) interconnected by a communication link (12), comprising: virtual storage shareable by each of said plurality of processors, the virtual storage having a plurality of virtual storage segments, each accessible by a same virtual addresse from anyone of the processors, means for maintaining at least two copies of each data structure, and means for maintaining two copies of a table used in locating such data structures.
Claim 3
Dependent Claim
91 words
The system of claim 1, further comprising: means for keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor; means for automatically updating each of said copies for each of said pages modified; a message queue table (Fig. 3A) stored in a virtual storage segment, having information about a plurality of message queues in the system; and means for placing a message queue created by a process in a first processor into a virtual storage segment created by said first processor.
Claim 4
Dependent Claim
39 words
The system of Claim 2, wherein the message queue table further comprises: means (Fig. 3B) for identifying the virtual storage segment containing the message queue; and means (Fig. 3C) for identifying the queue in said identified virtual storage segment.
Claim 5
Dependent Claim
153 words
The system of claim 1, further comprising: means for keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor; means for updating each of said copies for each of said pages modified; a message queue table stored in a first virtual storage segment having information about a plurality of message queues in the data processing system; means for issuing a message get system call from a process in any one of said plurality of processors; means for scanning the message queue table for an entry for said called message queue; means for creating a new message queue in a second virtual storage if no entry is found; means for designating ownership of the new message queue by the processor of the process issuing the message get system call; and means for adding an entry to said message table for said new message queue.
Claim 6
Dependent Claim
25 words
The system of Claim 4, further comprising: means for obtaining a global lock on said table upon the issuance of said message get system call.
Claim 7
Dependent Claim
42 words
The system of Claim 4, further comprising: means for returning the identification of the created message queue to the process which issued the message get system call after the copies of the pages containing the message and message queue table are updated.
Claim 8
Dependent Claim
125 words
The system of claim 1, further comprising: means for keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor; means for updating each of said copies for each of said pages modified; a message table stored in a first virtual storage segment having information about a plurality of message queues in the data processing system; means for issuing a message control system call from a process in any one of said plurality of processors to remove a message queue; means for deleting the message queue from a second virtual storage segment containing the queue; and means for deleting the entry for the deleted queue in the message table stored in the first virtual storage segment.
Claim 9
Dependent Claim
110 words
The system of claim 1, further comprising: means for keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor; means for updating each of said copies for each of said pages modified; a message queue table stored in a first virtual storage segment having information about a plurality of message queues in the data processing system; means for issuing a message control system call from a process in any one of said processors to update the control information associated with a queue; and means for updating the control information for the queue in response to a message control system call.
Claim 10
Dependent Claim
160 words
The system of claim 1, further comprising: means for keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor; means for updating each of said copies for each of said pages modified; a message queue table stored in a first virtual storage segment having information about a plurality of message queues in the data processing system; means for issuing a message send system call from a process in any one of said processors to send a message to a queue; means for scanning said message queue table to locate the queue; means for determining if the queue to which the message is to be sent is full; means for putting the process originating the message call to sleep if the queue is full; means for periodically waking up the process to complete the system call; and means for transferring the message to the queue if the queue is not full.
Claim 11
Independent Claim
50 words
The system of any of the Claims, 4, 7, 8 or 9, wherein: the processor having the process which originated the message system call directs said updating means to automatically update the copies of the pages containing the message queue table and copies of the pages containing the message queue.
Claim 12
Dependent Claim
83 words
The system of Claim 9, wherein: said table stores identifying information about a plurality of message queue headers which have descriptive information about a message associated with the header which is located in a second virtual storage segment; and said system further comprises means for the process to obtain a global lock on said table upon the issuance of the system call and means for freeing the global lock means in response to said determing means determining that the located queue is full.
Claim 13
Independent Claim
145 words
A method for insuring reliability for system-wide data structures in a data processing system having a plurality of processors interconnected by a communi- cations link, said method comprising: sharing virtual storage by each of said plurality of processors; accessing each one of a plurality of virtual storage segments having a plurality of pages of said virtual storage by a same virtual address from any one of said processors; keeping at least two copies of each virtual page in a virtual segment, wherein each of said copies is stored in a different processor; updating each of said copies for each of said pages modified; storing information about a plurality of message queues in the data processing system in a message queue table in a first virtual storage segment; and placing a message queue created by a process in a processor into a second virtual storage segment.
Claim 14
Independent Claim
145 words
A method for insuring reliability for system-wide data structures in a data processing system having a plurality of processors interconnected by a communi- cations link, said method comprising: sharing virtual storage by each of said plurality of processors; accessing each one of a plurality of virtual storage segments having a plurality of pages of said virtual storage by a same virtual address from any one of said processors; keeping at least two copies of each virtual page in a virtual segment, wherein each of said copies is stored in a different processor; updating each of said copies for each of said pages modified; storing information about a plurality of message queues in the data processing system in a message queue table in a first virtual storage segment; and placing a message queue created by a process in a processor into a second virtual storage segment.
Claim 15
Dependent Claim
86 words
The method of Claim 12, further comprising: issuing a message get system call from a process of one of said plurality of processors; scanning the message queue table for an entry for said message queue; creating a new message queue if no entry is found; designating the ownership of the new message queue by said processor issuing the system call; adding an entry to said message queue table for said new message queue; and updating each of the copies for each of said virtual pages modified.
Claim 16
Independent Claim
37 words
The method of Claims 12 and 13, further comprising: returning the identification of the created message queue to the process issuing the system call after all copies of the message queue and message queue table are updated.
Claim 17
Dependent Claim
90 words
The method of Claim 12, further comprising: storing status information about a plurality of message queues in a message header table stored in a second virtual segment; storing text information associated with each header in a third virtual segment; issuing a message control system call from a process in any one of said plurality of processors to remove a message queue; deleting the message queue from a second virtual storage segment; and deleting the entry for the deleted queue in the message queue table stored in the first virtual segment.
Claim 18
Dependent Claim
91 words
The method pf Claim 12, further comprising: issuing a message send system call from a process in any one of said processors to send a message to a queue; determining if the queue to which the message is to be sent is full; putting the process originating the message call to sleep if the queue is full; periodically waking up the process to complete the system call; transferring the message to the queue if the queue is not full; and updating each of said copies for each of said pages modified.
Claim 19
Independent Claim
34 words
The method of Claims 13 or 15, wherein: copies of the pages containing the message queue and copies of the pages containing the message table are updated upon completion of the message system call.
Claim 20
Dependent Claim
64 words
The system of Claim 1, further comprising: means for storing, in one of said virtual storage segments owned by one of said processors as an owning site, a table for a plurality of data structures; means for designating another processor to be a back-up processor for the processor owning the table; and means for storing a copy of said table in said back-up processor.
Claim 21
Dependent Claim
35 words
The system of Claim 18, further comprising: means for said owning processor to select a new back-up processor if said original back-up processor fails; and means for copying said table to said new back-up processor.
Claim 22
Dependent Claim
20 words
The system of Claim 18, wherein: the back-up processor becomes a new owning processor if said existing owning processor fails.
Claim 23
Dependent Claim
124 words
The system of Claim 1, further comprising: a table stored in a virtual storage segment having identifying information about a plurality of system-wide data structures, wherein the table is created by one of the processors during the start-up of the system; means for assigning a back-up processor for the processor owning the virtual storage segment containing the table and storing a copy of said table in said back-up processor; means for attaching said virtual storage segment containing the table to each of the plurality of processors upon the issuance of a first system call by such processor which uses the identifying information; and means for updating all copies of said table stored in the virtual segment upon the successful completion of the system call.
Claim 24
Dependent Claim
7 words
The system of Claim 21, further comprising:
Claim 25
Dependent Claim
18 words
means for maintaining the previous copies of the identifying information in the event the system call is aborted.
Claim 26
Dependent Claim
18 words
means for maintaining the previous copies of the identifying information in the event the system call is aborted.
Claim 27
Dependent Claim
17 words
The system of Claim 21, wherein: the table has identifying information about a plurality of message queues.
Claim 28
Dependent Claim
16 words
The system of Claim 21, wherein: the table has identifying information about a plurality of semaphores.
Claim 29
Dependent Claim
6 words
The system of Claim 21, wherein:
Claim 30
Dependent Claim
12 words
the table has identifying information about a plurality of shared storage segments.
Claim 31
Dependent Claim
12 words
the table has identifying information about a plurality of shared storage segments.
Claim 32
Dependent Claim
115 words
The system of Claim 1, further comprising: a table created by a first processor for storing in a first virtual storage segment identifying information about a plurality of data structures; means for assigning at least one back-up processor to said first processor; means for copying said table in the first processor to said back-up processor; means for issuing a system call to execute an atomic transaction on a data structure owned by a processor from a process in any one of said plurality of processors; means for assigning a back-up processor to said processor owning said data structure; and means for updating all copies of the data structure upon the successful completion of the transaction.
Claim 33
Dependent Claim
27 words
The system of Claim 26, wherein said system further comprises: means for maintaining the previous copies of the data structure in the event the transaction is aborted.
Claim 34
Dependent Claim
26 words
The system of Claim 26, further comprising: means for updating all copies of the identifying information in the table upon the successful completion of the transaction.
Claim 35
Dependent Claim
82 words
The system of Claim 1, further comprising: means for storing at least two copies of a virtual page in a virtual segment, wherein each copy is stored in a different processor; means for issuing a system call to execute an atomic transaction on a data structure stored in a virtual segment owned by a first processor from a process running on a second processor; and means for updating all copies of the data structure upon the successful completion of the system call.
Claim 36
Dependent Claim
24 words
The system of Claim 29, further comprising: means for maintaining the previous copies of the data structure in the event the transaction is aborted.
Claim 37
Independent Claim
181 words
A method for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising; storing identifying information about a plurality of data structures in a segment of virtual storage shareable and addressable by each of said processors, wherein a copy of said identifying information is stored in one of the plurality of processors; assigning a back-up processor for said processor containing a copy of the identifying information, wherein another copy of said identifying information is also stored in said back-up processor; issuing a system call, which uses the identifying information to execute an atomic transaction on a data structure stored in a virtual storage segment by a process on one of the plurality of processors; attaching the segment containing the identifying information to each of the processors upon the issuance of the first system call which uses the identifying information; and updating all copies of said identifying information upon a successful completion of the transaction; and maintaining the previous copies of identifying information in the event the transaction is aborted.
Claim 38
Independent Claim
181 words
A method for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising; storing identifying information about a plurality of data structures in a segment of virtual storage shareable and addressable by each of said processors, wherein a copy of said identifying information is stored in one of the plurality of processors; assigning a back-up processor for said processor containing a copy of the identifying information, wherein another copy of said identifying information is also stored in said back-up processor; issuing a system call, which uses the identifying information to execute an atomic transaction on a data structure stored in a virtual storage segment by a process on one of the plurality of processors; attaching the segment containing the identifying information to each of the processors upon the issuance of the first system call which uses the identifying information; and updating all copies of said identifying information upon a successful completion of the transaction; and maintaining the previous copies of identifying information in the event the transaction is aborted.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.