Optimistic Concurrency

Is this not the same thing as OptimisticLocking? -- SteveJorgensen

I believe it is the same thing. Admittedly OptimisticLocking doesn't actually hold any Locks on resources, and so OptimisticConcurrency seems a better name for the concept.

I suspect that it might be something along the lines of pipelining. -- MartinRudat

Re "pipelining": Not really. It's more to do with controlling access to shared resources by blindly updating them without locking, with the observation that most attempts to lock succeed anyway. However, the updates are atomic (typically a single pointer in RAM to a more sophisticated structure). The structure in question is best expressed as a tree, since only the root pointer need be updated. Hence, multiple threads may compute a new tree, but only the very last one to update the root wins (not that last one wins is any different in lock based protocols). Threads need to check that their setting remains in effect (or use a reservation protocol, as on the PowerPC instruction set); if their setting doesn't hold, it is incumbent on them to re-compute their tree again, and repeat the process for as long as necessary, timeouts notwithstanding.

SoftwareTransactionalMemory is an approach to implementing OptimisticConcurrency that has many nice properties and is becoming fairly popular (having an implementation in Clojure). It helps automate support for atomic transactions that read and write many places in memory. To make SoftwareTransactionalMemory efficient usually involves eschewing 'small' mutable cells in favor of large immutable values with shared structure. SoftwareTransactionalMemory can be implemented with just CompareAndSwap? or TestAndSet?. However, there are also more primitive forms of OptimisticConcurrency, such as those designed for operating on queues and other structures using DoubleCompareAndSwap?. These forms don't allow the degree of ad-hoc atomic operations provided by STM, but they do provide very efficient operations over some common data structures (notably queues, which are critical for message passing). You can find examples of this application of OptimisticConcurrency in SynthesisOs.

See: OptimisticLocking, SoftwareTransactionalMemory