[concurrency-interest] Lock-free mania

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Sun Apr 15 15:38:22 EDT 2007


It seems that there is some kind of a lock-free mania going
around. People desire to create so-called lock-free algorithms for the
short term interaction between threads where traditionally mutual
exclusion is applicable. The idea might come from a generalization of the
check-and-swap operation that is supported by nowadays processors
instead of the traditional test-and-set operation.

What is the advantage of the lock-free algorithm? Pros:

1: If there is no conflict in the actual interaction among threads,
  the overhead is less than by a conventional mutual exclusion
  algorithm.

What are the drawbacks of the lock-free algorithm? Cons:

1: It is more complicated, more difficult to prove its correctness or
  to test it. It is a major drawback.

2: When there are frequent conflicts between threads, i.e. under heavy
  load conditions, it becomes a busy waiting loop and, consequently,
  it becomes very inefficient just at the critical moment.

3: It cannot always be applied but only in special cases.

Why are people keen to invent so-called lock-free algorithms if they
cannot prove the correctness nor can they test them? I think there are
more cons than pros for the lock-free algorithms. What do you think?

Best Regards,
Szabolcs


More information about the Concurrency-interest mailing list