Serrure circulaire sans tampon

Je suis dans le processus de conception d'un système qui se connecte à un ou plusieurs flux de flux de données et de faire une analyse sur les données de déclencher des événements en fonction du résultat. Dans un typique multi-thread producteur/consommateur, de l'installation, je vais avoir plusieurs threads producteurs de mettre les données dans une file d'attente, et plusieurs consommateurs fils de la lecture des données, et les consommateurs ne sont intéressés que dans le dernier point de données, plus le nombre n de points. Le producteur threads vont bloquer si lente à la consommation ne peut pas suivre, et bien sûr des consommateurs threads bloc quand il n'y a pas non transformés, les mises à jour. À l'aide d'un typique simultanées de la file d'attente avec un lecteur/graveur de verrouillage fonctionnent bien, mais le taux de données pourrait être énorme, donc j'ai voulu réduire mon surcharge de verrouillage surtout écrivain serrures pour les producteurs. Je pense qu'une circulaire sans verrouillage de la mémoire tampon est ce dont j'avais besoin.

Maintenant deux questions:

Est circulaire sans verrouillage de la mémoire tampon la réponse?
Si oui, avant que je roule mes propres, savez-vous tout public mise en œuvre qui permettra de s'adapter à mon besoin?

Tous les pointeurs dans la mise en œuvre d'une circulaire sans verrouillage de la mémoire tampon sont toujours les bienvenus.

BTW, faire cela en C++ sur Linux.

Quelques informations supplémentaires:

Le temps de réponse est critique pour mon système. Idéalement, le consommateur threads souhaitez voir les mises à jour à venir dès que possible parce qu'un supplément de 1 milliseconde retard pourrait rendre le système de valeur, ou dont la valeur est beaucoup moins.

L'idée de design, je suis penchée vers est un semi-lock-gratuit tampon circulaire où le producteur thread mettre les données dans la mémoire tampon aussi vite qu'il le peut, appelons le chef de la mémoire tampon A, sans blocage, sauf si le tampon est plein, lors d'Une rencontre à la fin de tampon Z. Consommation des threads de chaque titulaire de deux pointeurs du tampon circulaire, P et P_n, où P est le fil de la mémoire tampon locale tête, et P_n est nième élément après P. Chaque thread consommateur de promouvoir ses P et P_n une fois terminé le traitement actuel P et la fin de pointeur de tampon Z est avancé, plus lent P_n. Lorsque P rattraper à Un, ce qui signifie plus de nouvelle mise à jour de processus, le consommateur tours et ne occupés à attendre pour faire avancer de nouveau. Si thread consommateur spin pendant trop longtemps, il peut être mis pour dormir et d'attendre une variable de condition, mais je suis d'accord avec la consommation prise de cycle du PROCESSEUR en attente de mise à jour parce que de ne pas augmenter mon temps de latence (je vais avoir plus de cœurs que les threads). Imaginez que vous avez une piste circulaire, et le producteur est en cours d'exécution en face d'un tas de consommateurs, la clé est de régler le système de sorte que le producteur est généralement en passant à seulement quelques pas d'avance sur les consommateurs, et la plupart de ces opérations peuvent être effectuées à l'aide d'un lock-gratuit techniques. Je comprends les détails de la mise en œuvre n'est pas simple...ok, très dur, c'est pourquoi je veux apprendre des erreurs des autres avant de faire un peu de mes propres.

Je pense qu'il serait utile si vous esquissez l'API que vous souhaitez que cette structure de données à mettre en œuvre.
Quelque chose que j'ai apprise, c'est prendre de gros morceaux de travail. Je ne sais pas la taille de vos éléments de travail, mais vous pouvez augmenter l'efficacité si vous pouvez produire des gros morceaux et consommer de gros morceaux. Vous pouvez aussi augmenter par la consommation de taille variable morceaux pour les consommateurs n'ont pas tous fini à la fois et affronter la file d'attente de données.
Une autre chose à penser est que si vous avez besoin d'un tampon ou d'une série de tampons. Vous pourriez avoir de producteur/consommateur paires partageant un tampon, et quand un tampon est plein, le producteur ou le consommateur passe temporairement à un autre tampon. C'est une forme de travail de voler.
l'api est probablement juste une mise en file d'attente méthode plus une file d'attente de la méthode ... deux d'entre eux étant synchrone/blocage de modes, à savoir dequeue devrait bloquer s'il n'y avait rien dans la file d'attente, et de mettre en file d'attente du bloc si le buffer circulaire étaient pleins.
Efficace sans verrouillage des algorithmes uniques flocons de neige dont la découverte habituellement mérite un article de recherche. Je ne vais pas tenter de répondre à cette question jusqu'à ce que l'OP se distingue par une des exigences réelles de ce qu'il pense d'une solution devrait ressembler.
Zan Lynx: Oui, s'emmitoufler travail peut réduire de verrouillage de frais généraux. J'ai cela dans mes précédents systèmes. J'ai également de la dynamique de regroupement de la taille de la base sur la charge de travail. Il a fonctionné assez bien, mais cette fois, le débit est trop rapide pour mon ancien système, c'est pourquoi j'ai à repenser l'ensemble de la chose.
Une milliseconde est très rapide, calendrier de l'échéance non modifiée de Linux. Si un autre processus à exécuter, alors vous pourriez facilement passer à côté. Vous devez utiliser des priorités en temps réel, et même alors, je ne suis pas sûr que vous pouvez répondre de façon fiable aux ces délais. Êtes-vous sûr que vous devez être que sensible? Pouvez-vous faire seulement les producteurs de fast, les mettent en œuvre par exemple un pilote de périphérique, et détendez-vous sur les exigences sur les consommateurs?
Doug, ce que je voulais dire c'est 1 milliseconde fera une grande différence. Je n'ai pas fait tout de profilage pour voir si d'autres processus du système peut-être causer la latence sur mon système, mais je pense que sur la moyenne de la préemption par le processus de système ne va pas avoir un impact significatif.
pourquoi ne pas simplement utiliser les sémaphores? Pas de verrouillage et de blocage, le consommateur ne va dormir lorsque le tampon est vide, producteur lorsque le tampon est plein. Quel est le mal?
Si vous avez vraiment besoin de dur-comportement en temps réel, c'est probablement la peine de regarder dans l'exécution du programme comme un dur en temps réel de la tâche sur une unité de système d'exploitation temps réel. Pour un Linux-friendly version, découvrez Xenomai, il vous permettra de courir en temps réel et régulier (soft real-time/non temps réel) processus simultanément dans le même environnement.

