MSDN Magazine - June 2008 - (Page 58)

developers and testers who had to solely rely on stress for better interleaved testing. It takes regular unit tests and methodically simulates interesting interleavings. The Intel Thread Checker This is a dynamic analysis tool for finding deadlocks (including potential deadlocks), stalls, data races, and incorrect uses of the native Windows synchronization APIs (see go.microsoft.com/fwlink/?LinkId=115727). The Thread Checker needs to instrument either the source code or the compiled binary to make every memory reference and every standard Win32 synchronization primitive observable. At run time, the instrumented binary provides sufficient information for the analyzer to construct a partial-order of execution. The tool then performs a “happens-before” analysis on the partial order. Please refer to the “Race Detection Algorithms” sidebar for more information on happens-before analysis. For performance and scalability reasons, instead of remembering all accesses to a shared variable, the tool only remembers recent accesses. This helps to improve the tool’s efficiency while analyzing Performance testing is an integral part of the concurrency testing process. long-running applications. However, the side effect is that it will miss some bugs. It’s a trade-off, and perhaps it’s more important to find many bugs in long-running applications than to find all bugs in a very short-lived application. The only other big drawback of the tool is that it can’t account for synchronization via interlocked operations, such as those used in custom spin locks. However, for applications that use only standard synchronization primitives, this is probably one of the best-supported test tools available for concurrency testing native applications. racerX This flow-sensitive static analysis tool is used for detecting races and deadlocks. It overcomes the requirement to tediously annotate the entire source code. In fact, the only annotation requirement is that users provide a table specifying APIs used to acquire and release locks. The locking primitives’ attributes such as spinning, blocking, and re-entrancy can also be specified. This table will typically be very small, 30 entries at most. This tremendously reduces the burden of source annotation for large systems. In the first phase, RacerX iterates over each source code file and builds a Control Flow Graph (CFG). The CFG has information related to function calls, shared memory, use of pointers, and other data. As it builds the CFG, it also refers back to the table of synchronization primitives and marks calls to these APIs. Once the complete CFG is built, the analysis phase kicks in, which includes running the race checker and deadlock checker. Traversing the CFG can be lengthy, but appropriate reduction and caching techniques are utilized to minimize the impact. As the context flow is traversed, the lockset algorithm is used to catch potential 58 msdn magazine races (refer to the “Race Detection Algorithms” sidebar for details about the algorithm). For deadlock analysis, it computes locking cycles every time locks are taken. The final phase involves post-processing all the reported errors in order to prioritize by importance and harmfulness of the error. As can be expected with static analysis, the authors spent a lot of time trying to reduce the false positives and present bugs with high confidence. The results of this tool have been impressive, and it seems very practical from a test engineering standpoint. Chord This is a flow-insensitive, context-sensitive static analysis tool for Java. Being flow-insensitive allows it be far more scalable than other static tools, but at the cost of losing precision. It also takes into account the specific synchronization primitives available in Java. The algorithm used is very involved and would require the introduction of many concepts. (See go.microsoft.com/ fwlink/?LinkId=116526 for more on Chord.) KISS Developed by Microsoft Research, this model checker tool is for concurrent C programs. Since state space explodes quickly in a concurrent system, KISS transforms a concurrent C program into a sequential program that simulates the execution of interleaving. A sequential model checker is then used to perform the analysis. The application is instrumented with statements that convert the concurrent program to a sequential program, with KISS assuming the responsibility of controlling the non-determinism. The nondeterminism context switching is bounded by similar principles described in CHESS above. The programmer is supposed to introduce asserts which validate concurrency assumptions. The tool does not report false positives. The tool is a research prototype and has been used by the Windows driver team, which primarily uses C code (see go.microsoft.com/fwlink/?LinkId=115723). Zing This tool is a pure model checker meant for design verification of concurrent programs. Zing has its own custom language that is used to describe complex states and transition, and it is fully capable of modeling concurrent state machines. Like other model checkers, Zing provides a comprehensive way to verify designs; it also helps build confidence in the quality of the design since you can verify assumptions and formally prove the presence or absence of certain conditions. It also contends with concurrent state space explosion by innovative reduction techniques. The model that Zing uses (to check for program correctness) has to be created either by hand or by translators. While some specific domain translators can be written, we have yet to come across any complete and successful translators for native or CLR applications. Without having translators, we believe Zing cannot be used in large software projects, except for verifying the correctness of critical subsections of the project (see go.microsoft.com/ fwlink/?LinkId=115725.) Performance Testing Performance testing is an integral and essential part of the concurrency testing process. After all, one of the key motivations for developing parallel applications is to deliver superior performance in comparison to sequential applications. As postulated in Amdahl’s law and Gustafson’s law, the performance gain achieved by a parallel Concurrency http://go.microsoft.com/fwlink/?LinkId=115727 http://go.microsoft.com/fwlink/?LinkId=116526 http://go.microsoft.com/fwlink/?LinkId=116526 http://go.microsoft.com/fwlink/?LinkId=115723 http://go.microsoft.com/fwlink/?LinkId=115725 http://go.microsoft.com/fwlink/?LinkId=115725

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.