Re: [PATCH 1/19] MUTEX: Introduce simple mutex implementation

Nikita Danilov
2005-12-17T15:57:55Z

Nick Piggin writes:
> David Howells wrote:
> > Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> >
> >
> >>> (2) Those that have CMPXCHG or equivalent: 68020, i486+, x86_64, ia64,
> >>>sparc.
> >>> (3) Those that have LL/SC or equivalent: mips (some), alpha, powerpc, arm6.
> >>>
> >>
> >>cmpxchg is basically exactly equivalent to a store-conditional, so 2 and 3
> >>are the same level.
> >
> >
> > No, they're not. LL/SC is more flexible than CMPXCHG because under some
> > circumstances, you can get away without doing the SC, and because sometimes
> > you can do one LL/SC in lieu of two CMPXCHG's because LL/SC allows you to
> > retrieve the value, consider it and then modify it if you want to. With
> > CMPXCHG you have to anticipate, and so you're more likely to get it wrong.
> >
>
> I don't think that is more flexible, just different. For example with
> cmpxchg you may not have to do the explicit load if you anticipate an
> unlocked mutex as the fastpath.
>
> My point is that they are of semantically equal strength.

In the context of implementing mutex they most likely are. But not
generally: LL/SC fails when _any_ write was made into monitored
location, whereas CAS fails only when value stored in that location
changes. As a result, CAS has to deal with "ABA problem" when value
(e.g., first element in a queue) is changed from A to B (head of the
queue is removed) and then back to A (old head is inserted back).

Nikita.