InformationsquelleAutor Shing Yip | 2009-05-15

algorithm c++concurrency lock-free multithreading

36

J'ai fait une étude particulière de sans verrouillage des structures de données dans les deux dernières années. J'ai lu la plupart des articles sur le sujet (il n'y a environ quarante ou bien que seulement environ dix ou quinze sont une vraie utilité 🙂

Autant que je sache, un lock-gratuit tampon circulaire n'a pas été inventé. Le problème sera de s'occuper de la situation complexe où un lecteur dépasse un écrivain ou vis-versa.

Si vous n'avez pas passé au moins six mois d'études sans verrouillage des structures de données, n'essayez pas d'écrire un vous-même. Vous vous trompez, et il peut ne pas être évident pour vous que des erreurs existent, jusqu'à ce que votre code ne fonctionne pas, après le déploiement, sur de nouvelles plateformes.

Je crois cependant qu'il existe une solution à votre exigence.

Vous devez le lier à un lock-free file d'attente avec un lock-gratuit-liste.

Le libre-liste va vous donner de pré-affectation et afin de parer à la (fiscalement cher) exigence d'un lock-free allocateur; lorsque le libre-la liste est vide, vous reproduire le comportement d'un tampon circulaire par instantanément la file d'attente un élément de la file d'attente et en l'utilisant à la place.

(Bien sûr, dans une serrure à base de mémoire tampon circulaire, une fois que le verrouillage est obtenu, l'obtention d'un élément est très rapide fondamentalement juste un déréférencement de pointeur - mais vous n'obtiendrez pas que, dans tous les sans verrouillage de l'algorithme; ils ont souvent d'aller bien sortir de leur façon de faire les choses; les frais généraux de l'échec d'un libre-liste pop suivie par une file d'attente est sur un pied d'égalité avec la quantité de travail tout sans verrouillage de l'algorithme devra faire).

Michael et Scott développé un très bon sans verrouillage de la file d'attente en 1996. Un lien ci-dessous va vous donner suffisamment de détails pour traquer le PDF de leur article; Michael et Scott, FIFO

Un lock-gratuit-liste est la plus simple sans verrouillage de l'algorithme et en fait, je ne pense pas que j'ai vu un papier réel pour elle.
- BTW, j'ai mis en place cette. liblfds.org
- Xavier: Le Michael et Scott FIFO ressemble beaucoup à celui que j'indépendamment mis en œuvre .net; il ne semble pas difficile. Si l' .net au moment de l'exécution et de garbage collector n'a pas de garantie que les objets ne seront jamais recyclés alors que les références existent, il aurait été dur pour empêcher l'ABA problème (Michael et Scott paper lien ci-dessus de ne pas mentionner cela), mais l' .net garbage collector à résoudre ce problème automatiquement. Par curiosité, comment avez-vous résolu l'ABA problème?
- les M&S en papier explicitement résout l'ABA problème, en utilisant l'aiguille du compteur de paires; "structure pointer_t {ptr: pointeur vers node_t, count: unsigned integer}". Le compteur est incrémenté lorsque cela est nécessaire, de sorte qu'il est presque impossible pour l'ACA à se produire.
- Xavier: Ah, j'ai un peu raté. Leur CAS semble supposer l'existence d'une instruction pour changer un deux-point struct; je suis absente d'une telle fonctionnalité .net.
- Je suis surpris. Double-mot de CAS est disponible dans l'API Win32. Si vous mettez en œuvre des dangers des pointeurs, je pense que vous pouvez toujours utiliser leur algorithme. Je vais essayer ça assez vite.
- Xavier: Double-mot CAS est exposé à des arguments de type "Long" seulement. Je peux penser à trois raisons: (1) Une structure contenant deux 32-bit éléments peut s'asseoir sur un étrange limite de 32 bits; (2) les plus utiles des scénarios impliquent le couplage d'une référence d'objet avec quelque chose, et pour une raison que les références de l'objet croître pour les 64 bits x64 (j'aurais quitté leur 32 bits, depuis+ de 2 milliards de les objets auraient été beaucoup plus que Windows 32 bits peut gérer); (3) Je ne suis pas sûr que le matériel va sérialiser un ACA qui se produit simutaneously avec un TAS sur la moitié.
- Dans Win32, il y a Interloqué*() appels de fonction API de tout, sauf de 64 bits ACA. 64-bit ACA (par exemple 128 bits atomiquement Tubé) a un type différent de prototype, en commençant par un caractère de soulignement, qui peut être pourquoi il n'est pas forcément présent. Je ne sais pas si ACA serialises correctement avec des TAS, mais je pense qu'il n' - le mécanisme de base est le verrou de la lignes de cache, de sorte que les ACA va essayer de verrouiller les deux lignes de cache alors que les CAS de verrouillage, d'un ACA remarquerez si quelqu'un a fermé la ligne de mémoire cache, c'est d'essayer d'obtenir.
- Notez qu'un sans verrouillage de longueur fixe (réseau sur la base, en fait) tampon circulaire, pour un seul lecteur et de l'écrivain, où le tampon est plein conduit à l'échec d'écrire, existe et a existé pendant une longue période.
- J'ai utilisé les lecteur/unique écrivain files d'attente souvent sur des systèmes embarqués. Aucune atomique primitives sont requis pour faire de la "volatilité" des variables, depuis chaque emplacement de stockage va être "possédée" par le lecteur ou l'auteur, et ni le lecteur et l'écrivain ne sera jamais laisser les autres voir illégitime de l'état.
- Je me demande si volatile est-elle suffisante? pourrait-il re-commande de problème? peut-barrières de la mémoire est-elle nécessaire?
- Différents compilateurs et les implémentations de faire des choses différentes avec des variables volatiles. Ce qui est nécessaire ici est surtout que si le thread 1 écrit deux variables X et Y, dans cet ordre, et si le thread 2 lit Y puis X, puis si le thread 2 voit la nouvelle valeur de Y, il faut aussi voir la nouvelle valeur de X. Sur les systèmes embarqués, où j'ai fait de telles choses, la volatilité des variables de fournir de telles garanties (pas dur quand il n'y a qu'un seul processeur). Sur les systèmes multi-core, je crois que la plupart des compilateurs génèrent les barrières de la mémoire suffisante pour garantir le au-dessus de la sémantique de variables...
- ...bien que l'utilisation de variables seraient probablement aussi générer d'autres inutiles (mais coûteuse), les barrières de la mémoire ainsi. Personnellement, je soupçonne que les processeurs de plus en plus de cœurs, il sera nécessaire d'avoir de la mémoire-les primitives de synchronisation qui peut fonctionner à un niveau plus fin que les barrières de la mémoire (dont le coût augmente avec le nombre de cœurs).
- Si je comprends bien, la volatilité ne sont pas nécessaires sur un seul système central - il n'y a pas de sources externes changer les valeurs dans les variables; seuls les threads sur la même base.
- Sur les systèmes multi-core, je sais récente MSVCs sera pour la lecture d'un volatile avant de lire la barrière de mémoire et d'écriture de l'écriture, mais qui, je pense, est totalement dépendant du compilateur. J'écrirais explicit les barrières de la mémoire (en espérant que le compilateur va supprimer tous les doublons!)
- Même sur un seul système de base, au moins en C, volatile est nécessaire pour s'assurer que le compilateur ne sera pas tenter de réorganiser ou d'éliminer les lectures et les écritures. Par exemple, si SPI_* ne sont pas volatils, for(i=0;i<16;i++){SPI_DAT = tx[i]; temp=16000; do {} while(!SPI_RDY && --temp); if (!temp) break; rx[i] = SPI_DAT;} pourrait être réécrite (en supposant que ni temp ni i a été utilisé plus tard dans le code)if (SPI_RDY) {memcpy(rx,tx,16); SPI_DAT = tx[15];} else SPI_DAT = tx[0];. Le dernier code serait beaucoup plus "efficace", mais ne serait pas très efficace pour la lecture ou l'écriture de données SPI.
- J'ai peut-être tort, mais je pense que, à moins que le volatile est l'exécution d'une barrière de mémoire, il n'aura pas d'impact sur la re-commandent le comportement du compilateur ou de l'UC. Tous il va faire est de vous assurer de sa valeur est lue à partir de la mémoire plutôt que d'un registre ou d'une cache.
- IIRC, volatile les accès à la mémoire de ne pas être réorganisée avec d'autres volatile accès. Mais dans la norme ISO C, c'est tout ce que vous obtenez. Dans MSVC, volatile va bien au-delà de cela, mais ces jours, vous devriez simplement utiliser std::atomic avec memory_order_release ou seq_cst ou ce que vous voulez.
InformationsquelleAutor
32

Le terme de l'art de ce que vous voulez est un sans verrouillage de la file d'attente. Il y a un excellente série de notes avec des liens vers le code et papiers par Ross Bencina. Le gars dont le travail que j'ai le plus confiance est Maurice Herlihy (pour les Américains, il prononce son prénom comme "Morris").
- Une file d'attente n'est pas une mémoire tampon circulaire.
- Xavier: Non, mais un tampon circulaire est une file d'attente. Le problème des appels pour une file d'attente. Et le plus efficace de la mise en œuvre d'une file d'attente est comme... (attendre) un tampon circulaire. Dans tous les cas, si vous voulez la recherche, vous la recherche pour "lock-free file d'attente", pas "sans verrouillage tampon circulaire'.
- Je ne vois pas pourquoi juste ne pas utiliser les sémaphores? Pas de verrouillage et de blocage, le consommateur ne va dormir lorsque le tampon est vide, producteur lorsque le tampon est plein. Quel est le mal? Comment certains sans verrouillage de la file d'attente de mieux que cela?
- le lock-free file d'attente peut être mieux car il n'y a pas de verrou à agir comme un goulot d'étranglement des performances. L'OP a été spécialement préoccupé par la réduction de verrouillage de surcharge lorsque le conflit est très élevé. Les sémaphores n'aident pas au conflit. Une serrure sans la file d'attente ne.
- liblfds.org a un bien considéré multi-producteur/multi-consommateurs tampon circulaire de la file d'attente. Ce n'est pas techniquement lock-free: un producteur qui dort dans le milieu de l'ajout d'une entrée peut bloquer les consommateurs de voir quelque chose à d'autres producteurs. Voir stackoverflow.com/questions/45907210/... pour une analyse de l'état de garanties. C'est très bas de contention (aucun entre un producteur et un consommateur, si elle n'est pas vide ou plein), et peut-être ce que vous voulez dans la pratique..
InformationsquelleAutor Norman Ramsey
11

L'obligation pour les producteurs ou les consommateurs bloc si le tampon est vide ou plein suggère que vous devriez utiliser une normale de verrouillage de la structure de données, avec des sémaphores ou les variables de condition de faire les producteurs et les consommateurs de bloc jusqu'à ce que les données sont disponibles. Sans verrouillage code, en général, ne bloque pas sur de telles conditions - il spins ou abandonne les opérations qui ne peut pas être fait au lieu de la bloquer à l'aide de l'OS. (Si vous pouvez vous permettre d'attendre jusqu'à ce qu'un autre thread produit ou consomme de données, alors pourquoi en attente d'un verrou pour un autre thread pour terminer la mise à jour de la structure de données pire?)

Sur (x86/x64) Linux, intra-synchronisation des threads à l'aide de mutex est raisonnablement pas cher si il n'y a pas de conflit. Se concentrer sur la façon de réduire le temps que les producteurs et les consommateurs doivent se tenir sur leurs verrous. Étant donné que vous avez dit que vous ne se soucient que les N dernières données enregistrées points, je pense qu'un tampon circulaire serait faire raisonnablement bien. Cependant, je ne comprends pas vraiment comment cela s'inscrit dans le blocage de l'exigence et de l'idée de consommateurs fait de consommer (enlever) les données lues. (Voulez-vous consommateur de ne regarder le dernier N de points de données, et de ne pas les supprimer? Voulez-vous les producteurs à s'en soucient pas si les consommateurs ne peuvent pas suivre, et juste écraser les anciennes données?)

Aussi, comme Zan Lynx a commenté, vous pouvez agréger/tampon de vos données en gros morceaux quand vous avez beaucoup de venir dans. Vous pourriez tampon d'un nombre fixe de points, ou de toutes les données reçues dans un certain laps de temps. Cela signifie qu'il y aura moins d'opérations de synchronisation. Elle introduit la latence, cependant, mais si vous n'utilisez pas Linux temps réel, alors vous aurez à faire face à une étendue de toute façon.
- absolument d'accord avec le premier paragraphe. Ne vois pas de raison pour ne pas utiliser un sémaphore ici.
- Une application qui a consacré des threads producteurs et consommateurs dédiés threads (par exemple, tel que décrit par l'OP) ne peut jamais être appelée "lock-free". Dans un lock-application gratuite avec N threads, vous devriez être en mesure de suspendre indéfiniment toute combinaison de (N-1) ou de moins en moins de fils, et la demande devrait encore continuer à faire des progrès. Mais une dédiée à la consommation thread ne peut pas indéfiniment faire des progrès si tous les producteurs sont suspendus, et en cas de suppression du "produit" sur le sol n'est pas autorisé, alors qu'un producteur ne peut pas progresser si aucune des consommateurs est autorisé à s'exécuter.
- peut décrire un algorithme ou une structure de données (comme une file d'attente). en.wikipedia.org/wiki/Non-blocking_algorithm Il n'est généralement pas appliquée à l'ensemble de l'application. La suspension de tous les threads producteurs signifie simplement la file d'attente vide. Mais dans une serrure sans file d'attente, la suspension de l'une quelconque ou plusieurs threads, à tout moment, ne doit pas s'arrêter le autres threads d'être en mesure de mettre en file d'attente & file d'attente. (Ce n'est pas facile à atteindre, et les implémentations efficaces ont souvent un fil de "réclamer" un slot: stackoverflow.com/questions/45907210/...)
- Oui, un consommateur/producteur doit dormir s'ils trouvent la file d'attente vide/plein. Mais non, il ne veut pas toujours dire que vous devez mettre en œuvre la file d'attente traditionnelle de verrouillage, et surtout pas avec un gros cadenas pour l'ensemble de la structure de données. Cette file d'attente (de même que le commentaire précédent) n'est pas "lock-free" dans le sens technique du terme, mais il permet aux producteurs d'être totalement indépendante de consommateurs (pas de conflit), donnant potentiellement un meilleur débit que vous pourriez obtenir de verrouillage. Bon point sur efficace de réveil vide->non-vide cependant.
InformationsquelleAutor Doug
5

Il y a une assez bonne série d'articles sur ce sur DDJ. Comme un signe de la difficulté de ce genre de choses peut être, c'est une correction sur un précédent article qui a mal. Assurez-vous de comprendre les erreurs avant de vous lancer à votre propre )-;

InformationsquelleAutor Henk Holterman
5

La mise en œuvre dans la bibliothèque boost est utile d'examiner. Il est facile à utiliser et assez haute performance. J'ai écrit un test & il a couru sur un quad core i7 ordinateur portable (8 threads) et d'obtenir ~4M de mise en file/file d'attente des opérations à la seconde. Une autre mise en œuvre ne sont pas mentionnés jusqu'à présent est la MPMC file d'attente à http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue. J'ai fait quelques tests simples avec cette mise en œuvre sur le même ordinateur portable avec 32 producteurs et 32 des consommateurs. Il est, comme annoncé, plus rapide que le coup de pouce lockless file d'attente.

Comme la plupart des autres réponses de l'état lockless programmation est dur. La plupart des implémentations sera difficile de détecter un coin de cas que de prendre un grand nombre de tests & de débogage pour le fixer. Ce sont généralement fixe avec attention le placement de barrières de mémoire dans le code. Vous trouverez également des preuves de l'exactitude publié de nombreux articles académiques. Je préfère tester ces implémentations avec une force brutale de l'outil. Tout lockless algorithme vous prévoyez sur l'utilisation dans la production doit être vérifiée de justesse à l'aide d'un outil comme http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html.

InformationsquelleAutor Alex
4

Une technique utile pour réduire la contention est de hachage les articles dans plusieurs files d'attente et ont chaque consommateur dédié à un "sujet".

Pour la plus récente du nombre d'éléments que vos consommateurs sont intéressés dans l' - vous ne voulez pas de verrouillage de l'ensemble de la file d'attente et d'itérer sur de trouver un élément à remplacer - juste de publier les articles des N-uplets, c'est à dire tous les N derniers éléments. Des points Bonus pour la mise en œuvre où le producteur de bloc sur la totalité de la file d'attente (lorsque les consommateurs ne peuvent pas suivre) avec un délai d'attente, la mise à jour de ses locaux tuple cache - de cette façon vous ne mettez pas de contre-pression sur la source de données.
- J'ai également considéré comme le patron/ouvrier modèle de thread où le patron fil de multidiffusion mises à jour de threads de travail' files d'attente privées. Je pense que c'est plus ou moins la direction vous allez. J'ai pour lui donner plus de bien, mais quand j'étais considérant qu'il est, patron/ouvrier semblait avoir trop de frais généraux, car tous les travailleurs doivent obtenir les mêmes mises à jour.
- Pas exactement ce que je veux dire dans le premier point est la tranche de votre flux entrant afin de ne pas tous les threads en concurrence pour le même verrouillage/file d'attente. Le deuxième point est la mise en cache sur le producteur de côté pour accueillir des pointes sur l'entrée et permettent également de ralentir les consommateurs de ne pas interrompre le producteur.
- Mais la logique métier exige que tous les thread de travail pour connaître toutes les données en streaming. Il n'y a qu'un seul type de données en provenance et à chaque point de données est tout aussi important, donc je ne peux pas vraiment la tranche de mon flux entrant et avoir des données différentes dans différentes files d'attente. Encaissement sur le producteur et le groupement des mises à jour du modèle de données pour prévenir les accaparer a été fait et il n'était pas assez pour supporter la charge.
- Quelle est la taille du domaine d'entrée? Si c'est quelque chose comme des données de marché dans le monde financier, vous avez limité, bien que grand, nombre d'articles et à seulement quelques types de mises à jour. Sont des travailleurs réactif aux événements d'entrée ou font-ils de leur propre traitement et seulement sondage pour vos commentaires lorsque cela est nécessaire?
- C'est quelque chose comme des données de marché dans le monde financier. Les travailleurs de faire leur propre traitement et ils ont un accès aléatoire à n chiffres de l'historique des mises à jour lorsque cela est nécessaire (n est un nombre configurable, mais ne changera pas pendant toute la durée de la procédure). Je voudrais concevoir un système qui fonctionne bien sur les deux grands et les petits n pour que je puisse avoir une base de code.
- Eh bien, vous pouvez main de n-tuples de consommateurs avec swap d'un pointeur (vous auriez besoin de s'inquiéter à propos de la mémoire des clôtures, etc. - ordonné atomique), mais ensuite, vous aurez dans des problèmes de gestion mémoire comme sur les dangers des pointeurs.
InformationsquelleAutor Nikolai Fetissov
4

Je suis d'accord avec cet article et vous déconseillons l'utilisation de lock-libre de structures de données. Relativement récent article sur la serrure sans files d'attente fifo est cette, de rechercher d'autres documents rédigés par le même auteur(s), il y a aussi une thèse de Doctorat sur Chalmers concernant sans verrouillage des structures de données (j'ai perdu le lien). Cependant, vous ne dites pas que la taille de vos éléments sont -- sans verrouillage des structures de données travailler efficacement avec mot-de taille moyenne, de sorte que vous aurez à allouer dynamiquement de vos éléments s'ils sont plus grands qu'une machine mot (32 bits ou 64 bits). Si vous allouer dynamiquement des éléments, vous déplacer le (supposé, puisque vous n'avez pas profilé de votre programme et vous êtes essentiellement faire l'optimisation prématurée) goulot d'étranglement pour l'allocateur de mémoire, si vous avez besoin d'un lock-free allocateur de mémoire, par exemple, L'écoulement, et de les intégrer à votre application.
- Si vous pré-allouer vos éléments, vous n'avez pas le stress de l'allocateur.
InformationsquelleAutor zvrba
4

Sutter la file d'attente est sous-optimal, et il le sait. L'Art de la programmation Multicœur est une grande référence, mais ne faites pas confiance à la Java gars sur les modèles de mémoire, période. Ross liens que vous obtenez pas de réponse définitive car ils avaient leurs bibliothèques dans de tels problèmes, et ainsi de suite.

Faire sans verrouillage de la programmation est d'avoir des ennuis, sauf si vous voulez passer beaucoup de temps sur quelque chose qui vous sont clairement au-dessus de génie avant de résoudre le problème (à en juger par la description, c'est une commune de la folie de "à la recherche de la perfection" dans de cohérence de cache). Il faut des années et conduit à ne pas résoudre les problèmes et d'optimiser plus tard, une maladie commune.
- Voulez-vous envoyer un lien pour l'analyse de Sutter la file d'attente?
- c'est tout le DDJ et l'un des gars à la suite de son blogs profilée .. Les point chaud de CAS n'est pas nécessaire pour de nombreux scénarios et que vous pouvez battre ce genre de granularité fine toute la journée, même avec de simples échanges.
- Voulez-vous dire Dennis Lang? home.comcast.net/~lang.dennis/code/#ring
- C'est ça, merci ... Mais je crois qu'il pourrait devoir encore quelques courses. Heck, quelque chose comme sensibles, comme s'attendant implicite des obstacles ou spécifique ou une cohérence absolue-la compréhension est un problème en attente de se produire dans la production. Je ne crois pas que le niveau de détail résout donc plus l'accent sur l'application au niveau de la conception plutôt que de bas niveau de la plomberie lorsqu'/seulement-si cela fait sens/est-identifié à l'être. Je salue l'effort, les livres, tous; mais ses juste des articles sur une touche sujet MS a du mal à faire le bien pour le marché de masse PFX foule.
- Juste un avis, il est toujours un travail important à faire que de regarder dans la plomberie. En parallèle des efforts de répercuter à travers le conseil d'administration et pas seulement les files d'attente, ou en effet milieu des années 1990, le filetage DDJ articles sans cesse; c'est, à partir de NT à plus tard Unix Solaris et l'adoption de techniques similaires ou des travaux récents sur le C++. Ce dernier est et sera probablement prendre des heures pour compléter et luttent encore le fait pas propre OO-post P2-Pro-comme de l'univers est raisonnable..
- Dennis site a déménagé à l' landenlabs.com/code/ring/ring.html - Elle a un verrouillage de l'anneau libre de tampon.
- que sans verrouillage de la mise en œuvre utilise volatile size_t m_rIndex, m_wIndx; au lieu de C++11 std::atomique pour les indices, mais il me semble que cela dépend de l'acquisition-charge / release magasin sur le comportement (par exemple, dans d'autres threads doivent voir le m_buffer[m_wIndex] = value magasin avant de voir m_wIndex = Next(m_wIndex)). Ainsi, il arrive de travailler sur des systèmes x86, mais s'arrête sur le BRAS/PowerPC/whatever. Il est également inefficace, parce qu'au lieu de chargement à partir de la volatile dans une variable locale, elle maintient le re-référencement de la volatilité de la valeur dans la Get() et Put() fonctions.
InformationsquelleAutor rama-jka toti
4

