C中的非忙阻塞队列实现 [英] Non-busy blocking Queue Implementation in C

问题描述

我正在尝试在 C 中实现一个队列，它会导致进程不忙地等待，直到队列中有一个元素可以使用.我尝试了两种不同的方法来实现这一目标.

I am trying to implement a queue in C that causes a process to non-busy wait until there is an element in the queue to consume. I have tried two different things to try to achieve this.

我遇到的第一个问题是入队/出队操作是否有 if 条件来检查边界(if(q->count == QUEUESIZE))，对 sem_wait 的调用将立即返回，因为没有其他进程获得锁.

The first problem I have is if the enqueue/dequeue operations have if conditionals to check the bounds( if(q->count == QUEUESIZE) ), the call to sem_wait will return immediately because no other process has obtained a lock.

如果我将条件更改为 while(q->count == QUEUESIZE)，我相信消费者进程会忙于等待"，直到生产者进程发布信号量，这不是我的实现目标，通过测试发现消费者进程不会获取锁而继续.

If I change the conditional to while(q->count == QUEUESIZE), I believe the consumer process will 'busy wait' until the semaphore is posted by the producer process, which is not my goal of the implementation, and through testing, I've found that the consumer process will not acquire the lock and continue.

我认为我很接近，但我似乎无法弄清楚如何解决这些问题.我曾考虑添加条件变量或 pthread_mutex，但想在增加额外复杂性之前用尽信号量选项.

I think that I am close, but I can't seem to figure out how to work around these issues. I have thought about adding condition variables or pthread_mutex, but wanted to exhaust the semaphore options before adding in additional complexity.

#define QUEUESIZE 48

typedef struct 
{           
    char q[QUEUESIZE+1][150];
    int first;                      
    int last;                       
    int count;                      
    sem_t *lock;                    
} Queue;


init_queue(Queue *q, sem_t *l)
{
    q->first = 0;
    q->last = QUEUESIZE-1;
    q->count = 0;
    q->lock = l;
}

enqueue(Queue *q, char x[150])
{
    while(q->count == QUEUESIZE)
        sem_wait(q->lock);

    if (q->count == 0)
    {
        if (sem_post(q->lock) == -1)
        {
            printf("Thread failed to unlock semaphore
");
        }
    }       
    q->last = (q->last+1) % QUEUESIZE;
    strcpy(q->q[ q->last ],x);    
    q->count = q->count + 1;
}

dequeue(Queue *q,char *ptr)
{
    char x[150];
    while(q->count == 0)
        sem_wait(q->lock);

    if (q->count == QUEUESIZE) 
    {
        if (sem_post(q->lock) == -1)
        {
            printf("Thread failed to unlock semaphore
");
        }
    }   
    strcpy(ptr,q->q[ q->first]);
    q->first = (q->first+1) % QUEUESIZE;
    q->count = q->count - 1;
}

推荐答案

根据要求，这是我的解决方案.

As requested, here is my solution.

#define QUEUESIZE 50

typedef struct 
{           
    char q[QUEUESIZE][150];
    int first;                      
    int last;                       
    int count;                      
    sem_t *full;
    sem_t *empty;
    sem_t *excl;

} Queue;


void init_queue(Queue *q, sem_t *f,sem_t *e, sem_t *ee,)
{
    q->first = 0;
    q->last = QUEUESIZE-1;
    q->count = 0;
    q->full = f;
    q->empty = e;
    q->excl = ee; 
}

void enqueue(Queue *q, char x[150])
{
    sem_wait(q->empty);
    sem_wait(q->excl);

    q->last = (q->last+1) % QUEUESIZE;
    strcpy(q->q[ q->last ],x);    
    q->count = q->count + 1;

    sem_post(q->excl);
    sem_post(q->full);
}

void dequeue(Queue *q,char *ptr)
{
    sem_wait(q->full);
    sem_wait(q->excl);

    strcpy(ptr,q->q[ q->first]);
    q->first = (q->first+1) % QUEUESIZE;
    q->count = q->count - 1;

    sem_post(q->excl);
    sem_post(q->empty);
}

我初始化信号量如下:

sem_init(full,1,0);
sem_init(empty,1,49);
sem_init(dequeue_excl,1,1);
sem_init(enqueue_excl,1,1);

这篇关于C中的非忙阻塞队列实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！