Voyons comment fonctionne la programmation simultanée et parallèle dans .Net, en utilisant le problème des philosophes de la restauration comme exemple. Un tel plan, de la synchronisation des threads / processus, au modèle des acteurs (dans les parties suivantes). L'article peut être utile pour une première connaissance ou pour rafraîchir vos connaissances.
Pourquoi être capable de faire ça? Les transistors atteignent leur taille minimale, la loi de Moore repose sur la limitation de la vitesse de la lumière, et donc la croissance est observée en quantité, plus de transistors peuvent être réalisés. Dans le même temps, la quantité de données augmente et les utilisateurs attendent une réaction immédiate des systèmes. Dans une telle situation, la programmation «normale», lorsque nous avons un thread d'exécution, n'est plus efficace. Il est nécessaire de résoudre en quelque sorte le problème de l'exécution simultanée ou compétitive. De plus, ce problème existe à différents niveaux: au niveau des flux, au niveau des processus, au niveau des machines du réseau (systèmes distribués). .NET dispose de technologies de haute qualité et éprouvées pour résoudre rapidement et efficacement ces problèmes.
Défi
Edsger Dijkstra a posé ce problème à ses élèves dès 1965. Le libellé établi est le suivant. Il y a un certain nombre (généralement cinq) de philosophes et autant de fourchettes. Ils sont assis à la table ronde, fourchettes entre les deux. Les philosophes peuvent manger dans leur assiette avec une nourriture sans fin, penser ou attendre. Pour manger le philosophe, vous devez prendre deux fourchettes (cette dernière partage la fourchette avec la première). Pour prendre et mettre une fourchette - deux actions distinctes. Tous les philosophes se taisent. La tâche est de trouver un tel algorithme qu'ils pensent tous et en ont marre même après 54 ans.
Tout d'abord, essayons de résoudre ce problème en utilisant l'espace partagé. Les fourchettes sont sur la table et les philosophes les prennent quand elles sont et les remettent. Il y a des problèmes de synchronisation, quand exactement prendre les bouchons? Que faire s'il n'y a pas de prise? et d'autres. Mais d'abord, lançons les philosophes.
Pour démarrer les threads, utilisez le pool de threads via la méthode Task.Run :
var cancelTokenSource = new CancellationTokenSource(); Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token); for (int i = 0; i < philosophersAmount; i++) { int icopy = i;
Pool de threads créé pour optimiser la création et la suppression de threads. Ce pool possède une file d'attente de tâches et le CLR crée ou supprime des unités d'exécution en fonction du nombre de ces tâches. Un pool pour tous les AppDomains. Ce pool doit être utilisé presque toujours, car vous n'avez pas besoin de vous soucier de créer, supprimer des threads, leurs files d'attente, etc. C'est possible sans pool, mais vous devez alors utiliser Thread directement, il est conseillé dans les cas où vous devez changer la priorité d'un thread, lorsque nous avons une longue opération, pour le premier plan d'un thread, etc.
Et la classe System.Threading.Tasks.Task permet simplement de travailler avec ce pool de threads (ou même de s'en passer). Il s'agit d'une opération asynchrone. En gros, c'est le même Thread , mais avec toutes sortes de commodités: la possibilité de lancer des tâches après un bloc d'autres tâches, de les renvoyer des fonctions, il est pratique de les interrompre, et bien d'autres. etc. Ils sont nécessaires pour prendre en charge les constructions asynchrones / en attente (modèle asynchrone basé sur les tâches, sucre syntaxique pour attendre le fonctionnement d'E / S). Nous en reparlerons.
CancelationTokenSource est nécessaire ici afin que le thread lui-même puisse être terminé par le signal du thread appelant.
Problèmes de synchronisation
Philosophes bloqués
Ok, on peut créer des threads, essayons de déjeuner:
Ici, nous essayons d'abord de prendre les fourchettes de gauche puis de droite, et si cela fonctionne, nous les mangeons et les remettons. Prendre une fourchette est atomique, c'est-à-dire deux flux ne peuvent pas prendre un en même temps (à tort: le premier lit que la prise est libre, le second aussi, le premier prend, le second prend). Pour ce faire, Interlocked.CompareExchange , qui doit être implémenté à l'aide d'une instruction de processeur ( TSL , XCHG ), qui bloque un morceau de mémoire pour la lecture et l'écriture atomiques séquentielles. Et SpinWait est équivalent à une construction while(true) avec seulement un peu de "magie" - le thread prend le processeur ( Thread.SpinWait ), mais transfère parfois le contrôle à un autre thread ( Thread.Yeild ) ou s'endort ( Thread.Sleep ).
Mais cette solution ne fonctionne pas, car les flux seront bientôt bloqués (pour moi dans une seconde): tous les philosophes prennent leur fourche gauche, mais pas celle de droite. Le tableau des fourches a alors des valeurs: 1 2 3 4 5.
Sur la figure, blocage des threads (blocage). Le vert indique l'exécution, le rouge indique la synchronisation et le gris indique le sommeil. Les losanges indiquent l'heure de début de la tâche.
La faim des philosophes
Bien qu'il ne soit pas nécessaire de penser particulièrement à la nourriture, vous devez obliger quiconque à abandonner la philosophie. Essayons de simuler la situation des flux de jeûne dans notre problème. La famine, c'est quand le ruisseau fonctionne, mais sans travail important, en d'autres termes, c'est la même impasse, seulement maintenant le ruisseau ne dort pas, mais cherche activement quelque chose à manger, mais il n'y a pas de nourriture. Afin d'éviter un blocage fréquent, nous remettrons la fiche si nous ne pouvions pas en prendre une autre.
Dans ce code, il est important que deux philosophes sur quatre oublient de mettre leur fork gauche. Et il s'avère qu'ils mangent plus de nourriture, tandis que d'autres commencent à mourir de faim, bien que les flux aient la même priorité. Ici, ils ne meurent pas de faim, car les mauvais philosophes remettent parfois leurs fourchettes. Il s'avère que les bons mangent environ 5 fois moins que les mauvais. Une petite erreur dans le code entraîne donc une baisse des performances. Ici, il convient de noter qu'une situation rare est possible lorsque tous les philosophes prennent la fourche gauche, il n'y a pas de droite, ils mettent la gauche, attendent, reprennent la gauche, etc. Cette situation est également la famine, plus comme une impasse. Je n'ai pas pu le répéter. Ci-dessous, une image d'une situation où deux mauvais philosophes ont pris les deux fourchettes et deux bons philosophes meurent de faim.
Ici, vous pouvez voir que les threads se réveillent parfois et essaient d'obtenir une ressource. Deux des quatre cœurs ne font rien (le graphique vert en haut).
La mort du philosophe
Eh bien, un autre problème qui peut interrompre le glorieux dîner des philosophes est si l'un d'eux meurt soudainement avec des fourchettes dans ses mains (et ils l'enterreront comme ça). Ensuite, les voisins seront laissés sans déjeuner. Vous pouvez NullReferenceException exemple de code pour ce cas vous-même, par exemple, une NullReferenceException levée après que le philosophe a pris les fourchettes. Et, soit dit en passant, l'exception ne sera pas traitée et le code appelant ne la détectera tout simplement pas (pour cela, AppDomain.CurrentDomain.UnhandledException , etc.). Par conséquent, les gestionnaires d'erreurs sont nécessaires dans les threads eux-mêmes et avec la terminaison correcte.
Serveur
Eh bien, comment pouvons-nous résoudre ce problème avec les impasses, la famine et la mort? Nous n'autoriserons qu'un seul philosophe à bifurquer, ajouter l'exclusion mutuelle des flux pour ce lieu. Comment faire Supposons qu'un serveur se trouve à côté des philosophes qui autorise un philosophe à prendre des fourchettes. Comment faire de ce serveur et comment les philosophes lui posent des questions intéressantes.
La manière la plus simple est lorsque les philosophes demandent simplement constamment au serveur l'accès aux fourches. C'est-à-dire maintenant les philosophes n'attendront pas une prise à proximité, mais attendent ou demandent à un serveur. Tout d'abord, nous n'utilisons que l'espace utilisateur pour cela, nous n'utilisons pas d'interruptions pour appeler des procédures à partir du noyau (à leur sujet ci-dessous).
Solutions d'espace utilisateur
Ici, nous ferons la même chose que nous faisions avec une fourchette et deux philosophes, nous tournerons dans un cycle et attendrons. Mais maintenant, ce seront tous les philosophes et comme si une seule fourchette, c'est-à-dire on peut dire qu'il n'y aura que ce philosophe qui aura pris cette "fourchette d'or" au serveur. Pour cela, nous utilisons SpinLock.
private static SpinLock spinLock = new SpinLock();
SpinLock est un bloqueur, avec, grosso modo, le même while(true) { if (!lock) break; } while(true) { if (!lock) break; } , mais avec encore plus de "magie" que dans SpinWait (qui y est utilisé). Maintenant, il sait compter ceux qui attendent, les endormir un peu, et plus encore. etc. En général, fait tout son possible pour optimiser. Mais nous devons nous rappeler que c'est toujours le même cycle actif qui mange les ressources du processeur et conserve un thread qui peut conduire à la famine si l'un des philosophes devient une priorité sur les autres, mais n'a pas de fourche dorée (problème d'inversion de priorité). Par conséquent, nous l'utilisons uniquement pour des changements très très courts dans la mémoire partagée, sans aucun appel tiers, verrous imbriqués, etc. surprises.
Figure pour SpinLock . Les streams se "battent" constamment pour la fourchette dorée. Des échecs se produisent - dans la figure, la zone sélectionnée. Les noyaux ne sont pas pleinement utilisés: seulement environ 2/3 de ces quatre fils.
Une autre solution ici serait d'utiliser uniquement Interlocked.CompareExchange avec la même attente active, comme indiqué dans le code ci-dessus (chez les philosophes affamés), mais cela, comme déjà mentionné, pourrait théoriquement conduire au blocage.
À propos d' Interlocked il convient de dire qu'il existe non seulement CompareExchange , mais également d'autres méthodes de lecture et d'écriture atomiques. Et en répétant les modifications dans le cas où un autre thread parvient à effectuer ses modifications (lecture 1, lecture 2, écriture 2, écriture 1 est mauvaise), il peut être utilisé pour des modifications complexes d'une valeur (motif interverrouillé).
Solutions en mode noyau
Pour éviter de perdre des ressources dans une boucle, voyons comment vous pouvez bloquer un flux. En d'autres termes, en poursuivant notre exemple, nous verrons comment le serveur endort le philosophe et ne le réveille qu'en cas de besoin. Voyons d'abord comment procéder via le mode noyau du système d'exploitation. Toutes les structures se révèlent souvent plus lentes que celles de l'espace utilisateur. Plusieurs fois plus lent, par exemple AutoResetEvent peut être 53 fois plus lent que SpinLock [Richter]. Mais avec leur aide, vous pouvez synchroniser les processus à travers le système, gérés ou non.
La construction principale ici est le sémaphore proposé par Dijkstroy il y a plus d'un demi-siècle. Un sémaphore est, en termes simples, un entier positif contrôlé par un système, et deux opérations sur lui - augmenter et diminuer. Si la réduction ne fonctionne pas, zéro, le thread appelant est bloqué. Lorsque le nombre est augmenté par un autre thread / processus actif, les threads sont ignorés et le sémaphore diminue à nouveau du nombre de ceux passés. Vous pouvez imaginer des trains dans un goulot d'étranglement avec un sémaphore. .NET propose plusieurs conceptions avec des fonctionnalités similaires: AutoResetEvent , ManualResetEvent , Mutex et Semaphore lui-même. Nous utiliserons AutoResetEvent , c'est la plus simple de ces constructions: seules deux valeurs sont 0 et 1 (false, true). Sa méthode WaitOne() bloque le thread appelant si la valeur était 0, et si 1, puis s'abaisse à 0 et la saute. Et la méthode Set() augmente à 1 et saute une attente, qui diminue à nouveau à 0. Elle agit comme un tourniquet dans le métro.
Nous compliquerons la solution et utiliserons le verrou pour chaque philosophe, et pas pour tout le monde à la fois. C'est-à-dire maintenant il peut y avoir plusieurs philosophes à la fois, et pas un. Mais encore une fois, nous bloquons l'accès à la table afin de prendre correctement les fourchettes, en évitant les courses (conditions de course).
Pour comprendre ce qui se passe ici, considérons le cas où le philosophe n'a pas pris les fourchettes, alors ses actions seront comme ça. Il attend l'accès à la table. L'ayant reçu, il essaie de prendre les fourchettes. Ça n'a pas marché. Il donne accès à la table (exclusion mutuelle). Et il passe son "tourniquet" ( AutoResetEvent ) (au début ils sont ouverts). Il entre à nouveau dans le cycle, car il n'a pas de fourches. Tente de les prendre et s'arrête à son tourniquet. Un voisin plus chanceux à droite ou à gauche, ayant fini de manger, déverrouille notre philosophe, "ouvrant son tourniquet". Notre philosophe le passe (et il se ferme derrière) pour la deuxième fois. Tente pour la troisième fois de prendre les fourchettes. Bonne chance Et passe son tourniquet pour dîner.
Lorsqu'il y a des erreurs aléatoires dans un tel code (elles existent toujours), par exemple, un voisin est incorrectement spécifié ou le même objet AutoResetEvent est AutoResetEvent pour tout le monde ( Enumerable.Repeat ), alors les philosophes attendront les développeurs, car trouver des erreurs dans un tel code est une tâche assez difficile. Un autre problème avec cette solution est qu'elle ne garantit pas qu'aucun philosophe ne mourra de faim.
Solutions hybrides
Nous avons examiné deux approches de synchronisation lorsque nous restons en mode utilisateur et tournons en boucle et lorsque nous bloquons un thread via le noyau. La première méthode convient aux verrous courts, la seconde aux verrous longs. Souvent, vous devez d'abord attendre brièvement qu'une variable change dans la boucle, puis bloquer le thread lorsque l'attente est longue. Cette approche est mise en œuvre dans le conceptions hybrides. Il y a les mêmes constructions que pour le mode noyau, mais maintenant avec une boucle en mode utilisateur: SemaphorSlim , ManualResetEventSlim , etc. La construction la plus populaire ici est Monitor , car C # a une syntaxe de lock bien connue. Monitor est le même sémaphore avec une valeur maximale de 1 (mutex), mais avec un support pour l'attente dans une boucle, la récursivité, le modèle de variable de condition (à ce sujet ci-dessous), etc. Voyons une solution avec.
Ici, nous verrouillons à nouveau toute la table pour accéder aux fourches, mais maintenant nous débloquons tous les ruisseaux en même temps, et non les voisins lorsque quelqu'un a fini de manger. C'est-à-dire premièrement, quelqu'un mange et bloque les voisins, et quand celui-ci a fini, mais veut à nouveau manger tout de suite, il va dans la serrure et réveille ses voisins, parce que son temps d'attente est plus court.
Nous évitons donc les blocages et la famine d'un philosophe. Nous utilisons une boucle pour une courte attente et bloquons le flux pour une longue. Le déverrouillage AutoResetEvent fonctionne plus lentement que si seul le voisin était déverrouillé, comme dans la solution avec AutoResetEvent , mais la différence ne devrait pas être grande, car les threads doivent d'abord rester en mode utilisateur.
Le lock syntaxe lock mauvaises surprises. Ils recommandent d'utiliser Monitor directement [Richter] [Eric Lippert]. L'un d'eux est que le lock quitte toujours Monitor , même s'il y avait une exception, puis un autre thread peut changer l'état de la mémoire partagée. Dans de tels cas, il est souvent préférable d'aller dans l'impasse ou de terminer le programme en toute sécurité. Une autre surprise est que Monitor utilise des blocs de synchronisation ( SyncBlock ), qui se trouvent dans tous les objets. Par conséquent, si vous sélectionnez le mauvais objet, vous pouvez facilement obtenir un blocage (par exemple, si vous verrouillez la chaîne internée). Nous utilisons toujours un objet caché pour cela.
Condition Le modèle variable vous permet de mettre en œuvre de manière plus concise les attentes d'une condition complexe. En .NET, elle est incomplète, à mon avis, car en théorie, il devrait y avoir plusieurs files d'attente sur plusieurs variables (comme dans Posix Threads), et non sur un verrou. Ensuite, on pourrait les faire pour tous les philosophes. Mais même sous cette forme, cela vous permet de réduire le code.
Beaucoup de philosophes ou async / await
Ok, maintenant nous pouvons bloquer efficacement les threads. Mais que se passe-t-il si nous recevons beaucoup de philosophes? 100? 10000? Par exemple, nous avons reçu 100 000 demandes à un serveur Web. La création d'un flux pour chaque demande sera une surcharge, car tant de threads ne seront pas exécutés en parallèle. Seulement autant de cœurs logiques seront exécutés (j'en ai 4). Et tout le monde prendra simplement des ressources. Une solution à ce problème est le modèle asynchrone / attente. Son idée est qu'une fonction ne contient pas de flux, si vous devez attendre qu'elle continue. Et quand elle fait ça, quelque chose arrive, elle reprend son exécution (mais pas forcément dans le même fil!). Dans notre cas, nous attendrons la prise.
SemaphoreSlim a une méthode WaitAsync() pour cela. Voici une implémentation utilisant ce modèle.
async / await , Task . , , Task. , , . , , , , . . async / await .
. 100 4 , 8 . Monitor 4 , . 4 2. async / await 100, 6.8 . , 6 . Monitor .
Conclusion
, .NET . , , , . . , , , TPL Dataflow, Reactive , Software Transaction .
Les sources