Je ne suis pas expert de matériel de modèles de mémoire et de verrouillage de libre-structures de données et j'ai tendance à éviter d'utiliser ces dans mes projets et je pars avec la traditionnelle verrouillé structures de données.

Cependant, j'ai récemment remarqué que la vidéo :
Lockless SPSC file d'attente basé sur l'anneau de la mémoire tampon

Ceci est basé sur de l'open source de haute performance de la bibliothèque Java appelé LMAX distruptor utilisé par un système d'échange : LMAX Distruptor

Basé sur la présentation ci-dessus, vous faire la tête et de la queue des pointeurs atomique et atomiquement vérifier l'état où la tête attrape la queue par derrière, ou vice versa.

Ci-dessous vous pouvez voir un très de base de C++11) mise en œuvre: la
```
//USING SEQUENTIAL MEMORY
#include<thread>
#include<atomic>
#include <cinttypes>
using namespace std;
#define RING_BUFFER_SIZE 1024  //power of 2 for efficient %
class lockless_ring_buffer_spsc
{
public :
lockless_ring_buffer_spsc()
{
write.store(0);
read.store(0);
}
bool try_push(int64_t val)
{
const auto current_tail = write.load();
const auto next_tail = increment(current_tail);
if (next_tail != read.load())
{
buffer[current_tail] = val;
write.store(next_tail);
return true;
}
return false;  
}
void push(int64_t val)
{
while( ! try_push(val) );
//TODO: exponential backoff /sleep
}
bool try_pop(int64_t* pval)
{
auto currentHead = read.load();
if (currentHead == write.load())
{
return false;
}
*pval = buffer[currentHead];
read.store(increment(currentHead));
return true;
}
int64_t pop()
{
int64_t ret;
while( ! try_pop(&ret) );
//TODO: exponential backoff /sleep
return ret;
}
private :
std::atomic<int64_t> write;
std::atomic<int64_t> read;
static const int64_t size = RING_BUFFER_SIZE;
int64_t buffer[RING_BUFFER_SIZE];
int64_t increment(int n)
{
return (n + 1) % size;
}
};
int main (int argc, char** argv)
{
lockless_ring_buffer_spsc queue;
std::thread write_thread( [&] () {
for(int i = 0; i<1000000; i++)
{
queue.push(i);
}
}  //End of lambda expression
);
std::thread read_thread( [&] () {
for(int i = 0; i<1000000; i++)
{
queue.pop();
}
}  //End of lambda expression
);
write_thread.join();
read_thread.join();
return 0;
}
```
- Utiliser une puissance de 2 pour votre size, de sorte que le % (modulo) est un peu juste au niveau du bit. Par ailleurs, la conservation d'un numéro de séquence dans votre slots serait de réduire les conflits entre le producteur et le consommateur. En cela, le producteur doit lire les write position, et vice-versa, de sorte que la ligne de cache contenant ces atomique variables de ping-pongs entre les cœurs. Voir stackoverflow.com/questions/45907210/... pour un logement de numéro de séquence manière. (C'est un multi-producteur multi-consommation de file d'attente et pourrait être grandement simplifiée à un seul producteur/consommateur file d'attente comme ça.)
- Je suis sûr que beaucoup de charges/stocke uniquement besoin memory_order_acquire ou release, pas la valeur par défaut seq_cst. C'est une grande différence sur x86, où seq_cst magasins besoin mfence (ou xchg), mais release magasins sont tout simplement x86 magasins. StoreLoad obstacles sont le plus cher de la barrière sur la plupart des autres architectures. (preshing.com/20120710/...)
- Il serait probablement mieux de mettre read après buffer dans la catégorie mise en page, il est dans une autre ligne de cache de write. Donc, les deux fils ne seront mémoire cache de lecture des lignes écrites par les autres, plutôt que tous les deux dans la même ligne de cache. En outre, ils doivent être size_t: il n'y a aucun point d'avoir 64 bits compteurs avec des pointeurs 32 bits. Et un type non signé rend modulo beaucoup plus efficace (godbolt.org/g/HMVL5C). Même uint32_t serait raisonnable pour presque toutes les utilisations. Il serait probablement préférable à un modèle de cette taille, ou d'allouer dynamiquement de la mémoire tampon.
- pourquoi modulo est plus efficace avec une puissance de 2?
- Parce que les ordinateurs utiliser les binaires des entiers, donc vous avez juste à garder le bas n bits avec un AND. par exemple,x % 8 = x & 7, et au niveau du bit ET est beaucoup moins cher que div, ou même des trucs que vous pouvez faire avec de la compilation constante de temps diviseurs.
InformationsquelleAutor Akin Ocal
2

