LinkedBlockingDeque详解

admin
Java
11天前
15热度
0评论

4.2 双向链表结构图

描述：

本图展示了包含三个节点（A、B和C）的一个典型双向链表。每个节点通过前驱(prev)和后继(next)指针相互连接，形成一个完整的双向循环。

graph LR;
    A((Node A)) --> B((Node B));
    A -->|prev| null;
    A -->|next| B;

    B((Node B)) --> C((Node Node C));
    B -->|prev| A;
    B -->|next| C;

    C((Node C)) --> A;
    C -->|prev| B;
    C -->|next| null;

    first(A);
    last(C);

解释：

节点A（首节点）
- prev为null
- next指向节点B
节点B（中间节点）
- prev指向前一个节点，即Node A
- next指向后一个节点，即Node C
节点C（尾节点）
- prev指向其前一个节点，即Node B
- next为null

队列状态：

当队列为空时：
- first和last均指null
当只有一个元素时：
- first和last指向同一个节点（假设该唯一节点是节点A）
- 节点的prev和next均为自身

4.3 双向链表插入操作图

描述：

本图展示了将一个新元素（E）插入到已有的双向链表中。我们分别演示了在首部（putFirst(E)）和尾部（putLast(E)）插入元素。

graph LR;
    A((Node A)) --> B((Node B));
    E((New Node E)) -->|prev| null;
    E -->|next| A;

    subgraph "After putFirst(E)"
        F((Node F)) --> E;
        E --> A;
        A --> B;
    end

    C((Node C)) --> A;
    C -->|prev| B;
    C -->|next| null;

解释：

插入新元素E到首部（putFirst(E)）
- 新节点E的prev为null
- E的next指向前一个首节点A
- 更新链表头first指向E
结构更新后
- 原来的首节点A，现在其prev指向新插入的E
- 链表仍由F、E、A和B构成（假设F是新的第一个元素）

graph LR;
    A((Node A)) --> B((Node B));
    C((Node C)) --> A;

    subgraph "After putLast(D)"
        D((New Node D)) -->|prev| C;
        D --> null;
        C --> D;
    end

解释：

插入新元素D到尾部（putLast(E)）
- 新节点E的next为null
- E的prev指向前一个尾节点C
- 更新链表尾last指向E

4.4 双向链表移除操作图

描述：

本图展示了从双向链表中删除首元素（takeFirst()) 和尾部元素 ( takeLast() ) 的过程。

graph LR;
    A((Node A)) --> B((Node B));
    C((Node C)) --> A;

    subgraph "After takeFirst()"
        E((Node B))
        F((Node A))
        G((Null))
    end

解释：

移除首元素（takeFirst()）
- 更新first为B
- 将A的next指向null（帮助GC）

graph LR;
    A((Node A)) --> B((Node B));
    C((Node C)) --> A;

    subgraph "After takeLast()"
        D((Node C))
        E((Null))
        F((B -> Node A))
    end

解释：

移除尾部元素（takeLast()）
- 更新last为A
- 将C的prev设为null，帮助GC回收节点C

4.5 线程安全操作图

本部分展示了在多线程环境下，两个线程尝试同时进行插入和移除操作时的情况。由于使用单锁机制，所有操作必须按顺序执行。

graph LR;
    T1{Thread 1: putFirst(E)}
    T2{Thread 2: takeLast()}

    subgraph "Initial State"
        A((Node A)) --> B((Node B));
        C((Node C)) --> A;
    end

    T1 -->|Lock Acquired| Add E to first
    T2 -->|Wait on Lock| Wait for Lock Release

    subgraph "After putFirst(E)"
        D((New Node E)) -->|prev| null;
        D --> A;
    end

    T1 -->|Release lock| Unlock

    T2 -->|Lock Acquired| Take last item
    T2 -->|Remove C| Remove C from list

解释：

初始状态
- 节点A、B和C组成双向链表，first指向Node A，last指向Node C。
线程T1尝试插入元素E到首部
- T1获取锁，并将新节点E添加为新的首节点。
线程T2等待
- T2试图移除尾部的C但无法获得锁，必须等待T1完成操作并释放锁。
线程T1释放锁
- 插入完成后释放锁，使T2能够获得锁并继续执行。
线程T2获取锁后移除元素C
- T2获取锁，并从双向链表中移除尾部的节点C。更新last指向Node A。

总结：

在LinkedBlockingDeque的设计中，单锁机制确保了所有操作的一致性，尽管这可能会导致性能上的降低（比如多线程环境下的竞争）。然而，在双端队列的应用场景下，这种设计能够提供更高的可靠性和简洁性。

这篇文档详细地介绍了 Java LinkedBlockingDeque 类的各种特性和性能特点，并提供了许多有用的指导和示例代码。以下是对该文档的一些关键点总结以及建议：

关键点总结

设计概述
- LinkedBlockingDeque 是一个基于双向链表的阻塞队列，实现了 BlockingDeque 接口。
- 它支持高效的双端操作（头部和尾部插入/删除）。
主要特性
- 可选有界：通过构造函数参数设置容量大小，默认为无界。
- 单锁机制：所有操作都使用同一个 ReentrantLock 保证线程安全，这意味着所有操作都是串行处理的，可能会造成一定的性能瓶颈。
- 支持双端阻塞队列和栈操作（如 putFirst, takeLast）。
适用场景
- 当需要支持工作窃取、双端操作时使用。
- 不适合纯 FIFO 场景，因为并发吞吐量较低，不如 LinkedBlockingQueue 高效。
性能分析
- 吞吐量受单锁机制的限制，在高并发情况下可能会有瓶颈。
- 内存占用较高，每个节点包含三个引用（对象本身、前驱和后继），而 LinkedBlockingQueue 仅需两个引用（对象本身和后继）。
注意事项
- 默认无界可能导致 OOM，请确保在创建时指定合理的容量。
- 使用 remove(Object) 方法会遍历整个队列，持有锁的时间较长，尽量避免频繁使用。
- 迭代器是弱一致性的，在迭代过程中修改队列不会抛出异常，但结果可能过期。

使用建议

选择合适的阻塞队列
- 如果只需要单向 FIFO 队列且对性能要求较高，请考虑 LinkedBlockingQueue。
- 对于需要双端操作的场景或工作窃取算法，则需要使用 LinkedBlockingDeque。
- 当容量固定并且内存占用是关键因素时，可以考虑使用 ArrayBlockingQueue。
合理设置队列容量
- 除非业务明确不需要限制队列大小，并且已经充分测试和控制了流量，否则请给队列设置一个合理的最大容量以防止 OOM。
性能优化技巧
- 使用 drainTo() 方法批量转移元素，减少锁竞争的机会。
- 监控队列的大小并定期检查，确保在达到容量阈值之前进行适当的处理。
避免常见陷阱
- 尽量避免在迭代过程中修改队列内容，可以考虑预先复制队列内容或者使用其他线程安全的数据结构。
- 注意捕获和处理 InterruptedException 异常，特别是在等待条件下被中断时需要正确处理以恢复正常的程序流程。

> 🔗 相关阅读：LinkedBlockingDeque