[数据结构-1]：环形buffer以及读写同步

目录

一、什么是环形buffer

二、环形buffer的优点与使用场合

三、环节buffer的读写同步

3.1 基本原理

3.2 代码示例

---

一、什么是环形buffer

环形缓冲区（Circular Buffer）也被称为环形队列（Circular Queue）或循环缓冲区，是一种数据结构，用于在固定大小的缓冲区中存储和处理数据。

环形缓冲区的特点是首尾相连，即缓冲区的最后一个元素和第一个元素相邻。当缓冲区写满时，新数据可以覆盖旧数据，实现循环利用。

环形缓冲区常见的应用场景是数据流处理，例如音频、视频、网络通信等。它具有以下优点：

1. 内存利用率高：由于循环利用，不会浪费内存空间。
2. 读写效率高：读写指针移动固定步长，无需频繁移动指针或进行数据搬移操作。
3. 简单且高效：相比其他数据结构，环形缓冲区操作简单，性能高。

环形缓冲区的实现通常需要两个指针，表示读和写的位置。读指针用于提取数据，写指针用于写入数据。同时，还需要记录缓冲区的大小和当前数据元素的数量。

通过合理管理读写指针和计数信息，可以实现有效的数据读写和同步，避免数据溢出和读写冲突的问题。

二、环形buffer的优点与使用场合

环形缓冲区（Circular Buffer）具有以下优点和适用场合：

优点：

1. 内存利用率高：环形缓冲区能够循环利用缓冲区的空间，不会浪费内存。当缓冲区写满时，新的数据可以覆盖旧的数据，避免了频繁地分配和释放内存空间的开销。
2. 读写效率高：环形缓冲区的读写操作只涉及指针的移动，不需要进行元素的搬移或内存复制，因此读写效率较高。读写指针以固定步长移动，无需频繁更新指针位置，特别适用于实时数据的处理。
3. 简单且高效：相比其他数据结构，环形缓冲区的实现较为简单，并且具有较高的性能。它不需要复杂的内存管理或链表操作，可以快速读写数据。

使用场合：

1. 数据流处理：环形缓冲区常用于处理连续的数据流，例如音频、视频、传感器数据等。通过循环利用缓冲区的空间，可实现高效的数据流存储以及快速的读取和处理。
2. 缓冲数据传输：环形缓冲区可以用于缓冲数据的传输，特别是在生产者和消费者之间的数据传输场景。通过缓冲区，可以平衡生产者和消费者的速度差异，避免数据丢失或阻塞。
3. 数据采样和循环记录：环形缓冲区适用于需要采样和记录连续数据的应用。例如嵌入式系统中的数据采集、实时监控系统中的历史数据记录等。
4. 实时任务调度：在实时任务调度中，环形缓冲区可用于存储任务队列。任务按照优先级或时间顺序排列，通过环形缓冲区的循环读取，可以高效地完成实时任务的调度和执行。

总之，环形缓冲区适用于需要循环读写、高效利用内存和处理连续数据的场景，可以提高数据处理的效率和性能。

三、环节buffer的读写同步

3.1 基本原理

在环形buffer中，读和写的同步通常可以通过使用信号量来实现。环形buffer的同步通常需要维护两个指针：read_index和write_index，分别表示当前读取到的位置和下一个写入的位置。

读取操作需要获取已经写入的数据，因此需要等待直到有数据可用。这可以通过一个信号量来实现，信号量的值初始化为0，并在写操作完成时加1。每次读取操作首先尝试获取信号量，如果信号量的值<=0，则表示没有数据可用，需要等待。当信号量的值>0时，读取操作将从环形buffer中读取数据，更新read_index指针，并将信号量的值减1。

写入操作也需要同步，因为当buffer写满后就不能再写入新的数据了。写入操作同样需要使用一个信号量，该信号量的值初始化为buffer的大小，并在读取操作完成时加1。每次写入操作首先尝试获取信号量，如果信号量的值<=0，则表示buffer已经写满，需要等待。当信号量的值>0时，写入操作将写入数据到环形buffer中，更新write_index指针，并将信号量的值减1。

这样，通过使用信号量，可以实现环形buffer的读和写的同步，避免了读写的冲突，以及buffer写满和读取空buffer的情况。

3.2 代码示例

以下是一个简单的C++代码示例，展示了如何在环形缓冲区中实现读和写的同步：

#include <iostream>
using namespace std;

const int BUFFER_SIZE = 10;

class CircularBuffer {
private:
  int buffer[BUFFER_SIZE];
  int readIndex;
  int writeIndex;
  int itemCount;

public:
  CircularBuffer() {
    readIndex = 0;
    writeIndex = 0;
    itemCount = 0;
  }

  bool isEmpty() {
    return (itemCount == 0);
  }

  bool isFull() {
    return (itemCount == BUFFER_SIZE);
  }

