Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Lock-Free Code A Limited Lock-Free Queue Atomicity Ordering Problems in Produce Ordering Problems in Consume

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

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. 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;

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.

Previous Page | 1 Lock-Free Code | 2 A Limited Lock-Free Queue | 3 Atomicity | 4 Ordering Problems in Produce | 5 Ordering Problems in Consume Next Page

RELATED ARTICLES Cloud Computing: Detecting Scalability Problems Logging In C++ : Part 2 recls 100% .NET QuickThread: A New C++ Multicore Library C Snippet #8		TOP 5 ARTICLES No Top Articles.