File d'attente libre de verrou - Producteur unique, consommateurs multiples

Question

Je recherche une méthode pour implémenter une structure de données de file d'attente sans verrou qui prend en charge un seul producteur et plusieurs consommateurs. J'ai regardé la méthode classique par Maged Michael et Michael Scott (1996) mais leur version utilise des listes chaînées. Je voudrais une implémentation qui utilise un tampon circulaire borné. Quelque chose qui utilise des variables atomiques? Sur une note de côté, je ne sais pas pourquoi ces méthodes classiques sont conçues pour les listes liées qui nécessitent beaucoup de gestion dynamique de la mémoire. Dans un programme multithread, toutes les routines de gestion de la mémoire sont sérialisées. N'avons-nous pas vaincu les avantages des méthodes sans verrous en les utilisant conjointement avec des structures de données dynamiques?

J'essaye de coder ceci en C/C++ using la bibliothèque de pthread sur une architecture d'Intel 64-bit.

Merci, Shirish

Answer 1

Pour un tampon circulaire traditionnel d'un bloc, je pense que cela ne peut pas être fait en toute sécurité avec des opérations atomiques. Vous devez faire tellement en une seule lecture. Supposons que vous avez une structure qui a ceci:

uint8_t* buf; 
unsigned int size; // Actual max. buffer size 
unsigned int length; // Actual stored data length (suppose in write prohibited from being > size) 
unsigned int offset; // Start of current stored data 

Sur une lecture que vous devez faire ce qui suit (ce qui est la façon dont je mis en œuvre de toute façon, vous pouvez échanger quelques pas comme je vais ensuite discuter):

1. Vérifiez si la longueur de lecture ne dépasse pas la longueur enregistrée
2. Vérifiez si la longueur offset + lecture ne dépassent pas les limites des tampons
3. données lues
4. Augmenter offset, diminuer sa longueur

Que devriez-vous certainement faire synchronisé (si atomique) pour que cela fonctionne? En fait, combiner les étapes 1 et 4 en une seule étape atomique, ou de préciser: faire synchronisé:

1. chèque read_length, cela peut être STH comme read_length=min(read_length,length);
2. longueur diminuer avec read_length: length-=read_length
3. obtenir une copie locale de l'offset unsigned int local_offset = offset
4. augmentation compensée par read_length: offset+=read_length

Ensuite, vous pouvez simplement faire un memcpy (ou w hatever) à partir de votre local_offset, vérifiez si votre lecture dépasse la taille du buffer circulaire (scindée en 2 memcpy's), .... Ceci est "assez" sécurisé, votre méthode d'écriture pourrait encore écrire sur la mémoire que vous lisez, donc assurez-vous que votre tampon est vraiment assez grand pour minimiser cette possibilité. Maintenant, bien que j'imagine que vous pouvez combiner 3 et 4 (je suppose que c'est ce qu'ils font dans le cas de la liste liée) ou même 1 et 2 dans les opérations atomiques, je ne peux pas vous voir faire tout ça en une seule fois. opération :).

Vous pouvez cependant essayer de laisser tomber la vérification de la longueur si vos consommateurs sont très intelligents et sauront toujours quoi lire. Vous auriez également besoin d'une nouvelle variable woffset, car l'ancienne méthode de (offset + length)% size pour déterminer le décalage d'écriture ne fonctionnerait plus. Notez que ceci est proche du cas d'une liste chaînée, où vous lisez toujours un élément (= fixe, taille connue) de la liste.Ici aussi, si vous en faites une liste circulaire, vous pouvez lire beaucoup ou écrire dans une position que vous lisez à ce moment-là! Enfin: mon conseil, il suffit d'aller avec des verrous, j'utilise une classe CircularBuffer, complètement sûr pour lire & écriture) pour un streamer vidéo en temps réel 720p60 et je n'ai pas de problèmes de vitesse du tout de verrouillage.

Answer 2

