面试题：Java中ConcurrentLinkedQueue如何保证无锁并发操作的线程安全

基于链表结构
- ConcurrentLinkedQueue 是基于链表的无界队列。链表结构使得它在并发操作时，可以通过对节点的引用操作来实现数据的插入和删除，而不需要像数组那样考虑连续内存空间的分配与竞争问题。
使用 volatile 修饰节点引用
- 队列中的节点的 next 引用被声明为 volatile。例如：
```
private static class Node<E> {
    volatile E item;
    volatile Node<E> next;
    // 其他代码
}
```
- 这保证了不同线程对节点引用的修改对其他线程是可见的。当一个线程修改了某个节点的 next 引用（比如在入队时添加新节点，或者出队时更新头节点的 next），其他线程能立即看到这个变化，避免了因缓存不一致导致的竞争条件。
无锁算法实现入队和出队操作
- 入队操作：
  - 入队时，线程会先找到队列的尾节点。由于 ConcurrentLinkedQueue 是无锁的，多个线程可能同时尝试找到尾节点。
  - 找到尾节点后，线程尝试通过 compareAndSet（CAS）操作将新节点设置为尾节点的 next。例如：
```
public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);
    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            if (p.casNext(null, newNode)) {
                if (p != t)
                    casTail(t, newNode);
                return true;
            }
        }
        else if (p == q)
            p = (t != (t = tail))? t : head;
        else
            p = q;
    }
}
```
  - compareAndSet 操作是原子的，只有当 p.next 确实为 null 时，才会将新节点设置为 p.next。如果在尝试 compareAndSet 时，p.next 已经被其他线程修改（即 q != null），则重新定位尾节点并再次尝试。这种方式避免了使用锁来同步对尾节点的修改，从而实现了并发安全的入队操作。
- 出队操作：
  - 出队时，线程首先获取头节点。头节点是队列中等待被移除的元素所在节点。
  - 然后尝试通过 compareAndSet 操作将头节点的 item 设置为 null，并将头节点的 next 设置为新的头节点。例如：
```
public E poll() {
    restartFromHead:
    for (;;) {
        for (Node<E> h = head, p = h, q;;) {
            E item = p.item;
            if (item != null && p.casItem(item, null)) {
                if (p != h)
                    updateHead(h, ((q = p.next) != null)? q : p);
                return item;
            }
            else if ((q = p.next) == null) {
                updateHead(h, p);
                return null;
            }
            else if (p == q)
                continue restartFromHead;
            else
                p = q;
        }
    }
}
```
  - 同样，compareAndSet 操作保证了只有当前头节点的 item 确实为非 null 时，才会将其设置为 null 并更新头节点。如果在尝试过程中，头节点的 item 已经被其他线程修改（即 item == null），则重新定位头节点并再次尝试。这种机制避免了在出队操作时的竞争条件，实现了并发安全的出队。
乐观锁策略
- ConcurrentLinkedQueue 整体采用乐观锁策略。它假设在大多数情况下，并发操作不会发生冲突。通过 compareAndSet 操作，线程尝试直接进行修改，如果修改失败（说明有其他线程同时修改了相关数据），则重试操作。这种方式相比于传统的悲观锁（在操作前先获取锁，假设操作一定会发生冲突），在高并发环境下能减少线程阻塞，提高并发性能。

星途面试题库

面试题：Java中ConcurrentLinkedQueue如何保证无锁并发操作的线程安全

知识考点

面试题答案