c++ - Lamport's Bakery Algorithm中如何绑定并制作唯一的票值？互斥体，C++

Question

社区。我已经搜索了一段时间，但没有找到任何针对Lamport 面包店算法的优化，以确保每个线程的唯一票值并将这些值限制在某个范围内。

换句话说，存在一个限制票值的黑白面包店算法，但如何优化它以确保它们是唯一的？或者我可以用原子变量（fetch_add 操作）编写解决方案，从而使票证值唯一，但是如何限制这个变量或者在什么情况下应该删除它？

下面是为每个线程提供唯一票证的代码。请帮助我通过应用一些减少操作来绑定这个 _ticket_counter 或给出任何想法，链接一个合适的算法。

extern const int NUM_THREADS;

class ImprovedBakeryLock : public Lockable {
public:
    ImprovedBakeryLock();
    ~ImprovedBakeryLock();
    void lock(int i) override;
    bool try_lock(int i) override;
    void unlock(int i) override;
private:
    std::atomic<uint64_t> _ticket_counter;
    volatile uint64_t* _token;
    const int _n;
};
ImprovedBakeryLock::ImprovedBakeryLock() :
    _n(NUM_THREADS), _ticket_counter(1)
{
    _token = new uint64_t[_n];
    memset((void*)_token, 0, _n * sizeof(uint64_t));
}
void ImprovedBakeryLock::lock(int num)
{
    _token[num] = _ticket_counter.fetch_add(1, std::memory_order_relaxed);

    for (int j = 0; j < _n; ++j) {
        while (_token[j] != 0 && _token[j] < _token[num])
            std::this_thread::yield();
    }
}
bool ImprovedBakeryLock::try_lock(int num)
{
    _token[num] = _ticket_counter.fetch_add(1, std::memory_order_relaxed);
    bool acquired = true;
    for (int j = 0; j < _n && acquired; ++j) {
        if (_token[j] != 0 && _token[j] < _token[num]) {
            acquired = false;
            _token[num] = 0;
        }
    }
    return acquired;
}
void ImprovedBakeryLock::unlock(int num)
{
    _token[num] = 0;
}

标签： c++mutexmutual-exclusion