Subj : Re: lock on IA-32
To   : comp.programming.threads
From : Michael Pryhodko
Date : Mon Mar 14 2005 05:10 pm

> There are distributed algorithms for mutual exclusion.  Google for
> Dekker's algorithm or Peterson's algorithm.  The algorithms assume
> a total order memory model so you need memory barriers to make it
> right in other memory models.

Unfortunately Dekker's (and Peterson's) algorithms are designed for two
threads (processes) only. While It can be generalized for multiple
threads -- it cannot be used for *arbitrary* number of threads (i.e.
when you do not know how much threads will compete).

And by the way -- I cannot think of any generalization which could do
Dekker's algorithms without expensive lookup across whole array of
'thread interested' flags. I found some paper about such
generalizations (e.g.
http://caltechcstr.library.caltech.edu/359/01/5195_TR_85.pdf) -- thay
are all traversing whole array of flags.

Bye.
Sincerely yours, Michael.

.