时间戳

首页 > 解决方案 > 是否可以同时推送和弹出创建线程安全队列？

c - 是否可以同时推送和弹出创建线程安全队列？

问题描述

这更像是一个理论而不是有用的问题，但我想不出办法来做到这一点。明确地说，目标是创建一个队列，允许多个线程同时推送和弹出而不会相互阻塞。

目标的一个示例是：线程 A 推送两次。线程A和线程B调用push，线程C和线程D调用pop。线程 A 获取队列位置 2，线程 B 获取队列位置 3，线程 C 获取队列位置 0，线程 D 获取队列位置 1。所有线程能够同时读取/写入各自的位置。

这些 push 和 pop 函数可以做到这一点，但不是线程安全的：

#include <pthreads.h>
#include <semaphore.h>

...

void push(void* item) {
    sem_wait(push_avaliability);
    int slot = atomic_fetch_add(tail, 1) % queue_size;
    pthread_mutex_lock(access_queue[slot]);
    queue[slot] = item;
    pthread_mutex_unlock(access_queue[slot]);
    sem_post(pop_avaliability);
}

void* pop() {
    sem_wait(pop_avaliability);
    int slot = atomic_fetch_add(head, 1) % queue_size;
    pthread_mutex_lock(access_queue[slot]);
    void* item = queue[slot];
    pthread_mutex_unlock(access_queue[slot]);
    sem_post(push_avaliability);
}

head和tail都被初始化为0，push_avaliability被初始化为队列的大小，pop_avaliability被初始化为0。这是仅有的两个修改这些变量的函数。（我知道头/尾存在溢出的可能性，并且在数组中存储指针会使队列的线程安全变得不重要，但这些问题对于这个问题并不重要。）

问题的一个例子是：假设线程 A 和线程 B 调用push并且线程 C 调用pop。线程 A 获得插槽 0 但不锁定它，然后线程 B 获得插槽 1 并写入它并发布有写入的空间。线程 C 唤醒并获取插槽 0，并尝试从中读取，但线程 A 尚未写入。

我可以通过增加头/尾并在互斥锁中写入/读取来解决此问题，该互斥锁阻止任何其他线程访问整个队列，但我想知道是否有可能以允许多个线程的方式做到这一点同时写入和读取队列。

标签： cmultithreading

解决方案

这是我正在使用的解决方案：

void push(void* item) {
    sem_wait(push_avaliability);
    int slot = atomic_fetch_add(tail, 1) % queue_size;
    while(slot_full[slot] != false);
    queue[slot] = item;
    slot_full[slot] = true;
    sem_post(pop_avaliability);
}

void* pop() {
    sem_wait(pop_avaliability);
    int slot = atomic_fetch_add(head, 1) % queue_size;
    while(slot_full[slot] != true);
    void* item = queue[slot];
    slot_full[slot] = false;
    sem_post(push_avaliability);
    return item;
}

（slot_full[i]被初始化为假）

while 循环不会使用大量时间，因为信号量主要处理等待插槽打开的情况。（在测试中，while 循环条件永远不会为真。）如果复制操作很昂贵，那么使用条件变量将是可行的方法，但我认为平均而言这可能比这种解决方案更昂贵。

这篇论文是无锁队列的有用参考，以及 mpoeter 的评论。

推荐阅读