You can find information on Lock-Free linked lists here (Click the PDF link on the right if you can't stand Post Script [grin]). I should note that there are many other papers on implementing other containers, you just need to look around a bit. I can't verify the validity of the information covered in GPG, so I'm not going to recommend it (that's not saying you shouldn't get it, that's just saying I haven't read it so I can't comment on how good the information is). If I recall correctly, the paper above either contains or references to a formal proof of their algorithm. Lock-free theory really is an advanced subject and not one to be taken up by someone new to threading, or even only mildy experienced with it. The principles and concepts used are typically far more detailed than the two or three word shorthand that is used (Think of polymorphism...now try and properly describe it in a paragraph or less [grin]).

Lock free containers rely on the usage of atomic operations to perform their operations. They are typically highly restricted in what operations are allowed, as being able to guarantee thread safety of a container over all operations is impossible without using locks. On the other hand, for your typical containers that will be concurrently written to by multiple threads, the number of operations you will realistically be performing on it is limited (for a queue, for instance, you will most likely just Enqueue and Dequeue, for a stack its Push/Pop).

Anyways, I've got a heap load of other links, but googling for lock free (container name) should give you other results.

Quote:Original post by Anonymous Poster
Am I correct in assuming that the various 'lock free' methods are limited in the allowed manipulation and wont work for some very commonly used operations (as in deleting nodes in the middle of a list (a common operation in game rendering where the display set is constantly changing...).

Not at all, read the paper i linked, it allows for lock free insertion and deletion from the middle of the list, singly linked though, so such operations are easily atomic. I say easily atomic since the operation is no where near as complex as that of say a Red/Black tree...

Quote:
Also just because a 'lock' isnt involved doesnt man that there isnt a delay (multiple CPUs can mean multiple caches that have to sync up for a particular memory space).

Delays are indeed possible, however they are generally much shorter (unless you've got a really bad implementation) than using critical sections/mutexes (or other forms of locking objects).

Quote:for cache/memory sync, etc...) though if threads are mixed (run on differenet CPUs and sometimes on the same CPU) for load scheduling it can be a complication (SpinWaits dont work on a single CPU).

There are many documented and proven methods of performing atomic inserts and deletions from collections that don't care for how many cores you have. See the paper, again.