54. 无锁编程应用分析

标准答案

✅ 无锁编程的典型应用场景：

1. 数据结构场景：

   • 无锁队列
   • 无锁栈
   • 无锁Map
   • 无锁计数器

2. 状态更新场景：

   • 状态机转换
   • 标志位更新
   • 配置刷新
   • 缓存更新

3. 并发控制场景：

   • 自旋锁实现
   • 原子操作
   • 版本控制
   • 资源回收

答案解析

1️⃣ 无锁队列实现

public class LockFreeQueue<T> {
    private static class Node<T> {
        private final T value;
        private volatile Node<T> next;
        
        public Node(T value) {
            this.value = value;
        }
    }
    
    private final AtomicReference<Node<T>> head;
    private final AtomicReference<Node<T>> tail;
    
    public LockFreeQueue() {
        Node<T> dummy = new Node<>(null);
        head = new AtomicReference<>(dummy);
        tail = new AtomicReference<>(dummy);
    }
    
    public void offer(T value) {
        Node<T> newNode = new Node<>(value);
        while (true) {
            Node<T> curTail = tail.get();
            Node<T> tailNext = curTail.next;
            
            if (curTail == tail.get()) {
                if (tailNext == null) {
                    if (curTail.next.compareAndSet(null, newNode)) {
                        tail.compareAndSet(curTail, newNode);
                        return;
                    }
                } else {
                    tail.compareAndSet(curTail, tailNext);
                }
            }
        }
    }
    
    public T poll() {
        while (true) {
            Node<T> curHead = head.get();
            Node<T> curTail = tail.get();
            Node<T> headNext = curHead.next;
            
            if (curHead == head.get()) {
                if (curHead == curTail) {
                    if (headNext == null) {
                        return null;
                    }
                    tail.compareAndSet(curTail, headNext);
                } else {
                    T value = headNext.value;
                    if (head.compareAndSet(curHead, headNext)) {
                        return value;
                    }
                }
            }
        }
    }
}

2️⃣ 无锁缓存更新

public class LockFreeCache<K, V> {
    private static class CacheEntry<V> {
        final V value;
        final long version;
        
        CacheEntry(V value, long version) {
            this.value = value;
            this.version = version;
        }
    }
    
    private final ConcurrentHashMap<K, AtomicReference<CacheEntry<V>>> cache;
    private final AtomicLong versionGenerator;
    
    public V get(K key) {
        AtomicReference<CacheEntry<V>> ref = cache.get(key);
        return ref != null ? ref.get().value : null;
    }
    
    public boolean update(K key, V value, V expectedValue) {
        AtomicReference<CacheEntry<V>> ref = cache.get(key);
        if (ref == null) {
            ref = new AtomicReference<>();
            AtomicReference<CacheEntry<V>> existing = 
                cache.putIfAbsent(key, ref);
            if (existing != null) {
                ref = existing;
            }
        }
        
        CacheEntry<V> current = ref.get();
        if (current != null && !current.value.equals(expectedValue)) {
            return false;
        }
        
        CacheEntry<V> update = 
            new CacheEntry<>(value, versionGenerator.incrementAndGet());
        return ref.compareAndSet(current, update);
    }
}

常见误区

• ❌ 误区1：认为无锁就一定比有锁快
• ❌ 误区2：忽视ABA问题的处理

典型场景与解决方案

✅ 计数器实现

public class LockFreeCounter {
    private final AtomicLongArray counters;
    private final int mask;
    private final ThreadLocalRandom random;
    
    public LockFreeCounter(int stripes) {
        // 确保是2的幂
        int count = 1;
        while (count < stripes) {
            count <<= 1;
        }
        this.counters = new AtomicLongArray(count);
        this.mask = count - 1;
        this.random = ThreadLocalRandom.current();
    }
    
    public void increment() {
        // 随机选择一个计数器，减少竞争
        int index = random.nextInt() & mask;
        boolean success = false;
        int attempts = 0;
        
        while (!success && attempts < 3) {
            success = incrementAt(index);
            attempts++;
            if (!success) {
                index = (index + 1) & mask;
            }
        }
        
        if (!success) {
            // 降级到普通CAS
            counters.incrementAndGet(index);
        }
    }
    
    private boolean incrementAt(int index) {
        long current = counters.get(index);
        return counters.compareAndSet(index, current, current + 1);
    }
    
    public long getCount() {
        long total = 0;
        for (int i = 0; i < counters.length(); i++) {
            total += counters.get(i);
        }
        return total;
    }
}

企业实战经验

Situation（业务背景）

高并发系统锁竞争严重，性能瓶颈。

Task（核心任务）

使用无锁编程优化关键路径。

Action（解决方案）

1. 识别热点代码
2. 实现无锁算法
3. 处理ABA问题
4. 性能压测验证

Result（结果）

• 吞吐量提升300%
• 延迟降低80%
• CPU使用率降低

深入追问

🔹 如何处理ABA问题？

• 使用版本号
• 使用标记指针
• 避免资源复用

🔹 无锁编程的适用条件？

• 竞争程度评估
• 硬件支持情况
• 代码复杂度权衡

相关面试题

1. CAS的实现原理？
2. 无锁队列的设计要点？
3. 如何确保无锁算法的正确性？