MSDN Magazine - June 2008 - (Page 61)

As with test goals, every test scenario should define a set of acceptance criteria (set of values that validate the test results). For parallel test scenarios, the following variables can be used as acceptance criteria. Variance in Test results This is indicative of an unstable application. The variance in test results can be understood by calculating the standard deviation of results. CPu utilization Low CPU usage could be a sign of concurrency bugs such as deadlocks and synchronization overheads. Conversely, a high CPU utilization does not necessarily indicate success, as livelocks result in high CPU utilization. Garbage Collections For managed applications, too many memory management operations can hinder actual work execution and could point to faulty design or implementation. Total Thread execution Time This enables you to approximate the total execution time if the program was to be executed race Detection Algorithms The lockset algorithm, used in both static and dynamic analysis tools, reports a potential race when shared memory is accessed by two or more threads without the threads holding a common lock. Fundamentally, the algorithm says that for each shared memory variable v, a non-empty set of locks C(v)that will be held by every thread while accessing the variable. Initially, C(v) is the list of all locks. Each thread also maintains two sets of locks: locks(t) indicating all the locks held and writeLocks(t) indicating all the write locks held. Here’s how the algorithm proceeds: 1. For each shared memory variable v, maintain a set C(v) of locks. Initially C(v) is the list of all locks. 2. Each thread also maintains two sets of locks: locks(t) indicating all the locks held and writeLocks(t) indicating all the write locks held. 3. On each read of v by thread t: a. Set C(v) = C(v) intersection locks(t). b. If C(v) == NULL set, then raise an error. 4. On each write of v by thread t: a. Set C(v) = C(v) intersection writeLocks(t). b. If C(v) ==NULL set, then raise an error. Essentially, as the application progresses, the C(v) of each variable starts shrinking. An error is raised if the C(v) ever becomes null (for example, if the intersection of the threads’ locksets are NULL at the time of accessing the shared memory). Unfortunately, not all races reported by a lockset algorithm are real races. One can write race-free code without using locks either by applying clever programming tricks or using other synchronization primitives such as signaling. This makes finding genuine bugs really hard. Annotations and certain suppressions can help alleviate this problem. Another algorithm for detecting races is the “happens-before” algorithm, which is based on partial ordering of events in distributed systems. Here is an overview of the algorithm that computes the partial order to determine what events happened before another event (events, in this context, are all instructions, including read/ write and locks): • Within any single thread, events are ordered in the order of their occurrence. • Among threads, events are ordered according to the synchronization primitives’ properties. For example, if lock(a) is being acquired by two threads, then the unlock by one thread is said to have happened-before the lock of another thread. • If two or more threads access a shared variable, and the accesses are not deterministically ordered by the “happens-before” relationship, then a race is said to have occurred. The algorithm is illustrated in Figure A. msdnmagazine.com Thread 1’s unlock happened-before Thread 2’s lock. Thus, the access to the shared variable can never happen at the same time and there is no race. One major drawback of the algorithm is that monitoring such relationships can be very expensive. The larger issue is that the ability of this algorithm to detect races totally depends on the scheduling order. The partial order is built only for this specific instance of the scheduling and may miss bugs for the same test on a different day. Figure B will not report any races, but an execution order in Figure C will report races. Many races are known to have occurred only after several years following a product’s release. So, this detection does not leave one with a comforting sense of a complete coverage. On the flip side, happens-before generates very low false positives. Most bugs are real. However, happens-before misses many errors (false negatives) and is very hard to implement efficiently. Similarly, the lockset algorithm is very efficient, and can detect more errors. However, it tends to generate too many false positives. There have been efforts to combine these algorithms to overcome the disadvantages of both the approaches. Note: these race detection algorithms have evolved over several years, and sources to these can be found by searching the ACM /IEEE portals. Figure A Happens-Before Algorithm Figure B Races Will Not Be Reported Figure C Races Will Be Detected June 2008 61 http://msdnmagazine.com

Table of Contents Feed for the Digital Edition of MSDN Magazine - June 2008

MSDN Magazine - June 2008 Contents Toolbox CLR Inside Out Cutting Edge Patterns In Practice SAAS Concurrency Robotics Form Filler GUI Library Service Station Foundations Windows With C++ Concurrent Affairs Going Places { End Bracket }

MSDN Magazine - June 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.