Lockfree standard collections and tutorial or articles

Does someone know of a good resource for the implementation (meaning source code) of lock-free usual data types. I'm thinking of Lists, Queues and so on?

Locking implementations are extremely eas开发者_如何学运维y to find but I can't find examples of lock free algorithms and how to exactly does CAS work and how to use it to implement those structures.

Check out Julian M Bucknall's blog. He describes (in detail) lock-free implementations of queues, lists, stacks, etc.

http://www.boyet.com/Articles/LockfreeQueue.html

http://www.boyet.com/Articles/LockfreeStack.html

http://www.liblfds.org

Written in C.

If C++ is okay with you, take a look at boost::lockfree. It has lock-free Queue, Stack, and Ringbuffer implementations.

In the boost::lockfree::details section, you'll find a lock-free freelist and tagged pointer (ABA prevention) implementation. You will also see examples of explicit memory ordering via boost::atomic (an in-development version of C++0x std::atomic).

Both boost::lockfree and boost::atomic are not part of boost yet, but both have seen attention from the boost-development mailing list and are on the schedule for review.