无锁队列简介

张开发
• 2026/4/13 8:36:08 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

无锁队列简介
无锁多线程编程中有lock-free(无锁)wait-free(无等待)blocking(阻塞)Non-blocking(非阻塞)。阻塞blocking在阻塞算法中线程尝试获取一个不可用的资源时会被挂起即进入阻塞状态直到资源变为可用。阻塞同步是最简单的同步机制但可能导致性能问题因为线程在等待资源时无法执行任何操作。阻塞状态下线程被挂起是在等待不进行任何操作。非阻塞 non-blocking非阻塞算法确保线程在访问共享资源时不会被挂起。如果资源不可用线程可以决定执行其他操作比如重试操作或回退。这种方法提高了系统的整体响应性和吞吐量。如果资源不可用就去做其他的事情而不是在等待。无锁lock-free无锁算法是非阻塞同步策略的一种它确保至少有一个线程能在有限的步骤中完成其操作从而在全局上避免了死锁。无锁同步通常依赖于原子操作如CASCompare-And-Swap。强调的是 无互斥锁阻塞。所有线程都持续前进不会因为某个线程持有锁而被挂起。如果更新时发现冲突如 CAS 失败线程会通过重试、回退或帮助其他线程完成来解决冲突。当一个线程占用共享资源其他线程再去访问这个共享资源时会发现有冲突就去处理其他事情了通常是进行重试。不保证某个特定线程能前进但保证系统整体不会因为任何一个线程的延迟或挂起而完全停滞。无等待wait-free算法无等待算法是一种特殊类型的非阻塞同步它保证所有线程都能在有限的步骤中完成其操作从而为每个线程提供了最强的进度保障。实现无等待算法非常复杂通常需要精心设计的数据结构。无等待一定是无锁无锁不一定是无等待。在数据处理程序、实时系统等场景中要使用无锁。生产者消费者队列常见的是 MPMC多生产者多消费者队列 和 MPSC多生产者单消费者队列。底层的数据结构是 数组 或 链表 或 两者混合。基于数据的队列处理速度更快但需要提前分配好内存。基于链表可以动态增长但需要频繁申请销毁内存。基于两者混合具有两者的有点点但实现复杂。根据链表队列可以分为入侵式 和 非入侵式。非侵入式节点的指针存储在队列内部。存放入队列中的是数据对象本身。侵入式节点指针存储在数据对象内部。放入队列中的是指向数据对象的指针。非侵入式是数据对象是队列的一个元素next指针也是队列的一个元素。侵入式是数据对象就是队列节点next指针在数据对象内部。队列长度也可划分为 无界 和 有界。无界不设置数量上限可以一直添加直到内存耗尽。有界设置数量上限如果达到上限就进行处理。一般为报错、丢弃、覆盖掉老数据。为 无界 和 有界。无界不设置数量上限可以一直添加直到内存耗尽。有界设置数量上限如果达到上限就进行处理。一般为报错、丢弃、覆盖掉老数据。

更多文章