L'utilisation d'un tampon circulaire rend nécessaire un verrou, car un blocage est nécessaire pour empêcher la tête de dépasser la queue. Mais sinon les pointeurs tête et queue peuvent facilement être mis à jour atomiquement. Ou dans certains cas, le tampon peut être si grand que l'écrasement n'est pas un problème. (Dans la vraie vie, vous verrez cela dans les systèmes de négociation automatisés, avec des tampons circulaires dimensionnés pour contenir X minutes de données de marché.Si vous êtes X minutes derrière, vous avez des problèmes pires que d'écraser votre tampon). Lorsque j'ai implémenté la file d'attente MS en C++, j'ai construit un allocateur sans verrou à l'aide d'une pile, ce qui est très facile à implémenter. Si j'ai MSQueue alors à la compilation je sais sizeof (MSQueue :: node). Ensuite, je fais une pile de N tampons de la taille requise. Le N peut croître, c'est-à-dire si pop() renvoie null, il est facile d'aller demander au tas d'autres blocs, et ceux-ci sont poussés sur la pile. En dehors de l'appel potentiellement bloquant pour plus de mémoire, ceci est une opération sans verrou.

Notez que le T ne peut pas avoir un dtor non trivial. J'ai travaillé sur une version qui permettait de faire des choses non triviales, ça a vraiment marché. Mais j'ai trouvé qu'il était plus facile de faire du T un pointeur vers le T que je voulais, où le producteur a libéré la propriété, et le consommateur a acquis la propriété. Cela nécessite bien sûr que le T lui-même soit alloué en utilisant des méthodes lockfree, mais le même allocateur que j'ai fait avec la pile fonctionne ici aussi.

Dans tous les cas, le but de la programmation sans verrouillage n'est pas que les structures de données elles-mêmes soient plus lentes. Les points sont les suivants:

1. Le verrouillage libre me rend indépendant du planificateur. La programmation basée sur le verrouillage dépend du planificateur pour s'assurer que les détenteurs d'un verrou fonctionnent afin qu'ils puissent libérer le verrou. C'est ce qui provoque l'inversion des priorités Sous Linux, il y a des attributs de verrou pour s'assurer que cela se produise
2. Si je suis indépendant du planificateur, le système d'exploitation a beaucoup plus de facilité à gérer les temps, et j'ai beaucoup moins de changement de contexte
3. il est plus facile d'écrire des programmes multithread corrects en utilisant lockfree car je n'ai pas à m'inquiéter de deadlock, livelock, scheduling, syncronization, etc ... Ceci est particulièrement vrai avec les implémentations de mémoire partagée où un processus peut mourir en maintenant un verrou dans la mémoire partagée, et il n'y a aucun moyen de libérer le verrou
4. les méthodes sans verrou sont beaucoup plus faciles à l'échelle. En fait, j'ai implémenté des méthodes sans verrous utilisant la messagerie sur un réseau. serrures distribués comme celui-ci sont un cauchemar

Cela dit, il existe de nombreux cas où des méthodes basées verrouillage sont préférables et/ou nécessaires

1. lors de la mise à jour des choses qui sont coûteuses ou impossibles à copier. La plupart des méthodes sans verrou utilisent une sorte de versioning, c'est-à-dire font une copie de l'objet, le mettent à jour et vérifient si la version partagée est toujours la même que lorsque vous l'avez copiée. Els ecopy encore, appliquer la mise à jour, et vérifier à nouveau. Continuez à faire cela jusqu'à ce que cela fonctionne. Cela est correct lorsque les objets sont petits, mais qu'ils sont grands, ou contiennent des poignées de fichier, etc, alors non recommandé
2. La plupart des types sont inaccessibles sans verrou, par ex. tout conteneur STL. Ceux-ci ont des invariants qui nécessitent un accès non atomique, par exemple assert (vector.size() == vector.end() - vector.begin()). Donc, si vous mettez à jour/lisez un vecteur qui est partagé, vous devez le verrouiller.

Answer 3

Ceci est une vieille question, mais personne n'a fourni une solution acceptée. Donc, je propose cette information pour les autres qui peuvent être à la recherche.

Ce site: http://www.1024cores.net

Fournit des structures de données lockfree/waitfree vraiment utiles avec des explications approfondies.

Ce que vous cherchez est une solution sans verrou au problème de lecteur/graveur.

Voir: http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem