Transparent consistent active replication of multithreaded application programs

• US 7,231,554 B2
• Filed: 03/24/2003
• Issued: 06/12/2007
• Est. Priority Date: 03/25/2002
• Status: Expired due to Fees

• Current Assignee: Open Invention Network LLC
• Original Assignee: Availigent, Inc.
• Inventors: Melliar-Smith, Peter M., Moser, Louise E.
• Primary Examiner(s): Bonzo; Bryce P.
• Application Number:
  US10/397,038
• Publication Number:
  US 20040078617A1
• Time in Patent Office: 1,541 Days
• Field of Search: 714/38, 714/51, 714/50
• US Class Current: 714/38.13
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1492 by run-time replication performed by the application software
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2209/542 Intercept
• CPC Class Codes: G06F 2209/546 Xcast
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A method and system for transparent consistent active replication of multithreaded application programs is described. At each replica, control messages that contain mutex ordering information indicating the order in which threads in the replicas claim mutexes are multicast, and the control messages are delivered using a multicast group communication protocol that delivers the messages in an order that determines the order in which the operating system'"'"'s thread library grants the claims of mutexes to the threads in the replicas. Because the replicas receive the same messages in the same source order, the corresponding threads in the different replicas are granted their corresponding claims to the corresponding mutexes in the same order, maintaining strong replica consistency.

Claims

1. A system for executing threads in replicas of an application program within a computing environment, using the active replication strategy, in which resources are shared between threads in a replica, wherein said shared resources comprise either data or code sections for manipulating said data, comprising:

means for communicating to multiple replicas the claims of shared resources by threads in a replica; and

means for ordering shared resource claims to be granted to threads in multiple replicas corresponding to the order in which claims for the resources were communicated, ordered and delivered through said means for communicating the order of claiming;

wherein a thread within a replica is suspended upon claiming a shared resource until said claim is communicated to all of said replicas; and

wherein said thread suspension is suppressed if said shared resource claim has already been communicated to all of the replicas.

2. A system as recited in claim 1, wherein said means for ordering resource claims is configured to prevent threads from being granted a shared resource until claim information has been communicated to the replicas by at least one of said replicas.

3. A system as recited in claim 2, wherein each said replica is configured to order shared resource claims in response to the order of arrival of said shared resource claim information communicated to said replicas.

4. A system as recited in claim 3, wherein said shared resource claim information is communicated by multicasting a message to said replicas.

5. A system as recited in claim 4, wherein shared resource claim granting is configured to maintain an identical claim granting order across said replicas.

6. A system as recited in claim 1, wherein said means for communicating to multiple replicas comprises a means for simultaneously communicating shared resource claim information from a thread in a given replica to all of the replicas.

7. A system as recited in claim 6, wherein said means for simultaneously communicating shared resource claims comprises the multicasting of messages to said replicas.

8. A system as recited in claim 7, wherein said multicast messages contain information about which shared resource is being claimed, which thread is claiming the given shared resource, and which shared resource claim request of said thread is being made.

9. A system as recited in claim 8, wherein said information of which shared resource claim request of said thread is being made comprises a shared resource claim number.

10. A system as recited in claim 1, wherein said means for ordering shared resource claims comprises a routine for selectively granting a resource request, with a particular resource claim number, based on the order in which that resource request was communicated, ordered and delivered to the replicas.

11. A system as recited in claim 1, wherein said means of ordering shared resource claims controls access to a mutual exclusion construct (mutex) through which access to said shared resource is controlled.

12. A system as recited in claim 11, wherein access to said shared resource is controlled by multicasting a message to said replicas.

13. A system as recited in claim 12, wherein said message being multicast comprises elements that identify a shared resource, a thread wanting to access said shared resource, and the thread'"'"'s resource claim number.

14. A system as recited in claim 1,

wherein said means for communicating and said means of ordering are configured to transparently execute within said system;

wherein said transparent execution is provided in application replicas without modifying the application code.

15. A system as recited in claim 14, wherein said transparent execution comprises executing functions of a consistent multithreading library for said replicas that do not require the application program code to be modified to perform said means for communicating, and said means for ordering.

16. A system as recited in claim 1, further comprising means for communicating pending claims for shared resources to the replicas.

17. A system as recited in claim 16, wherein said means for communicating pending claims for shared resources comprises multicasting a message to all of the replicas.

18. A system as recited in claim 17, wherein said message comprises information about the order in which the threads claim said shared resource.

19. A system as recited in claim 1, wherein said means for ordering shared resource claims in which each corresponding shared resource in a replica maintains identical ordering of corresponding accesses to that shared resource for the corresponding threads in that replica.

