跳到主要内容使用 VarHandle 实现内存安全的无锁数据结构 | 极客日志Javajava算法
使用 VarHandle 实现内存安全的无锁数据结构
综述由AI生成Java VarHandle 在实现内存安全无锁数据结构中展现出类型安全、内存语义明确及平台无关性优势。文章详细展示了基于 Treiber 算法的无锁栈、Michael-Scott 算法的无锁队列及无锁哈希表的完整代码实现,包含 ABA 问题防护机制。内容涵盖缓存行填充、批量操作优化等性能技巧,以及并发测试框架搭建和常见陷阱解决方案,为高并发场景下的 Java 编程提供实践参考。
苹果系统11 浏览 一、VarHandle 基础与优势
1. VarHandle 与 Atomic 对比
class Counter {
private volatile int value = 0;
private static final VarHandle VALUE_HANDLE;
static {
try {
VALUE_HANDLE = MethodHandles.lookup()
.findVarHandle(Counter.class, "value", int.class);
} catch (Exception e) {
throw new Error(e);
}
}
public boolean compareAndSet(int expected, int update) {
return VALUE_HANDLE.compareAndSet(this, expected, update);
}
}
2. VarHandle 的核心特性
public class VarHandleFeatures {
enum AccessMode {
GET,
SET,
GET_VOLATILE,
SET_VOLATILE,
GET_ACQUIRE,
SET_RELEASE,
GET_OPAQUE,
SET_OPAQUE,
COMPARE_AND_SET,
COMPARE_AND_EXCHANGE,
GET_AND_SET,
GET_AND_ADD,
GET_AND_BITWISE_OR
}
}
二、无锁栈实现(Treiber Stack)
1. 完整的无锁栈实现
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicReference;
public class LockFreeStack<E> {
private static class Node<E> {
final E item;
Node<E> next;
Node(E item) {
this.item = item;
this.next = null;
}
}
private volatile Node<E> top = null;
private static final VarHandle TOP_HANDLE;
static {
try {
TOP_HANDLE = MethodHandles.lookup()
.findVarHandle(LockFreeStack.class, "top", Node.class);
} catch (Exception e) {
throw new Error(e);
}
}
public void push(E item) {
Node<E> newNode = new Node<>(item);
Node<E> currentTop;
do {
currentTop = (Node<E>) TOP_HANDLE.getAcquire(this);
newNode.next = currentTop;
} while (!TOP_HANDLE.compareAndSet(this, currentTop, newNode));
postPush(newNode);
}
public E pop() {
Node<E> currentTop;
Node<E> nextTop;
do {
currentTop = (Node<E>) TOP_HANDLE.getVolatile(this);
if (currentTop == null) {
throw new NoSuchElementException("Stack is empty");
}
nextTop = currentTop.next;
} while (!TOP_HANDLE.compareAndSetRelease(this, currentTop, nextTop));
currentTop.next = null;
return currentTop.item;
}
public E popSafe() {
Node<E> currentTop;
Node<E> nextTop;
do {
currentTop = (Node<E>) TOP_HANDLE.getVolatile(this);
if (currentTop == null) {
return null;
}
nextTop = currentTop.next;
} while (!TOP_HANDLE.weakCompareAndSet(this, currentTop, nextTop));
E item = currentTop.item;
currentTop.next = null;
return item;
}
public void pushAll(E[] items) {
if (items == null || items.length == 0) {
return;
}
Node<E> first = new Node<>(items[0]);
Node<E> last = first;
for (int i = 1; i < items.length; i++) {
Node<E> node = new Node<>(items[i]);
last.next = node;
last = node;
}
Node<E> currentTop;
do {
currentTop = (Node<E>) TOP_HANDLE.getAcquire(this);
last.next = currentTop;
} while (!TOP_HANDLE.compareAndSet(this, currentTop, first));
}
public E peek() {
Node<E> currentTop = (Node<E>) TOP_HANDLE.getAcquire(this);
return currentTop != null ? currentTop.item : null;
}
public boolean isEmpty() {
return TOP_HANDLE.getOpaque(this) == null;
}
public int size() {
int count = 0;
Node<E> current = (Node<E>) TOP_HANDLE.getAcquire(this);
while (current != null) {
count++;
current = current.next;
}
return count;
}
public void clear() {
TOP_HANDLE.setVolatile(this, null);
}
protected void postPush(Node<E> newNode) {
}
public E popOptimized() {
final int MAX_SPINS = 100;
int spins = 0;
while (true) {
Node<E> currentTop = (Node<E>) TOP_HANDLE.getAcquire(this);
if (currentTop == null) {
return null;
}
if (spins < MAX_SPINS && TOP_HANDLE.getVolatile(this) == currentTop) {
spins++;
Thread.onSpinWait();
continue;
}
Node<E> nextTop = currentTop.next;
if (TOP_HANDLE.compareAndSet(this, currentTop, nextTop)) {
E item = currentTop.item;
currentTop.next = null;
return item;
}
spins = 0;
}
}
}
2. 带 ABA 问题防护的增强版栈
public class LockFreeStackWithStamped<E> {
private static class StampedReference<T> {
final T reference;
final long stamp;
StampedReference(T reference, long stamp) {
this.reference = reference;
this.stamp = stamp;
}
}
private static class Node<E> {
final E item;
volatile Node<E> next;
Node(E item) {
this.item = item;
}
}
private volatile StampedReference<Node<E>> top = new StampedReference<>(null, 0);
private static final VarHandle TOP_HANDLE;
private static final VarHandle STAMP_HANDLE;
static {
try {
TOP_HANDLE = MethodHandles.lookup()
.findVarHandle(LockFreeStackWithStamped.class, "top", StampedReference.class);
} catch (Exception e) {
throw new Error(e);
}
}
public void push(E item) {
Node<E> newNode = new Node<>(item);
StampedReference<Node<E>> currentTop;
StampedReference<Node<E>> newTop;
do {
currentTop = (StampedReference<Node<E>>) TOP_HANDLE.getAcquire(this);
newNode.next = currentTop.reference;
newTop = new StampedReference<>(
newNode, currentTop.stamp + 1
);
} while (!TOP_HANDLE.compareAndSet(
this, currentTop, newTop
));
}
public E pop() {
StampedReference<Node<E>> currentTop;
StampedReference<Node<E>> newTop;
Node<E> nextNode;
do {
currentTop = (StampedReference<Node<E>>) TOP_HANDLE.getVolatile(this);
Node<E> topNode = currentTop.reference;
if (topNode == null) {
return null;
}
nextNode = topNode.next;
newTop = new StampedReference<>(
nextNode, currentTop.stamp + 1
);
} while (!TOP_HANDLE.compareAndSetRelease(
this, currentTop, newTop
));
return currentTop.reference.item;
}
}
三、无锁队列实现(Michael-Scott 队列)
1. 完整的无锁队列实现
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicReference;
public class LockFreeQueue<E> {
private static class Node<E> {
volatile E item;
volatile Node<E> next;
Node(E item) {
this.item = item;
}
}
private volatile Node<E> dummy = new Node<>(null);
private volatile Node<E> head;
private volatile Node<E> tail;
private static final VarHandle HEAD_HANDLE;
private static final VarHandle TAIL_HANDLE;
private static final VarHandle NEXT_HANDLE;
private static final VarHandle ITEM_HANDLE;
static {
try {
MethodHandles.Lookup lookup = MethodHandles.lookup();
HEAD_HANDLE = lookup.findVarHandle(
LockFreeQueue.class, "head", Node.class
);
TAIL_HANDLE = lookup.findVarHandle(
LockFreeQueue.class, "tail", Node.class
);
NEXT_HANDLE = lookup.findVarHandle(
Node.class, "next", Node.class
);
ITEM_HANDLE = lookup.findVarHandle(
Node.class, "item", Object.class
);
} catch (Exception e) {
throw new Error(e);
}
}
public LockFreeQueue() {
head = dummy;
tail = dummy;
}
public void enqueue(E item) {
if (item == null) {
throw new NullPointerException();
}
Node<E> newNode = new Node<>(item);
Node<E> currentTail;
Node<E> tailNext;
while (true) {
currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
tailNext = (Node<E>) NEXT_HANDLE.getAcquire(currentTail);
if (currentTail == (Node<E>) TAIL_HANDLE.getVolatile(this)) {
if (tailNext == null) {
if (NEXT_HANDLE.compareAndSet(
currentTail, null, newNode)) {
TAIL_HANDLE.compareAndSetRelease(
this, currentTail, newNode
);
return;
}
} else {
TAIL_HANDLE.compareAndSet(
this, currentTail, tailNext
);
}
}
}
}
public E dequeue() {
while (true) {
Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this);
Node<E> currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead);
if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) {
if (currentHead == currentTail) {
if (headNext == null) {
throw new NoSuchElementException("Queue is empty");
}
TAIL_HANDLE.compareAndSet(
this, currentTail, headNext
);
} else {
E item = (E) ITEM_HANDLE.getVolatile(headNext);
if (item != null) {
if (HEAD_HANDLE.compareAndSetRelease(
this, currentHead, headNext)) {
ITEM_HANDLE.setVolatile(currentHead, null);
NEXT_HANDLE.setVolatile(currentHead, null);
return item;
}
}
}
}
}
}
public E dequeueSafe() {
while (true) {
Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this);
Node<E> currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead);
if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) {
if (currentHead == currentTail) {
if (headNext == null) {
return null;
}
TAIL_HANDLE.compareAndSet(
this, currentTail, headNext
);
} else {
E item = (E) ITEM_HANDLE.getVolatile(headNext);
if (item != null && HEAD_HANDLE.compareAndSet(
this, currentHead, headNext)) {
ITEM_HANDLE.setRelease(currentHead, null);
NEXT_HANDLE.setRelease(currentHead, null);
return item;
}
}
}
}
}
public E peek() {
while (true) {
Node<E> currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this);
Node<E> headNext = (Node<E>) NEXT_HANDLE.getAcquire(currentHead);
if (currentHead == (Node<E>) HEAD_HANDLE.getVolatile(this)) {
if (headNext == null) {
return null;
}
E item = (E) ITEM_HANDLE.getAcquire(headNext);
if (item != null) {
return item;
}
}
}
}
public boolean isEmpty() {
Node<E> currentHead = (Node<E>) HEAD_HANDLE.getOpaque(this);
Node<E> currentTail = (Node<E>) TAIL_HANDLE.getOpaque(this);
return currentHead == currentTail && NEXT_HANDLE.getOpaque(currentHead) == null;
}
public void enqueueAll(E[] items) {
if (items == null || items.length == 0) {
return;
}
Node<E> first = new Node<>(items[0]);
Node<E> last = first;
for (int i = 1; i < items.length; i++) {
Node<E> node = new Node<>(items[i]);
NEXT_HANDLE.setRelease(last, node);
last = node;
}
Node<E> currentTail;
Node<E> tailNext;
while (true) {
currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
tailNext = (Node<E>) NEXT_HANDLE.getAcquire(currentTail);
if (currentTail == (Node<E>) TAIL_HANDLE.getVolatile(this)) {
if (tailNext == null) {
if (NEXT_HANDLE.compareAndSet(
currentTail, null, first)) {
TAIL_HANDLE.compareAndSetRelease(
this, currentTail, last
);
return;
}
} else {
TAIL_HANDLE.compareAndSet(
this, currentTail, tailNext
);
}
}
}
}
}
2. 无锁双端队列
public class LockFreeDeque<E> {
private static class Node<E> {
volatile E item;
volatile Node<E> prev;
volatile Node<E> next;
Node(E item) {
this.item = item;
}
}
private final Node<E> sentinel = new Node<>(null);
private volatile Node<E> head = sentinel;
private volatile Node<E> tail = sentinel;
private static final VarHandle HEAD_HANDLE;
private static final VarHandle TAIL_HANDLE;
private static final VarHandle NEXT_HANDLE;
private static final VarHandle PREV_HANDLE;
private static final VarHandle ITEM_HANDLE;
static {
try {
MethodHandles.Lookup lookup = MethodHandles.lookup();
HEAD_HANDLE = lookup.findVarHandle(
LockFreeDeque.class, "head", Node.class
);
TAIL_HANDLE = lookup.findVarHandle(
LockFreeDeque.class, "tail", Node.class
);
NEXT_HANDLE = lookup.findVarHandle(
Node.class, "next", Node.class
);
PREV_HANDLE = lookup.findVarHandle(
Node.class, "prev", Node.class
);
ITEM_HANDLE = lookup.findVarHandle(
Node.class, "item", Object.class
);
} catch (Exception e) {
throw new Error(e);
}
}
public LockFreeDeque() {
NEXT_HANDLE.setRelease(sentinel, sentinel);
PREV_HANDLE.setRelease(sentinel, sentinel);
}
public void addFirst(E item) {
if (item == null) throw new NullPointerException();
Node<E> newNode = new Node<>(item);
Node<E> currentHead;
do {
currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this);
Node<E> next = (Node<E>) NEXT_HANDLE.getAcquire(currentHead);
NEXT_HANDLE.setRelease(newNode, next);
PREV_HANDLE.setRelease(newNode, currentHead);
} while (!NEXT_HANDLE.compareAndSet(
currentHead, next, newNode
));
HEAD_HANDLE.compareAndSetRelease(this, currentHead, newNode);
}
public void addLast(E item) {
if (item == null) throw new NullPointerException();
Node<E> newNode = new Node<>(item);
Node<E> currentTail;
do {
currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
Node<E> prev = (Node<E>) PREV_HANDLE.getAcquire(currentTail);
PREV_HANDLE.setRelease(newNode, prev);
NEXT_HANDLE.setRelease(newNode, currentTail);
} while (!PREV_HANDLE.compareAndSet(
currentTail, prev, newNode
));
TAIL_HANDLE.compareAndSetRelease(this, currentTail, newNode);
}
public E removeFirst() {
Node<E> currentHead;
Node<E> nextNode;
do {
currentHead = (Node<E>) HEAD_HANDLE.getAcquire(this);
nextNode = (Node<E>) NEXT_HANDLE.getAcquire(currentHead);
if (nextNode == sentinel) {
return null;
}
Node<E> nextNext = (Node<E>) NEXT_HANDLE.getAcquire(nextNode);
} while (!NEXT_HANDLE.compareAndSet(
currentHead, nextNode, nextNext
));
HEAD_HANDLE.compareAndSetRelease(this, currentHead, nextNode);
E item = (E) ITEM_HANDLE.getAndSet(nextNode, null);
NEXT_HANDLE.setRelease(nextNode, null);
PREV_HANDLE.setRelease(nextNode, null);
return item;
}
public E removeLast() {
Node<E> currentTail;
Node<E> prevNode;
do {
currentTail = (Node<E>) TAIL_HANDLE.getAcquire(this);
prevNode = (Node<E>) PREV_HANDLE.getAcquire(currentTail);
if (prevNode == sentinel) {
return null;
}
Node<E> prevPrev = (Node<E>) PREV_HANDLE.getAcquire(prevNode);
} while (!PREV_HANDLE.compareAndSet(
currentTail, prevNode, prevPrev
));
TAIL_HANDLE.compareAndSetRelease(this, currentTail, prevNode);
E item = (E) ITEM_HANDLE.getAndSet(prevNode, null);
NEXT_HANDLE.setRelease(prevNode, null);
PREV_HANDLE.setRelease(prevNode, null);
return item;
}
}
四、无锁哈希表实现
1. 无锁哈希表基础实现
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.function.Function;
public class LockFreeHashTable<K, V> {
private static class Entry<K, V> {
final K key;
volatile V value;
volatile int hash;
Entry(K key, V value, int hash) {
this.key = key;
this.value = value;
this.hash = hash;
}
}
private volatile Entry<K, V>[] table;
private volatile int size = 0;
private volatile int threshold;
private static final VarHandle TABLE_HANDLE;
private static final VarHandle SIZE_HANDLE;
private static final VarHandle ENTRY_VALUE_HANDLE;
private static final VarHandle ENTRY_HASH_HANDLE;
static {
try {
MethodHandles.Lookup lookup = MethodHandles.lookup();
TABLE_HANDLE = lookup.findVarHandle(
LockFreeHashTable.class, "table", Entry[].class
);
SIZE_HANDLE = lookup.findVarHandle(
LockFreeHashTable.class, "size", int.class
);
ENTRY_VALUE_HANDLE = lookup.findVarHandle(
Entry.class, "value", Object.class
);
ENTRY_HASH_HANDLE = lookup.findVarHandle(
Entry.class, "hash", int.class
);
} catch (Exception e) {
throw new Error(e);
}
}
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
private static final Object TOMBSTONE = new Object();
@SuppressWarnings("unchecked")
public LockFreeHashTable() {
table = (Entry<K, V>[]) new Entry<?, ?>[DEFAULT_INITIAL_CAPACITY];
threshold = (int) (DEFAULT_INITIAL_CAPACITY * LOAD_FACTOR);
}
public V get(K key) {
int hash = hash(key);
Entry<K, V>[] tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this);
int index = indexFor(hash, tab.length);
for (int i = 0; i < tab.length; i++) {
Entry<K, V> entry = tabAt(tab, index);
if (entry == null) {
return null;
}
if (entry.key == TOMBSTONE) {
index = nextIndex(index, tab.length);
continue;
}
int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry);
if (entryHash == hash && (entry.key == key || (key != null && key.equals(entry.key)))) {
return (V) ENTRY_VALUE_HANDLE.getAcquire(entry);
}
index = nextIndex(index, tab.length);
}
return null;
}
public V put(K key, V value) {
if (key == null) throw new NullPointerException();
int hash = hash(key);
Entry<K, V>[] tab;
int index;
while (true) {
tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this);
index = indexFor(hash, tab.length);
for (int i = 0; i < tab.length; i++) {
Entry<K, V> entry = tabAt(tab, index);
if (entry == null) {
if (tryPutNewEntry(tab, index, key, value, hash)) {
return null;
}
break;
}
if (entry.key == TOMBSTONE) {
if (tryReplaceTombstone(tab, index, key, value, hash)) {
return null;
}
}
int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry);
if (entryHash == hash && (entry.key == key || key.equals(entry.key))) {
V oldValue = (V) ENTRY_VALUE_HANDLE.getAcquire(entry);
if (ENTRY_VALUE_HANDLE.compareAndSet(
entry, oldValue, value)) {
return oldValue;
}
break;
}
index = nextIndex(index, tab.length);
}
if (needResize()) {
resize();
}
}
}
private boolean tryPutNewEntry(Entry<K, V>[] tab, int index, K key, V value, int hash) {
Entry<K, V> newEntry = new Entry<>(key, value, hash);
Entry<K, V> expected = null;
Entry<K, V> actual = (Entry<K, V>) TABLE_HANDLE.compareAndExchange(
this, tab, tab
);
if (actual != tab) {
return false;
}
VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class);
if (arrayHandle.compareAndSet(tab, index, null, newEntry)) {
incrementSize();
return true;
}
return false;
}
private void incrementSize() {
int current;
do {
current = (int) SIZE_HANDLE.getVolatile(this);
} while (!SIZE_HANDLE.compareAndSet(this, current, current + 1));
}
public V remove(K key) {
int hash = hash(key);
Entry<K, V>[] tab;
int index;
while (true) {
tab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this);
index = indexFor(hash, tab.length);
for (int i = 0; i < tab.length; i++) {
Entry<K, V> entry = tabAt(tab, index);
if (entry == null) {
return null;
}
if (entry.key == TOMBSTONE) {
index = nextIndex(index, tab.length);
continue;
}
int entryHash = (int) ENTRY_HASH_HANDLE.getAcquire(entry);
if (entryHash == hash && (entry.key == key || key.equals(entry.key))) {
V oldValue = (V) ENTRY_VALUE_HANDLE.getAcquire(entry);
if (ENTRY_VALUE_HANDLE.compareAndSet(
entry, oldValue, TOMBSTONE)) {
decrementSize();
return oldValue;
}
break;
}
index = nextIndex(index, tab.length);
}
}
}
private void decrementSize() {
int current;
do {
current = (int) SIZE_HANDLE.getVolatile(this);
} while (!SIZE_HANDLE.compareAndSet(this, current, current - 1));
}
private int indexFor(int hash, int length) {
return hash & (length - 1);
}
private int nextIndex(int index, int length) {
return (index + 1) & (length - 1);
}
private int hash(Object key) {
int h = key.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
@SuppressWarnings("unchecked")
private Entry<K, V> tabAt(Entry<K, V>[] tab, int index) {
VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class);
return (Entry<K, V>) arrayHandle.getVolatile(tab, index);
}
private boolean needResize() {
int currentSize = (int) SIZE_HANDLE.getOpaque(this);
return currentSize >= threshold;
}
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] oldTab = (Entry<K, V>[]) TABLE_HANDLE.getAcquire(this);
int oldCap = oldTab.length;
if (oldCap >= (1 << 30)) {
threshold = Integer.MAX_VALUE;
return;
}
int newCap = oldCap << 1;
Entry<K, V>[] newTab = (Entry<K, V>[]) new Entry<?, ?>[newCap];
if (TABLE_HANDLE.compareAndSet(this, oldTab, newTab)) {
rehash(oldTab, newTab);
threshold = (int) (newCap * LOAD_FACTOR);
}
}
private void rehash(Entry<K, V>[] oldTab, Entry<K, V>[] newTab) {
for (Entry<K, V> entry : oldTab) {
if (entry != null && entry.key != TOMBSTONE) {
int newIndex = indexFor(entry.hash, newTab.length);
while (true) {
Entry<K, V> existing = tabAt(newTab, newIndex);
if (existing == null) {
VarHandle arrayHandle = MethodHandles.arrayElementVarHandle(Entry[].class);
if (arrayHandle.compareAndSet(
newTab, newIndex, null, entry)) {
break;
}
}
newIndex = nextIndex(newIndex, newTab.length);
}
}
}
}
public int size() {
return (int) SIZE_HANDLE.getAcquire(this);
}
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
V value = get(key);
if (value != null) {
return value;
}
V newValue = mappingFunction.apply(key);
if (newValue == null) {
return null;
}
V result = put(key, newValue);
return result != null ? result : newValue;
}
}
五、性能优化技巧
1. 内存布局优化
public class PaddedAtomicReference<T> {
private volatile long p1, p2, p3, p4, p5, p6, p7;
private volatile T value;
private volatile long p8, p9, p10, p11, p12, p13, p14, p15;
private static final VarHandle VALUE_HANDLE;
static {
try {
VALUE_HANDLE = MethodHandles.lookup()
.findVarHandle(PaddedAtomicReference.class, "value", Object.class);
} catch (Exception e) {
throw new Error(e);
}
}
public boolean compareAndSet(T expected, T update) {
return VALUE_HANDLE.compareAndSet(this, expected, update);
}
@SuppressWarnings("unchecked")
public T get() {
return (T) VALUE_HANDLE.getAcquire(this);
}
public void set(T newValue) {
VALUE_HANDLE.setRelease(this, newValue);
}
}
import jdk.internal.vm.annotation.Contended;
public class ContendedCounter {
@Contended
private volatile long value1 = 0;
@Contended
private volatile long value2 = 0;
private static final VarHandle VALUE1_HANDLE;
private static final VarHandle VALUE2_HANDLE;
static {
try {
VALUE1_HANDLE = MethodHandles.lookup()
.findVarHandle(ContendedCounter.class, "value1", long.class);
VALUE2_HANDLE = MethodHandles.lookup()
.findVarHandle(ContendedCounter.class, "value2", long.class);
} catch (Exception e) {
throw new Error(e);
}
}
public void increment1() {
long current;
do {
current = (long) VALUE1_HANDLE.getAcquire(this);
} while (!VALUE1_HANDLE.compareAndSet(this, current, current + 1));
}
}
2. 批量操作优化
public class BatchCounter {
private static final int BATCH_SIZE = 64;
private static final ThreadLocal<ThreadLocalCounter> COUNTERS = ThreadLocal.withInitial(ThreadLocalCounter::new);
private volatile long globalCount = 0;
private static final VarHandle GLOBAL_COUNT_HANDLE;
static {
try {
GLOBAL_COUNT_HANDLE = MethodHandles.lookup()
.findVarHandle(BatchCounter.class, "globalCount", long.class);
} catch (Exception e) {
throw new Error(e);
}
}
private static class ThreadLocalCounter {
private long localCount = 0;
private int batch = 0;
public void increment() {
localCount++;
batch++;
if (batch >= BATCH_SIZE) {
flushToGlobal();
}
}
private void flushToGlobal() {
if (localCount > 0) {
long currentGlobal;
do {
currentGlobal = (long) GLOBAL_COUNT_HANDLE.getAcquire(BatchCounter.this);
} while (!GLOBAL_COUNT_HANDLE.compareAndSet(
BatchCounter.this, currentGlobal, currentGlobal + localCount
));
localCount = 0;
batch = 0;
}
}
}
public void increment() {
COUNTERS.get().increment();
}
public long get() {
COUNTERS.get().flushToGlobal();
return (long) GLOBAL_COUNT_HANDLE.getAcquire(this);
}
}
六、测试与验证
1. 并发测试框架
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
public class LockFreeStructureTest {
public static void testLockFreeStack() throws Exception {
LockFreeStack<Integer> stack = new LockFreeStack<>();
int threadCount = 10;
int operationsPerThread = 10000;
ExecutorService executor = Executors.newFixedThreadPool(threadCount);
CyclicBarrier barrier = new CyclicBarrier(threadCount);
AtomicInteger pushCount = new AtomicInteger(0);
AtomicInteger popCount = new AtomicInteger(0);
Runnable task = () -> {
try {
barrier.await();
for (int i = 0; i < operationsPerThread; i++) {
stack.push(i);
pushCount.incrementAndGet();
if (i % 3 == 0) {
stack.popSafe();
popCount.incrementAndGet();
}
}
} catch (Exception e) {
e.printStackTrace();
}
};
for (int i = 0; i < threadCount; i++) {
executor.submit(task);
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.MINUTES);
System.out.println("Push operations: " + pushCount.get());
System.out.println("Pop operations: " + popCount.get());
System.out.println("Final stack size: " + stack.size());
Integer item;
int remaining = 0;
while ((item = stack.popSafe()) != null) {
remaining++;
}
System.out.println("Remaining items after cleanup: " + remaining);
assert remaining == pushCount.get() - popCount.get();
}
public static void testABAPrevention() throws Exception {
LockFreeStackWithStamped<Integer> stack = new LockFreeStackWithStamped<>();
stack.push(1);
stack.push(2);
ExecutorService executor = Executors.newFixedThreadPool(2);
Future<?> future1 = executor.submit(() -> {
Integer top = stack.peek();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
return stack.pop();
});
Future<?> future2 = executor.submit(() -> {
stack.pop();
stack.pop();
stack.push(2);
return null;
});
future2.get();
Object result = future1.get();
System.out.println("ABA test result: " + result);
executor.shutdown();
}
public static void performanceComparison() {
int iterations = 1000000;
Queue<Integer> clq = new ConcurrentLinkedQueue<>();
long start = System.nanoTime();
for (int i = 0; i < iterations; i++) {
clq.offer(i);
if (i % 2 == 0) {
clq.poll();
}
}
long clqTime = System.nanoTime() - start;
LockFreeQueue<Integer> lfq = new LockFreeQueue<>();
start = System.nanoTime();
for (int i = 0; i < iterations; i++) {
lfq.enqueue(i);
if (i % 2 == 0) {
lfq.dequeueSafe();
}
}
long lfqTime = System.nanoTime() - start;
System.out.println("ConcurrentLinkedQueue time: " + clqTime / 1e6 + " ms");
System.out.println("LockFreeQueue time: " + lfqTime / 1e6 + " ms");
System.out.println("Speedup: " + (double) clqTime / lfqTime);
}
public static void main(String[] args) throws Exception {
System.out.println("Testing LockFreeStack...");
testLockFreeStack();
System.out.println("\nTesting ABA Prevention...");
testABAPrevention();
System.out.println("\nPerformance Comparison...");
performanceComparison();
}
}
七、最佳实践与注意事项
1. 内存语义选择指南
public class MemorySemanticsGuide {
class CorrectUsage {
private volatile Data data;
private static final VarHandle DATA_HANDLE;
void publisher() {
Data newData = new Data();
newData.init();
DATA_HANDLE.setRelease(this, newData);
}
void consumer() {
Data currentData = (Data) DATA_HANDLE.getAcquire(this);
if (currentData != null) {
currentData.process();
}
}
}
}
2. 常见陷阱与解决方法
public class CommonPitfalls {
class Pitfall1 {
private int value;
}
class Pitfall2 {
private static final VarHandle HANDLE;
static {
try {
HANDLE = MethodHandles.lookup()
.findVarHandle(Pitfall2.class, "field", int.class);
} catch (Exception e) {
throw new Error(e);
}
}
}
class Pitfall3 {
private static class VersionedRef<T> {
final T ref;
final long version;
}
}
class Pitfall4 {
void safePop(Node<E> node) {
node.item = null;
node.next = null;
}
}
class Pitfall5 {
void operationWithBackoff() {
int attempts = 0;
while (!tryOperation()) {
attempts++;
if (attempts > MAX_ATTEMPTS) {
exponentialBackoff(attempts);
}
}
}
private void exponentialBackoff(int attempts) {
try {
Thread.sleep((1L << Math.min(attempts, 10)));
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
}
3. 性能监控与调优
import java.util.concurrent.atomic.LongAdder;
public class PerformanceMonitor {
public static class Stats {
private final LongAdder operations = new LongAdder();
private final LongAdder casFailures = new LongAdder();
private final LongAdder retries = new LongAdder();
private volatile long startTime = 0;
private static final VarHandle START_TIME_HANDLE;
static {
try {
START_TIME_HANDLE = MethodHandles.lookup()
.findVarHandle(Stats.class, "startTime", long.class);
} catch (Exception e) {
throw new Error(e);
}
}
public void recordOperation() {
operations.increment();
}
public void recordCASFailure() {
casFailures.increment();
}
public void recordRetry() {
retries.increment();
}
public void startTiming() {
START_TIME_HANDLE.setVolatile(this, System.nanoTime());
}
public long getElapsedNanos() {
long start = (long) START_TIME_HANDLE.getAcquire(this);
return System.nanoTime() - start;
}
public void printStats() {
long ops = operations.sum();
long failures = casFailures.sum();
long retryCount = retries.sum();
double failureRate = ops > 0 ? (double) failures / ops : 0;
System.out.printf("Operations: %,d%n", ops);
System.out.printf("CAS failures: %,d (%.2f%%)%n", failures, failureRate * 100);
System.out.printf("Retries: %,d%n", retryCount);
System.out.printf("Elapsed time: %.2f ms%n", getElapsedNanos() / 1e6);
if (ops > 0) {
System.out.printf("Throughput: %.2f ops/ms%n", ops / (getElapsedNanos() / 1e6));
}
}
}
public static class MonitoredLockFreeStack<E> extends LockFreeStack<E> {
private final Stats stats = new Stats();
@Override
public void push(E item) {
stats.startTiming();
int attempts = 0;
while (true) {
attempts++;
stats.recordOperation();
try {
super.push(item);
return;
} catch (Exception e) {
stats.recordCASFailure();
if (attempts > 10) {
stats.recordRetry();
try {
Thread.sleep(1L << Math.min(attempts - 10, 4));
} catch (InterruptedException ie) {
Thread.currentThread().interrupt();
throw new RuntimeException(ie);
}
}
}
}
}
public Stats getStats() {
return stats;
}
}
}
八、总结
VarHandle 无锁数据结构优势:
- 类型安全 - 编译期检查,避免 Unsafe 的类型错误
- 内存语义明确 - 清晰的 acquire/release/volatile 语义
- 性能优异 - 接近原生操作的性能
- 平台兼容 - 在 AOT 编译和未来 JDK 版本中支持更好
- 代码可维护 - 标准 API,易于理解和维护
使用建议:
- 对于新建项目,优先使用 VarHandle 而不是 Unsafe
- 理解不同内存语义的适用场景
- 注意处理 ABA 问题和内存泄漏
- 进行充分的并发测试和性能测试
- 结合缓存行填充等优化技巧
通过 VarHandle 实现的无锁数据结构,可以在保证线程安全的同时,获得接近最优的性能表现,是现代 Java 并发编程的重要工具。
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online