无优先级倒置的环形缓冲区

Question

我有一个高优先级进程需要向低优先级进程传递数据。我编写了一个基本的环形缓冲区来处理数据传递：

class RingBuffer {
  public:
    RingBuffer(int size);
    ~RingBuffer();

    int count() {return (size + end - start) % size;}

    void write(char *data, int bytes) {
      // some work that uses only buffer and end
      end = (end + bytes) % size;
    }

    void read(char *data, int bytes) {
      // some work that uses only buffer and start
      start = (start + bytes) % size;
    }

  private:
    char *buffer;
    const int size;
    int start, end;
};

这里有一个问题。假设低优先级进程有一个 oracle，可以准确地告诉它需要读取多少数据，以便不必调用 count()。那么（除非我漏掉了什么），就没有并发问题。然而，一旦低优先级线程需要调用 count()（高优先级线程可能也想调用它来检查缓冲区是否已满），就有可能导致 count() 函数中的数学运算或对 end 的更新不是原子操作，从而引入漏洞。

我可以在对 start 和 end 的访问周围放置一个互斥锁，但如果高优先级线程必须等待低优先级线程获取的锁，则会导致优先级反转。

我可能可以使用原子操作来解决这个问题，但我不知道是否有一个很好的、跨平台的库可以提供这些操作。

是否有一个标准的环形缓冲区设计可以避免这些问题？

- user168715

---

你对使用的平台有任何限制吗？ - Peter G.

@Peter 假设使用x86（在此情况下，我记得32位对齐地址的写入是原子性的），尽管越便携越好。 - user168715

这里有一个操作大部分时间无需等待的队列：http://software.intel.com/en-us/articles/single-producer-single-consumer-queue/ - Peter G.

Answer 1

你所拥有的应该是可以的，只要你遵守以下准则：

• 只有一个线程可以进行写操作。
• 只有一个线程可以进行读取操作。
• 对 start 和 end 的更新和访问是原子性的。这可能是自动的，例如 Microsoft 表示：

对于正确对齐的 32 位变量，简单的读写操作是原子操作。换句话说，在原子方式下，所有位都会被更新，而不仅仅是变量的某一部分。

• 即使在获取值时，你也需要考虑到 count 可能已经过时了。对于读取线程，count 将返回你可以依赖的 最小 计数；对于写入线程，count 将返回 最大 计数，真实计数可能会更低。

- Mark Ransom

---

编译器会不会将更新操作拆分成非原子序列的步骤？例如，将write()的最后一行转换为end += bytes; end %= size;？ - user168715

编译器可以非原子地计算RHS，根据您的平台，甚至可能以非原子方式存储int（即在8位平台上使用两个8位写入来存储16位int）。 - Peter G.

@user168715，如果您绝对不信任编译器能够正确处理计算，请创建一个volatile临时变量来保存计算结果，然后将其复制以进行更新。 - Mark Ransom

Answer 2

Boost提供了循环缓冲，但它不是线程安全的。不幸的是，我不知道有任何实现是线程安全的。

即将发布的C++标准将原子操作加入标准库，因此它们将来会可用，但目前大多数实现不支持它们。

我没有看到任何跨平台的解决方案来保持在两个线程同时写入时 "count" 的正确性，除非您实现锁定。

通常，您可能会使用消息系统，并强制低优先级线程请求高优先级线程进行更新，或者采取类似的措施。例如，如果低优先级线程消耗了15个字节，则应要求高优先级线程将计数减少15。

基本上，您将限制对高优先级线程的“写”访问，并仅允许低优先级线程进行读取。这样，您可以避免所有锁定，并且高优先级线程无需担心等待较低线程完成写入，使高优先级线程真正成为高优先级。

- Collin Dauphinee

Answer 3

boost::interprocess 在 boost/interprocess/detail/atomic.hpp 中提供了跨平台的原子函数。

- Khaled Nassar