Class Note for CMPSCI 691 at UMass(13)
Class Note for CMPSCI 691 at UMass(13)
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for CMPSCI 691 at UMass(13)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 691W Parallel and Concurrent Programming Spring 2006 Lecture 8 March 6 Lecturer Emery Berger Scribe Vitaliy Lvin 81 Data Races Data races form an important class of bugs that software engineers have to deal with For example Linux kernel has 46 documented races Races are typically caused by a human error failure to follow a locking discipline or overall lack of such Their exposure depends on nondeterminism of the thread scheduler which can interrupt threads at any time and cause their instructions to be interleaved in unpredictable ways They can cause unpredictable crashes and data corruption The worst property of data races is that they are notoriously hard to detect reproduce locate and eliminate which has earned them the name of Heisenbugs from the Heisenberg Uncertainty Principle Let7s de ne races more precisely De nition 81 A program has a data race two or more threads in that program access some variable simultaneously and at least one of them changes its value This de nition says nothing about the undesirable side effects of data races Races can often be benign or have no effect on program execution The usual way to prevent data races is to use mutual exclusion to serialize access to shared data Several types of data races exist 0 Readwrite con icts o Writewrite con icts 82 Data race detection There are two general approaches to detecting data races static and dynamic In the static approach the source code is being analyzed to detect unserialized accesses to shared data It may seem like a great idea but existing techniques are essentially heuristics with very large numbers of false positives due to the fact that static analysis cannot distinguish data dynamically allocated on the heap etc Most widelyused data race detection tools use the dynamic approach at the run time 821 Happensbefore The notion of happensbefore relationship was rst introduced by Lamport in the context of distributed sys tems but can be successfully applied to dynamic race detection The purpose of happensbefore relationship 8 1 82 Lecture 8 March 6 is to establish partial ordering of events across different threads processes De nition 82 Out of two sequential events in the same thread the earlier one is said to have happened before the latter one An unlock operation in one thread is said to have happened before a lock operation in a di erent thread if those operations referred to the same lock the distributed context a send of a message always happens before a receive of that same message Happensbefore is transitive Two accesses to a shared variable can form a data race if they cannot be orderd using happensbefore Detecting races using happensbefore has a number of signi cant drawbacks 0 One has to instrument the code to track perthread info about concurrent accesses to every shared location 0 Detection depends on schedulercontrolled interleaving of events to elicit races hence a high false negative rate 822 Eraser Eraser presents a different approach to dynamic race detection The key idea behind it is to track lock sets that govern access to each shared location A data race is an access to a shared variable that is not governed by locks It nds more races then happensbefore based tools7 but still causes lOSOX slowdown The lockset algorithm works as follows 1 V shared location 1 keep Cv set of candidate locks7 initially set to contain all locks 2 V accesses to 1 set 01 Cv set of currently held locks lock re nement step 3 IfCv ll show a data race warning This algorithm can sometimes be too strict 0 During intialization7 when no locks are usually held 0 Readshared data that is only written during initialization and is safe without locks throughout the rest of the program 0 Readerwriter locks The following re nements x the abovementioned problems 0 Ignore the initialization part and assume intialization is over when a thread different from the creator accesses shared data 0 Assume every shared location is safe to access without locks until rst written 0 Track locks held only when writing separately from usual lock tracking to correctly handle readerwriter locks Eraser was originally implemented using ATOM binary rewriting tool on Alpha modern binary rewriting tools like Pin exist It kept a shadow word for every word of memory in the data section and on the heap7 and instrumented every direct memory access7 which cause lOSOX slowdown Lecture 8 March 6 83 83 Races Not Enough Racesfreedom is neither a necessary nor suf cient condition of program correctness The real goal should be atomicityi
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'