Re: Are lock free algorithms possible in C++?
Andy wrote:
Assuming I've got an atomic & fenced CAS instruction available via a
library; is it possible to use this to write a lock free algorithm in C
++?
The short answer is yes.
Unfortunately, there's more to that than a simple answer.
First, any lock-free algorithm should be thoroughly analyzed prior to
trying to implement it in any language (for example, your algorithm is
not lock-free at all! More on that at the end of the post)
Second, it's very hard to write portable lock-free C++ code.
You are always at the mercy of the library that you're using to
implement atomic primitives. For example, does your "AtomicTestAndSet"
function feature acqure or release semantics? (i.e., does it issue a
relevant memory fence?) Does the library that you're using give you any
guarantees with respect to compiler cooperation (like pthread library does).
With advent of c++0x's atoimc<> and boost::atomic it's becoming easier
however.
Although the memory fence would prevent hardware re-ordering I'm
worried that compiler could reorder memory access rendering the fence
useless. For example consider the below, grossly simplified example:
bool continue = true;
while(continue) {
while(isLocked) { }
// atomically set isLocked to true if it has the value false
if(AtomicTestAndSet(&isLocked, true, false)) {
continute = false;
}
}
SharedStdVector[3] += 10;
This snippet has several problems.
First, even if we assume that AtomicTestAndSet has both acquire and
release semantics (i.e., it issues a full memory barrier), the access to
isLocked is not synchronized. The line "while (isLocked)" might go into
an infinite loop even if another thread updates isLocked to false. It
can happen due to the compiler optimization where the compiler is
allowed to treat all code as a single-threaded code, and isLocked will
be read from the main memory only once.
One way to fix that is to mark isLocked as volatile (beware though,
there has been a long thread on this topic about 3 months ago which I
had been a part of. Using volatile is not for a faint of heart and
should only be done by a library-writer
http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/fcef57c539a42ef5/be98b8ef87ff64a4?hl=en&tvc=1&q=is+alexandrescu+right#be98b8ef87ff64a4).
Better yet, make all access to isLocked atomic, i.e.
atomic<bool> isLocked; or similar
But the bigger issue in your code is that even if you can get it to
work, it's not lock-free.
Lock-free is not about avoiding mutexes or other synchronization
primitives. Lock-free is a property of an algorithm that guarantees
progress of the overall program at every step. I.e., that at least one
of the threads will make progress.
What you did is you wrote an implementation of a lock without resorting
to system-provided primitives. But it's a lock nevertheless. And you
have all the issues with locking - what if another thread stalls and
never updates isLocked to false? Also, you can dead-lock as easily as
with system-provided locks. Moreover, since usually system-provided
locks don't resort to busy-waiting as you do they will most likely have
a better performance as well. And, at least on Linux, taking an
uncontested lock is never a system call, just a single atomic operation.
I'm pretty sure that taking an uncontested lock on other operating
systems is optimized as well.
HTH,
Andy.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]