Identifying a set of functionally distinct reorderings in a multithreaded program

摘要

A facility for identifying functionally distinct memory access reorderings for a multithreaded program is described. The facility monitors execution of the program to detect, for each of one or more memory locations, an order in which the memory location was accessed by the threads of the program, each access being at least one of a read access and a write access. Among a number of possible memory access reorderings of a read access by a reading thread to a location and a write access by a writing thread to the same location where the write access preceded the read access, the facility identifies as functionally distinct memory access reorderings those possible memory access reorderings where the reading thread could have become newly aware of changed state of the writing thread as a result of the indicated read access.

主权项

1. A computer-readable storage medium storing instructions that, when executed by a computing system, cause the computing system to perform operations identifying functionally distinct memory access reorderings for a multithreaded program, the operations comprising:
executing the program; during execution of the program, for each of one or more selected memory locations, observing the relative times at which each thread of the program performs read accesses to the memory location and write accesses to the memory location; using the observed memory accesses by the threads to the selected memory location to maintain vector clocks for each thread and each selected memory location, the vector clocks of the selected memory locations each having a component for each thread indicating a time corresponding to the most recent state of thread that could be represented by the contents of the memory location, the vector clocks of the threads each having a component for each other thread indicating a time corresponding to the most recent state of other thread that could have been communicated to the thread, directly or indirectly, through any of the selected memory locations; identifying each instance in which, in a vector clock of a first thread, a component for a second thread advanced from a first time to a second time, wherein a time window is delineated starting at the first time and ending at the second time; for each identified instance,
identifying a memory location read by the first thread that caused the advance in the component of the vector clock of the first for the second thread;identifying a set of memory write operations by the second thread to the identified memory location that occurred in the time window, while excluding from the set all operations occurring outside the time window; andfor each identified write operation in the set, storing an indication that reordering the read access to the identified memory location by the first thread with the identified write access to the identified memory location is a functionally distinct reordering.