学习
实践
活动
工具
TVP
写文章
专栏首页Java程序猿部落线程安全的无锁RingBuffer的实现

线程安全的无锁RingBuffer的实现

在程序设计中,我们有时会遇到这样的情况,一个线程将数据写到一个buffer中,另外一个线程从中读数据。所以这里就有多线程竞争的问题。

通常的解决办法是对竞争资源加锁。但是,一般加锁的损耗较高。其实,对于这样的一个线程写,一个线程读的特殊情况,可以以一种简单的无锁RingBuffer来实现。这样代码的运行效率很高。

代码的基本原理如下。

如图所示,假定buffer的长度是bufferSize. 我们设置两个指针。head指向的是下一次读的位置,而tail指向的是下一次写的位置。由于这里是环形buffer (ring buffer),这里就有一个问题,怎样判断buffer是满或者空。

这里采用的规则是,buffer的最后一个单元不存储数据。所以,如果head == tail,那么说明buffer为空。如果 head == tail + 1 (mod bufferSize),那么说明buffer满了。

接下来就是最重要的内容了:怎样以无锁的方式进行线程安全的buffer的读写操作。基本原理是这样的。在进行读操作的时候,我们只修改head的值,而在写操作的时候我们只修改tail的值。在写操作时,我们在写入内容到buffer之后才修改tail的值;而在进行读操作的时候,我们会读取tail的值并将其赋值给copyTail。

赋值操作是原子操作。所以在读到copyTail之后,从head到copyTail之间一定是有数据可以读的,不会出现数据没有写入就进行读操作的情况。同样的,读操作完成之后,才会修改head的数值;而在写操作之前会读取head的值判断是否有空间可以用来写数据。

所以,这时候tail到head - 1之间一定是有空间可以写数据的,而不会出现一个位置的数据还没有读出就被写操作覆盖的情况。这样就保证了RingBuffer的线程安全性。

最后附上代码供参考。欢迎批评指正,也欢迎各种讨论!

public class RingBuffer {

    private final static int bufferSize = 1024;
    private String[] buffer = new String[bufferSize];
    private int head = 0;
    private int tail = 0;
    
    private Boolean empty() {
        return head == tail;
    }
    private Boolean full() {
        return (tail + 1) % bufferSize == head;
    }
    public Boolean put(String v) {
        if (full()) {
            return false;
        }
        buffer[tail] = v;
        tail = (tail + 1) % bufferSize;
        return true;
    }
    public String get() {
        if (empty()) {
            return null;
        }
        String result = buffer[head];
        head = (head + 1) % bufferSize;
        return result;
    }
    public String[] getAll() {
        if (empty()) {
            return new String[0];
        }
        int copyTail = tail;
        int cnt = head < copyTail ? copyTail - head : bufferSize - head + copyTail;
        String[] result = new String[cnt];
        if (head < copyTail) {
            for (int i = head; i < copyTail; i++) {
                result[i - head] = buffer[i];
            }
        } else {
            for (int i = head; i < bufferSize; i++) {
                result[i - head] = buffer[i];
            }
            for (int i = 0; i < copyTail; i++) {
                result[bufferSize - head + i] = buffer[i];
            }
        }
        head = copyTail;
        return result;
    }
}
文章分享自微信公众号:
Java程序猿部落

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

