On 29 March 2012 at 12:01 PM, Heinrich Apfelmus <apfelmus at quantentunnel.de> wrote:
Since I don't know much about concurrency, I have a simple question: what is the difference between atomic compare-and-swap and software transactional memory? Both are lock-free?
Well, terminology-wise it would probably be more accurate to say that you can implement lock-free algorithms using both (i.e. it's not really CAS and STM that are lock-free, but the algorithms implemented using them). But maybe this is a pedantic distinction. As to the difference between the two: CAS is just a machine instruction that takes an old "expected" value, a new value and an address and updates the memory pointed to by the address iff it contains the old/expected value. All this happens atomically, so you avoid the potential conflicts between threads concurrently reading from and writing to the same address. STM is much higher-level. It's an abstraction that allows the programmer to treat any sequence of reads and writes as a single atomic operation. This is, as the name says, implemented in software. So while the two are related, CAS is a machine primitive that works for a single operation and on a single word while STM is a software abstraction that isolates sequences of operations on multiple memory locations from each other.
Is it possible to implement every data structure based on CAS in terms of STM? What are the drawbacks? The other way round?
I think so. Atomically reading and writing a single memory location (which CAS does) is just a very simple transaction. But using a CAS instruction should be more efficient, since STM has to maintain a transaction log and commit transactions, which creates some overhead. I hope this makes some sense. Cheers, Florian