  void write(int data) {
    if (isFull()) {
      cout << "Buffer is full. Cannot write data." << endl;
      return;
    }

    buffer[writeIndex] = data;
    writeIndex = (writeIndex + 1) % BUFFER_SIZE;
    itemCount++;
    cout << "Data " << data << " has been written to buffer." << endl;
  }

  int read() {
    if (isEmpty()) {
      cout << "Buffer is empty. Cannot read data." << endl;
      return -1; // or any other suitable error value
    }

    int data = buffer[readIndex];
    readIndex = (readIndex + 1) % BUFFER_SIZE;
    itemCount--;
    cout << "Data " << data << " has been read from buffer." << endl;
    return data;
  }
};

int main() {
  CircularBuffer buffer;

  buffer.write(1);
  buffer.write(2);
  buffer.write(3);

  buffer.read();
  buffer.read();
  buffer.read();

  return 0;
}

在上面的示例中，CircularBuffer类表示环形缓冲区，其构造函数初始化了读写指针和计数项。isEmpty()和isFull()函数分别用于检查缓冲区是否为空和是否已满。

write(int data)函数用于将数据写入缓冲区，它先检查缓冲区是否已满，若已满则输出错误信息。若缓冲区未满，则将数据写入缓冲区，同时更新写指针和计数项。

read()函数用于从缓冲区读取数据，它先检查缓冲区是否为空，若为空则输出错误信息，并返回适当的错误值。若缓冲区非空，则读取数据到变量中，同时更新读指针和计数项。

在主函数中创建了一个CircularBuffer对象，并进行了几次写入和读取操作，以展示缓冲区的同步行为。

请注意，该示例是一个简要的示例，实际应用中可能需要更多的同步保证和错误处理机制来处理并发访问和异常情况。

3.3?环形buffer如何通过信号量实现读和写的同步, C++代码示例

要实现环形缓冲区的读和写的同步，你可以使用两个信号量来管理缓冲区的满和空状态。一个信号量用于表示缓冲区是否满，另一个信号量用于表示缓冲区是否空。下面是使用信号量实现读和写同步的C++代码示例：

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
using namespace std;

const int BUFFER_SIZE = 10;

class CircularBuffer {
private:
  int buffer[BUFFER_SIZE];
  int readIndex;
  int writeIndex;
  int itemCount;
  
  mutex mtx;
  condition_variable bufferFull;
  condition_variable bufferEmpty;

public:
  CircularBuffer() {
    readIndex = 0;
    writeIndex = 0;
    itemCount = 0;
  }

  bool isEmpty() {
    return (itemCount == 0);
  }

  bool isFull() {
    return (itemCount == BUFFER_SIZE);
  }

  void write(int data) {
    unique_lock<mutex> lock(mtx);
    bufferFull.wait(lock, [this] { return !isFull(); });

    buffer[writeIndex] = data;
    writeIndex = (writeIndex + 1) % BUFFER_SIZE;
    itemCount++;
    cout << "Data " << data << " has been written to buffer." << endl;

    lock.unlock();
    bufferEmpty.notify_one();
  }

  int read() {
    unique_lock<mutex> lock(mtx);
    bufferEmpty.wait(lock, [this] { return !isEmpty(); });

    int data = buffer[readIndex];
    readIndex = (readIndex + 1) % BUFFER_SIZE;
    itemCount--;
    cout << "Data " << data << " has been read from buffer." << endl;

    lock.unlock();
    bufferFull.notify_one();

    return data;
  }
};

int main() {
  CircularBuffer buffer;

  thread writer([&buffer]() {
    for (int i = 1; i <= 5; i++) {
      buffer.write(i);
      this_thread::sleep_for(chrono::milliseconds(500));
    }
  });

  thread reader([&buffer]() {
    for (int i = 1; i <= 5; i++) {
      buffer.read();
      this_thread::sleep_for(chrono::seconds(1));
    }
  });

  writer.join();
  reader.join();

  return 0;
}

在上述代码中，CircularBuffer类与之前的示例代码类似。在类中添加了互斥锁（mutex）mtx和条件变量（condition variable）bufferFull、bufferEmpty。mtx用于保护共享资源的互斥访问，bufferFull和bufferEmpty用于在读写操作中进行等待和唤醒的同步。

在write(int data)和read()函数中，使用unique_lock来管理互斥锁。在写入操作中，调用bufferFull.wait()来等待缓冲区非满的条件满足，然后执行写入操作。在读取操作中，调用bufferEmpty.wait()来等待缓冲区非空的条件满足，然后执行读取操作。

当写入或读取操作完成后，通过调用bufferEmpty.notify_one()或bufferFull.notify_one()来唤醒等待的线程。

在主函数中创建了一个writer线程和一个reader线程，并分别模拟了写入和读取操作。使用chrono库来控制线程的睡眠时间，以展示读写操作的同步行为。

需要注意的是，上述代码仅提供了一个简单的示例，实际应用中可能需要更多的同步保证和错误处理机制，以及对信号量的正确使用和释放。