如何实现一个非阻塞队列？阻塞和非阻塞算法有什么区别？
当讨论阻塞和非阻塞算法时所使用的术语可能会令人困惑，因此让我们从并发领域的术语开始，通过以下图表对其进行梳理。
?? 阻塞：
阻塞算法使用锁。线程A首先获取锁，而如果线程A在持有锁的情况下被挂起，则线程B可能会等待任意长的时间。这种算法可能会导致线程B挨饿。
?? 非阻塞：
非阻塞算法允许线程A访问队列，但线程A必须在一定步骤内完成任务。其他线程，如线程B，可能会因被拒绝而挨饿。
这是阻塞和非阻塞算法的主要区别：阻塞算法会阻塞线程B，直到锁被释放。非阻塞算法会通知线程B访问被拒绝。
?? 免饥饿：
线程饥饿指线程无法访问某些共享资源且无法继续执行。免饥饿指这种情况不会发生。
?? 等待自由：
所有线程都可以在有限的步骤内完成任务。
????????-???????? = ??????-???????????????? + ????????????????????-????????
?? 非阻塞队列实现
我们可以使用比较和交换（CAS）来实现非阻塞队列。下面的图表说明了算法。
?? 好处
1.无线程挂起。线程B可以立即获得响应，然后决定下一步该做什么。这样，线程的延迟大大降低了。2.无死锁。线程A和B不等待锁释放，因此不可能发生死锁。
?? 代码示例
import java.util.concurrent.atomic.AtomicReference;public class NonBlockingQueue<T> {private static class Node<T> {final T value;AtomicReference<Node<T>> next;public Node(T value) {this.value = value;this.next = new AtomicReference<>(null);}}private AtomicReference<Node<T>> head, tail;public NonBlockingQueue() {Node<T> dummy = new Node<>(null);head = new AtomicReference<>(dummy);tail = new AtomicReference<>(dummy);}public boolean enqueue(T value) {Node<T> node = new Node<>(value);while (true) {Node<T> last = tail.get(), next = last.next.get();if (last == tail.get()) {if (next == null) {if (last.next.compareAndSet(null, node)) {tail.compareAndSet(last, node);return true;}} else {tail.compareAndSet(last, next);}}}}public T dequeue() {while (true) {Node<T> first = head.get(), last = tail.get(), next = first.next.get();if (first == head.get()) {if (first == last) {if (next == null) {return null;}tail.compareAndSet(last, next);} else {T value = next.value;if (head.compareAndSet(first, next)) {return value;}}}}}}
在这个实现中，我们使用了一个Node类表示队列中的一个节点。每个节点保存了一个值，以及一个AtomicReference类型的next变量，表示这个节点的下一个节点。
?enqueue
我们使用AtomicReference类型的head和tail来分别指向队列的头和尾。在enqueue()方法中，我们首先创建一个新的节点，并不断循环尝试将其添加到队列尾部。在每次循环中，我们首先获取当前队列的最后一个节点last以及它的下一个节点next，然后判断是否有其他线程在同时修改队列，如果没有，则通过compareAndSet()方法将新节点添加到last的next中，如果成功，则通过compareAndSet()方法将tail指向新节点，并返回true，表示添加成功。如果失败，则尝试将tail指向当前队列的最后一个节点。
?dequeue
在dequeue()方法中，我们首先不断循环尝试获取队列头和尾，以及队列头的下一个节点。然后，我们判断队列是否为空，如果为空则返回null。否则，我们返回队列头的下一个节点的值，并通过compareAndSet()方法将head指向下一个节点，完成出队操作。如果失败，则继续循环。
这个实现保证了非阻塞特性，因为在enqueue()和dequeue()方法中，每个线程都可以通过CAS操作进行无锁操作。
原创文章，作者：小技术君，如若转载，请注明出处：https://www.sudun.com/ask/34029.html
