寻找对我的线程安全、无锁队列实现的批评

Looking for critique of my thread safe, lock-free queue implementation(寻找对我的线程安全、无锁队列实现的批评)

问题描述

所以，经过一番研究，我写了一个队列.它使用固定大小的缓冲区，因此它是一个循环队列.它必须是线程安全的，我试图让它无锁.我想知道它有什么问题，因为这些事情我自己很难预测.

So, I've written a queue, after a bit of research. It uses a fixed-size buffer, so it's a circular queue. It has to be thread-safe, and I've tried to make it lock-free. I'd like to know what's wrong with it, because these kinds of things are difficult to predict on my own.

这是标题:

template <class T>
class LockFreeQueue
{
public:
    LockFreeQueue(uint buffersize) : buffer(NULL), ifront1(0), ifront2(0), iback1(0), iback2(0), size(buffersize) { buffer = new atomic <T>[buffersize]; }
    ~LockFreeQueue(void) { if (buffer) delete[] buffer; }

    bool pop(T* output);
    bool push(T input);

private:
    uint incr(const uint val)
        {return (val + 1) % size;}

    atomic <T>* buffer;
    atomic <uint> ifront1, ifront2, iback1, iback2;
    uint size;
};

下面是实现:

template <class T>
bool LockFreeQueue<T>::pop(T* output)
{
    while (true)
    {
        /* Fetch ifront and store it in i. */
        uint i = ifront1;

        /* If ifront == iback, the queue is empty. */
        if (i == iback2)
            return false;

        /* If i still equals ifront, increment ifront, */
        /* Incrememnting ifront1 notifies pop() that it can read the next element. */
        if (ifront1.compare_exchange_weak(i, incr(i)))
        {
            /* then fetch the output. */
            *output = buffer[i];
            /* Incrememnting ifront2 notifies push() that it's safe to write. */
            ++ifront2;
            return true;
        }

        /* If i no longer equals ifront, we loop around and try again. */
    }
}

template <class T>
bool LockFreeQueue<T>::push(T input)
{
    while (true)
    {
        /* Fetch iback and store it in i. */
        uint i = iback1;

        /* If ifront == (iback +1), the queue is full. */
        if (ifront2 == incr(i))
            return false;

        /* If i still equals iback, increment iback, */
        /* Incrememnting iback1 notifies push() that it can write a new element. */
        if (iback1.compare_exchange_weak(i, incr(i)))
        {
            /* then store the input. */
            buffer[i] = input;
            /* Incrementing iback2 notifies pop() that it's safe to read. */
            ++iback2;
            return true;
        }

        /* If i no longer equals iback, we loop around and try again. */
    }
}

我根据评论对代码进行了一些重大修改(感谢 KillianDS 和 n.m.！).最重要的是，ifront 和 iback 现在是 ifront1、ifront2、iback1 和 iback2.push() 现在将递增 iback1，通知其他推送线程他们可以安全地写入下一个元素(只要它未满)，写入元素，然后递增 iback2.iback2 是 pop() 检查的所有内容.pop() 做同样的事情，但使用 ifrontn 索引.

I made some major modifications to the code, based on comments (Thanks KillianDS and n.m.!). Most importantly, ifront and iback are now ifront1, ifront2, iback1, and iback2. push() will now increment iback1, notifying other pushing threads that they can safely write to the next element (as long as it's not full), write the element, then increment iback2. iback2 is all that gets checked by pop(). pop() does the same thing, but with the ifrontn indices.

现在，我又一次陷入了这应该工作......"的陷阱，但我对形式证明或类似的东西一无所知.至少这一次，我想不出它可能会失败的潜在方式.任何建议都值得赞赏，除了停止尝试编写无锁代码".

Now, once again, I fall into the trap of "this SHOULD work...", but I don't know anything about formal proofs or anything like that. At least this time, I can't think of a potential way that it could fail. Any advice is appreciated, except for "stop trying to write lock-free code".

推荐答案

处理无锁数据结构的正确方法是编写一个半正式的证明，证明您的设计可以在伪代码中运行.你不应该问这个无锁代码是线程安全的"，而是我证明这个无锁代码是线程安全的有什么错误吗?"

The proper way to approach a lock free data structure is to write a semi formal proof that your design works in pseudo code. You shouldn't be asking "is this lock free code thread safe", but rather "does my proof that this lock free code is thread safe have any errors?"

只有在您获得伪代码设计有效的正式证明后，您才会尝试实现它.这通常会暴露出必须小心处理的垃圾收集等问题.

Only after you have a formal proof that a pseudo code design works do you try to implement it. Often this brings to light issues like garbage collection that have to be handled carefully.

您的代码应该是注释中的正式证明和伪代码，其中穿插相对不重要的实现.

Your code should be the formal proof and pseudo code in comments, with the relatively unimportant implementation interspersed within.

验证您的代码是否正确包括理解伪代码、检查证明，然后检查您的代码是否无法映射到您的伪代码和证明.

Verifying your code is correct then consists of understanding the pseudo code, checking the proof, then checking for failure for your code to map to your pseudo code and proof.

直接获取代码并尝试检查它是否无锁是不切实际的.证明是正确设计这类东西的重要部分，实际代码是次要的，因为证明是困难的部分.

Directly taking code and trying to check that it is lock free is impractical. The proof is the important thing in correctly designing this kind of thing, the actual code is secondary, as the proof is the hard part.

并且在和当你完成了以上所有，并让其他人验证它，你必须把你的代码通过实际测试，看看你是否有盲点和漏洞，或者不理解您的并发原语，或者您的并发原语中是否存在错误.

And after and while you have done all of the above, and have other people validate it, you have to put your code through practical tests to see if you have a blind spot and there is a hole, or don't understand your concurrency primitives, or if your concurrency primitives have bugs in them.

如果您对编写半正式证明来设计代码不感兴趣，那么您不应该手动滚动无锁算法和数据结构并将它们放入生产代码中.

If you aren't interested in writing semi formal proofs to design your code, you shouldn't be hand rolling lock free algorithms and data structures and putting them into place in production code.

确定一堆代码是否线程安全"是把所有工作量都交给其他人了.您需要有一个论据，为什么您的代码是线程安全的"以这样一种方式排列，以便其他人尽可能容易地找到其中的漏洞.如果你的论点为什么你的代码线程安全"的排列方式使得更难找到漏洞，那么即使没有人能在你的代码中发现漏洞，也不能假定你的代码是线程安全的.

Determining if a pile of code "is thread safe" is putting all of the work load on other people. You need to have an argument why your code "is thread safe" arranged in such a way that it is as easy as possible for others to find holes in it. If your argument why your code "is thread safe" is arranged in ways that makes it harder to find holes, your code cannot be presumed to be thread safe, even if nobody can spot a hole in your code.

您在上面发布的代码是一团糟.它包含注释掉的代码，没有正式的不变量，没有证明行，没有强烈描述为什么它是线程安全的，并且通常不会尝试以易于发现的方式显示自己是线程安全的缺陷.因此，没有一个理性的读者会认为代码线程是安全的，即使他们在其中找不到任何错误.

The code you posted above is a mess. It contains commented out code, no formal invariants, no proofs that the lines, no strong description of why it is thread safe, and in general does not put forward an attempt to show itself as thread safe in a way that makes it easy to spot flaws. As such, no reasonable reader will consider the code thread safe, even if they cannot find any errors in it.

这篇关于寻找对我的线程安全、无锁队列实现的批评的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！