Editing Linearizability (section)

== High-level atomic operations ==
The easiest way to achieve linearizability is running groups of primitive operations in a [[critical section]]. Strictly, independent operations can then be carefully permitted to overlap their critical sections, provided this does not violate linearizability. Such an approach must balance the cost of large numbers of [[lock (computer science)|locks]] against the benefits of increased parallelism.

Another approach, favoured by researchers (but not yet widely used in the software industry), is to design a linearizable object using the native atomic primitives provided by the hardware. This has the potential to maximise available parallelism and minimise synchronisation costs, but requires mathematical proofs which show that the objects behave correctly.

A promising hybrid of these two is to provide a [[transactional memory]] abstraction. As with critical sections, the user marks sequential code that must be run in isolation from other threads. The implementation then ensures the code executes atomically. This style of abstraction is common when interacting with databases; for instance, when using the [[Spring Framework]], annotating a method with @Transactional will ensure all enclosed database interactions occur in a single [[database transaction]]. Transactional memory goes a step further, ensuring that all memory interactions occur atomically. As with database transactions, issues arise regarding composition of transactions, especially database and in-memory transactions.

A common theme when designing linearizable objects is to provide an all-or-nothing interface: either an operation succeeds completely, or it fails and does nothing. ([[ACID]] databases refer to this principle as [[Atomicity (database systems)|atomicity]].) If the operation fails (usually due to concurrent operations), the user must retry, usually performing a different operation. For example:
* [[Compare-and-swap]] writes a new value into a location only if the latter's contents matches a supplied old value. This is commonly used in a read-modify-CAS sequence: the user reads the location, computes a new value to write, and writes it with a CAS (compare-and-swap); if the value changes concurrently, the CAS will fail and the user tries again.
* [[Load-link/store-conditional]] encodes this pattern more directly: the user reads the location with load-link, computes a new value to write, and writes it with store-conditional; if the value has changed concurrently, the SC (store-conditional) will fail and the user tries again.
* In a [[database transaction]], if the transaction cannot be completed due to a concurrent operation (e.g. in a [[Deadlock (computer science)|deadlock]]), the transaction will be aborted and the user must try again.