Atomicity makes an operation appear indivisible to concurrent observers: no thread can see or interfere with an intermediate state. A single-threaded call creates only an illusion of atomicity; shared mutable state requires explicit synchronization. section 7.7
A cache update must preserve one coherent operation across its dependent steps:
- Check whether the key exists and update it, or check capacity and evict an entry. section 7.7
- Add the replacement or new entry without allowing another thread to interleave between the check and mutation. section 7.7.3
Two threads, one free cache slot
Two threads can both observe that an LFU cache is not full, then both insert without evicting. The cache may overflow or one value may overwrite the other. Synchronization makes the check-and-update sequence indivisible.
Listing 7.10 Java concurrent LFU cache set
public boolean set(Key key, Value value) {
writeLock.lock(); #1
try { #2
if (this.hashTable.contains(key)) {
PriorityQueueNode node = this.hashTable.get(key);
node.setValue(value);
return node.updatePriority(node.getCounter());
} else if (this.getSize() >= this.maxSize) {
this.evictOneEntry(); #3
}
PriorityQueueNode newNode = this.elements.add(key, value, 1);
this.hashTable.put(key, newNode);
return true;
} finally { #4
writeLock.unlock(); #5
}
}
The concurrent LFU set implementation places a write lock around the entire update, including lookup, eviction, insertion, and guaranteed unlock in a finally block. section 7.7.3
