LockFreeAlgorithm
From APIDesign
- Officially described at wikipedia::Lock free algorithm.
- Use TransactionalDataStructure to implement such algorithms easily
Typical Example
Let's keep the internal data in a dedicated immutable structure called Data. When performing an update:
- Read the current state.
- Compute an update based on the current state
- Use compare and swap operation to transactionally (hence the similarity with TransactionalMemory) update the state of the object
- repeat everything again if there was a clash
- and the current value was modified by some other thread meanwhile
import java.util.concurrent.atomic.AtomicReference; public abstract class Helper { private static final class Data { final int value1; final int value2; final int value3; Data(int value1, int value2, int value3) { this.value1 = value1; this.value2 = value2; this.value3 = value3; } } private final AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0)); protected abstract int combine(int x, int y); public final void update() { Data current; while (true) { current = data.get(); // the following three operations must be performed in a "transaction" ... int v1 = combine(current.value1, current.value2); int v2 = combine(current.value2, current.value3); int v3 = combine(current.value3, current.value1); // either we want to apply them all or none at all! if (data.compareAndSet(current, new Data(v1, v2, v3))) { // CAS checks the value in data is still == to current // if so it changes it to new Data and we can return return; } // otherwise try again } } }
Neat usage of immutability. The data that are supposed to be consistent are final in a Data class. The mutability is handled all at once with AtomicReference compareAndSet method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value. No locks involved, hence the reference to LockFreeAlgorithms. Let's call such a pattern TransactionalDataStructure.
Follow
