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
