[concurrency-interest] Concurrency-interest Digest, Vol 58, Issue 5

Mark Moir Mark.Moir at Sun.COM
Sun Nov 8 21:25:02 EST 2009



> From: Martin Buchholz <martinrb at google.com>
> Subject: Re: [concurrency-interest] PriorityBlockingQueue put()
> 	operation
> To: Joe Bowbeer <joe.bowbeer at gmail.com>
> Cc: "concurrency-interest at cs.oswego.edu"
> 	<concurrency-interest at cs.oswego.edu>
> Message-ID:
> 	<1ccfd1c10911072037h488c72a8v38bb68cce3d36073 at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> On Sat, Nov 7, 2009 at 15:00, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
> 
>> Wikipedia currently makes this distinction:
>>
>>   "In computer science, non-blocking synchronization ensures that threads
>> competing for a shared resource do not have their execution indefinitely
>> postponed by mutual exclusion. A non-blocking algorithm is lock-free if
>> there is guaranteed system-wide progress; wait-free if there is also
>> guaranteed per-thread progress."
>>
>>   http://en.wikipedia.org/wiki/Non-blocking_synchronization
>>
>> So non-blocking < lock-free < wait-free ?
>>
>>
> I read it a little differently.
> "lock-free" is a kind of "non-blocking synchronization",
> the weakest kind.  So:
> non-blocking <= lock-free < wait-free
> 
> non-blocking synchronization cannot involve locks,
> since some thread can acquire the lock and never be scheduled again,
> causing *all* threads to
> "have their execution indefinitely postponed by mutual exclusion".


David is right that these terms are overloaded and that the use here
is not related to the obstruction-free/lock-free/wait-free meaning of
non-blocking.  It would probably be useful to make this distinction in
a clear and consistent way in the documentation.

The Wikipedia entry (have we really got to the point of citing
Wikipedia? :-)) is sort of right in spirit, but is not precise enough
to be meaningful, and is somewhat misleading.  In particular, it is
possible to have blocking behavior without having mutual exclusion.

Furthermore, there are unstated assumptions about the system and
system mode.  For example, a lock-free algorithm does not guarantee
system-wide progress.  What it guarantees is that *if* some thread
takes infinitely many steps attempting to complete an operation,
*then* infinitely many operations complete.  If the scheduler decides
not to run any threads, then no progress will be made, but that does
not mean the algorithm is not lock-free.

Also, a lock-free algorithm must make the guarantee it makes in a
fully asynchronous execution model, in which the algorithm cannot make
assumptions about the relative execution speed of different threads,
cannot make fairness assumptions, cannot assume any thread will take
another step, etc.  (Similarly for obstruction-free and wait-free.)

Finally, it is not true that lock-freedom is the weakest form of
non-blocking progress condition.  Obstruction-freedom is weaker: it
guarantees progress to an operation *only* if it eventually executes
in isolation.  A lock-free algorithm guarantees that if (exactly) two
operations continually take steps in completing an operation, one of
the will eventually complete.  Obstruction-freedom does not guarantee
that.

I have often thought of obstruction-freedom as "the weakest
non-blocking progress condition" and in a deterministic system, I
think that is true.  But others have pointed out that in a
probabilistic model, you can have an algorithm that guarantees
completion in isolation with high probability, but not
deterministically.  Whether you still consider such a thing to be
non-blocking is up to you  :-) .

I hope this is helpful. 

Cheers

Mark


More information about the Concurrency-interest mailing list