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

From: Nikita Danilov
Date: Sat Dec 17 2005 - 11:23:18 EST


Nick Piggin writes:
> David Howells wrote:
> > Nick Piggin <nickpiggin@xxxxxxxxxxxx> 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.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/