精华内容
下载资源
问答
  • 循环缓冲区

    千次阅读 2018-07-26 09:55:46
    这次需要记录之前了解到的参考自linux内核循环队列kfifo的循环缓冲区实现方法。 1、循环缓冲区的实现依靠队列来实现,也就是分配一个数组来存储实际数据。 2、对于一个循环缓冲区来说,我们需要关注的点有: ①...

    这次需要记录之前了解到的参考自linux内核循环队列kfifo的循环缓冲区实现方法。

    1、循环缓冲区的实现依靠队列来实现,也就是分配一个数组来存储实际数据。

    2、对于一个循环缓冲区来说,我们需要关注的点有:

    ①缓冲区大小应该设置多少?

    ②缓冲区队头(in)、队尾(out)初始值?

    ③缓冲区什么时候为空,什么时候为满?

    ④如何表示缓冲区长度?

    ⑤如何入队,如何出队?

    ⑥如何处理索引值溢出问题?

     

    3、要实现循环缓冲区,我们当然可以用我们数据结构课学过的循环队列来实现,也就是:

    设队列大小为M;in和out为下标值。

    ①循环缓冲区的大小设置为M(没有限制)

    ②初始化队头 in=0 ,队尾 out = 0

    ③out == in的时候缓冲区为空,(in+1)%M == out 的时候为满

    ④缓冲区长度len =(in - out + M)% M

    ⑤入队:a[in] = data ;  in = (in+1) % M;

        出队:data = a[out] ;  out = (out+1)%M;

    ⑥索引溢出通过对缓冲区长度进行求余来实现。

     

    4、我们也可以通过另一种更好的方法来实现

    同样设队列大小为M;in和out为下标值,但是他们的数据类型都是unsigned int(无符号整型)!!!

    ①循环缓冲区的大小M设置为2的幂(举例M=2^4=16)

    ②初始化队头 in=0 ,队尾 out = 0

    ③out == in的时候缓冲区为空,(in - out ) == M的时候缓冲区为满。

    ④缓冲区的长度len = (in - out)

    ⑤入队:a[ in & (M-1) ] = data ; in = ++in;

        出对:data = a[ out & (M-1) ] ; out = ++out;

    ⑥因为我们缓冲区的大小M设置为2的幂,而unsigned int 型的溢出值肯定是M的2的幂次倍,也就是我们的unsigned int 能表示的数值范围就是2的幂数倍个M。所以,当我们需要得到当前in或者out对应于实际分配到内存的那块循环缓冲区的哪个位置时,可以让in或者out跟(M-1)相与;而更新in和out时,只需要++in和++out。

     

    下面举例说明:

    M = 10000;(M设置为16)

    (M-1) = 01111; 

    由于in和out都是unsigned int数据类型,所以in和out能表示的数值范围为maxof(unsigned_int)=2^32-1 = 4294967295

    a、当out在[0,M-1]范围内,就设out = 6(0110),out & (M-1) = 0110,也就是6。嗯,这个简单。

    b、当out 在[M,4294967295]范围内,设out = 28(11100),out & (M-1) = 11100 & 01111 = 01100,也就是out等于28时对应的循环缓冲区的位置下标为12。

    c、分析一下最极端的情况当out等于unsigned int的最大值4294967295,

        out&(M-1)= 01111,也就是循环缓冲区的最后一个位置。

        而out+1就溢出了,由于unsigned int溢出时变为0,又从最后一个位置加到第一个位置了。

       

    总结:

    关键字:unsigned int 、按位与运算、2的次幂

    a、必须要将M设置为2的次幂。

    b、用这种方法不必让in和out对M取余,通过与运算,可以提升速度。

    b、unsigned int 溢出时自动变为0,更新in和out时只需要加1即可,方便。

    展开全文
  • 下载Circular-master.zip-14.4 ...,但是没有循环缓冲器或循环队列(“双头”队列)。本课程旨在填补这一空白。 概念化这个混乱 循环缓冲器可从容器的正面和背面快速push和pop。假设没有重新分配,则这些操作的时...

    目录

    介绍

    概念化这个混乱

    使用这个混乱

    兴趣点


    介绍

    微软.NET提供了一些基本的通用数据结构,例如Stack<T>Queue<T>LinkedList<T>,但是没有循环缓冲器或循环队列(双头队列)。本课程旨在填补这一空白。

    概念化这个混乱

    循环缓冲器可从容器的正面和背面快速pushpop。假设没有重新分配,则这些操作的时间复杂度为O(1) ,而其他插入和删除操作的时间复杂度为O(n) 

    这使缓冲区适合作为通用堆栈或队列。尽管Microsoft拥有堆栈或队列,但仍可能希望以这种方式使用这个类的原因是这个类允许按索引访问并完全实现IList<T> 

    使用这个混乱

    该类相对易于使用。大多数IList<T>ICollection<T>接口成员都是显式的,因为它们的大多数操作都是O(n)而不是O(1。这意味着您必须转换为适当的接口才能完全访问其列表或集合成员。这是为了防止对数据结构的随意使用——它并不是主要用作列表类,而可以用作一个列表类。访问修饰符反映了这一点。

    主要APIPushBack()PopBack()PushFront()PopFront()组成 ,分别在容器的后面或前面添加和删除项目。也有一些更多的标准列表/集合成员如Contains()IndexOf()this[] Clear()

    这是演示/测试代码的摘录:

    Console.WriteLine("Adding 10 items");
    for (var i = 0; i < 10; ++i)
        list.PushBack(i + 1);
    
    Console.Write("Enumerating "+ list.Count+" items:");
    foreach (var item in list)
        Console.Write(" " + item.ToString());
    Console.WriteLine();
    
    Console.WriteLine("Removing 1 item");
    list.PopFront();

    兴趣点

    我真的受不了实现Insert(),尤其是在循环缓冲区上,如果有错误,可能在Insert()代码中。我不确定例程是否可以简化。有很多极端的情况。

    展开全文
  • 说说循环缓冲区(Ring Buffer)

    万次阅读 2013-11-28 21:04:54
    关于循环缓冲区(Circular Buffer)的概念,其实来自于Linux内核(Maybe),是为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个,而在其它情况下使用它也是必须...

          关于循环缓冲区(Ring Buffer)的概念,其实来自于Linux内核(Maybe),是为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个,而在其它情况下使用它也是必须要加锁的。对应在Linux内核中有对它的定义:

    struct kfifo {
             unsigned char *buffer;
             unsigned int size;
             unsigned int in;
             unsigned int out;
             spinlock_t *lock;
    };
        当然关于对它有对应的操作函数,这里不再说了(不是今天的重点)。我们只要了解这种概念就好。   

        关于定义: 其中buffer指向存放数据的缓冲区,size是缓冲区的大小,in是写指针下标,out是读指针下标,lock是加到struct kfifo上的自旋锁(上面说不加锁不是这里的锁),防止多个进程并发访问此数据结构。当in==out时,说明缓冲区为空;当(in-out)==size时,说明缓冲区已满。 

                                                                   

        注:我们保有对应的读写指针,当第一批数据(蓝色)完成,第二批数据(红色)会根据当前的写指针位置继续我们的数据操作,当达到最大的Buffer_Size时,会重新回到Buffer的开始端。

       对此我给出一个简单的模拟实现Class:

    /*
     * =====================================================================================
     *
     *       Filename:  ring_buffer_class.h
     *        Version:  1.0
     *        Created:  2013年11月28日 13时08分04秒
     *       Revision:  none
     *       Compiler:  clang
     *         Author:  sim szm, xianszm007@gmail.com
     *
     * =====================================================================================
     */
    #include <iostream>
    class ring_buffer {
    public:
        ring_buffer( void* buffer, unsigned int buffer_size );
        void buffer_data( const void* data, unsigned int& len );
        void get_Data( void* outData, unsigned int& len );
        void skip_data( unsigned int& len );
        inline unsigned int free_space();
        inline unsigned int buffered_bytes();
    private:
        void flush_state();
        unsigned char *read_ptr, *write_ptr;
        unsigned char *end_pos;
        unsigned char *buffer;
        int max_read, max_write, buffer_data_;
    };
    ring_buffer::ring_buffer( void* buffer, unsigned int buffer_size ) {
        buffer = (unsigned char*)buffer;
        end_pos = buffer + buffer_size;
        read_ptr = write_ptr = buffer;
        max_read = buffer_size;
        max_write = buffer_data_ = 0;
        flush_state();
    }
    void ring_buffer::buffer_data( const void* data, unsigned int& len ) {
        if ( len > (unsigned int)max_read )
            len = (unsigned int)max_read;
        memcpy( read_ptr, data, len );
        read_ptr += len;
        buffer_data_ += len;
        flush_state();
    }
    void ring_buffer::get_Data( void* outData, unsigned int& len ) {
        if ( len > (unsigned int)max_write )
            len = (unsigned int)max_write;
        memcpy( outData, write_ptr, len );
        write_ptr += len;
        buffer_data_ -= len;
        flush_state();
    }
    void ring_buffer::skip_data( unsigned int& len ) {
        unsigned int requestedSkip = len;
        for ( int i=0; i<2; ++i ) {            // 可能会覆盖,做两次
            int skip = (int)len;
            if ( skip > max_write )
                skip = max_write;
            write_ptr += skip;
            buffer_data_ -= skip;
            len -= skip;
            flush_state();
        }
        len = requestedSkip - len;
    }
    inline unsigned int ring_buffer::free_space() {
        return (unsigned int)max_read;
    }
    inline unsigned int ring_buffer::buffered_bytes() {
        return (unsigned int)buffer_data_;
    }
    void ring_buffer::flush_state() {
        if (write_ptr == end_pos)	
    	  write_ptr = buffer;
        if (read_ptr == end_pos)		
    	  read_ptr = buffer;
        if (read_ptr == write_ptr) {
            if ( buffer_data_ > 0 ) {
                max_read = 0;
                max_write = end_pos - write_ptr;
            } else {
                max_read = end_pos - read_ptr;
                max_write = 0;
            }
        } else if ( read_ptr > write_ptr ) {
            max_read = end_pos - read_ptr;
            max_write = read_ptr - write_ptr;
        } else {
            max_read = write_ptr - read_ptr;
            max_write = end_pos - write_ptr;
        }
    }

       我们更多要说的是Ring Buffer关于在我们在日志处理方面的一个应用,我们知道对于Program来说日志记录提供了故障前应用程序状态的详细信息,在一段时间的运行过程中,会将不断地产生大量的跟踪数据,以及调试信息并持续地将其写入到磁盘上的文本文件中。多亿进行有效的日志记录,需要使用大量的磁盘空间,并且在多线程环境中,所需的磁盘空间会成倍地增加。常规的日志处理来说存在一些问题,比如硬盘空间的可用性,以及在对一个文件写入数据时磁盘 I/O 的速度较慢。持续地对磁盘进行写入操作可能会极大地降低程序的性能,导致其运行速度缓慢。通常,可以通过使用日志轮换策略来解决空间问题,将日志保存在几个文件中,当这些文件大小达到某个预定义的字节数时,对它们进行截断和覆盖。

                                     

        所以要克服空间问题并实现磁盘 I/O 的最小化,某些程序可以将它们的跟踪数据记录在内存中,仅当请求时才转储这些数据。这个循环的、内存中的缓冲区称为循环缓冲区它可以将相关的数据保存在内存中,而不是每次都将其写入到磁盘上的文件中。在需要的时候(比如当用户请求将内存数据转储到文件中时、程序检测到一个错误时,或者由于非法的操作或者接收到的信号而引起程序崩溃时)可以将内存中的数据转储到磁盘。循环缓冲区日志记录由一个固定大小的内存缓冲区构成,进程使用这个内存缓冲区进行日志记录。

       当然现在我们面对的大多是多线程的协同工作,对于日志记录来说,倘若采取传统的加锁机制访问我们的存储文件,这些线程将在获得和释放锁上花费了大部分的时间,所以采取循环缓冲区会是一个不错的办法。通过使得每个线程将数据写入到它自己的内存块,就可以完全避免同步问题。当收到来自用户的转储数据的请求时,每个线程获得一个锁,并将其转储到中心位置。或者分配一个很大的全局内存块,并将其划分为较小的槽位,其中每个槽位都可由一个线程用来进行日志记录。每个线程只能够读写它自己的槽位,而不是整个缓冲区。当每个线程第一次尝试写入数据时,它会尝试寻找一个空的内存槽位,并将其标记为忙碌。当线程获得了一个特定的槽位时,可以将跟踪槽位使用情况的位图中相应的位设置为1,当该线程退出时,重新将这个位设置为 0。在这里需要同时需要维护当前使用的槽位编号的全局列表,以及正在使用它的线程的线程信息。

       但是这里需要注意的是当一个线程已经死亡,却没有释放相应的槽位,并在垃圾收集器释放该槽位之前,再次使用了这个线程 ID 并为其分配一个新的槽位。对于新的线程来说,检查全局列表并且重用相同的槽位(如果以前的实例使用了它的话),这是非常重要的。因为垃圾收集器线程和写入者线程可能同时尝试修改全局列表,所以同样也需要使用某种锁定机制。

     

    展开全文
  • 循环缓冲区的定义

    千次阅读 2012-11-02 16:27:39
    /*  * See Documentation/circular-buffers.txt for more information.  */ #ifndef _LINUX_CIRC_BUF_H #define _LINUX_CIRC_BUF_H 1 struct circ_buf { char *buf; int head;.../

    <linux/circ_buf.h>


    /*
     * See Documentation/circular-buffers.txt for more information.
     */


    #ifndef _LINUX_CIRC_BUF_H
    #define _LINUX_CIRC_BUF_H 1


    struct circ_buf {
    char *buf;
    int head;
    int tail;
    };


    /* Return count in buffer.  */
    #define CIRC_CNT(head,tail,size) (((head) - (tail)) & ((size)-1))


    /* Return space available, 0..size-1.  We always leave one free char
       as a completely full buffer has head == tail, which is the same as
       empty.  */
    #define CIRC_SPACE(head,tail,size) CIRC_CNT((tail),((head)+1),(size))


    /* Return count up to the end of the buffer.  Carefully avoid
       accessing head and tail more than once, so they can change
       underneath us without returning inconsistent results.  */
    #define CIRC_CNT_TO_END(head,tail,size) \
    ({int end = (size) - (tail); \
     int n = ((head) + end) & ((size)-1); \
     n < end ? n : end;})


    /* Return space available up to the end of the buffer.  */
    #define CIRC_SPACE_TO_END(head,tail,size) \
    ({int end = (size) - 1 - (head); \
     int n = (end + (tail)) & ((size)-1); \
     n <= end ? n : end+1;})


    #endif /* _LINUX_CIRC_BUF_H  */

    展开全文
  • 延迟:使用循环缓冲区插入延迟音频的概念证明。 用户界面允许用户动态改变干,湿信号,反馈水平和延迟时间之间的平衡。 第一个原型应该是合唱效果,镶边效果和其他类型延迟(例如乒乓延迟)的基础
  • 工作集、granule、缓冲区、缓冲池概念及关系? granule:为了让内存在db_chache_size和shared_pool_size之间高效的移动,oracle在9i重构SGA,使用固定大小的内存块即为granule。这个参数就是为什么当你分配给shared...
  • C++ Socket send recv 循环发送和接收 阻塞与缓冲区

    万次阅读 多人点赞 2018-02-24 16:59:51
    套接字的概念及分类 在网络中,要全局的标识一个参与通信的进程,需要三元组:协议,IP地址以及端口号。要描述两个应用进程之间的端到端的通信关联需要五元组:协议,信源主机IP,信源应用进程端口,信宿主机IP,...
  • getch getche getchar的区别和缓冲区概念

    万次阅读 多人点赞 2006-03-18 16:11:00
    getch getche getchar的区别和缓冲区概念 今天同学问我一个问题,.Net上编译C程序最后的结果总是一闪而过。记得有个函数能够实现其功能,于是分不清这几个函数之间的关系,总结一下。 1.输入输出缓冲区概念...
  • 1.输入输出缓冲区概念(C++用的多一些)  我想以一个例子说明,比如我想把一篇文章以字符序列的方式输出到计算机显示器屏幕上,那么我的程序内存作为数据源而显示器驱动程序作为数据目标,如果数据源直接对数据...
  • c语言输入输出缓冲区概念

    千次阅读 2009-05-27 12:27:00
    输入输出缓冲区概念 我想以一个例子说明,比如我想把一篇文章以字符序列的方式输出到计算机显示器屏幕上,那么我的程序内存作为数据源而显示器驱动程序作为数据目标,如果数据源直接对数据目标发送数据的话。...
  • (2)缓冲区的理解。 其他部分有时间重新整理。 套接字的概念及分类 在网络中,要全局的标识一个参与通信的进程,需要三元组:协议,IP地址以及端口号。要描述两个应用进程之间的端到端的通信关联需要五元组:...
  • 环形缓冲区

    千次阅读 2015-12-03 14:35:58
    环形缓冲区的基本概念环形缓冲区的基本概念来自Wikipedia:环形缓冲器圆形缓冲区(circular buffer),也称作圆形队列(circular queue),循环缓冲区(cyclic buffer),环形缓冲区(ring buffer),是一种用于表示...
  • getch getche getchar的区别和缓冲区概念  今天同学问我一个问题,.Net上编译C程序最后的结果总是一闪而过。记得有个函数能够实现其功能,于是分不清这几个函数之间的关系,总结一下。 1.输入输出缓冲区概念...
  • 键盘输入的字符都存到缓冲区内,一旦键入回车,getchar就进入缓冲区读取字符,一次只返回第一个字符作为getchar函数的值,如果有循环或足够多的getchar语句,就会依次读出缓冲区内的所有字符直到'/n'.要理解这一点,之所以...
  • getchar、scanf以及缓冲区概念

    万次阅读 多人点赞 2011-08-20 18:47:47
     键盘输入的字符都存到缓冲区内,一旦键入回车,getchar就进入缓冲区读取字符,一次只返回第一个字符作为getchar函数的值,如果有循环或足够多的getchar语句,就会依次读出缓冲区内的所有字符直到'\n '。...
  • 缓冲区

    千次阅读 2016-04-15 15:30:51
    缓冲区像前篇文章讨论的那样被写满和释放,对于每个非布尔原始数据类型都有一个缓冲区类,尽管缓冲区作用于它们存储的原始数据类型,但缓冲区十分倾向于处理字节,非字节缓冲区可以再后台执行从字节或到字节的转换,...
  • Cache:缓存,是高速缓存,是位于CPU和主内存之间的容量较小但速度很快的存储器,因为CPU的速度远远高于主内存的速度,CPU从内存中读取数据需等待很长的时间,而 Cache保存着CPU刚用过的数据或循环使用的部分数据...
  • STM32进阶之串口环形缓冲区实现

    千次阅读 多人点赞 2019-10-15 22:34:52
    文章目录队列的概念队列的特点队列的常见两种形式普通队列环形队列从队列到串口缓冲区的实现定义一个结构体:初始化写入环形缓冲区的代码实现:读取缓冲区的数据的代码实现:测试效果补充喜欢就关注我吧!...
  • [Linux]——文件缓冲区

    千次阅读 2019-05-25 14:39:46
    提到文件缓冲区这个概念我们好像并不陌生,但是我们对于这个概念好像又是模糊的存在脑海中,之间我们在介绍c语言文件操作已经简单的提过这个概念,今天我们不妨深入理解什么是文件缓冲区。 为什么需要文件缓冲区 当...
  • 环形缓冲区应用实例

    2020-02-25 21:14:20
    概念(来自维基百科):圆形缓冲区(circular buffer),也称作圆形队列(circular queue),循环缓冲区(cyclic buffer),环形缓冲区(ring buffer),是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,...
  • 这篇文章给出了我自己写的纯C语言面向对象开发的缓冲区模块
  • 直接缓冲区与非直接缓冲区概念: 1)非直接缓冲区:通过 static ByteBuffer allocate(int capacity) 创建的缓冲区,在JVM中内存中创建,在每次调用基础操作系统的一个本机IO之前或者之后,虚拟机都会将缓冲...
  • 上网搜索这个换行符究竟什么来头,查到了“缓冲区”这个概念 并说及时刷新缓冲区可以解决这个问题 一种跨平台的方法 getchar() #include int main() { float price_1=1.25,price_2=0.65,price_3=...
  • 环形缓冲器(ringr buffer),也称作圆形队列(circular queue),循环缓冲区(cyclic buffer),圆形缓冲区(circula buffer),是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。...
  • linux中页缓冲和块缓冲概念

    千次阅读 2016-04-27 22:41:01
    页缓冲在《linux内核情景分析》一书的第5.6节文件的写与读一章中说明的很详细,这里摘抄下来; 在文件系统层中有三隔主要的数据结构,file结构、...因此不能在file结构上设置缓冲区队列,因为这些file结构体之间都不共
  • 什么是缓冲区(buffer),什么是缓存(cache)

    千次阅读 多人点赞 2020-11-17 22:31:03
    比如我们从磁盘里取信息,我们先把读出的数据放在缓冲区,计算机再直接从缓冲区中取数据,等缓冲区的数据取完后再去磁盘中读取,这样就可以减少磁盘的读写次数,再加上计算机对缓冲区的操作大大快于对磁盘的操作,故...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,400
精华内容 26,960
关键字:

循环缓冲区的概念