无锁固定大小队列失败

Question

我尝试用D语言实现类似无锁固定大小队列的东西

import core.atomic;
struct Chunk(T, uint N)
{
    T[N] data;
    shared uint count_;
    shared uint queueCounter;

    @property bool full() { return count_ == N; }

    void append(T value)
    {
        atomicOp!("+=")(queueCounter, 1);
        while(1)
        {
            uint c = count_;
            if(cas(&count_, c, c + 1))
            {
                data[c] = value;
                atomicOp!("-=")(queueCounter, 1);
                break;
            }
        }       
    }

    bool wait()
    {
        if(!full())
        {
            return false;
        }

        while(0 != queueCounter) {}

        return true;
    }
}

这样称呼它：

import std.parallelism;

struct S
{
    bool dirty;
    int time;
    int[16] data;
}

int main(string[] argv)
{
    const uint N = 14343;

    Chunk!(S, N) ch;


    foreach(i; taskPool.parallel(std.range.iota(N), 10))
    {
        S item;
        item.time = i;
        ch.append(item);
    }
    while(!ch.wait()) {}

    // DONE

    return 0;
}

它在 N == 14343 上工作正常，但在没有任何消息的情况下失败 14344（值取决于 S.sizeof）。

为什么程序会失败？

我的 CAS 追加是否正确？

在 "DONE" 字符串之后 chunk.data 是否可以完全访问？

Answer 1

看起来您在 Windows 上运行，默认堆栈大小为 1 MB（至少根据 this article at MSDN）。

你的 S.sizeof 可能是 72，它给出的 S 不超过 14563 个实例（堆栈上还有其他东西，因此你的最大值 N 略低） .

在堆栈上放置一个较大的变量会导致堆栈溢出，这应该在调用 main 时立即发生：然后将 ch 的值赋给 Chunk!(S, N).init，这会导致写入堆栈边界之外，击中保护页并因此导致程序因分段错误而崩溃（至少这是 Linux 上的结果，当 N 大到足以溢出默认的 8 兆字节堆栈时），或者，在 Windows 术语，访问冲突（我现在没有 Windows 框来验证它）。

有几个解决方案：

使用较小的 N.
增加堆栈大小（参见上面链接的文章）。
在堆上分配 data。

无锁固定大小队列失败

fail with lock-free fixedsize queue

d

cas

lock-free