没有优先级反转的环形缓冲区

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

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（）中的数学或更新为结束不是原子，引入了一个错误。

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

我可能能够使用原子操作工作，但我不知道有一个很好的跨平台库提供这些。

是否有避免这些问题的标准环形缓冲设计？

来源

2011-04-21 user168715

提供了跨平台的原子功能是否有在平台上的任何约束的使用？ – 2011-04-21 16:39:20

@Peter让我们假设x86（其中IIRC 32位写入对齐的地址是原子的），尽管越便携越好。 – user168715 2011-04-21 17:22:36

这里是一个等待免费的队列http://software.intel.com/zh-cn/articles/single-producer-single-consumer-queue/ – 2011-04-21 20:41:16

你应该确定什么，只要你坚持以下原则：

只有一个线程可以执行写操作。
只有一个线程可以读取。
更新和访问start和end是原子。这可能是自动的，例如微软指出：

简单的读取和写入正确对齐的32位变量原子操作。换句话说，你的不会最终只有一个部分的变量更新;所有位以原子方式更新为。

您允许的事实，count可能是过时的，即使你得到的价值。在读线程中，count会返回最小值您可以依赖的值;对于写作线程count将返回最大计数和真实计数可能会更低。

来源

2011-04-21 16:11:47

是否有编译器将更新分为非原子序列的步骤？也就是说，将write（）的最后一行变成'end + = bytes;结束％=大小;'？ – user168715 2011-04-21 16:19:41

编译器可以非原子方式计算RHS，并且根据您的平台甚至可以非原子方式存储int（即，在8位平台上使用两个8位写入来存储16位整数）。 – 2011-04-21 16:52:56

@ user168715，如果你绝对不相信你的编译器做正确的事情，那么创建一个'volatile'临时变量来保存计算，然后复制它以进行更新。 – 2011-04-21 18:22:37

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

即将到来的C++标准将原子操作添加到标准库中，所以它们将在未来可用，但大多数实现还不支持它们。

我没有看到任何跨平台的解决方案来保持count同时保持两个线程都写入它，除非你实现锁定。

通常情况下，您可能会使用消息传递系统并强制低优先级线程请求高优先级线程进行更新或类似的操作。例如，如果低优先级线程消耗15个字节，它应该请求高优先级线程将计数减少15.

本质上，您将限制对高优先级线程的“写入”访问，并且只允许低优先级线程读取。这样，您可以避免所有锁定，并且高优先级线程不必担心等待写入由底层线程完成，从而使高优先级线程真正具有高优先级。

来源

2011-04-21 16:16:45

boost::interprocess在boost/interprocess/detail/atomic.hpp

来源

2011-04-21 16:25:43

没有优先级反转的环形缓冲区

回答

相关问题