Tampon circulaire sans verrouillage

Question

Je suis en train de concevoir un système qui se connecte à un ou plusieurs flux de données, effectue une analyse des données et déclenche des événements en fonction du résultat. Dans une configuration typique de producteur/consommateur multithread, j'aurai plusieurs threads de producteur mettant des données dans une file d'attente, et plusieurs threads de consommateur lisant les données, et les consommateurs sont seulement intéressés par le dernier point de données plus un nombre n de points. Les threads du producteur devront se bloquer si le consommateur lent ne peut pas suivre, et bien sûr les threads du consommateur se bloqueront lorsqu'il n'y aura pas de mises à jour non traitées. L'utilisation d'une file d'attente concurrente typique avec un verrou de lecteur/écrivain fonctionnera bien mais le taux de données entrant pourrait être énorme, donc je voulais réduire mes frais de verrouillage, en particulier les verrous d'écriture pour les producteurs. Je pense qu'un tampon circulaire sans verrou est ce dont j'avais besoin.

Maintenant, deux questions :

1. Le tampon circulaire sans verrou est-il la solution ?

2. Si c'est le cas, avant que je ne crée mon propre système, connaissez-vous une implémentation publique qui répondrait à mes besoins ?

Toute indication sur l'implémentation d'un tampon circulaire sans verrou est la bienvenue.

BTW, je fais ça en C++ sur Linux.

Quelques informations supplémentaires :

Le temps de réponse est critique pour mon système. Idéalement, les fils consommateurs voudront voir les mises à jour arriver le plus rapidement possible, car un retard supplémentaire d'une milliseconde pourrait rendre le système sans valeur, ou avec une valeur bien moindre.

L'idée de conception vers laquelle je penche est un tampon circulaire semi-libre où le thread producteur met les données dans le tampon aussi vite qu'il le peut, appelons-le la tête du tampon A, sans blocage jusqu'à ce que le tampon soit plein, lorsque A rencontre la fin du tampon Z. Les threads consommateurs détiendront chacun deux pointeurs vers le tampon circulaire, P et P _n où P est la tête de mémoire tampon locale du thread et P _n est le nième élément après P. Chaque thread de consommateur fera avancer ses P et P _n une fois qu'il a fini de traiter le P actuel et que le pointeur de fin de tampon Z est avancé avec le P le plus lent _n . Lorsque P rattrape A, ce qui signifie qu'il n'y a plus de nouvelle mise à jour à traiter, le consommateur tourne et attend que A avance à nouveau. Si le thread du consommateur tourne trop longtemps, il peut être mis en veille et attendre une variable de condition, mais je suis d'accord avec le fait que le consommateur prenne un cycle CPU en attendant la mise à jour car cela n'augmente pas ma latence (j'aurai plus de cœurs CPU que de threads). Imaginez que vous ayez une piste circulaire, et que le producteur soit devant un groupe de consommateurs, la clé est de régler le système de sorte que le producteur soit généralement juste un peu en avance sur les consommateurs, et la plupart de ces opérations peuvent être effectuées en utilisant des techniques sans verrou. Je comprends qu'il n'est pas facile d'obtenir les détails de l'implémentation correcte... ok, très difficile, c'est pourquoi je veux apprendre des erreurs des autres avant de faire les miennes.

Answer 1

Ces deux dernières années, j'ai particulièrement étudié les structures de données sans verrou. J'ai lu la plupart des articles dans ce domaine (il n'y en a qu'une quarantaine, bien que seuls dix ou quinze d'entre eux soient vraiment utiles).

A ma connaissance, un tampon circulaire sans verrou n'a pas été inventé. Le problème sera de gérer la condition complexe où un lecteur dépasse un écrivain ou vis-versa.

Si vous n'avez pas passé au moins six mois à étudier les structures de données sans verrou, n'essayez pas d'en écrire une vous-même. Vous vous tromperez et il se peut que vous ne soyez pas conscient de l'existence d'erreurs, jusqu'à ce que votre code échoue, après déploiement, sur de nouvelles plates-formes.

Je crois cependant qu'il existe une solution à votre problème.

Vous devriez coupler une file d'attente sans verrou avec une liste libre sans verrou.

La liste libre vous donnera une pré-affectation et évitera ainsi l'exigence (fiscalement coûteuse) d'un allocateur sans verrou ; lorsque la liste libre est vide, vous reproduisez le comportement d'un tampon circulaire en retirant instantanément un élément de la file d'attente et en l'utilisant à la place.

(Bien sûr, dans un tampon circulaire basé sur un verrou, une fois que le verrou est obtenu, l'obtention d'un élément est très rapide - il s'agit simplement d'une déréférence de pointeur - mais vous n'obtiendrez pas cela dans n'importe quel algorithme sans verrou ; ils doivent souvent faire des efforts considérables pour faire les choses ; l'overhead d'un pop de liste libre suivi d'un dequeue est comparable à la quantité de travail que n'importe quel algorithme sans verrou devra faire).

Michael et Scott ont développé une très bonne file d'attente sans verrou en 1996. Un lien ci-dessous vous donnera assez de détails pour retrouver le PDF de leur article ; Michael et Scott, FIFO

Une liste libre sans verrou est l'algorithme sans verrou le plus simple et, en fait, je ne pense pas avoir vu un article à ce sujet.

Answer 2

Le terme d'art pour ce que vous voulez est un file d'attente sans verrou . Il y a un excellent ensemble de notes avec des liens vers le code et les documents par Ross Bencina. Le gars dont je fais le plus confiance au travail est Maurice Herlihy (pour les Américains, il prononce son prénom comme "Morris").

Answer 3

L'exigence que les producteurs ou les consommateurs bloquent si le tampon est vide ou plein suggère que vous devriez utiliser une structure de données de verrouillage normale, avec des sémaphores ou des variables de condition pour que les producteurs et les consommateurs bloquent jusqu'à ce que les données soient disponibles. Le code sans verrouillage ne bloque généralement pas sur de telles conditions - il tourne ou abandonne les opérations qui ne peuvent pas être effectuées au lieu de bloquer en utilisant le système d'exploitation. (Si vous pouvez vous permettre d'attendre qu'un autre thread produise ou consomme des données, alors pourquoi attendre sur un verrou qu'un autre thread finisse de mettre à jour la structure de données est-il pire).

Sous Linux (x86/x64), la synchronisation intra-thread utilisant des mutex est raisonnablement bon marché s'il n'y a pas de contention. Concentrez-vous sur la minimisation du temps pendant lequel les producteurs et les consommateurs doivent conserver leurs verrous. Étant donné que vous avez dit que vous ne vous souciez que des N derniers points de données enregistrés, je pense qu'un tampon circulaire pourrait faire cela raisonnablement bien. Cependant, je ne comprends pas vraiment comment cela s'accorde avec l'exigence de blocage et l'idée que les consommateurs consomment (suppriment) réellement les données qu'ils lisent. (Voulez-vous que les consommateurs ne regardent que les N derniers points de données, et ne les suppriment pas ? Voulez-vous que les producteurs ne se soucient pas de savoir si les consommateurs ne peuvent pas suivre, et se contentent d'écraser les anciennes données) ?

