Mutual-Exclusion Algorithms Resilient to Transient Memory Faults

• US 20120159504A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Moscibroda, Thomas, Oshman, Rotem
• Granted Patent: US 8,943,510 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 2201/825 the problem or solution involving locking
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Techniques for implementing mutual-exclusion algorithms that are also fault-resistant are described herein. For instance, this document describes systems that implement fault-resistant, mutual-exclusion algorithms that at least prevent simultaneous access of a shared resource by multiple threads when (i) one of the multiple threads is in its critical section, and (ii) the other thread(s) are waiting in a loop to enter their respective critical sections. In some instances, these algorithms are fault-tolerant to prevent simultaneous access of the shared resource regardless of a state of the multiple threads executing on the system. In some instances, these algorithms may resist (e.g., tolerate entirely) transient memory faults (or “soft errors”).

Claims

1. A system comprising:

one or more processors;

one or more memories;

a first thread, stored in the one or more memories and executable on the one or more processors, the first thread including a critical section;

a second thread, stored in the one or more memories and executable on the one or more processors, the second thread also including a critical section; and

an execution engine, stored in the one or more memories and configured to cause execution of the first and second threads on the one or more processors using a fault-resistant, mutual-exclusion algorithm that at least prevents simultaneous execution of the critical section of the first thread and the critical section of the second thread after the system experiences a soft error and when (i) one of the first and second threads is in its critical section, (ii) the other of the first and second threads is waiting in a loop to enter its critical section, and (iii) there is no contention between the first and second threads.

2. A system as recited in claim 1, wherein the execution engine further prevents, with use of the fault-resistant, mutual-exclusion algorithm, simultaneous execution of the critical section of the first thread and the critical section of the second thread after the system experiences the soft error when there is contention between the first and second threads.

3. A system as recited in claim 1, wherein the fault-resistant, mutual-exclusion algorithm is fault-tolerant to prevent the simultaneous execution of the critical section of the first thread and the critical section of the second thread regardless of when the system experiences the soft error.

4. A system as recited in claim 1, wherein each of the critical sections accesses a common resource when executed, and wherein the fault-resistant, mutual-exclusion algorithm prevents simultaneous access to the common resource.

5. A system as recited in claim 1, wherein:

the fault-resistant, mutual-exclusion algorithm defines an entry section of code for the first and second threads to execute prior to execution of their respective critical sections; and

the fault-resistant, mutual-exclusion algorithm is configured to resist m faults by;

when the first or second thread completes the entry section, instructing the first or second thread to determine whether each of m+1 shared variables has been set;

instructing the first or second thread to again execute the entry section when the first or second thread determines that at least one of the m+1 shared variables has been set; and

instructing the first or second thread to execute the respective critical section when the first or second thread determines that each of the m+1 shared variables has not been set.

6. A system as recited in claim 5, wherein the fault-resistant, mutual-exclusion algorithm is further configured to resist m faults by:

instructing the first or second thread to set each of the m+1 shared variables after the first or second thread completes its execution of the entry section and determines that each of the m+1 shared variables have not been set.

7. A system as recited in claim 5, wherein the fault-resistant, mutual-exclusion algorithm defines an exit section of code for the first and second threads to execute after execution of their respective critical sections, and wherein the fault-resistant, mutual-exclusion algorithm is further configured to resist m faults by:

instructing the first or second thread to clear each of the m+1 shared variables after executing the respective critical section and prior to starting the respective exit section.

8. A system as recited in claim 1, wherein a selected subset of steps of the fault-resistant, mutual-exclusion algorithm comprise Dekker'"'"'s algorithm or Peterson'"'"'s algorithm.

9. A system as recited in claim 1, wherein:

the one or more memories further store third and fourth threads having respective critical sections of code executable on the one or more processors; and

the execution engine is further configured to enable the first, second, third, and fourth threads to compete with one another to enter the respective critical section.

10. A system as recited in claim 1, wherein the first thread and the second thread are executable on a same one or different ones of the one or more processors, and the first thread and the second thread are stored in a same one or different ones of the one or more memories.

11. A system comprising:

one or more processors;

one or more memories;

