поточно-реализация 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; 
} 

, то есть possibilit y состояния гонки. Последний комментарий

Здесь есть возможность состояния гонки, очередь может фактически быть пустым в данный момент, и поэтому возвращаемое значение в заблуждение

описывает проблему.

Я определил мою структуру данных, как, например,

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

Вы только что обнаружили причину, по которой блокировка, потоки и параллелизм в целом сложны. Легко создать несколько функций-оболочек, которые получают и освобождают блокировки и предотвращают сбои при сбое данных, на самом деле трудно получить блокировку сразу, когда вы зависите от состояния от более ранних обращений.

Я бы сказал, что функция queue_is_empty неверна, потому что она существует вообще. Он не может возвращать полезное значение, потому что, как вы обнаружили, возвращаемое значение устарело, прежде чем вы его вернете. Поскольку функция не может вернуть полезное возвращаемое значение, она не должна существовать. И здесь вам нужно много думать о предоставляемом вами API.

Одним из вариантов является блокировка ответственности вызывающих абонентов. Вызывающий может иметь что-то вроде:

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

тогда Вы столкнетесь с проблемами, с обработкой ошибок и возвратов из функций, блокировка изменений состояния вокруг функций, не входящих в интерфейс очереди и т.д. И как только у вас есть больше, чем один из этих замков, которым нужно управлять блокировкой, чтобы предотвратить взаимоблокировки.

Другим вариантом является сокращение API для обеспечения безопасных операций. Запуск и удаление очереди работают правильно. Вам действительно нужно is_empty? Для чего это? Не стоит ли ожидать ожидания элемента очереди, когда очередь пуста? Вы не можете решить это с помощью dequeue_without_waiting? И т. Д.

Answer 2

В принципе, ваша функция уже правильная. Это просто, что результат устарел, как только вы освободите замок. В многопоточной программе вопрос о том, является ли параллельная очередь пустой, довольно бессмысленна, поскольку другой поток может в любой момент ввести данные в очередь.