File d'attente thread-safe pour plusieurs écrivains en C

Question

Je travaille sur une application C multi-thread à l'aide de pthreads. J'ai un thread qui écrit dans une base de données (la bibliothèque de base de données ne peut être utilisée que dans un seul thread) et plusieurs threads qui collectent des données, les traitent et doivent ensuite envoyer les résultats au thread de la base de données pour le stockage. J'ai déjà mentionné que c'est "possible". créer une file d'attente sécurisée pour plusieurs rédacteurs en C, mais chaque endroit que je vois mentionné indique simplement que c'est "trop ??compliqué pour cet exemple". et illustre simplement une file d'attente sécurisée à un seul auteur.

J'ai besoin des choses suivantes:

• Insertion et retrait efficaces. Je suppose que comme toute autre file d'attente, la mise en file d'attente et la mise en file d'attente O (1) sont possibles.
• Mémoire allouée dynamiquement, c'est-à-dire une structure liée. Je n'ai pas besoin de limite arbitraire sur la taille de la file d'attente, donc un tableau n'est vraiment pas ce que je recherche.

EDIT: Les threads de lecture ne doivent pas tourner sur une file d'attente vide, car il est probable que le temps passera sans minutes d'écriture, avec de courtes rafales d'un grand nombre d'écritures.

Answer 1

Bien sûr, il y a des files d'attente sans verrouillage. D'après ce que vous avez dit dans les commentaires, les performances ne sont pas du tout critiques, car vous créez de toute façon un fil de discussion par écriture.

Il s'agit donc d'un cas d'utilisation standard pour une variable de condition. Créez-vous une structure contenant un mutex, une variable de condition, une liste chaînée (ou un tampon circulaire si vous préférez) et un indicateur d'annulation:

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

Si vous utilisez une liste avec des nœuds externes, vous souhaiterez peut-être allouer la mémoire en dehors du verrou mutex, afin de réduire le temps de conservation. Mais si vous concevez les événements avec un nœud de liste intrusif, c'est probablement le plus facile.

Modifier: vous pouvez également prendre en charge plusieurs lecteurs (sans garantie portable pour un événement donné) si vous annulez le message " signal " à "diffuser". Bien que vous n'en ayez pas besoin, cela ne coûte rien non plus.

Answer 2

Si vous n'avez pas besoin d'une file d'attente sans verrou, vous pouvez simplement envelopper une file existante avec un verrou.

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;
}

La seule chose après cela est d'ajouter une sorte de gestion pour mtQueueNext lorsque la file d'attente est vide.

EDIT: Si vous n’avez qu’un seul lecteur, une file d’attente sans verrou à un seul rédacteur, il vous suffit de verrouiller mtQueuePush pour éviter la création simultanée de plusieurs rédacteurs.

Il existe un nombre limité de files d'attente sans lecteur / lecteur uniques, même si la plupart d'entre elles sont implémentées en tant que classes de modèles c ++. Cependant, effectuez une recherche google et, si besoin est, trouvez comment les réécrire en C simple.

Answer 3

http://www.liblfds.org

Bibliothèque de structures de données sans verrouillage écrite en C

A la file d'attente M & amp; S.

Answer 4

Je choisirais plusieurs files d'attente pour un seul écrivain (une par thread d'écrivain). Ensuite, vous pouvez vérifier pour savoir comment faire en sorte qu'un seul lecteur lise les différentes files d'attente.