【JUC进阶】12. 环形缓冲区

有一只柴犬

发布于 2024-01-25 10:49:32

6650

文章被收录于专栏：JUCJUC

1、前言

上一篇《【JUC进阶】11. BlockingQueue》中介绍到ArrayBlockingQueue，在物理上是一个数组，但在逻辑上来说是个环形结构。这就衍生出来我们今天要介绍的主题，环形缓冲区。

2、基本概述

2.1、什么是环形缓冲区

环形缓冲区（Circular Buffer）是一种数据结构，它允许我们在固定大小的缓冲区中高效地存储和读取数据。这种缓冲区通常用于处理流式数据，例如网络数据流或文件数据流。

他之所以被称为环形缓冲区，因为它循环存储数据。数据以 FIFO（先进先出）方式从缓冲区读取，这意味着首先读取最旧的数据。我们使用缓冲区在两点（例如生产者和消费者）之间存储和传输数据。

其大致结构如图：

循环缓冲区有一个指针指向缓冲区的下一个空位置，并且我们随着每个新条目递增该指针。这意味着当缓冲区已满时，我们添加一个新元素，它会覆盖最旧的元素。这可以确保缓冲区不会溢出，并且新数据不会覆盖重要数据。当缓冲区已满时，循环缓冲区不需要移动元素来为新数据腾出空间。

相反，当缓冲区已满时，新数据将覆盖最旧的数据。将元素添加到循环缓冲区的时间复杂度是常数 O(1)。这使得它在我们必须快速添加和删除数据的实时系统中非常高效。

2.2、结构刨析

循环缓冲区有两个指针，一个指向缓冲区的头部（head），另一个指向缓冲区的尾部（tail）。头指针指向我们将插入下一个元素的位置，尾指针指向缓冲区中最旧元素的位置。

当头指针和尾指针相遇时，我们认为缓冲区已满。实现循环缓冲区的一种方法是使用带有模运算符的数组，当到达数组末尾时进行回绕：

2.3、优点

节省内存：环形缓冲区可以循环使用，因此不需要一直分配固定大小的内存空间。当缓冲区已满时，新的数据将覆盖最早的数据，从而减少了内存的占用。这对于处理大量数据或者有限的内存资源非常重要。
高性能：环形缓冲区可以提高数据读取和写入的效率。由于数据在缓冲区中是循环存储的，读/写指针只需要不断移动，而不需要频繁地分配和释放内存。这使得环形缓冲区非常适合处理高速数据流，例如网络传输或实时数据处理。
适用于并发场景：环形缓冲区可以支持多个读者和写者同时访问。当多个线程需要同时读取或写入数据时，可以通过互斥锁或其他同步机制来确保数据的正确性和一致性。这使得环形缓冲区非常适合并发处理和多线程编程。

2.4、缺点

数据覆盖：当缓冲区已满时，新的数据将覆盖最早的数据，这可能导致数据丢失或重要信息被覆盖。在某些应用场景下，这种数据覆盖可能会导致问题，需要特别注意。
数据不一致：由于环形缓冲区的特性，数据的读取和写入是循环进行的，这可能会导致数据的不一致性。例如，当多个线程同时读取和写入数据时，可能会出现数据冲突或数据错乱的情况。
难以扩展：环形缓冲区的容量是固定的，无法动态扩展。当缓冲区已满时，如果需要处理更多的数据，必须重新分配更大的内存空间，这可能会导致性能下降或内存占用增加的问题。
指针管理复杂：由于环形缓冲区的特殊性质，读/写指针需要特殊管理，以确保数据的正确性和一致性。这可能会增加代码的复杂度，并引入潜在的错误风险。
并发控制开销：在多线程环境下，环形缓冲区需要使用同步机制（如互斥锁）来保护数据的读取和写入操作。这可能会导致并发控制开销增加，并可能降低系统的性能。

3、如何使用

3.1、定义一个环形缓冲区

/**
 * @author Shamee loop
 * @date 2023/7/11
 */
public class CircularBuffer {
    private int[] buffer;
    // 头部指针
    private int head;
    // 尾部指针
    private int tail;
    private int size;
    // 初始容量
    private int capacity;

    public CircularBuffer(int capacity) {
        this.capacity = capacity;
        buffer = new int[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 向缓冲区中添加数据，如果满了则覆盖
     * @param value
     */
    public synchronized void push(int value) {
        if (size == capacity) {
            // 缓冲区已满，覆盖最早的数据
            head = (head + 1) % capacity;
        }
        buffer[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
    }


    /**
     * 向缓冲区中弹出数据，如果空了，则抛出异常
     * @return
     */
    public synchronized int pop() {
        if (size == 0) {
            throw new NoSuchElementException("Buffer is empty");
        }
        int value = buffer[head];
        head = (head + 1) % capacity;
        size--;
        return value;
    }

    /**
     * 获取缓冲区中第一个数据，但不会弹出数据
     * @return
     */
    public synchronized int peek() {
        if (size == 0) {
            throw new NoSuchElementException("Buffer is empty");
        }
        return buffer[head];
    }

    /**
     * 判断缓冲区是否空了
     * @return
     */
    public synchronized boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断缓冲区是否满了
     * @return
     */
    public synchronized boolean isFull() {
        return size == capacity;
    }
}

3.2、Demo使用

public static void main(String[] args) {
    CircularBuffer buffer = new CircularBuffer(5);
    for (int i = 0; i < 10; i++) {
        buffer.push(i);
    }
    for (int i = 0; i < 10; i++) {
        int value = buffer.pop();
        System.out.println("Received value: " + value);
    }
}

输出结果：