2

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

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

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

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

#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\n");
        }
    }       
    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\n");
        }
    }   
    strcpy(ptr,q->q[ q->first]);
    q->first = (q->first+1) % QUEUESIZE;
    q->count = q->count - 1;
}
4

2 回答 2

4

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

#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);
于 2013-04-26T18:46:08.323 回答
0

正如您在使用信号量的示例中所认识到的那样，您需要操作系统的一些支持来完成此操作。如果您使用的是支持 POSIX 消息队列的操作系统，则可以依赖它。否则，您可以使用 pthread 条件变量作为实现的基础。

诀窍是，您需要两个条件变量来覆盖完整和空等待状态。实现很简单，但很难覆盖极端情况，甚至更难测试。

我准备了一个示例，它是历史悠久的 Apache apr_queue 实现，但依赖项被剥离为仅 pthreads：https ://github.com/chrismerck/rpa_queue

于 2019-04-26T15:58:00.497 回答