Symmetric Multiprocessor Fault Tolerant Computer System

• US 20070214340A1
• Filed: 05/23/2006
• Published: 09/13/2007
• Est. Priority Date: 05/24/2005
• Status: Active Grant

• Current Assignee: Stratus Technologies Ireland Ltd. (Stratus Technologies Bermuda Holdings Ltd.)
• Original Assignee: Marathon Technologies Corporation (Stratus Technologies Bermuda Holdings Ltd.)
• Inventors: Koyama, Keiichi, Melnick, Jerry, Watanabe, Satoshi, Leveille, Paul, Bissett, Thomas, Corbin, Stephen, Tremblay, Glenn
• Granted Patent: US 7,877,552 B2
• Time in Patent Office: Days
• US Class Current: 711/203
• CPC Class Codes: G06F 11/1405 at machine instruction level
• CPC Class Codes: G06F 11/1683 at instruction level
• CPC Class Codes: G06F 11/1691 using a quantum
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• 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 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A symmetric multiprocessing fault-tolerant computer system controls memory access in a symmetric multiprocessing computer system. To do so, virtual page structures are created, where the virtual page structures reflect physical page access privileges to shared memory for processors in a symmetric multiprocessing computer system. Access to shared memory is controlled based on physical page access privileges reflected in the virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system. A symmetric multiprocessing fault-tolerant computer system may use duplication or continuous replay.

Claims

1. A method of implementing a fault-tolerant computer system using symmetric multiprocessing computer systems, the method comprising controlling at least one of the symmetric multiprocessing computer systems by:

creating virtual paging structures, a virtual paging structure being associated with a processor in the symmetric multiprocessing computer system and reflecting physical page access privileges to shared memory for the processor; and

controlling access to shared memory based on physical page access privileges reflected in the virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system.

2. The method of claim 1 wherein controlling access to shared memory comprises:

receiving a request from a processor to access a portion of memory;

determining access to the portion of memory to be permitted by the processor by comparing the virtual paging structure for the processor to the virtual paging structures for other processors that access the portion of memory; and

updating physical page access privileges in the virtual paging structure for the processor based on the access to be permitted by the processor.

3. The method of claim 1 wherein the processor comprises a task executing on a processor.

4. The method of claim 1 wherein the virtual paging structure comprises shadow page tables, wherein a shadow page table comprises a copy of a page table created by the operating system of the symmetric multiprocessing computer system and is associated with a processor of the symmetric multiprocessing computer system.

5. The method of claim 1 wherein the virtual paging structure comprises nested page tables that collectively provide two or more levels of virtual to physical translation.

6. The method of claim 1 wherein creating virtual paging structures comprises creating page tables prior to execution of any task by a processor in the symmetric multiprocessing computer system.

7. The method of claim 1 wherein creating virtual paging structures comprises creating at least page directories prior to execution of any task by a processor in the symmetric multiprocessing computer system.

8. The method of claim 1 wherein the fault-tolerant computer system is a duplication fault tolerant computer system comprising two symmetric multiprocessing computer systems operating simultaneously in instruction lock-step and each controlling access to shared memory based on physical page access privileges reflected in virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system.

9. The method of claim 1 wherein:

the symmetric multiprocessing computer system comprises a first symmetric multiprocessing computer system, and

the fault-tolerant computer system is a continuous replay fault-tolerant computer system comprising the first symmetric multiprocessing computer system and a second symmetric multiprocessing computer system, the method further comprising;

having the first symmetric multiprocessing computer system process an instruction stream and create a journal reflecting a sequence of events at the first symmetric multiprocessing computer system, and

when a failure of the first symmetric multiprocessing computer system is detected, processing the journal using the second symmetric multiprocessing computer system, such that the first and second symmetric multiprocessing computer systems operate in instruction lock-step,

having the second symmetric multiprocessing computer system create virtual paging structures, with a virtual paging structure being associated with a processor in the second symmetric multiprocessing computer system and reflecting physical page access privileges to shared memory for the processor, and

having the second symmetric multiprocessing computer system control access to shared memory based on physical page access privileges reflected in the virtual paging structures to coordinate deterministic shared memory access between processors in the second symmetric multiprocessing computer system.

10. Computer software, stored on a computer-readable medium, comprising instructions that, when executed, control at least one symmetric multiprocessing computer system of a fault-tolerant computer system by:

creating virtual paging structures, a virtual paging structure being associated with a processor in the symmetric multiprocessing computer system and reflecting physical page access privileges to shared memory for the processor; and

controlling access to shared memory based on physical page access privileges reflected in the virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system.

11. The computer software of claim 10 wherein controlling access to shared memory comprises:

receiving a request from a processor to access a portion of memory;

determining access to the portion of memory to be permitted by the processor by comparing the virtual paging structure for the processor to the virtual paging structures for other processors that access the portion of memory; and

updating physical page access privileges in the virtual paging structure for the processor based on the access to be permitted by the processor.

12. The computer software of claim 10 wherein the processor comprises a task executing on a processor.

13. The computer software of claim 10 wherein the virtual paging structure comprises shadow page tables, wherein a shadow page table comprises a copy of a page table created by the operating system of the symmetric multiprocessing computer system and is associated with a processor of the symmetric multiprocessing computer system.

14. The computer software of claim 10 wherein the virtual paging structure comprises nested page tables that collectively provide two or more levels of virtual to physical translation.

15. The computer software of claim 10 wherein creating virtual paging structures comprises creating page tables prior to execution of any task by a processor in the symmetric multiprocessing computer system.

16. The computer software of claim 10 wherein creating virtual paging structures comprises creating at least page directories prior to execution of any task by a processor in the symmetric multiprocessing computer system.

17. The computer software of claim 10 wherein the fault-tolerant computer system is a duplication fault tolerant computer system comprising two symmetric multiprocessing computer systems operating simultaneously in instruction lock-step and each controlling access to shared memory based on physical page access privileges reflected in virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system.

18. The computer software of claim 10 wherein:

the symmetric multiprocessing computer system comprises a first symmetric multiprocessing computer system, and

the fault-tolerant computer system is a continuous replay fault-tolerant computer system comprising the first symmetric multiprocessing computer system and a second symmetric multiprocessing computer system, the method further comprising;

having the first symmetric multiprocessing computer system process an instruction stream and create a journal reflecting a sequence of events at the first symmetric multiprocessing computer system, and

when a failure of the first symmetric multiprocessing computer system is detected, processing the journal using the second symmetric multiprocessing computer system, such that the first and second symmetric multiprocessing computer systems operate in instruction lock-step,

having the second symmetric multiprocessing computer system create virtual paging structures, with a virtual paging structure being associated with a processor in the second symmetric multiprocessing computer system and reflecting physical page access privileges to shared memory for the processor, and

having the second symmetric multiprocessing computer system control access to shared memory based on physical page access privileges reflected in the virtual paging structures to coordinate deterministic shared memory access between processors in the second symmetric multiprocessing computer system.

19. A duplication fault-tolerant computer system comprising two symmetric multiprocessing computer systems operating simultaneously in instruction lock-step and each controlling access to shared memory based on physical page access privileges reflected in virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system,

wherein a virtual paging structure is associated with a processor in one of the symmetric multiprocessing computer systems and reflects physical page access privileges to shared memory for the processor.

20. The fault-tolerant computer system of claim 19 wherein controlling access to shared memory comprises:

receiving a request from a processor to access a portion of memory;

determining access to the portion of memory to be permitted by the processor by comparing the virtual paging structure for the processor to the virtual paging structures for other processors that access the portion of memory; and

updating physical page access privileges in the virtual paging structure for the processor based on the access to be permitted by the processor.

21. The fault-tolerant computer system of claim 19 wherein the processor comprises a task executing on a processor.

22. The fault-tolerant computer system of claim 19 wherein the virtual paging structure comprises shadow page tables, wherein a shadow page table comprises a copy of a page table created by the operating system of the symmetric multiprocessing computer system and is associated with a processor of the symmetric multiprocessing computer system.

23. The fault-tolerant computer system of claim 19 wherein the virtual paging structure comprises nested page tables that collectively provide two or more levels of virtual to physical translation.

24. The fault-tolerant computer system of claim 19 wherein creating virtual paging structures comprises creating page tables prior to execution of any task by a processor in the symmetric multiprocessing computer system.

25. The fault-tolerant computer system of claim 19 wherein creating virtual paging structures comprises creating at least page directories prior to execution of any task by a processor in the symmetric multiprocessing computer system.

26. A continuous replay fault-tolerant computer system comprising:

a first symmetric multiprocessing computer system and a second symmetric multiprocessing computer system operating in instruction lockstep, each controlling access to shared memory based on physical page access privileges reflected in virtual paging structures to coordinate deterministic shared memory access between processors in the symmetric multiprocessing computer system;

the first symmetric multiprocessing computer system processing an instruction stream and creating a journal reflecting sequence of events at the first symmetric multiprocessing computer system; and

when a failure of the first symmetric multiprocessing computer system is detected, processing the journal using the second symmetric multiprocessing computer system, the first and second symmetric multiprocessing computer systems operating in instruction lock-step,

wherein a virtual paging structure is associated with a processor in each of the symmetric multiprocessing computer systems and reflects physical page access privileges to shared memory for the processor.

27. The fault-tolerant computer system of claim 26 wherein controlling access to shared memory comprises:

receiving a request from a processor to access a portion of memory;

determining access to the portion of memory to be permitted by the processor by comparing the virtual paging structure for the processor to the virtual paging structures for other processors that access the portion of memory; and

updating physical page access privileges in the virtual paging structure for the processor based on the access to be permitted by the processor.

28. The fault-tolerant computer system of claim 26 wherein the processor comprises a task executing on a processor.

29. The fault-tolerant computer system of claim 26 wherein the virtual paging structure comprises shadow page tables, wherein a shadow page table comprises a copy of a page table created by the operating system of the symmetric multiprocessing computer system and is associated with a processor of the symmetric multiprocessing computer system.

30. The fault-tolerant computer system of claim 26 wherein the virtual paging structure comprises nested page tables that collectively provide two or more levels of virtual to physical translation.

31. The fault-tolerant computer system of claim 26 wherein creating virtual paging structures comprises creating page tables prior to execution of any task by a processor in the symmetric multiprocessing computer system.

32. The fault-tolerant computer system of claim 26 wherein creating virtual paging structures comprises creating at least page directories prior to execution of any task by a processor in the symmetric multiprocessing computer system.