Многопользовательская потокобезопасная очередь в C

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

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

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

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

Ответ 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

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

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

Ответ 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, чтобы предотвратить несколько одновременных авторов.

Theres nubmer одиночных цепочек без чтения/записи, поскольку большинство из них реализованы как классы шаблонов С++. Однако выполните поиск в google и, если нужно, подумайте, как их переписать в простой C.

Ответ 3

http://www.liblfds.org

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

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

Ответ 4

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