0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

ringbuffer数据结构介绍

科技绿洲 来源:Linux开发架构之路 作者:Linux开发架构之路 2023-11-13 10:44 次阅读

最近在研究srsLTE的代码,其中就发现一个有意思的数据结构------ringbuffer。

虽然,这是一个很基本的数据结构,但时,它在LTE这种通信协议栈系统中却大行其道,也是很容易被协议开发人员忽略的。在整个通信协议的开发团队中,一般会有一个平台中间件的团队,他们的任务是给业务部门提供高性能、高可靠性的中间件代码,如内存池、线程池、消息通信机制、日志系统等等。这篇文章就来讨论下这个简约而不简单的ringbuffer。

ringbuffer数据结构

环形缓冲器(ringr buffer),也称作圆形队列(circular queue),循环缓冲区(cyclic buffer),圆形缓冲区(circula buffer),是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。

在通信程序中,经常使用环形缓冲器作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的循环缓冲区,可以向通信程序提供对缓冲区的互斥访问。

图片

用法

圆形缓冲区的一个有用特性是:当一个数据元素被用掉后,其余数据元素不需要移动其存储位置。相反,一个非圆形缓冲区(例如一个普通的队列)在用掉一个数据元素后,其余数据元素需要向前搬移。换句话说,圆形缓冲区适合实现先进先出缓冲区,而非圆形缓冲区适合后进先出缓冲区。

圆形缓冲区适合于事先明确了缓冲区的最大容量的情形。扩展一个圆形缓冲区的容量,需要搬移其中的数据。因此一个缓冲区如果需要经常调整其容量,用链表实现更为合适。

写操作覆盖圆形缓冲区中未被处理的数据在某些情况下是允许的。特别是在多媒体处理时。例如,音频的生产者可以覆盖掉声卡尚未来得及处理的音频数据。

工作机制

一般的,圆形缓冲区需要4个指针 :

  • 在内存中实际开始位置;
  • 在内存中实际结束位置,也可以用缓冲区长度代替;
  • 存储在缓冲区中的有效数据的开始位置(读指针);
  • 存储在缓冲区中的有效数据的结尾位置(写指针)。
    读指针、写指针可以用整型值来表示。下例为一个未满的缓冲区的读写指针:

图片

下例为一个满的缓冲区的读写指针:

图片

区分缓冲区满或者空

缓冲区是满、或是空,都有可能出现读指针与写指针指向同一位置,有多种策略用于检测缓冲区是满、或是空。常用的做法是总是保持一个存储单元为空,缓冲区中总是有一个存储单元保持未使用状态。缓冲区最多存入 size-1个数据。如果读写指针指向同一位置,则缓冲区为空。如果写指针位于读指针的相邻后一个位置,则缓冲区为满。这种策略的优点是简单、鲁棒;缺点是语义上实际可存数据量与缓冲区容量不一致,测试缓冲区是否满需要做取余数计算。

出色的KFIFO

kfifo是一种"First In First Out “数据结构,它采用了前面提到的环形缓冲区来实现,提供一个无边界的字节流服务。采用环形缓冲区的好处为,当一个数据元素被用掉后,其余数据元素不需要移动其存储位置,从而减少拷贝提高效率。更重要的是,kfifo采用了并行无锁威廉希尔官方网站 ,kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。

熟悉Linux内核的读者应该对kfifo.c和kfifo.h并不陌生.kfifo经过简单改进就可以在用户态进行使用,笔者在实际项目中多次使用,经过实践,代码是稳定、可靠、高效的。

ringbuffer蕴藏的巨大能量

消息队列

ringbuffer的一个天生的高性能的消息队列,特别是在单生产/单消费的模式下,它是无锁的,这点非常重要。之前的文章曾介绍过,LTE的协议栈实现对时序是敏感的,这意味着代码的执行不能有阻塞的风险,而线程间的通信几乎是协议栈中必须的基本功能。因此,用ringbuffer去实现一个高性能的消息队列是一种非常理想的方案。当然,由于不同的线程的运行模型不同,例如PDCP线程属于包驱动的线程,大部分时间它是属于阻塞的,当有数据到达,如RRC可以通过消息队列给PDCP发送一个消息,这个时候需要唤醒PDCP进行处理,这个是属于线程同步的威廉希尔官方网站 范畴,可以通过MUTEX、信号量等方案去实现。如果你的系统的Linux(rt-patch),eventfd也是不错的选择,eventfd优势是可以使用poll、select、epoll等操作,这样协议栈的线程实现的方式上较为简洁,关键是eventfd性能也非常的快。

当然这里需要划一个重点,不同线程间需要独立的消息队列,来保证FIFO的无锁特性,当然缺点是会浪费一些内容,但是这在协议栈的开发中往往不是什么大的问题,性能和稳定永远是第一位的。由于FIFO通常是固定大小的数据结构不太适合可变消息的发送,这里的技巧是队列里面只放消息的指针,消息的内容通常是在内存池中申请不同大小的结构。

srsLTE代码的实现PDCP和RLC并不一定是以单独的线程运行的,但是在实际项目中,为了性能的考虑,通常是需要线程化的,且上下行也要线程化,且绑定不同的CPU核,来保证性能。

下图是PDCP和RLC线程的消息队列实例:

图片

内存池

内存池在通信协议栈和很多的软件中都是常用的威廉希尔官方网站 ,它的好处是除了可以避免内存碎片,更重要的一点是,内存是预先申请的,并且自我管理,在申请和释放的效率更快,这对协议栈的实现是十分重要的。

内存池的实现在方式都是大同小异的,通常将内存分为8字节、16字节、32字节… 1K等大小不同的内存块,并通过链表的方式进行管理。具体的实现方式可以自行到github上搜索,实现方式都是类似的。

