单一生产者/消费者循环缓冲区,仅阻止消费者 [英] Single producer/consumer circular buffer which only blocks consumer
问题描述
我想用一个生产者和一个消费者来实现一个缓冲区,在这里只有消费者可能被阻塞.这里重要的细节是,如果队列已满,生产者可以删除更新.
I'd like to implement a buffer with single producer and a single consumer, where only the consumer may be blocked. Important detail here is that the producer can drop the update if the queue is full.
我已经考虑过转换一个免等待的实现,但是乍一看似乎没有一种简单的方法可以通知消费者新数据已经到来而又不会丢失通知.因此,我决定使用计数信号量(为了清楚起见,省略了一些错误处理细节)采用以下非常简单的方法:
I've considered converting a wait-free implementation, but at first glance there seems to be no easy way to notify the consumer new data has arrived without losing notifications. So I settled on the very simple approach below, using a counting semaphore (some error handling details omitted for clarity):
Object ar[SIZE];
int head = 0, tail = 0;
sem_t semItems; // initialized to 0
void enqueue(Object o) {
int val;
sem_getvalue(&semItems, &val);
if (val < SIZE - 1) {
ar[head] = o;
head = (head + 1) % SIZE;
sem_post(&semItems);
}
else {
// dropped
}
}
Object dequeue(void) {
sem_wait(&semItems);
Object o = ar[tail];
tail = (tail + 1) % SIZE;
return o;
}
此代码是否存在安全问题?我很惊讶在流行文学中的任何地方都没有看到这样的实现.另一个问题是sem_post()
是否会阻塞(在Linux的幕后调用futex_wake()
).当然,也欢迎使用更简单的解决方案.
Are there any safety issues with this code? I was surprised not to see an implementation like it anywhere in the popular literature. An additional question is whether sem_post()
would ever block (calls futex_wake()
under the hood in linux). Simpler solutions are also welcome of course.
edit:经过编辑的代码在阅读器和编写器之间留有间隔(请参见Mayurk的回复).
edit: edited code to leave a space between reader and writer (see Mayurk's response).
推荐答案
我可以在此实现中看到一个问题.请考虑以下顺序.
I can see one problem in this implementation. Consider the following sequence.
- 假定缓冲区已满,但使用者尚未启动.所以(head = 0,tail = 0,sem_val = SIZE).
- dequeue()从使用者线程中调用. sem_wait()成功.因此,仅在这种情况下(head = 0,tail = 0,sem_val = SIZE-1).消费者开始阅读ar [0].
- 现在有一个线程开关. enqueue()从生产者线程中调用. sem_getvalue()将返回SIZE-1.因此,生产者在ar [0]处写信.
基本上,我认为您需要互斥保护来进行读写操作.但是添加互斥锁可能会阻塞线程.因此,我不确定您是否从这种逻辑中得到预期的行为.
Basically I think you need mutex protection for reading and writing operations. But adding mutex might block the threads. So I am not sure whether you get expected behavior from this logic.
这篇关于单一生产者/消费者循环缓冲区,仅阻止消费者的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!