Dr. Dobb's Journal - September 2008 - (Page 69)

d09sutt_p3ds 7/14/08 12:46 PM Page 69 usually pointers (C++), object references (Java, .NET), or integers. Trying to use an ordinary list ::iterator variable as a lockfree shared variable isn’t a good idea and can’t reliably meet the atomicity requirement, as we will see. Let’s consider the races on iHead and iTail in these lines from Produce and Consume: void Produce(const T& t) { … iTail = list.end(); list.erase(list.begin(), iHead); } bool Consume(T& t) { … if (iNext != iTail) { iHead = iNext; … } by protecting all such uses with locks, else you’ve written a race [3]. (Note: Using C++0x’s std::atomic is not an option for list ::iterator, because atomic requires T to be a bit-copyable type, and STL types and their iterators aren’t guaranteed to be that.) The general issue is that you can’t make assumptions about the side effects of library functions you call, and you have to make sure they’re fully performed before you publish the new state. So a slightly improved version might try to store the result of list.end into a local unshared variable and assign it after the barrier: // Better, but is it enough? list.push_back(t); tmp = list.end(); mb(); // full fence iTail = tmp; Ordering Problems in Produce Second, reads and writes of a lock-free variable must occur in an expected order, which is nearly always the exact order they appear in the program source code. But compilers, processors, and caches love to optimize reads and writes, and will helpfully reorder, invent, and remove memory reads and writes unless you prevent it from happening. The right prevention happens implicitly when you use mutex locks or ordered atomic variables (C++0x std::atomic, Java/.NET volatile); you can also do it explicitly, but with considerably more effort, using ordered API calls (e.g., Win32 InterlockedExchange) or memory fences/barriers (e.g., Linux mb). Trying to write lock-free code without using any of these tools can’t possibly work. Consider again this code from Produce, and ignore that the assignment iTail isn’t atomic as we look for other problems: list.push_back(t); // A: add the new item iTail = list.end(); // B: publish it If reads and writes of iHead and iTail are not atomic, then Produce could read a partly updated (and therefore corrupt) iHead and try to dereference it, and Consume could read a corrupt iTail and fall off the end of the queue. Marginean does note this requirement: “Reading/writing list ::iterator is atomic on the machine upon which you run the application.” [2] Unfortunately, this still isn’t enough. Besides the fact that assigning to iTail isn’t atomic and that we still have a race on iTail in general, compilers and processors can also invent writes to iTail that break this code. Let’s consider write invention in the context of another problem area: Consume. Ordering Problems in Consume Here’s another reordering problem, this time from Consume: if (iNext != iTail) { iHead = iNext; t = *iHead; // C // D Alas, atomicity is necessary but not sufficient (see next section), and not supported by list ::iterator. First, in practice, many list ::iterator implementations I examined are larger than the native machine/pointer size, which means that they can’t be read or written with atomic loads and stores on most architectures. Second, in practice, even if they were of an appropriate size, you’d have to add other decorations to the variable to ensure atomicity, for example to require that the variable be properly aligned in memory. Finally, the code isn’t valid ISO C++. The 1998 C++ Standard said nothing about concurrency, and so provided no such guarantees at all. The upcoming second C++ standard that is now being finalized, C++0x, does include a memory model and thread support, and explicitly forbids it. In brief, C++0x says that the answer to questions such as, “What do I need to do to use a list mylist thread-safely?” is “Same as any other object”—if you know that an object like mylist is shared, you must externally synchronize access to it, including via iterators, This is a classic publication race because lines A and B can be (partly or entirely) reordered. For example, let’s say that some of the writes to the T object’s members are delayed until after the write to iTail, which publishes that the new object is available; then the consumer thread can see a partly assigned T object. What is the minimum necessary fix? We might be tempted to write a memory barrier between the two lines: // Is this change enough? list.push_back(t); // A: add the new item mb(); // full fence iTail = list.end(); // B: publish it Before reading on, think about it and see if you’re convinced that this is (or isn’t) right. Have you thought about it? As a starter, here’s one issue: Although list.end is probably unlikely to perform writes, it’s possible that it might, and those are side effects that need to be complete before we publish iTail. Note that Consume updates iHead to advertise that it has consumed another item before it actually reads the item’s value. Is that a problem? We might think it’s innocuous, because the producer always leaves the iHead item alone to stay at least one item away from the part of the list the consumer is using. It turns out this code is broken regardless of which order we write lines C and D, because the compiler or processor or cache can reorder either version in unfortunate ways. Consider what happens if the consumer thread performs a consecutive two calls to Consume: The memory reads and writes performed by those two calls could be reordered so that iHead is incremented twice before we copy the two list nodes’ values, and then we have a problem because the producer may try to remove nodes the consumer is still using. Note: This doesn’t mean the compiler or processor transformations are broken; they’re not. Rather, the code is racy and has insufficient synchronization, and so it breaks the memory 69 September 2008 l www.ddj.com l Dr. Dobb’s Journal http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - September 2008

Dr. Dobb's Journal - September 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation With Erik Demaine Application Lifecycle Management Meets Model-Driven Development Building a Robust Development Environment Real Users Really Matter Matching Wildcards: An Algorithm The Android Mobile Phone Platform Managing Application Thread Use Signalling Integer Overflows in Java .NET Development & the IBM WebSphere Portal Server The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - September 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.