20. A system as recited in claim 19, wherein said resource claim information for a particular thread is recorded in an ordered claims queue in the order in which said claims are to be fulfilled.

21. A system as recited in claim 1, wherein said means for communicating, and said means for ordering, are configured as a set of functions of a consistent multithreading library that are executed in response to selected calls to functions of the operating system'"'"'s thread library.

22. A system as recited in claim 21, wherein said set of functions are configured to intercept calls to select functions within the operating system'"'"'s thread library.

23. A system as recited in claim 22, wherein said set of functions are dynamically linked into the replicas of said program.

24. A system as recited in claim 23, wherein said set of functions are configured for claiming or releasing a shared resource in a virtually deterministic manner in which identical threads in separate replicas are granted resource access in an identical order.

25. A system as recited in claim 23, wherein said functions of the consistent multithreading library are configured to maintain replica consistency without the need to modify object code, impose single threaded execution, impose distinctions such as Primary and Backup on the replicas, or count instruction execution between non-deterministic events.

26. A system as recited in claim 21, wherein said functions of said consistent multithreading library, including said means for communicating, and said means for ordering are configured to maintain strong replica consistency, by forcing virtually deterministic execution.

27. A system as recited in claim 26, wherein the threads in said replicas are forced to access the resources that they share in an identical order.

28. A system as recited in claim 26, wherein said strong replica consistency is maintained within client-server systems.

29. A system as recited in claim 26, wherein said strong replica consistency is maintained within fault-tolerant systems.

30. A system as recited in claim 26, wherein for said replicas strong replica consistency is maintained without distinguishing replicas into roles as either Primary or Backup replicas.

31. A system as recited in claim 26, wherein said strong replica consistency is maintained without the need to provide special hardware.

32. A system as recited in claim 26, wherein said strong replica consistency is maintained without the need to perform hardware or software instruction counting between non-deterministic events.

33. A system as recited in claim 26, wherein said strong replica consistency is maintained without modifying either the application source code or the application object code.

34. A system as recited in claim 21, wherein said shared resource comprises memory or an input/output location accessible to the threads of said replica.

35. A system as recited in claim 21, wherein said means for communicating is configured to communicate messages containing shared resource claim information.

45. A system for replicating multithreaded application programs on computers within a computing environment, using the active replication strategy to host replicas, comprising:

means for linking with said application program and processing shared resource access requests, as contained within a consistent multithreading library; and

means maintaining an identical order of shared resource access by threads within replicas, thereby providing virtual determinism and strong replica consistency;

wherein said means for maintaining an identical order of resource access is configured for;

multicasting a message identifying resource claims; and

granting claims for resources in response to the order in which messages identifying resource claims are delivered;

wherein said message contains information that identifies the shared resource for which a claim is being made, the thread that is claiming the resource, and the resource claim number of the thread;

wherein said granting of claims, in response to the order in which messages containing resource claims are delivered, causes the suspension of threads claiming a shared resource, until said resource is available and any prior claims for that resource have been granted; and

wherein a prior claim for a resource, relative to a specific claim, is a claim contained in a message that is ordered and delivered ahead of the first message that contained said specific claim.

46. A system as recited in claim 45, wherein said computers that host said replicas of said application programs are configured for executing a programming within an environment supporting multithreading, multitasking, distributed computing, fault tolerance, or a client-server paradigm.

47. A system as recited in claim 45, wherein said means for maintaining an identical order of resource access comprises functions of a consistent multithreading library that are executed in response to shared resource access requests and associated operations.

48. A system as recited in claim 47, wherein said functions of said consistent multithreading library are configured as wrapper functions of the functions of the operating system'"'"'s thread library.

49. A system as recited in claim 48, wherein said functions of said consistent multithreading library are configured to:

communicate shared resource claim information to all of the replicas;

order resource claim information in each replica in response to the order in which shared resource claims are delivered; and

grant shared resource claims in each replica in response to said order, wherein the corresponding threads of the replicas access corresponding shared resources in an identical order.

50. A system as recited in claim 49, wherein said library is configured for maintaining pending claims and ordered claims queues that record the order in which mutexes are claimed, granted and released.

51. A system as recited in claim 47, wherein said wrapper functions of consistent multithreading library intercept calls to the operating system'"'"'s thread library and execute preceding the execution of functions of the operating system'"'"'s thread library.

52. A system as recited in claim 51, wherein said consistent multithreading library is configured for being dynamically linked into said application programs.

36. A system executing a multithreaded application program within a computing environment in which replicas of said program are created using the active replication strategy, comprising:

a computer configured for executing said replicas; and

programming associated with said computer for carrying out the operations of, suspending a thread that claims a shared resource, in response to programming of functions contained in a consistent multithreading library;

communicating the order of the claims of the shared resources by the threads in the replicas, in response to the operation of a multicast group communication protocol; and

granting access to shared resources, and activating suspended threads, in response to said ordering of shared resource claims when said resources are available, in response to resource granting functions;

wherein multicasting of a claim request can be suppressed if a given replica has already received the same claim for the same shared resource by the same thread.

37. A system as recited in claim 36, wherein a resource identifier, thread identifier, and claim identifier, are communicated by said multicast group communication protocol.

38. A system as recited in claim 36, wherein said replicated multithreaded program is rendered virtually deterministic in order to maintain strong replica consistency.

39. A system as recited in claim 36, wherein said resource granting functions are executed in conjunction with a consistent multithreading library for controlling access to shared resources.

40. A system as recited in claim 39:

wherein said functions of said consistent multithreading library intercept calls to functions of the operating system'"'"'s thread library,

wherein strong replica consistency is maintained while said functions of the consistent multithreading library remain transparent to said application program.

41. A system as recited in claim 36, wherein the order in which said multicast protocol delivers messages containing a claim by a given thread for access to a given shared resource for a given claim number, determines the order in which the claims to the shared resource are granted to said threads in said replicas within said computing environment.

42. A system as recited in claim 36, wherein said thread suspension, multicast group communication of claim order, and resource granting functions are invoked by functions of the consistent multithreading library that intercept the functions for claiming and releasing resources provided by the operating system'"'"'s thread library.

43. A system as recited in claim 36, wherein threads that are not currently claiming the same shared resources are allowed to process concurrently.

44. A system as recited in claim 36, wherein said communication comprises the multicasting of messages containing information, or the writing into shared memory of information, related to the claiming of shared resources.

53. A method of identically ordering accesses to corresponding shared resources by corresponding threads in different replicas of an actively replicated multithreaded application program, comprising:

invoking a claim on a shared resource by a thread in a replica in preparation for accessing said shared resource;

suspending execution of said thread invoking said resource claim;

multicasting a message to communicate information about said resource claim by said thread in said replica to all of the replicas;

ordering and delivering said information about said resource claims by said multicast;

granting access to said resource, when available, to a thread in response to the order in which said information is delivered to the replicas; and

releasing said resource, by said thread granted said resource, after said thread has completed accessing said shared resource.

54. A method as recited in claim 53, wherein access to said shared resource is controlled by a mutual exclusion construct (mutex), to which a claim by a given thread must be granted prior to that thread accessing said shared resource associated with said mutual exclusion construct.

55. A method as recited in claim 54, wherein information about said shared resource claims is recorded in pending claims and ordered claims queues.

56. A method as recited in claim 54, wherein said claim to a mutual exclusion construct is obtained by the steps comprising:

(a) determining (T, M, N) for a claim to a mutual exclusion construct associated with said shared resource, wherein T represents the thread making said claim, M represents the mutual exclusion construct being claimed, and N represents the claim number by thread to any mutex;

(b) determining if (T, N) is the next thread and claim number for which access to the mutual exclusion construct M is to be granted, and if so, the following is performed,

(i) recording that thread T has been granted its Nth claim,

(ii) marking said mutual exclusion construct as unavailable,

(iii) granting said mutual exclusion construct to thread T, and

(iv) bypassing following steps (c) through (e);

(c) determining that a claim (T, N) has not been delivered, in which case information about the claim is multicast to other replicas;

(d) marking thread T claiming mutual exclusion construct M as suspended; and

(e) suspending thread T.

57. A method as recited in claim 56, wherein said resource releasing comprises:

marking the mutual exclusion construct associated with said resource as available;

selecting the next ordered and delivered but ungranted claim (T′

, N′

) for the mutual exclusion construct, wherein T′

represents the thread making said resource claim and N′

represents the claim number by thread T′

; and

signaling thread T′

to awaken thread T′

, if thread T′

is suspended.

58. A method as recited in claim 53, wherein said method of identically ordering accesses to shared resources by threads in replicas comprises a consistent multithreading library containing functions that control access to shared resources.

59. A method as recited in claim 58, wherein said consistent multithreading library is interposed ahead of the operating system'"'"'s thread library and where the functions of the consistent multithreading library wrap the corresponding functions of the operating system'"'"'s thread library.

60. A method as recited in claim 59, wherein said consistent multithreading library is interposed ahead of the operating system'"'"'s thread library by dynamic or static linking.