Juste pour être complet: il y a bien testé sans verrouillage mémoire tampon circulaire dans OtlContainers, mais il est écrit en Delphi (TOmniBaseBoundedQueue est tampon circulaire et TOmniBaseBoundedStack est délimitée de la pile). Il y a également une surabondance de la file d'attente dans la même unité (TOmniBaseQueue). La surabondance de la file d'attente est décrit dans Dynamique sans verrouillage de file d'attente, en train de faire. La mise en œuvre initiale de la délimitée de la file d'attente (tampon circulaire) a été décrit dans Un lock-free file d'attente, enfin! mais le code a été mis à jour depuis.

InformationsquelleAutor
2

C'est un vieux thread, mais comme il n'a pas été mentionné, mais - il y a un lock-free, circulaire, 1 producteur -> 1 à la consommation, FIFO disponibles dans la JUCE C++ cadre.

https://www.juce.com/doc/classAbstractFifo#details

InformationsquelleAutor Nikolay Tsenkov
2

Découvrez Perturbateur (Comment l'utiliser) qui est un anneau de la mémoire tampon que plusieurs threads peuvent s'abonner à:

InformationsquelleAutor Rolf Kristensen
2

Bien que c'est une vieille question, personne n'a indiqué DPDK's lockless anneau de la mémoire tampon. C'est un haut débit de l'anneau de la mémoire tampon qui prend en charge plusieurs producteurs et plusieurs consommateurs. Il fournit également de consommateur et de producteur modes, et l'anneau de la mémoire tampon, c'est d'attendre sans en SPSC mode. Il est écrit en C et prend en charge plusieurs architectures.

En outre, il prend en charge en Vrac et l'Éclatement des modes où les éléments peuvent être mis en file d'attente/dequeued en vrac. La conception de laisser multiples de consommateurs ou de producteurs multiples écrire à la file d'attente à la même époque par simple de réserver l'espace à travers le déplacement atomique pointeur.
- Est-il vraiment sans verrouillage, ou que si un producteur / consommateur ne dort pas après avoir réclamé une fente mais, avant de terminer la mise en file/file d'attente? Voir cette analyse de la multi-producteur multi-consommation de file d'attente dans liblfds.org, qui fonctionne probablement assez similaire. Dans la pratique, il fonctionne très bien avec les bas de contention, mais il n'est pas techniquement sans verrouillage. De toute façon, upvoted car en vrac/mode rafale sonne comme une bonne idée.
- Je suis d'accord, il ne garantit pas la résiliation de sécurité et d'après [1024cores] (1024cores.net/home/lock-free-algorithms/introduction), c'est un blocage de l'algorithme et le système risque de ne pas progresser. Mais il devient attendre gratuit SPSC mode. - Je modifier la réponse pour en tenir compte.
- Jetez aussi un oeil à Dimitri de la mise en œuvre de la Délimitée MPMC file d'attente: 1024cores.net/home/lock-free-algorithms/queues/.... De nouveau ce n'est pas sans verrouillage, mais est lockless, et est très simple et efficace. Cependant, en termes de performance de la DPDK de la file d'attente en vrac/mode rafale peut atteindre jusqu'à plusieurs centaines de millions d'opérations par seconde en termes de débit en fonction de la taille des lots. La combinaison d'opérations atomiques et en lecture/écriture séquentielle rend très efficace.
InformationsquelleAutor Saman Barghi
1

Voici comment j'allais le faire:
- carte de la file d'attente dans un tableau
- garder l'état, de la prochaine lecture et à la prochaine prochaine écriture index
- garder un vide plein vecteur de bits autour de
Insertion consiste en l'utilisation d'un CAS avec un incrément de rouler sur la prochaine écriture. Une fois que vous avez un logement, ajouter de la valeur et puis définissez le vide/plein bits correspondant.

Déménagements exigent un contrôle de la peu avant de les tester sur underflows mais dans les autres, sont les mêmes que pour l'écrire, mais à l'aide de lecture d'index et de compensation du vide/plein bits.

Être averti,
1. Je ne suis pas expert en ces choses
2. atomique ASM ops semblent être très lent lorsque je l'ai utilisé, donc si vous vous retrouvez avec plus de quelques-uns d'entre eux, vous pourriez être plus rapide d'utiliser des verrous intégrés à l'intérieur de l'insérer/supprimer des fonctions. La théorie est que d'une seule atomique op pour saisir le verrou, puis (très) peu de non atomique ASM ops pourrait être plus rapide que la même chose fait par plusieurs atomique de la fpo. Mais pour faire ce travail nécessiterait manuel ou automatique inlineing donc, c'est tout un bloc court de l'ASM.
- Les opérations atomiques sont en effet lente en eux-mêmes. Ce qui les rend utiles, c'est qu'ils échelle.
- Si les opérations à l'intérieur de la serrure sont très petites (comme dans 5-10 lignes de l'ASM), vous pourriez encore être en avance à l'utilisation d'une stratégie de verrouillage, si vous écrivez de la serrure directement dans les sections critiques plutôt que comme un appel de fonction.
- Je suis confus. Une section critique pour moi est la section de code qui doit être en série exécuté. Le verrou est le mécanisme qui assure serialiality de l'exécution. Pourriez-vous m'expliquer ce que tu veux dire?
- Qu'est ce que c'est aussi bien pour moi. Voir modifier.
InformationsquelleAutor BCS

