Параллельная очередь, C

Question

Итак, я пытаюсь реализовать параллельную очередь в C. Я разделил методы на «методы чтения» и «методы записи». Итак, при доступе к методам записи, таким как push () и pop (), я получаю блокировку записи. И то же самое для методов чтения. Кроме того, у нас может быть несколько читателей, но только один писатель.

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

Итак, мой главный вопрос - как реализовать нескольким читателям доступ к методам чтения одновременно?

На данный момент это мой общий код метода чтения: (В коде psuedo - не C. Я на самом деле использую pthreads).

mutex.lock();
while (nwriter > 0) {
  wait(&reader);
  mutex.unlock();
}
nreader++;
//Critical code
nreader--;
if (nreader == 0) {
  signal(&writer)
}
mutex.unlock

Итак, представьте, что у нас есть читатель, который содержит мьютекс. Теперь любой другой читатель, который придет и попытается получить мьютекс, не сможет. Разве это не заблокирует? Тогда как многие читатели одновременно получают доступ к методам чтения?

Верны ли мои рассуждения? Если да, то как решить проблему?

Answer 1

Если это не упражнение, используйте блокировку чтения-записи из pthreads (pthread_rwlock_* функции).

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

if( !queue.empty() ) {
    data = queue.top();
    queue.pop();
}

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

Answer 2

Пожалуйста, найдите следующие функции чтения \ записи.

В своих функциях я использовал мьютексы canRead и canWrite для числа читателей:

Функция записи:

lock(canWrite) // Wait if mutex if not free
// Write
unlock(canWrite)

Функция чтения:

lock(canRead) // This mutex protect the nReaders
nReaders++    // Init value should be 0 (no readers)
if (nReaders == 1) // No other readers
{
   lock(canWrite)  // No writers can enter critical section
}
unlock(canRead)

// Read

lock(canRead)
nReaders--;
if (nReaders == 0) // No more readers
{
   unlock(canWrite) // Writer can enter critical secion
}
unlock(canRead)

Answer 3

Вы можете попробовать эту библиотеку, она встроена в c native, без блокировки, подходит для кроссплатформенности lfqueue ,

Например: -

int* int_data;
lfqueue_t my_queue;

if (lfqueue_init(&my_queue) == -1)
    return -1;

/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
 while (lfqueue_enq(&my_queue, int_data) == -1) {
    printf("ENQ Full ?\n");
}

/** Wrap This scope in other threads **/
/*Dequeue*/
while  ( (int_data = lfqueue_deq(&my_queue)) == NULL) {
    printf("DEQ EMPTY ..\n");
}

// printf("%d\n", *(int*) int_data );
free(int_data);
/** End **/

lfqueue_destroy(&my_queue);

Answer 4

Классическое решение - несколько читателей, один писатель.

Структура данных начинается без читателей и без писателей.

Вы разрешаете любое количество одновременных читателей.

Когда появляется писатель, вы блокируете его, пока все текущие читатели не закончат;затем вы отпускаете его (все новые читатели и писатели, чьи писатели заблокированы, выстраиваются в очередь за ним по порядку).