Atomicity
First, reads and writes of a lock-free variable must be atomic. For this reason, lock-free variables are typically no larger than the machine's native word size, and are usually pointers (C++), object references (Java, .NET), or integers. Trying to use an ordinary list<T>::iterator variable as a lock-free 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;
... }
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<T>::iterator is atomic on the machine upon which you run the application." [2]
Alas, atomicity is necessary but not sufficient (see next section), and not supported by list<T>::iterator. First, in practice, many list<T>::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<T> 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, 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<T>::iterator, because atomic<T> requires T to be a bit-copyable type, and STL types and their iterators aren't guaranteed to be that.)
