is_empty 在队列数据结构中的线程安全实现

Question

我正在尝试创建线程安全队列，而大部分操作

 queue *queue_create_empty(void);
 void queue_enqueue(queue *q, const void *value, const size_t value_size);
 void *queue_dequeue(queue *q);
 void queue_destroy(queue *q, void (*freefunc)(void *value));

我发现其中一个特别难以捉摸，

 bool queue_is_empty(const queue *q);

特别是如果函数定义是

 bool queue_is_empty(const queue *q) {
     assert(q);

     pthread_mutex_lock(q->mutex);
     bool ret = q->is_empty;
     pthread_mutex_unlock(q->mutex);

     /* 
      * Here there is a possibility of a race condition, the queue may actually
      * be empty at this point, and therefore the return value is misleading
      */
     return ret;
 }

那么就有可能出现竞争条件。最后评论

Here there is a possibility of a race condition, the queue may actually be empty at this point, and therefore the return value is misleading

描述问题。

我已经这样定义了我的数据结构，

 typedef struct queue {
     element *head;
     element *tail;

     /* Lock for all read/write operations */
     pthread_mutex_t *mutex;

     /* Condition variable for whether or not the queue is empty */
     /* Negation in variable names is poor practice but it is the */
     /* only solution here considering the conditional variable API */
     /* (signal/broadcast) */
     pthread_cond_t *not_empty;

     /* Flag used to gauge when to wait on the not_empty condition variable */
     bool is_empty;

     /* A flag to set whenever the queue is about to be destroyed */
     bool cancel;
 } queue;

并且为了实现其他我已经解决的功能 queue_is_empty 功能不足，仅检查 q->is_empty 因为我在检查值之前已经锁定了结构。

queue_dequeue 函数作为一个例子，说明人们想知道队列是否为空。请参阅第一个 if 语句。

 void *queue_dequeue(queue *q) {
     assert(q);

     void *value = NULL;
     pthread_mutex_lock(q->mutex);

     /* We have a mutex-lock here, so we can atomically check this flag */
     if (q->is_empty) {
         /* We do not have to check the cancel flag here, if the thread is awoken */
         /* in a destruction context the waiting thread will be awoken, the later */
         /* if statement checks the flag before modification of the queue */

         /* This allows other threads to access the lock, thus signalling this thread */
         /* When this thread is awoken by this wait the queue will not be empty, or */
         /* the queue is about to be destroyed */
         pthread_cond_wait(q->not_empty, q->mutex);
     }

     /* We have a mutex lock again so we may atomically check both flags */
     if (!q->cancel && !q->is_empty) {
         value = q->head->value;
         if (q->head->next) {            
             q->head = q->head->next;
             free(q->head->previous);

             /* Make dereferencing dangling pointers crash the program */
             q->head->previous = NULL;
         } else {
             free(q->head);
             q->head = NULL;
             q->is_empty = true;
         }        
     }

     pthread_mutex_unlock(q->mutex);
     return value; 
 }

如何公开线程安全的 queue_is_empty 函数？

Answer 1

基本上，你的功能已经正确了。只是在你释放锁的那一刻，结果已经过时了。在多线程程序中，询问并发队列是否为空是毫无意义的，因为另一个线程随时可能向队列中输入数据。

Answer 2

您刚刚发现了锁定、线程和并发通常很难的原因。创建一些包装函数来获取和释放锁并防止数据损坏导致的崩溃很容易，但当您依赖于早期访问的状态时，实际上很难正确锁定。

我认为函数 queue_is_empty 是不正确的，因为它存在。它不可能 return 是一个有用的值，因为正如您发现的那样，return 值在您 return 它之前就已经过时了。由于该函数不能 return 一个有用的 return 值，因此它不应该存在。这就是您需要认真考虑您提供的 API 的地方。

一种选择是让调用者负责锁定。来电者可能有类似的东西：

queue_lock(q);
if (!queue_is_empty(q))
    do_something(q);
queue_unlock(q);

然后您将运行处理错误处理和 return 来自函数的问题，围绕不属于队列接口的函数的锁定状态更改等。一旦您有超过您需要管理锁顺序以防止死锁的那些锁之一。

另一种选择是减少 API 以仅提供安全操作。入队和出队工作正常。你真的需要is_empty吗？到底有什么好处呢？是否只是为了避免在队列为空时等待队列元素？能不改用dequeue_without_waiting解决吗？等等

is_empty 在队列数据结构中的线程安全实现

Thread-safe implementation of is_empty in a queue datastructure

c

mutex

thread-safety

race-condition

data-structures