System and method for implementing operating system message queues with recoverable shared virtual storage

• US 5,222,217 A
• Filed: 01/18/1989
• Issued: 06/22/1993
• Est. Priority Date: 01/18/1989
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morgan, Stephen P., Shaheen-Gouda, Rader, Robert K., Blount, Marion L., Rader, Katalin A. V.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Coleman, Eric
• Application Number:
  US07/298,384
• Time in Patent Office: 1,616 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/325, 395/425, 395/650, 395/575
• US Class Current: 1/1
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/2043 where the redundant components share a common memory address space
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 2201/825 the problem or solution involving locking
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies
• CPC Class Codes: Y10S 707/99955 Archiving or backup

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 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.

Claims

1. A data processing system having a plurality of processors interconnected by a communications link, comprising:

virtual storage shareable during operation of said system by each of said plurality of processors, said virtual storage having a plurality of virtual storage segments, each accessible during operation of said system by a same virtual address from any one of said processors;

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 when modified by a completed transaction;

a message queue table 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 crated by said first processor.

2. The system of claim 1, wherein the message queue table further comprises:

means for identifying the virtual storage segment containing the message queue; and

means for identifying the message queue in said identified virtual storage segment.

3. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage by each of the plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by a same virtual address from any one of said processors during operation of said system;

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 when modified by a completed transaction;

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 is 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.

4. The system of claim 3, further comprising:

means for obtaining a global lock on said table upon the issuance of said message get system call.

5. The system of claim 3, wherein:

the processor having the process which originated the message get 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.

6. The system of claim 3, wherein:

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.

7. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage by each of said plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by a same virtual address from any one of said processors during operation of said system;

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 when modified by a completed transaction;

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 int eh first virtual storage segment.

8. The system of claim 7, wherein:

the processor originating the message control system call directs the updating means to update the pages containing both copies of the message queue and the message queue table.

9. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage by each of said plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments by a same virtual address from any one of said processors during operation of said system;

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 when modified by a completed transaction;

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.

10. The system of claim 9, wherein:

the processor issuing the system call directs the updating means to update all copies of the pages containing the queue.

11. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage by each of said plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by same virtual address from any one of said processors during operation of said system;

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 when modified by a completed transaction;

a message queue table stored in a first virtual storage segment having information about a plurality of message queues int eh 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 of the queue is not full.

12. The system of claim 11, 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 the 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 determining means determining that the located queue is full.

13. The system of claim 11, wherein:

the processor originating the call automatically directs said updating means to update all copies of the pages containing the queue which receives a message upon completion of the message transfer.

14. A method for insuring reliability for system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, said method comprising:

sharing virtual storage by each of said plurality of processors during operation of said system;

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 during operation of said system;

keeping at least two copies of each virtual page in a virtual segment, wherein each of said copies is stored in a different processor;

storing information about a plurality of message queues in the data processing system in a message queue table in a first virtual storage segment;

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 when modified by a completed transaction.

15. The method of claim 14, 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 get system call.

16. The method of claim 14, 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.

17. 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:

sharing virtual storage by each of said plurality of processors during operation of said system;

accessing each one of a plurality of virtual storage segments of said virtual storage by a same virtual address from any one of said processors during operation of said system;

keeping at least two copies of a virtual page, wherein each of said copies is stored in a different processor;

storing information about the identity and location of a plurality of message queues in the data processing system in a message queue table stored in a first virtual storage segment;

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.

18. The Method of claim 17, wherein:

all copies of the message queue and message queue table are updated upon completion of the message control system call transaction.

19. A method for insuring reliability of system-wide data structures in data processing system having a plurality of processors interconnected by a communications link, comprising:

sharing virtual storage by each of said plurality of processors during operation of said system;

accessing each one of a plurality of virtual storage segments of said virtual storage by a same virtual address for any one of said processors during operation of said system;

keeping at least two copies of each virtual page of a virtual segment, wherein each of said copies is stored in a different processor;

storing information about a plurality of message queues in the data processing system in a message queue table stored in a first virtual storage segment;

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.

20. A system for insuring reliability in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for producing a message from a requesting process in one of said plurality of processors;

means for placing the message from the requesting process in a virtual storage segment accessible by each of said plurality for processors during operation of said system;

means for passing the message to a receiving process;

means for updating in the segment of said virtual storage originally containing the data structure; and

means for keeping at least two copies of the virtual storage containing the data, wherein each of the copies is stored in a different processor.

21. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage among the plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by a same address form each of said processors during operation of said system;

means for placing a message in a virtual storage segment by a requesting process; and

means for examining said virtual storage segment periodically by a receiving processor for said placed message.

22. A system for insuring reliability of system-wide data structure sin a data processing system having a plurality of processors interconnected by a communications link, said system comprising:

means for sharing virtual storage among the plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by a same address form each one of said processors during operation of said system;

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 b a back-up processor of the processor owning the table; and

means for storing a copy of said table in said back-up processor.

23. The system of claim 22, 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.

24. The system of claim 22, wherein:

the back-up processor becomes a new owning processor if said existing owning processor fails.

25. The system of claim 24, further comprising:

means for selecting a new back-up processor by said new owning processor and copying said table to the new back-up processor.

26. 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 during operation of said system, wherein a copy of said identifying information is stored in one of a 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 store din 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 the successful completion of the transaction.

27. A system for insuring reliability of system-side data structures in a data processing system having a plurality of processors interconnected by a communication link, wherein each processor shares virtual storage segments, each accessible by a same virtual address from any one of said processors during operation of said system, 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 said segment containing the identifying information to each of said processors upon the issuance of the first system call which uses the identifying information; and

maintaining the previous copies of identifying information in the event the transaction is aborted.

28. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communication link, wherein each processor shares virtual storage segments, each accessible by a same virtual address from any one of said processors during operation of said system, 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 of 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.

29. The system of claim 28, further comprising:

means for maintaining the previous copies of the identifying information in the event the system call is aborted.

30. The system of claim 28, wherein:

the table has identifying information about a plurality of message queues.

31. The system of claim 28, wherein:

the table has identifying information about a plurality of semaphores.

32. The system of claim 28, wherein:

the table has identifying information about a plurality of shared storage segments.

33. A system for insuring reliability of system-wide data structures in a data processing system having a plurality of processors interconnected by a communications link, comprising:

means for sharing virtual storage by each of the plurality of processors during operation of said system;

means for accessing each one of a plurality of virtual storage segments of said virtual storage by a virtual address form any one of said processors during operation of said system;

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 int he 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 form 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.

34. The system of claim 33, wherein said system further comprises:

means for maintaining the previous copies of the data structure in the event the transaction is aborted.

35. The system of claim 33, further comprising:

means for updating all copies of the identifying information in the table upon the successful completion of the transaction.