Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
sav07_lecture_26 [2007/07/01 23:20] feride.cetin |
sav07_lecture_26 [2007/07/03 00:06] feride.cetin |
||
|---|---|---|---|
| Line 146: | Line 146: | ||
| ===== Goldilocks ===== | ===== Goldilocks ===== | ||
| + | == Introduction == | ||
| + | Goldilocks is a lockset-based algorithm for precisely computing the happens-before relation and detecting data-races at runtime(dynamic race detection). | ||
| + | == Dynamic race detection == | ||
| + | 1. Vector clocks | ||
| + | * precisely compute the happens-before relation | ||
| + | * have significantly more overhead | ||
| + | 2. Locksets | ||
| + | * imprecise -> may generate false race warnings | ||
| + | * efficient | ||
| + | |||
| + | * **Goldilocks:** | ||
| + | - precise | ||
| + | - efficient (purely lockset based) | ||
| + | |||
| + | * **Happens-before relation:** Data race occurs between two accesses to a shared variable if they are not ordered by the happens-before relation. | ||
| + | |||
| + | * A concurrent execution δ is represented by a finite sequence | ||
| + | |||
| + | {{sav1.jpg|Figure 4}} | ||
| + | - t<sub>i</sub> is a thread | ||
| + | - s<sub>i</sub> is a program state | ||
| + | - α<sub>i</sub> is one of the following actions: acq(), rel (), read(), write(), fork (), join(), and alloc() | ||
| + | |||
| + | == References == | ||
| * [[http://iacoma.cs.uiuc.edu/iacoma-papers/asid06.pdf|Accurate and Efficient Filtering for the Intel Thread Checker Race Detector]] | * [[http://iacoma.cs.uiuc.edu/iacoma-papers/asid06.pdf|Accurate and Efficient Filtering for the Intel Thread Checker Race Detector]] | ||
| * [[http://www.vs.inf.ethz.ch/publ/papers/VirtTimeGlobStates.pdf]] | * [[http://www.vs.inf.ethz.ch/publ/papers/VirtTimeGlobStates.pdf]] | ||