Subj : Re: Lock Free -- where to start
To   : comp.programming.threads
From : Joe Seigh
Date : Wed Oct 05 2005 12:36 pm

Sergey P. Derevyago wrote:
> Peter Dimov wrote:
>>I think that this is not allowed by the definition of "lock free". A
>>locking algorithm will not make progress if the thread that has just
>>acquired the lock is preempted and never receives a chance to run.
>>
> 
> 	Yes, the progress is a must.
> 	But look: spin lock loops shortly and obviously doesn't make any progress.
> Unfortunately, some "lock free" algorithms make long loops (e.g. make some
> progress, determine that some critical data was concurrently touched and start
> the "progress" once again) and it's not so obvious that there can be no real
> progress as well.

If a lock-free algorithm loops that usually means some other thread is
making progress.   Looping would be a problem for wait-free algorithms
if there wasn't a bound on the number of loops but it's not a problem
for lock-free algorithms.

Non lock-free algorithms usually loop waiting for a specific action by some
other thread.  If lock-free algorihtms loop it's because their waiting for
some interval of no actions by other threads.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.