De plus, comme l'a fait remarquer Zan Lynx, vous pouvez agréger/tamponner vos données en plus gros morceaux lorsque vous en recevez beaucoup. Vous pouvez mettre en mémoire tampon un nombre fixe de points, ou toutes les données reçues dans un certain laps de temps. Cela signifie qu'il y aura moins d'opérations de synchronisation. Cela introduit cependant une latence, mais si vous n'utilisez pas Linux en temps réel, vous devrez de toute façon vous en accommoder dans une certaine mesure.

Answer 4

L'implémentation dans la bibliothèque boost vaut la peine d'être considérée. Elle est facile à utiliser et assez performante. J'ai écrit un test et l'ai fait tourner sur un ordinateur portable quadruple cœur i7 (8 threads) et j'ai obtenu ~4M d'opérations d'enqueue/dequeue par seconde. Une autre implémentation qui n'a pas été mentionnée jusqu'à présent est la file d'attente MPMC à l'adresse suivante http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue . J'ai fait quelques tests simples avec cette implémentation sur le même ordinateur portable avec 32 producteurs et 32 consommateurs. Elle est, comme annoncé, plus rapide que la file d'attente boost lockless.

Comme la plupart des autres réponses l'indiquent, la programmation sans serrure est difficile. La plupart des implémentations ont des cas de figure difficiles à détecter qui nécessitent beaucoup de tests et de débogage pour les résoudre. Ces cas sont généralement résolus en plaçant soigneusement des barrières de mémoire dans le code. Vous trouverez également des preuves d'exactitude publiées dans de nombreux articles universitaires. Je préfère tester ces implémentations avec un outil de force brute. Tout algorithme sans verrou que vous envisagez d'utiliser en production doit être vérifié à l'aide d'un outil tel que http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html .

Answer 5

Il existe une série d'articles intéressants à ce sujet. sur DDJ . Pour montrer à quel point ce genre de choses peut être difficile, c'est une correction sur un article précédent qui s'est trompé. Assurez-vous de comprendre les erreurs avant de lancer votre propre )- ;