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 :
-
Le tampon circulaire sans verrou est-il la solution ?
-
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.
0 votes
Je pense qu'il serait utile d'esquisser l'API que vous voulez que cette structure de données implémente.
1 votes
Une chose que j'ai apprise, c'est de prendre de gros morceaux de travail. Je ne connais pas la taille de vos éléments de travail, mais vous pouvez gagner en efficacité si vous pouvez produire de plus gros morceaux et consommer de plus gros morceaux. Vous pouvez également l'augmenter en consommant des morceaux de taille variable afin que les consommateurs ne terminent pas tous en même temps et ne se disputent pas la file d'attente des données.
0 votes
Il faut également se demander si vous avez besoin d'un seul tampon ou d'une série de tampons. Vous pourriez avoir des paires producteur/consommateur partageant un tampon, et lorsqu'un tampon est plein, le producteur ou le consommateur passe temporairement à un autre tampon ouvert. C'est une forme de vol de travail.
0 votes
@Dave l'api est vraisemblablement juste une méthode enqueue plus une méthode dequeue ... les deux étant des méthodes synchrones/bloquantes, c'est-à-dire que dequeue devrait bloquer s'il n'y avait rien dans la file d'attente, et enqueue bloquer si le tampon circulaire était plein.
3 votes
Les algorithmes efficaces sans verrou sont des flocons de neige uniques dont la découverte mérite généralement un article de recherche. Je ne vais pas tenter de répondre à cette question tant que le PO n'aura pas distingué ses besoins réels de ce qu'il pense être une solution.
0 votes
Zan Lynx : Oui, regrouper le travail peut réduire les frais de verrouillage. Je l'ai fait dans mes systèmes précédents. J'ai aussi une taille de regroupement dynamique basée sur la charge de travail. Cela a plutôt bien fonctionné, mais cette fois le débit de données est trop rapide pour que mon ancien système puisse le gérer, c'est pourquoi je dois repenser tout cela.
2 votes
Une milliseconde est un délai très rapide sur un Linux non modifié. Si un autre processus s'exécute, vous pouvez facilement le manquer. Vous devriez utiliser des priorités en temps réel, et même dans ce cas, je ne suis pas sûr que vous puissiez respecter ces délais de manière fiable. Etes-vous sûr que vous avez besoin d'être aussi réactif ? Pouvez-vous faire en sorte que seuls les producteurs soient aussi rapides, les mettre en œuvre, par exemple dans un pilote de périphérique, et assouplir les exigences imposées aux consommateurs ?
0 votes
Doug, ce que je voulais dire, c'est qu'une milliseconde supplémentaire fait une grande différence. Je n'ai pas fait de profilage pour voir si d'autres processus système pouvaient causer de la latence sur mon système, mais je pense qu'en moyenne la préemption par un processus système n'aura pas d'impact significatif.
0 votes
Pourquoi ne pas utiliser les sémaphores ? Pas de verrouillage/blocage, le consommateur ne se met en veille que lorsque le tampon est vide, le producteur lorsque le tampon est plein. Quel est le problème avec ça ?
0 votes
Si vous avez vraiment besoin d'un comportement en temps réel dur, cela vaut probablement la peine de chercher à exécuter le programme comme une tâche en temps réel dur sur un système d'exploitation en temps réel dur. Pour une version adaptée à Linux, jetez un coup d'oeil à Xenomai, qui vous permettra d'exécuter simultanément des processus en temps réel et des processus réguliers (temps réel doux/non réel) dans le même environnement.