C 中是否有单消费者单生产者无锁队列实现？

发布于 2024-07-24 10:20:26 字数 589 浏览 4 评论 0 原文

我正在编写一个带有消费者线程和生产者线程的程序，现在看来队列同步在程序中是一个很大的开销，我寻找了一些无锁队列实现，但只找到了Lamport的版本和PPoPP上的改进版本' 08：

enqueue_nonblock(data) {
    if (NULL != buffer[head]) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}

dequeue_nonblock(data) {
    data = buffer[tail];
    if (NULL == data) {
        return EWOULDBLOCK;
    }
    buffer[tail] = NULL;
    tail = NEXT(tail);
    return 0;
}

两个版本都需要为数据预先分配数组，我的问题是是否有任何使用 malloc() 动态分配空间的单消费者单生产者无锁队列实现？

另一个相关问题是，如何测量队列同步中的精确开销？比如pthread_mutex_lock()需要多少时间等。

原文

I'm writing a program with a consumer thread and a producer thread, now it seems queue synchronization is a big overhead in the program, and I looked for some lock free queue implementations, but only found Lamport's version and an improved version on PPoPP '08:

enqueue_nonblock(data) {
    if (NULL != buffer[head]) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}

dequeue_nonblock(data) {
    data = buffer[tail];
    if (NULL == data) {
        return EWOULDBLOCK;
    }
    buffer[tail] = NULL;
    tail = NEXT(tail);
    return 0;
}

Both versions require a pre-allocated array for the data, my question is that is there any single-consumer single-producer lock-free queue implementation which uses malloc() to allocate space dynamically?

And another related question is, how can I measure exact overhead in queue synchronization? Such as how much time it takes of pthread_mutex_lock(), etc.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不再让梦枯萎 2024-07-31 10:20:26

如果您担心性能，那么添加 malloc() 不会有任何帮助。如果您不担心性能，为什么不简单地通过互斥体控制对队列的访问。您是否实际测量过此类实现的性能？在我看来，您似乎正在走熟悉的过早优化路线。

回复收藏 0 原文

爱冒险 2024-07-31 10:20:26

您展示的算法能够正常工作，因为尽管两个线程共享资源（即队列），但它们以非常特殊的方式共享资源。因为只有一个线程会更改队列的头索引（生产者），并且只有一个线程每次会更改尾索引（当然是消费者），所以您无法获得共享对象的不一致状态。同样重要的是，生产者在更新头索引之前将实际数据放入，并且消费者在更新尾索引之前读取它想要的数据。

它工作得很好，因为数组是相当静态的；两个线程都可以依赖那里的元素的存储。您可能无法完全替换该数组，但您可以做的是更改该数组的用途。

即，不是将数据保存在数组中，而是使用它来保存指向数据的指针。然后，您可以 malloc() 和 free() 数据项，同时通过数组在线程之间传递对它们的引用（指针）。

此外，posix 确实支持读取纳秒时钟，尽管实际精度取决于系统。您可以在之前和之后读取这个高分辨率时钟，然后减去即可。