2018什么做网站,国外平面设计,阿里云服 WordPress,网络规划设计师是职业资格吗前言#xff1a;
ring buffer / circular buffer 又名环形队列 / 环形缓冲区#xff0c;其通过开辟固定尺寸的内存来实现反复复用同一块内存的目的。由于预先开辟了固定尺寸的内容#xff0c;所以当数据满的时候#xff0c;可以有两种处理方式#xff0c;具体使用哪一种按…前言
ring buffer / circular buffer 又名环形队列 / 环形缓冲区其通过开辟固定尺寸的内存来实现反复复用同一块内存的目的。由于预先开辟了固定尺寸的内容所以当数据满的时候可以有两种处理方式具体使用哪一种按照实际需求具体如下
1当队列满的时候新来的数据会覆盖最古老的数据这种数据结构的特点是数据的写入不会因为队列满了而停止同时也会导致旧数据的丢失常用在一些对老旧数据不敏感的场景。如果数据很重要且不希望被丢弃那么不要使用这种覆盖的模式比如 流媒体场景下每一帧数据都要确保完整地被渲染出来不然会出现跳帧和音画同步无法完成等问题所以不适合这种模式。
2当数据满的时候block 或者禁止写入操作直到队列有空间时再允许写入。这种模式下可以保证数据不被覆盖掉。
环形队列优势在于不需要反复开辟(alloc)内存空间可以反复复用同一块内存区域这样避免了反复申请释放内存带来的时间开销和内存碎片化。 ps下文以环形队列来代替 ring buffer / circular buffer / 环形缓冲区。 环形队列的最小可操作单位并不是固定的可以是一个字节的内存空间也可以是N个字节或者是其他数据结构体类型的内存尺寸这取决于环形队列最小单元的尺寸。比如 char ringbuffer[409600] 的环形队列可操作的最小单位一般就是一个字节long long ringbuffer[409600] 的环形队列很可能就是按照8个字节作为一个最小粒度单元的。 下文中使用单位一次来指代环形队列的最小可操作元素同样地一个步进单位也是指一次地址移动的步长。 设计思路
环形队列 的管理需要 4 个 index 值 队列开始处 start队列结束处 end已填充区域的头部 head已填充区域的尾部 tail。因为环形队列是固定尺寸的缓冲区所以一般情况下使用内存地址来表示者 4个 index。
start 和 end 表示开辟的固定内存空间的 起始位置用来限定整个环形队列可以游走的空间范围。start指向内存开始的地址end指向内存结束的地址。
head 和 tail 反映已经写入数据的内存空间的 起始位置这里用反映而不是用表示是说明 head 和 tail 对于地址的表示 和 start 和 end 有所不同。 head 指向下一次可写入地址的开始位置注意这里是下一次可写入而不是上一次写入的尾部。tail 指向已经写入区域的最老的内存单元的地址。head 指向的是未被写入的地址tail指向的是已经被写入的地址。 几个重要的限定条件
1head index 只能指向未被写入的位置。 A ‘head’ index - the point at which the producer inserts items into the buffer. 2tail index 可以指向任何位置。 A ‘tail’ index - the point at which the consumer finds the next item in the buffer. 3队列满当 head index 前进一个 单位后等于 tail index 的时候队列就满了这个时候其实还剩余一个未被写入的单位因为 head 永远是指向未被写入的单位。所以队列满等于 head sizeof(element) tail 。如果head 和 tail 是指针那么 head 1 tail因为指针 加 1 会根据指针类型自动调节字节步长。 the buffer is full when the head pointer is one less than the tail pointer. 伪代码 bool isempty(){ if(tail head) return true; else return false; } 4队列空当 tail index 等于 head index 的时候队列就空了。 Typically when the tail pointer is equal to the head pointer, the buffer is empty 伪代码 bool isfull(){ if(tail head1) return true; else return false; } 上面伪代码只做说明不可实用因为实际情况下需要考虑到 head 和 tail 到达和越过 end 时需要重置到 start 位置重新计算的问题。 是否需要考虑同步问题
是需要考虑同步问题。
单生产者和单消费者场景下产消双方没有机会操作相同的队列单元但是head index 和 tail index 还是存在 race condition 的。
多生产者和多消费者场景下更需要加锁。 implement with c 11
队列满则覆盖版老数据版本 队列满则等待可用空间版本 implement with c
队列满则覆盖版老数据版本 队列满则等待可用空间版本 lock free practice
队列满则覆盖版老数据版本 队列满则等待可用空间版本 参考
Circular Buffers — The Linux Kernel documentationhttps://www.kernel.org/doc/html/v4.20/core-api/circular-buffers.html
