MSDN Magazine - June 2008 - (Page 55)

such tools might warn about races that are in fact benign, reporting errors known as false positives. A deadlock occurs when two or more threads wait on each other, forming a cycle and preventing all of them from making any forward progress. Deadlocks can be introduced by the programmer while trying to avoid race conditions. For example, incorrect use of synchronization primitives such as acquiring locks in an incorrect order can result in two or more threads waiting for each other. Deadlocks can also occur in cases that don’t use locking constructs; any kind of circular wait can result in a deadlock. Take a look at the following example of a potential deadlock situation. Thread 1 does the following: Acquire Lock A; Acquire Lock B; Release Lock B; Release Lock A; Thread 2 proceeds like so: Acquire Lock B; Acquire Lock A; // if thread 1 has already acquired lock // A and waiting to acquire lock B, then // this is a deadlock Release Lock A; Release Lock B; Here, the optimizing compiler might observe that y will eventually be reassigned to 5 anyway, and it might reorder the code such that y gets assigned 5 before x gets assigned 10; from the perspective of the single thread executing these two assignments, the ordering doesn’t matter. Hence, there is a chance that Thread 2’s assert will get fired, since x might not equal 10. Where necessary, one can avoid compiler memory reordering High CPU utilization with no sign of real work being done is a classic warning of a livelock. by using volatile variables and compiler intrinsics. It is also worth mentioning that with common optimization flags turned on, Thread 2 may never see an update to variables y or x. Here the user will have to use volatile variables. Compiler reordering is not the only complication. Memory access optimizations such as caching and advanced fetching by speculative executions may cause memory operations executed by one thread on one CPU to be perceived to have happened in a different order by another thread on another CPU. This kind of memory reordering perception can only happen in a system with multiple CPUs or multiple CPU cores. To clarify, suppose there are two threads of execution: thread 1 and thread 2. Further assume m and n are global, both initialized to 0, and a, b, c, d are local variables. Thread 1 (on processor 1) has these instructions: m = 5; // A1 int a = m; // A2 int b = n; // A3 Starvation is an indefinite delay or permanent blocking of one or more runnable threads in a multithreaded application. Threads that are not being scheduled to run even though they are not blocking or waiting on anything else are said to be starving. Starvation is typically the result of scheduling rules and policies. For example, if one schedules a high-priority, non-blocking, continuously executing thread along with a low-priority thread, then, on a single core CPU, the lower thread will never get a chance to run. To help avoid such conditions, the Windows® scheduler intervenes frequently to reduce starvation by occasionally boosting priorities of starving threads. Livelocks occur when threads are scheduled but are not making forward progress because they are continuously reacting to each other’s state changes. The best way to describe this is if two people were to approach each other in a narrow hallway and they step aside for one another, each time blocking the other’s path. Such side stepping prevents forward progress and results in a live lock. High CPU utilization with no sign of real work being done is a classic warning sign of a livelock. Livelocks are incredibly difficult to detect and diagnose. When the compiler is optimizing code, it may decide to reorder pieces of code to improve performance. However, this can cause unexpected behavior in threads monitoring changes to global state. For example, let’s say you have two threads of execution: thread 1 and thread 2. Let’s also assume two global variables, x and y, both initialized to 0. Thread 1 runs these lines: x=10; y=5; Thread 2 (on processor 2) has these: n = 5; //A4 int c = n; //A5 int d = m; //A6 Problems from Memory Ordering Logically (in a sequentially consistent memory world), b == d == 0 can never happen after all of these instructions have executed. However, hardware memory reordering can cause the writes to shared memory (A1 and A4) to be store-buffer forwarded, which can lead the different processors to observe the writes differently. Testing Strategies Thread 2 executes the following: if (y == 5) { Assert(x != 10); } Testing a concurrent application entails testing for correctness, reliability, performance, and scalability. The correctness of the application is determined using techniques such as static analysis, dynamic analysis, and model checking. Performance and reliability are tested for by studying the overheads introduced by parallelism and stress testing. Scalability is tested by analyzing how well the application performs on systems of varying sizes. Static analysis techniques analyze code without actually executing the program. Usually, static analysis is performed by looking at metadata from a compiled application or annotated source code. June 2008 55 msdnmagazine.com 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.