an execution engine, stored in the one or more memories and configured to cause execution of first and second threads on the one or more processors using a fault-resistant, mutual-exclusion algorithm that substantially prevents simultaneous access to a common resource by the first and second threads after the system experiences m soft errors, the fault-resistant, mutual-exclusion algorithm substantially preventing the simultaneous access of the resource at least partly by satisfying the hamming-distance-(m+1) property.

12. A system as recited in claim 11, wherein the first and second threads each include a respective critical section of code that accesses the resource and a remainder section of code that executes after the critical section, and wherein the fault-resistant, mutual-exclusion algorithm satisfies the hamming-distance-(m+1) property by having a hamming distance of m+1 bits between v and v′

, wherein;

v represents the state of memory shared between the first and second threads when the first and second threads are in the respective remainder sections; and

v′

represents the state of the memory shared between the first and second threads when one of the first and the second threads is in its respective critical section and the other of the first and second threads is in its respective remainder section.

13. A system as recited in claim 11, wherein the first and second threads each include a respective critical section of code that accesses the resource, and wherein the fault-resistant, mutual-exclusion algorithm also substantially prevents the simultaneous access of the resource by instructing the first and second threads to engage in a handshake that, when completed, enables the first thread or the second thread to enter its respective critical section.

14. A system as recited in claim 13, wherein the fault-resistant, mutual-exclusion algorithm defines an entry section of code for the first and second threads to execute prior to execution of their respective critical sections, and wherein the fault-resistant, mutual-exclusion algorithm instructs the first and second threads to engage in the handshake based at least in part on:

(i) one of the first and second threads being in the entry section; and

(ii) the other of the first and second threads being in the entry section or its critical section.

15. A system as recited in claim 11, wherein the fault-resistant, mutual-exclusion algorithm comprises a fault-tolerant, mutual-exclusion algorithm that prevents the simultaneous access of the resource by the first and second threads after the system experiences the m soft errors and regardless of when the system experiences the m soft errors.

16. A system as recited in claim 11, wherein:

the first and second threads each include a respective critical section of code that accesses the resource;

the resource is further accessible to respective critical sections of code of third and fourth threads stored in the one or more memories and executing on the one or more processors; and

the execution engine is further configured to enable the first, second, third, and fourth threads to compete with one another to enter the respective critical section.

17. A system comprising:

one or more processors;

one or more memories;

a resource, stored in the one or more memories and accessible to first and second threads stored in the one or more memories and executing on the one or more processors, the first and second threads each including a respective critical section of code that accesses the resource; and

an execution engine, stored in the one or more memories and configured to cause execution of the first and second threads on the one or more processors using a fault-resistant, mutual-exclusion algorithm, wherein the fault-resistant, mutual-exclusion algorithm;

prevents simultaneous access of the resource by the first and second threads after the system experiences m soft errors when (i) one of the first and second threads is in its critical section, (ii) the other of the first and second threads is waiting in a loop to enter its critical section, and (iii) there is no contention between the first and second threads;

satisfies the hamming-distance-(m+1) property; and

instructs the first and the second threads to engage in a handshake that, when completed, enables the first thread or the second thread to enter its respective critical section.

18. A system as recited in claim 17, wherein the fault-resistant, mutual-exclusion algorithm is also fault-tolerant to prevent the simultaneous access of the resource by the first and second threads regardless of when the system experiences the m soft errors.

19. A system as recited in claim 17, wherein the fault-resistant, mutual-exclusion algorithm prevents the simultaneous access of the resource by the first and second threads after the system experiences the m soft errors with reference to at least m variables stored in the one or more memories and shared between the first and second threads.

20. A system as recited in claim 17, wherein the first and second threads each include a remainder section of code that executes after the respective critical section, and wherein the fault-resistant, mutual-exclusion algorithm satisfies the hamming-distance-(m+1) property by having a hamming distance of m+1 bits between v and v′

, wherein;

v represents the state of memory shared between the first and second threads when the first and second threads are in the respective remainder sections; and

v′

represents the state of the memory shared between the first and second threads when one of the first and the second threads is in its respective critical section and the other of first and second threads is in its respective remainder section.