site_archiver@lists.apple.com Delivered-To: darwin-kernel@lists.apple.com To be clear, I didn't write any of the following: On Dec 7, 2005, at 4:14 AM, Nikita Danilov wrote: Kevin Van Vechten writes: [...] 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 post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel@lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.a... 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. - 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. This email sent to site_archiver@lists.apple.com