Print indd

3
Complex and Compositional Atomic Operations
We classify synchronization primitives into three main categories, that use dif-
ferent amounts and kinds of hardware support:
(
α) Software lock-based: using (efficient) hardware lock support
(
β) Software lock-free: using hardware CAS or LL/SC
(
γ) Dedicated hardware for whole critical section (wait-free)
In this paper, we first describe and compare (
α) and (β). Then we propose to
combine their conceptual advantages by using dedicated hardware support (
γ)
for complex and compositional atomic operations (CaCAO approach).
A main attribute of synchronization primitives is the number of retries. An
operation has zero retries, if the read-modify-write cycle is non-conditional. This
means, if there is no interfering concurrency on the data structure that makes
a retry of the operation necessary. This holds true, e.g. for the fetch-and-ops,
but not for the CAS, since the latter only writes back if the read value did not
change in the meantime.
3.1