Tuesday, September 06, 2005

Threads Cannot be Implemented as a Library

Weiqi Gao has a post by the same name. I followed the post to the original source.

If you are a multi-threaded developer using C or C++, I think you will find this article very interesting.

Here are a few items that jumped out at me:

  • Given the following:

    thread 1 -> x = 1; r1 = y;
    thread 2 -> y = 1; r2 = x;

    Sequential consistent memory model would say that either r1 or r2 would have a value of 1 after execution. However the author of the article has this to say about sequential consistent memory, "In practice, it appears unlikely that such a restrictive memory model can be implemented with reasonable performance on conventional architectures." [Hans J. Boehm]

    It turns out that r1 == r2 == 0 is perfectly valid for the above.

  • Rewriting of adjacent data such that:

    struct { char a; char b; } x = { 'x', 'y' };

    thread 1 -> x.a = 'k';
    thread 2 -> x.b = 'h';

    It is valid for x.a == 'x' and x.b == 'y', because load and store can happen on different threads at the same time because they are in the same "memory location", where "memory location" is not defined.

  • Global data.

    Rewriting of adjacent memory even allows for adjacent global variables outside of a struct declaration. "Since linkers may, and commonly do, reorder globals, this implies that an update to any global variable may potentially read and rewrite any other global variable." [Hans J. Boehm]

    As I often say in my C++ classes, "never, ever, never use a global variable, and when you can't avoid it, still don't use one." Of course the real problem here is not global variables.


The paper goes on to discuss the importance of language support and clear specification of the memory model for correct multi-threaded programs. The author and others are working toward addressing these issues in the C++ standard similar to how they were addressed in Java.