为什么要有环形缓冲器

当有大量数据的时候，我们不能存储所有的数据，那么计算机处理数据的时候，只能先处理先来的，那么处理完后呢，就会把数据释放掉，再处理下一个。那么，已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队，如果要将剩余的数据都往前移动一次，那么效率就会低下了，肯定不现实，所以，环形队列就出现了。

频繁的内存分配不但增加了系统开销，更使得内存碎片不断增多，非常不利于我们的服务器长期稳定运行。也许我们可以使用内存池，比如SGI STL中附带的小内存分配器。但是对于这种按照严格的先进先出顺序处理的，块大小并不算小的，而且块大小也并不统一的内存分配情况来说，更多使用的是一种叫做环形缓冲区的方案。

image.png
image.png
image.png

区分缓冲区是否为满的策略

1.总是保持一个存储单元为空

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

2.使用数据计数

这种策略不使用显式的写指针，而是保持着缓冲区内存储的数据的计数。因此测试缓冲区是空是满非常简单；对性能影响可以忽略。缺点是读写操作都需要修改这个存储数据计数，对于多线程访问缓冲区需要并发控制。

3.镜像指示位

缓冲区的长度如果是n，逻辑地址空间则为0至n-1；那么，规定n至2n-1为镜像逻辑地址空间。本策略规定读写指针的地址空间为0至2n-1，其中低半部分对应于常规的逻辑地址空间，高半部分对应于镜像逻辑地址空间。当指针值大于等于2n时，使其折返（wrapped）到ptr-2n。使用一位表示写指针或读指针是否进入了虚拟的镜像存储区：置位表示进入，不置位表示没进入还在基本存储区。
在读写指针的值相同情况下，如果二者的指示位相同，说明缓冲区为空；如果二者的指示位不同，说明缓冲区为满。这种方法优点是测试缓冲区满/空很简单；不需要做取余数操作；读写线程可以分别设计专用算法策略，能实现精致的并发控制。 缺点是读写指针各需要额外的一位作为指示位。
这种方法的逻辑是，如果写指针超出了读指针n位，在普通情况下，读写指针重合，但在这种情况下，写指针在镜像空间的读指针+n位，不和读指针重合

如果缓冲区长度是2的幂，则本方法可以省略镜像指示位。如果读写指针的值相等，则缓冲区为空；如果读写指针相差n，则缓冲区为满，这可以用条件表达式（写指针 == (读指针 异或 缓冲区长度)）来判断。

示例：

public class RingBuffer {
    /**
     * ringBuffer的总长度，最大能够存储的成员数
     */
    private int length;

    /**
     * ringBuffer内部存储的现有的成员数
     */
    private int size;

    /**
     * 写指针,代表下一次操作执行的位置
     */
    private int writePos;

    /**
     * 读指针,代表下一次操作执行的位置
     */
    private int readPos;

    /**
     * 放置成员的循环数组，长度为length
     */
    private Object[] list;


    /**ringBuffer的构造函数<br>
     * 初始化各种参数和object数组
     * @param length  ringBuffer的总长度，最大能够存储的成员数
     */
    public RingBuffer(int length){
        this.length=length;
        list=new Object[length];
        size=0;
        writePos=0;
        readPos=0;
    }

    /**显示ringBuffer已满，是否还能插入新的元素
     * @return 如果数组已满，不能插入，返回true<br>如果能插入，返回false
     */
    public boolean isFull(){
        if(size==length){
            return true;
        }
        return false;
    }

    /**显示ringBuffer是否为空，是否还能取出元素
     * @return 如果数组为空，不能取出元素，返回true <br> 如果能取出，返回false
     */
    public boolean isEmpty(){
        if(size==0){
            return true;
        }
        return false;
    }

    /**在ringBuffer中插入一个元素，在写指针处插入元素
     * @param object  被插入的元素
     * @return 如果成功插入，返回true<br> 如果队列已满，返回false
     */
    public boolean put(Object object){
        if(isFull()){
            //如果队列已满
            return false;
        }
        if(writePos==length-1){
            //如果这次写入的位置在队列的最后一个元素
            list[writePos]=object;
            //那么下次写入的位置为0
            writePos=0;
        }
        else{
            //这次写入的位置不是队列最后一个元素，那么现在writePos处写入，然后++
            list[writePos++]=object;
        }
        //ringBuffer中的成员数增加
        //size的处理在最后操作，防止size增加了，读操作却没有读到
        size++;
        return true;
    }

    /**从ringBuffer中取出一个元素
     * @return 如果队列为空，返回null <br> 否则，返回读指针对应的元素
     */
    public Object take(){
        if(isEmpty()){
            return null;
        }
        Object result;
        if(readPos==length-1){
            //如果这次取出的位置在队列的最后一个元素
            result=list[readPos];
            //将对于位置的元素清空
            list[readPos]=null;
            readPos=0;
        }
        else{
            result=list[readPos];
            list[readPos++]=null;
        }

        size--;
        return result;
    }

    public void printRingBuffer(){
        System.out.println("开始打印环形缓冲区");
        System.out.println("length=" + length + ", size=" + size + ", writePos=" + writePos + ", readPos=" + readPos);
        for(int i=0;i<length;i++){
            System.out.println("区域位置坐标:"+i+"  :"+list[i]);
        }
        System.out.println("打印环形缓冲区结束");
        System.out.println();
    }
}

public class test {
    public static void main(String[] args) {
        RingBuffer ringBuffer=new RingBuffer(5);
        ringBuffer.put("0");
        ringBuffer.put("1");
        ringBuffer.put("2");
        ringBuffer.put("3");
        ringBuffer.put("4");
        ringBuffer.put("5");
        ringBuffer.take();
        ringBuffer.take();
        ringBuffer.put("5");
        ringBuffer.printRingBuffer();
        ringBuffer.take();
        ringBuffer.take();
        ringBuffer.take();
        ringBuffer.take();
        ringBuffer.take();
        ringBuffer.printRingBuffer();
        ringBuffer.put("5");
        ringBuffer.printRingBuffer();
    }
}