c++ - 用原子做饱和运算

Question

我一直在寻找一种方法来保护整数以原子方式递增但并进行边界检查。我四处寻找其他帖子，但似乎都没有好的解决方案(有些是 C++11 之前的帖子)。

我需要的是像下面这样的库:

class bounded_atomic_uint
{
    private:
    uint32_t ctr;
    uint32_t max;
    mutex mtx;

    public:
    bounded_atomic_uint(uint32_t max = UINT32_MAX) : ctr(0), max(max) {}
    ~bounded_atomic_uint() = default;
    // make in uncopyable and un-movable
    bounded_atomic_uint(bounded_atomic_uint&&) = delete;
    bounded_atomic_uint& operator=(bounded_atomic_uint&&) = delete;

    bool inc();
    bool dec();
    uint32_t get();
};

bool bounded_atomic_uint::inc() {
    lock_guard<mutex> lck (mtx);
    if (ctr < max) {
        ctr++;
        return true;
    }
    else
    {
        cout << "max reached (" << max << ")" << endl; // to be removed!
        return false; // reached max value
    }
}

bool bounded_atomic_uint::dec() {
    lock_guard<mutex> lck (mtx);
    if (ctr > 0) {
        ctr--;
        return true;
    }
    else {
        cout << "min reached (0)" << endl; // to be removed!
        return false; // reached min value
    }
}

uint32_t bounded_atomic_uint::get() {
    lock_guard<mutex> lck (mtx);
    return ctr;
}

像这样使用:

#include <iostream>
#include <mutex>
#include <cstdint>

using namespace std;

int main() {

    bounded_atomic_uint val(3);

    if (val.dec())
        cout << "error: dec from 0 succeeded !!" << endl;
    cout << val.get() << endl; // make sure it prints 0
    val.inc();
    val.inc();
    cout << val.get() << endl;
    if (!val.inc())
        cout << "error: havent reached max but failed!!" << endl;

    if (val.inc())
        cout << "error max not detected!!" << endl;

    cout << val.get() << endl;

    return 0;
}

有没有更简单(或更正确)的方法来做到这一点？std::atomic 和 boost::atomic 似乎都没有办法避免出界检查(在锁内)。

如果不是，这个简单类是否足够好？还是我在这里遗漏了什么？

注意库中的couts将在实际使用时被删除!

Answer 1

您问题的这一部分有图书馆吗 is off-topic ，所以让我来回答“我们如何实现”这个问题，这个问题很切题，也很有趣。

让我们首先从您的示例中删除锁并将普通 int 替换为 atomics :

class bounded_atomic_uint
{
    private:
    atomic<uint32_t> ctr;
    uint32_t max;

    public:
    bounded_atomic_uint(uint32_t max = UINT32_MAX) : ctr(0), max(max) {}
    ~bounded_atomic_uint() = default;
    // make in uncopyable and un-movable
    bounded_atomic_uint(bounded_atomic_uint&&) = delete;
    bounded_atomic_uint& operator=(bounded_atomic_uint&&) = delete;

    bool inc();
    bool dec();
    uint32_t get();
};

bool bounded_atomic_uint::inc() {
    if (ctr < max) {
        ctr++;
        return true;
    }
    else
    {
        cout << "max reached (" << max << ")" << endl; // to be removed!
        return false; // reached max value
    }
}

此代码的问题在于，在边界检查和增量之间，值可能已更改。所以只能保证在没有争用的情况下不越界。

您可以通过确保值在增量之间没有变化来轻松解决此问题。这正是compare_exchange提供:

bool bounded_atomic_uint::inc() {
    while(true) {
        auto ctr_old = ctr.load();
        if (ctr_old < max) {
            if(ctr.compare_exchange_weak(ctr_old, ctr_old + 1)) {
                return true;
            }
        }
        else
        {
            cout << "max reached (" << max << ")" << endl; // to be removed!
            return false; // reached max value
        }
    }
}

现在如果计数器在边界检查和增量写入之间发生变化，compare_exchange_weak 将失败，因此我们必须重试。如果在此期间数字超出了界限，我们将在下一次循环迭代中检测到这一点并相应地退出。请注意，如果您忽略 compare_exchange 的虚假故障*，则只有在对原子进行实际并发写入时才需要循环，因此此实现实际上是 lock-free .

我们可以通过将原子的重复加载分解为 compare_exchange 来稍微提高效率(记住 compare_exchange 将原子的实际值写回到第一个参数):

bool bounded_atomic_uint::inc() {
    auto ctr_old = ctr.load();
    do {
        if (ctr_old >= max) {
            cout << "max reached (" << max << ")" << endl; // to be removed!
            return false; // reached max value
        }
    } while(!ctr.compare_exchange_weak(ctr_old, ctr_old + 1));
    return true;
}

_{*我们可以通过使用 compare_exchange_strong 来消除虚假的失败，但由于无论如何我们都必须循环，所以实际上没有充分的理由在这里这样做。}