3 ms·
> Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, in a way. Some CPUs provide atomic instructions that perform
by gpderetta 10y ago
> Does this in turn mean that there must be a "commit" instruction that is uninterruptible?
Yes, in a way.
Some CPUs provide atomic instructions that perform multiple operations in a bounded time. These instructions cannot be interrupted (by other threads, the OS, interrupts) and appear all-or-nothing (i.e. the intermediate effects are not visible. The most common of such instructions is Compare And Exchange (aka CAS); CAS is often used as the 'commit' action in lock-free algorithms.
Some other architectures have instead a more general 'transactional' feature (known as Load Linked/Store Conditional or LS/SC) which provides for very limited transactions of a single cacheline. A naive implementation could live-lock, but in practice server class architectures provide stronger guarantees.
It can be proven that LL/SC and CAS are equally powerful (i.e. the same set of lock-free/wait-free algorithms can be implemented with both).
LL/SC is more natural for RISC machines, while CAS is common in CISC, but there are plenty of counterexamples.