Vous pouvez essayer lfqueue

Il est simple à utiliser, il est circulaire conception de verrouillage gratuit

int *ret;
lfqueue_t results;
lfqueue_init(&results);
/** Wrap This scope in multithread testing **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
while (lfqueue_enq(&results, int_data) != 1) ;
/*Dequeue*/
while ( (ret = lfqueue_deq(&results)) == NULL);
//printf("%d\n", *(int*) ret );
free(ret);
/** End **/
lfqueue_clear(&results);

InformationsquelleAutor Oktaheta

0

Il y a des situations que vous n'avez pas besoin de verrouillage pour empêcher la condition de course, surtout quand vous avez un seul producteur et le consommateur.

Envisager de ce point de LDD3:

Soigneusement mis en œuvre, un tampon circulaire nécessite pas de verrouillage en l'absence de plusieurs producteurs ou des consommateurs. Le producteur est le seul fil qui est autorisé à modifier l'écriture de l'index et le tableau de l ' emplacement des points d'. Aussi longtemps que l'écrivain magasins une nouvelle valeur dans la mémoire tampon avant la mise à jour de l'écriture de l'index, le lecteur pourra toujours voir une vue cohérente. Le lecteur, à son tour, est le seul fil qui peut accéder à la lecture de l'index et la valeur qu'elle renvoie. Avec un peu de soins pour s'assurer que les deux pointeurs tout en n'excédant pas les uns les autres, le producteur et le consommateur peut accéder à la mémoire tampon simultanément avec aucune des conditions de course.

InformationsquelleAutor Dražen G.

Vous devez vous connecter pour publier un commentaire.