Kevin Van Vechten writes:
> To be clear, I didn't write any of the following:
Sorry, mea culpa, I trimmed original message over-zealously.
>
> On Dec 7, 2005, at 4:14 AM, Nikita Danilov wrote:
>
> > Kevin Van Vechten writes:
> >
> > [...]
> >
> >>>
> >>> In xnu-792.6.22/libkern/gen/OSAtomicOperations.c the following
> >>> code is
> >>> used for the dequeue. I believe the problem to be that the value in
> >>> newListHead is not necessarily current by the time the atomic CAS is
> >>> executed.
> >>>
> >>> This is a pretty contrived case, as it requires one thread to be
> >>> preempted between the assignment to newListHead and the CAS, and
> >>> then two (or more) elements must be dequeued and at least the first
> >>> dequeued element be put back again [last] so that the CAS succeeds.
> >
> > This is a common predicament of CAS based lock-free data-types (if I
> > understand your description correctly). It's called ABA problem, when
> > CAS controlled pointer changes from A to B and then back to A, leading
> > to falsely positive CASs. Common solutions include:
> >
> > - do not use CAS, use LL/SC (load-linked, store-conditional)
> > instruction pair instead. That requires hardware support, of
> > course.
> >
> > - data-type clients have to guarantee that ABA never happens. E.g.,
> > elements removed from queue are never put back, or only put back
> > sufficiently late. There is a whole cottage industry built
> > around these
> > techniques. :-)
> >
Nikita.
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Darwin-kernel mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/darwin-kernel/email@hidden
This email sent to email@hidden
