Потокобезопасная очередь с несколькими записями в C

Question

Я работаю над многопоточным приложением C, использующим pthreads. У меня есть один поток, который записывает в базу данных (библиотека базы данных безопасна для использования только в одном потоке), и несколько потоков, которые собирают данные, обрабатывают их, а затем должны отправить результаты в поток базы данных для хранения. Я упоминал в упомянутом выше, что «возможно» создать безопасную очередь с несколькими записывающими в C, но в каждом месте, где я вижу упомянутое, просто говорится, что это «слишком сложно для этого примера» и просто демонстрируется безопасная очередь с одним записывающим .

Мне нужны следующие вещи:

• Эффективная вставка и удаление. Я бы предположил, что, как и любая другая очередь O (1), возможна постановка в очередь и снятие очереди.
• Динамически распределяемая память, то есть связанная структура. Мне не нужно иметь произвольное ограничение на размер очереди, поэтому массив на самом деле не то, что я ищу.

РЕДАКТИРОВАТЬ: Чтение потоков не должно вращаться в пустой очереди, так как, вероятно, будет минутное время без записи, с короткими пакетами большого количества записей.

Answer 1

Конечно, есть очереди без блокировки. Однако, исходя из того, что вы сказали в комментариях, производительность здесь совсем не критична, так как вы все равно создаете поток для каждой записи.

Итак, это стандартный вариант использования условной переменной. Создайте себе структуру, содержащую мьютекс, переменную условия, связанный список (или кольцевой буфер, если хотите) и флаг отмены:

write:
    lock the mutex
    (optionally - check the cancel flag to prevent leaks of stuff on the list)
    add the event to the list
    signal the condition variable
    unlock the mutex

read:
   lock the mutex
   while (list is empty AND cancel is false):
       wait on the condition variable with the mutex
   if cancel is false:  // or "if list non-empty", depending on cancel semantics
       remove an event from the list
   unlock the mutex
   return event if we have one, else NULL meaning "cancelled"

cancel:
   lock the mutex
   set the cancel flag
   (optionally - dispose of anything on the list, since the reader will quit)
   signal the condition variable
   unlock the mutex

Если вы используете список с внешними узлами, вы можете выделить память вне блокировки мьютекса, просто чтобы сократить время, в течение которого она удерживается. Но если вы создаете события с помощью навязчивого узла списка, это, вероятно, проще всего.

Редактировать: вы также можете поддерживать несколько считывателей (без переносных гарантий, для которых вы получаете данное событие), если при отмене вы меняете «сигнал» на «трансляцию». Хотя вам это не нужно, на самом деле это тоже ничего не стоит.

Answer 2

Если вам не нужна очередь без блокировки, то вы можете просто обернуть существующую очередь блокировкой.

Mutex myQueueLock;
Queue myQueue; 
void mtQueuePush(int value)
{
    lock(myQueueLock);
    queuePush(myQueue, value);
    unlock(myQueueLock);
}
int mtQueueNext()
{
    lock(myQueueLock);
    int value = queueFront(myQueue);
    queuePop(myQueue);
    unlock(myQueueLock);
    return value;
}

После этого единственное, что нужно добавить - это некое указание для mtQueueNext, когда очередь пуста.

EDIT: Если у вас есть одна беззащитная очередь с одним считывателем, вам нужно иметь блокировку только вокруг mtQueuePush, чтобы предотвратить одновременное выполнение нескольких записей.

Существует множество одиночных очередей без чтения и записи, однако большинство из них реализованы в виде шаблонных классов c ++. Тем не менее, выполните поиск в Google и, если нужно, решите, как переписать их на простом языке C.

Answer 3

http://www.liblfds.org

Библиотека структур данных без блокировки, написанная на C.

Имеет очередь M & S.

Answer 4

Я бы пошел для нескольких очередей одного записывающего (одна на поток записывающего). Затем вы можете проверить this , как заставить одного читателя читать различные очереди.