Can thread-safe collections be created without locks?

Question

This is purely for fun, any questions are welcome.

So, is it possible to create thread safe collections without any locks? I mean any mechanisms for synchronizing threads, including Mutex, Semaphore, and even Interlocked, all of them. Is this possible at the user level, without calling system functions? Well, maybe the implementation is not effective, I'm interested in a theoretical possibility. If not what is the minimum means for this?

EDIT: Why immutable collections do not work.

This is a Stack class with Add methods that returns another Stack.

Now here is the program:

 Stack stack = new ...; ThreadedMethod() { loop { //Do the loop stack = stack.Add(element); } } 

this expression stack = stack.Add(element) not atomic, and you can overwrite a new stack from another thread.

Thanks Andrew

Answer 1

It seems that even guru software developers seem to misunderstand what constitutes a lock.

A distinction must be made between atomic operations and locks. Atomic operations, such as comparisons and swaps, perform an operation (which would otherwise require two or more instructions) as the only continuous instruction. Locks are built from atomic operations, however, they can lead to revitalization of threads or waiting until the lock is unlocked.

In most cases, if you manage to implement a parallel algorithm with atomic operations without resorting to locking, you will find that it will be an order of magnitude faster. This is why there is so much interest in algorithms without waiting and blocking.

A ton of research has been carried out to introduce various data structures without expectation. Although the code tends to be short, they are notoriously difficult to prove that they really work because of the subtle race conditions that arise. Debugging is also a nightmare. However, a lot of work has been done, and you can find hash cards without waiting / locking, queues (locking Free Lock Free Michael), stacks, lists, trees, the list goes on. If you're lucky, you'll also find some open source versions.

Just unplug my "my-data data structure" and find out what you get.

For further reading on this interesting topic, start with the Art of Multiprocessing Programming by Maurice Herlihy.

Answer 2

Yes, immutable collections! :)

Answer 3

It depends on how you define this term (as other commentators discussed), but yes, it is possible that many data structures will at least be implemented in a non-blocking way (without using the traditional mutual exclusion locks).

I highly recommend if you are interested in the topic that you read Cliff Click's blog - Cliff is the head of the gurus at Azul Systems who produce hardware + custom JVMs to run Java systems at the mass and mass level (come up with about 1000 cores and in hundreds gigabytes of RAM), and, obviously, in such systems blocking can be fatal (disclaimer: not Azul employee or client, just a fan of their work).

Dr Click famously came up with a non-blocking HashTable, which is basically a complex (but pretty brilliant) state machine using atomic operations CompareAndSwap.

There is a two-part blog entry describing the algorithm ( part one , part two ), as well as a message read on Google ( slides , video ) - the latter, in particular, is a fantastic introduction. Took a few pieces to "get" him - it's hard, let him meet! - but if you have a hunch (or if you are smarter than me in the first place!), you will find it very useful.

Answer 4

I do not think so. The problem is that at some point you will need some primitive of mutual exclusion (possibly at the machine level), for example, the atomic testing and typing operation. Otherwise, you can always develop race conditions. Once you have a test suite, you have a lock.

At the same time, in older hardware that did not support this in the instruction set, you could disable interrupts and thus prevent the use of another "process", but effectively put the system in serialized mode and force the mutual exclusion sorting for some time.

Answer 5

Yes, you can do concurrency without system support. You can use the Peterson algorithm or the more general bakery algorithm to emulate blocking.

Answer 6

At least you need atomic operations. There are blocking algorithms for single processors. I'm not sure for multiple CPUs