Editing Linearizability (section)

== Primitive atomic instructions ==
Processors have [[Instruction (computer science)|instructions]] that can be used to implement [[Lock (computer science)|locking]] and [[lock-free and wait-free algorithms]]. The ability to temporarily inhibit [[interrupt]]s, ensuring that the currently running [[Process (computing)|process]] cannot be [[context switch]]ed, also suffices on a [[uniprocessor]]. These instructions are used directly by compiler and operating system writers but are also abstracted and exposed as bytecodes and library functions in higher-level languages:
* atomic read-write;
* atomic swap (the RDLK instruction in some [[Burroughs large systems#Multiple processors|Burroughs mainframes]], and the XCHG [[x86 instruction listings|x86 instruction]]);
* [[test-and-set]];
* [[fetch-and-add]];
* [[compare-and-swap]];
* [[load-link/store-conditional]].

Most [[central processing unit|processors]] include store operations that are not atomic with respect to memory. These include multiple-word stores and string operations. Should a high priority interrupt occur when a portion of the store is complete, the operation must be completed when the interrupt level is returned. The routine that processes the interrupt must not modify the memory being changed. It is important to take this into account when writing interrupt routines.

When there are multiple instructions which must be completed without interruption, a CPU instruction which temporarily disables interrupts is used. This must be kept to only a few instructions and the interrupts must be re-enabled to avoid unacceptable response time to interrupts or even losing interrupts. This mechanism is not sufficient in a multi-processor environment since each CPU can interfere with the process regardless of whether interrupts occur or not. Further, in the presence of an [[instruction pipeline]], uninterruptible operations present a security risk, as they can potentially be chained in an [[infinite loop]] to create a [[denial of service attack]], as in the [[Cyrix coma bug]].

The [[C programming language|C standard]] and [[SUSv3]] provide <code>sig_atomic_t</code> for simple atomic reads and writes; incrementing or decrementing is not guaranteed to be atomic.<ref>{{cite book|url=https://books.google.com/books?id=2SAQAQAAQBAJ&pg=PA428|title=The Linux Programming Interface|first=Michael|last=Kerrisk|date=7 September 2018|publisher=No Starch Press|via=Google Books|isbn=9781593272203}}</ref> More complex atomic operations are available in [[C11 (C standard revision)|C11]], which provides <code>stdatomic.h</code>. Compilers use the hardware features or more complex methods to implement the operations; an example is libatomic of GCC.

The [[ARM architecture|ARM instruction set]] provides <code>LDREX</code> and <code>STREX</code> instructions which can be used to implement atomic memory access by using [[Monitor (synchronization)|exclusive monitors]] implemented in the processor to track memory accesses for a specific address.<ref>{{cite web|title=ARM Synchronization Primitives Development Article|url=https://developer.arm.com/products/architecture/a-profile/docs/dht0008/latest/1-arm-synchronization-primitives}}</ref> However, if a [[context switch]] occurs between calls to <code>LDREX</code> and <code>STREX</code>, the documentation notes that <code>STREX</code> will fail, indicating the operation should be retried. In the case of 64-bit ARMv8-A architecture, it provides <code>LDXR</code> and <code>STXR</code> instructions for byte, half-word, word, and double-word size.<ref>{{Cite web |url=https://documentation-service.arm.com/static/5efa1989dbdee951c1ccdea1 |title=ARMv8-A Synchronization primitives |page=6 |accessdate=2023-12-14}}</ref>