那么,ringbuffer和内存池有什么关系呢?实际上,ringbuffer和内存池的实现并无直接的关系,但是内存池在实现上有个至关重要的问题,那就内存的申请和释放可能不是在同一个线程中。简单的说就是,内存的申请和释放可能存在竞争的情况,通常的做法是进行加锁进行保护。但是加锁的操作可能对协议的时序产生不确定的影响,这对时序要求较高的协议实现(如CMAC)是无法接受的。

ringbuffer的优秀的特性又一次被应用的淋漓尽致,做法也是相当的简单,就是使用ringbuffer单生产/单消费的模式的无锁特性,释放的线程可以将需要释放的地址使用ringbuffer发送给申请的线程,由申请的线程进行内存的释放,这就就不需要加锁的操作,因为同一个线程不会出现并发的链表操作。

下图是结合了消息队列和内存池威廉希尔官方网站 的一次应用,该方案是十分经典和有效的,在很多大型的通信系统中都能看到这种方案的影子:

图片

总结

本文是结合笔者的实际项目经验,介绍了ringbuffer在协议栈软件开发中的一些应用和技巧,主要是ringbuffer单生产/单消费的模式的无锁特性在内存池内存释放和消息队列中的应用技巧。如果读者也有类似的性能方面的系统需求,可以不妨试试 ringbuffer,性能超乎你的想象,且没有特别复杂的算法和CPU指令集的限制。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 缓冲器
    +关注

    关注

    6

    文章

    1922

    浏览量

    45478
  • 数据结构
    +关注

    关注

    3

    文章

    573

    浏览量

    40126
  • 线程池
    +关注

    关注

    0

    文章

    57

    浏览量

    6846
收藏 人收藏

    评论

    相关推荐

    数据结构

    1.数据结构的概念 所谓数据结构是指由某一数据对象及该对象中所有数据成员之间的关系组成的集合。成员之间的关系有很多种,最常见的是前后件关系。 2.
    发表于 03-04 14:13

    常见的数据结构

    `数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。一、什么是数据结构数据结构,直
    发表于 05-10 07:58

    C语言与数据结构

    目录个人介绍笔试单选题C语言数据结构计算机与操作系统网络通信填空题C语言与数据结构网络通信问答题嵌入式基础知识C语言与数据结构C编程一面二面功能快捷键合理的创建标题,有助于目录的生成如
    发表于 08-06 07:10

    数据结构教程,下载

    1. 数据结构的基本概念 2. 算法与数据结构3. C语言的数据类型及其算法描述要点4. 学习算法与数据结构的意义与方法
    发表于 05-14 17:22 0次下载
    <b class='flag-5'>数据结构</b>教程,下载

    什么是数据结构

    什么是数据结构 1、数据类型和数据结构·数据值:atomic data value: 不可再分解。如3、2、5等。nonatomicdata value: 可以再分解,其成分称为
    发表于 08-13 13:56 1680次阅读

    C数据结构介绍

    C数据结构,个人收集整理了很久的资料,大家根据自己情况,有选择性的下载吧~
    发表于 10-27 14:03 0次下载

    数据结构与算法

    全国C语言考试公共基础知识点——数据结构与算法,该资料包含了有关数据结构与算法的全部知识点。
    发表于 03-30 14:27 0次下载

    数据结构与算法分析

    一部浅显易懂的介绍数据结构与算法的书籍。
    发表于 07-14 17:12 0次下载

    数据结构

    数据结构PPT教程
    发表于 02-27 16:43 0次下载

    数据结构是什么_数据结构有什么用

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高
    发表于 11-17 14:45 1.6w次阅读
    <b class='flag-5'>数据结构</b>是什么_<b class='flag-5'>数据结构</b>有什么用

    为什么要学习数据结构数据结构的应用详细资料概述免费下载

    本文档的主要内容详细介绍的是为什么要学习数据结构数据结构的应用详细资料概述免费下载包括了:数据结构在串口通信当中的应用,数据结构在按键监测
    发表于 09-11 17:15 13次下载
    为什么要学习<b class='flag-5'>数据结构</b>?<b class='flag-5'>数据结构</b>的应用详细资料概述免费下载

    什么是数据结构?为什么要学习数据结构数据结构的应用实例分析

    本文档的主要内容详细介绍的是什么是数据结构?为什么要学习数据结构数据结构的应用实例分析包括了:数据结构在串口通信当中的应用,
    发表于 09-26 15:45 14次下载
    什么是<b class='flag-5'>数据结构</b>?为什么要学习<b class='flag-5'>数据结构</b>?<b class='flag-5'>数据结构</b>的应用实例分析

    数据结构解决滑动窗口问题

    前文用 [单调栈解决三道算法问题]介绍了单调栈这种特殊数据结构,本文写一个类似的数据结构「单调队列」。 也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点
    的头像 发表于 04-19 10:50 656次阅读
    <b class='flag-5'>数据结构</b>解决滑动窗口问题

    NetApp的数据结构是如何演变的

    混合和多云部署模型是企业IT组织的新常态。随着这些复杂的环境,围绕数据管理的新挑战出现了。NetApp的数据管理愿景是一种无缝连接不同的数据结构云,无论它们是私有环境、公共环境还是混合环境。
    发表于 08-25 17:15 0次下载
    NetApp的<b class='flag-5'>数据结构</b>是如何演变的

    redis数据结构的底层实现

    Redis是一种内存键值数据库,常用于缓存、消息队列、实时数据分析等场景。它的高性能得益于其精心设计的数据结构和底层实现。本文将详细介绍Redis常用的
    的头像 发表于 12-05 10:14 619次阅读