原始发表时间:2019-12-19
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • JAVA 中无锁的线程安全整数 AtomicInteger介绍和使用

    转载自 http://blog.csdn.net/bigtree_3721/article/details/51296064

    allsmallpig
  • 无锁队列的实现

    关于无锁队列的实现,网上有很多文章,虽然本文可能和那些文章有所重复,但是我还是想以我自己的方式把这些文章中的重要的知识点串起来和大家讲一讲这个技术。下面开始正文...

    Linux阅码场
  • 无锁队列的实现

    锁是高性能程序的杀手,但是为了保证数据的一致性,在多线程的应用环境下又不得不加锁。但是在某些特殊的场景下, 是可以通过优化数据结构来达到无锁的目的。那么我们就来...

  • 线程同步和锁_自旋锁的实现

    自旋锁(Spinlock)是一种广泛运用的底层同步机制。自旋锁是一个互斥设备,它只有两个值:“锁定”和“解锁”。它通常实现为某个整数值中的某个位。希望获得某个特...

    全栈程序员站长
  • 共享内存无锁队列的实现

    共享内存无锁队列是老调重弹了,相关的实现网上都能找到很多。但看了公司内外的很多实现,都有不少的问题,于是自己做了重新实现。主要是考虑了一些异常情况加强健壮性,并...

    豆豆的包包
  • c语言 无锁编程,无锁编程与有锁编程的效率总结、无锁队列的实现(c语言)「建议收藏」

    无锁编程,即通过CAS原子操作去控制线程的同步。如果你还不知道什么使CAS原子操作,建议先去查看相关资料,这一方面的资料网络上有很多。

    全栈程序员站长
  • 动态代理+读写锁实现线程安全的HashMap缓存工具类

    jdk1.8之前是没有线程安全的集合工具类,例如currentHashMap,那怎样实现高效、线程安全的集合工具类呢? 可以利用读写锁实现线程安全,动态代理帮...

    Yuyy
  • 如何实现超高并发的无锁缓存?

    一、需求缘起 【业务场景】 有一类写多读少的业务场景:大部分请求是对数据进行修改,少部分请求对数据进行读取。 例子1:滴滴打车,某个司机地理位置信息的变化(可能...

    架构师之路
  • 字典树收集(初步读写锁实现线程安全,待续)

    将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀...

    算法之名
  • 线程的锁

    其中,AbstractQueuedSynchronizer为AQS,而且我们后面要讲的Lock显式锁的内部类(ReentrantLock、 ReadWriteL...

    晚上没宵夜
  • java多线程中的死锁、活锁、饥饿、无锁都是什么鬼?

    死锁、活锁、饥饿是关于多线程是否活跃出现的运行阻塞障碍问题,如果线程出现了这三种情况,即线程不再活跃,不能再正常地执行下去了。 死锁 死锁是多线程中最差的一种情...

    Java技术栈
  • 使用Unsafe实现“无锁”的原子数据结构 | 锁系列-Java中的锁

    现在市面上很少有关于Unsafe的话题。这个Unsafe有个compareAndSwap方法是原子的,并且使用这个方法可以实现高性能的lock-free的数据结...

    ImportSource
  • 高性能无锁并发框架Disruptor,太强了

    Disruptor是一个开源框架,研发的初衷是为了解决高并发下队列锁的问题,最早由LMAX提出并使用,能够在无锁的情况下实现队列的并发操作,并号称能够在一个线程...

    愿天堂没有BUG
  • 高性能无锁并发框架 Disruptor,太强了!

    Disruptor是一个开源框架,研发的初衷是为了解决高并发下队列锁的问题,最早由LMAX提出并使用,能够在无锁的情况下实现队列的并发操作,并号称能够在一个线程...

    Java技术栈
  • 线程的锁机制

    多线程编程访问共享变量时会出现问题,但是多进程编程访问共享变量不会出现问题。因为多进程中,同一个变量各自有一份拷贝存在于每个进程中,互不影响,而多线程中,所有变...

    养码场
  • 一种高效无锁内存队列的实现

    Disruptor是LMAX公司开源的一个高效的内存无锁队列。这两天看了一下相关的设计文档和博客,下面尝试进行一下总结。 第一部分。引子 谈到并发程序设计,有几...

    李海彬
  • 无锁队列的几种实现及其性能对比

    作者:juliatliu,腾讯 PCG 运营开发工程师 一、无锁队列用在什么样的场景? 当需要处理的数据非常多,比如行情数据,一秒处理非常多的数据的时候,可以考...

    腾讯技术工程官方号
  • Go 使用互斥锁(sync.Mutex)实现线程安全的内存本地缓存(LocalCache)

    如果嵌入结构的字段和外部结构的字段相同,那么, 为了避免命名冲突, 想要修改嵌入结构的字段值需要加上外部结构中声明的嵌入结构名称.

    一个会写诗的程序员
  • .NET/JAVA/GO 固定时间窗口算法实现(无锁线程安全)

    最近有一个生成 APM TraceId 的需求,公司的APM系统的 TraceId 的格式为:APM AgentId+毫秒级时间戳+自增数字,根据此规则生成的 ...

    晓晨

扫码关注腾讯云开发者

领取腾讯云代金券