寻找我的线程安全，无锁队列实现的批判 [英] 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和nm！）。最重要的是，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.
这篇关于寻找我的线程安全，无锁队列实现的批判的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
