Techniquement, pourquoi les processus d'Erlang sont-ils plus efficaces que les threads du système d'exploitation?

170

Caractéristiques d'Erlang

De Erlang Programming (2009):

La concurrence Erlang est rapide et évolutive. Ses processus sont légers en ce que la machine virtuelle Erlang ne crée pas de thread de système d'exploitation pour chaque processus créé. Ils sont créés, planifiés et gérés dans la machine virtuelle, indépendamment du système d'exploitation sous-jacent. En conséquence, le temps de création du processus est de l'ordre de la microseconde et indépendant du nombre de processus existants simultanément. Comparez cela avec Java et C #, où pour chaque processus un thread de système d'exploitation sous-jacent est créé: vous obtiendrez des comparaisons très compétitives, avec Erlang surpassant largement les deux langages.

De la programmation orientée concurrence dans Erlang (pdf) (diapositives) (2003):

Nous observons que le temps nécessaire pour créer un processus Erlang est constant de 1µs jusqu'à 2500 processus; ensuite, il augmente jusqu'à environ 3µs pour jusqu'à 30 000 processus. Les performances de Java et C # sont indiquées en haut de la figure. Pour un petit nombre de processus, il faut environ 300 µs pour créer un processus. Créer plus de deux mille processus est impossible.

Nous voyons que pour jusqu'à 30 000 processus, le temps d'envoi d'un message entre deux processus Erlang est d'environ 0,8 µs. Pour C #, cela prend environ 50µs par message, jusqu'au nombre maximum de processus (qui était d'environ 1800 processus). Java était encore pire, pour jusqu'à 100 processus, il fallait environ 50 µs par message, puis il augmentait rapidement à 10 ms par message alors qu'il y avait environ 1000 processus Java.

Mes pensées

Je ne comprends pas parfaitement pourquoi les processus Erlang sont tellement plus efficaces pour générer de nouveaux processus et ont une empreinte mémoire beaucoup plus petite par processus. Le système d'exploitation et la machine virtuelle Erlang doivent faire la planification, les changements de contexte et garder une trace des valeurs dans les registres, etc.

Pourquoi les threads du système d'exploitation ne sont-ils pas implémentés de la même manière que les processus d'Erlang? Doivent-ils soutenir quelque chose de plus? Et pourquoi ont-ils besoin d'une plus grande empreinte mémoire? Et pourquoi ont-ils une reproduction et une communication plus lentes?

Techniquement, pourquoi les processus d'Erlang sont-ils plus efficaces que les threads du système d'exploitation en ce qui concerne le frai et la communication? Et pourquoi les threads du système d'exploitation ne peuvent-ils pas être implémentés et gérés de la même manière efficace? Et pourquoi les threads du système d'exploitation ont-ils une plus grande empreinte mémoire, ainsi qu'une génération et une communication plus lentes?

Plus de lecture

multithreading erlang green-threads lightweight-processes Jonas
la source
1
Avant d'essayer de comprendre la raison pour laquelle une hypothèse est vraie, vous devez établir si l'hypothèse est vraie - par exemple, étayée par des preuves. Avez-vous des références pour des comparaisons similaires démontrant qu'un processus Erlang est en fait plus efficace qu'un (disons) un thread Java sur une JVM à jour? Ou une application C utilisant directement le processus du système d'exploitation et la prise en charge des threads? (Ce dernier me semble très, très improbable. Le premier n'est que peu probable.) Je veux dire, avec un environnement suffisamment limité (le point de Francisco), c'est peut-être vrai, mais je voudrais voir les chiffres.
TJ Crowder
1
@Donal: Comme c'est le cas avec tant d'autres déclarations absolues. :-)
TJ Crowder
1
@Jonas: Merci, mais j'ai atteint la date (1998-11-02) et la version JVM (1.1.6) et je me suis arrêté. La JVM de Sun s'est pas mal améliorée au cours des 11,5 dernières années (et vraisemblablement l'interpréteur d'Erlang l'a également), en particulier dans le domaine du threading. (Juste pour être clair, je ne dis pas que l'hypothèse n'est pas vraie [et Francisco et Donal ont expliqué pourquoi Erland pourrait faire quelque chose là-bas]; je dis que cela ne devrait pas être pris au pied de la lettre sans être vérifié.)
TJ Crowder
1
@Jonas: "... mais je suppose que tu peux le faire à Erlang ..." C'est cette partie "devine", mec. :-) Vous devinez que la commutation de processus d'Erlang passe au-delà des milliers. Vous devinez qu'il le fait mieux que les threads Java ou OS. Deviner et le développement de logiciels ne sont pas une bonne combinaison. :-) Mais je pense avoir fait valoir mon point.
TJ Crowder
17
@TJ Crowder: Installez erlang et exécutez erl +P 1000100 +hms 100et tapez ensuite {_, PIDs} = timer:tc(lists,map,[fun(_)->spawn(fun()->receive stop -> ok end end) end, lists:seq(1,1000000)]).et attendez environ trois minutes pour obtenir le résultat. C'est si simple. Il faut 140us par processus et 1 Go de RAM entière sur mon ordinateur portable. Mais c'est directement sous forme de shell, ça devrait être mieux à partir du code compilé.
Hynek -Pichi- Vychodil

Réponses:

113

Il existe plusieurs facteurs contributifs:

  1. Les processus Erlang ne sont pas des processus OS. Ils sont implémentés par la machine virtuelle Erlang à l'aide d'un modèle de thread coopératif léger (préemptif au niveau Erlang, mais sous le contrôle d'un runtime planifié en coopération). Cela signifie qu'il est beaucoup moins coûteux de changer de contexte, car ils ne commutent que sur des points connus et contrôlés et n'ont donc pas besoin de sauvegarder l'intégralité de l'état du processeur (registres normal, SSE et FPU, mappage d'espace d'adressage, etc.).
  2. Les processus Erlang utilisent des piles allouées dynamiquement, qui commencent très petites et se développent si nécessaire. Cela permet de générer des milliers, voire des millions, de processus Erlang sans aspirer toute la RAM disponible.
  3. Erlang était autrefois à un seul thread, ce qui signifie qu'il n'y avait aucune obligation d'assurer la sécurité des threads entre les processus. Il prend désormais en charge SMP, mais l'interaction entre les processus Erlang sur le même planificateur / cœur est toujours très légère (il existe des files d'attente d'exécution distinctes par cœur).
Marcelo Cantos
la source
6
Pour votre 2ème point: Et si le processus n'est pas encore exécuté, il n'y a aucune raison de lui allouer une pile. De plus: Plusieurs astuces peuvent être jouées en tripotant le GC d'un processus tel qu'il ne collecte jamais de mémoire. Mais c'est avancé et quelque peu dangereux :)
JE DONNE DES RÉPONSES CRAP
3
À votre troisième point: Erlang applique des données immuables, donc l'introduction de SMP ne devrait pas affecter la sécurité des threads.
nilskp
@ nilskp, c'est vrai, erlang est aussi un langage de programmation fonctionnel. Il n'y a donc pas de données "variables", cela conduit à la sécurité des threads.
liuyang1
6
@nilskp: (RE: vous commentez le point 3…) Même si le langage lui-même a un système de types immuable, l'implémentation sous-jacente - passage de message, ordonnanceur, etc. - est une tout autre histoire. La prise en charge correcte et efficace de SMP ne s'est pas produite simplement en appuyant sur un commutateur.
Marcelo Cantos
@rvirding: Merci pour l'addendum de clarification. J'ai pris la liberté d'intégrer vos points dans le corps de ma réponse.
Marcelo Cantos
73

Après quelques recherches supplémentaires, j'ai trouvé une présentation de Joe Armstrong.

Depuis Erlang - logiciel pour un monde simultané (présentation) (à 13 min):

[Erlang] est un langage concurrent - j'entends par là que les threads font partie du langage de programmation, ils n'appartiennent pas au système d'exploitation. C'est vraiment ce qui ne va pas avec les langages de programmation comme Java et C ++. Ses threads ne sont pas dans le langage de programmation, les threads sont quelque chose dans le système d'exploitation - et ils héritent de tous les problèmes qu'ils ont dans le système d'exploitation. L'un des problèmes est la granularité du système de gestion de la mémoire. La gestion de la mémoire dans le système d'exploitation protège des pages entières de mémoire, de sorte que la plus petite taille d'un thread est la plus petite taille d'une page. C'est en fait trop gros.

Si vous ajoutez plus de mémoire à votre machine - vous avez le même nombre de bits qui protège la mémoire de sorte que la granularité des tables de pages augmente - vous finissez par utiliser, disons, 64 Ko pour un processus que vous savez exécuter dans quelques centaines d'octets.

Je pense qu'il répond sinon à toutes, au moins à quelques-unes de mes questions

Jonas
la source
2
En relation: stackoverflow.com/questions/2267545/…
Jonas
2
La protection de la mémoire sur les piles est là pour une raison. Erlang ne protège-t-il tout simplement pas les piles de différents contextes d'exécution via la MMU du processeur? (Et j'espère juste pour le meilleur?) Et si un thread utilise plus que sa petite pile? (Toutes les allocations de pile sont-elles vérifiées pour voir si une pile plus grande est nécessaire? La pile est-elle mobile?)
Thanatos
2
@Thanatos: Erlang ne permet pas aux programmes d'accéder à la mémoire ou de jouer avec la pile. Toutes les allocations doivent passer par le runtime géré, à la fois du tas et de la pile. En d'autres termes: la protection matérielle est inutile car elle protège contre des choses qui ne peuvent pas arriver de toute façon. Le langage est sécurisé pour les pointeurs, les piles, la mémoire et les types. Un processus ne peut pas utiliser plus que sa «petite pile» car la pile se développe selon les besoins. Vous pouvez le considérer comme l'opposé de minuscule: infiniment grand. (Mais paresseusement attribué.)
Jörg W Mittag
4
Vous devriez jeter un œil au système d'exploitation Singularity de Microsoft Research. Dans Singularity, tout le code, le noyau, les pilotes de périphérique, les bibliothèques et les programmes utilisateur s'exécutent dans l'anneau 0 avec tous les privilèges du noyau. L'ensemble du code, du noyau, des pilotes de périphériques, des bibliothèques et des programmes utilisateur s'exécute dans un seul espace d'adressage physique plat sans aucune protection de la mémoire. L'équipe a constaté que les garanties offertes par le langage sont bien plus solides que les garanties que la MMU peut offrir, et en même temps, l'utilisation de la MMU leur coûte jusqu'à 30% (!!!) de performances. Alors, pourquoi utiliser la MMU si votre langue le fait déjà de toute façon?
Jörg W Mittag
1
Le système d'exploitation OS / 400 fonctionne de la même manière. Il n'y a qu'un seul espace d'adressage plat pour tous les programmes. Et la plupart des langages actuellement utilisés ont les mêmes propriétés de sécurité (ECMAScript, Java, C♯, VB.NET, PHP, Perl, Python, Ruby, Clojure, Scala, Kotlin, Groovy, Ceylon, F♯, OCaml, le Partie "Objectif" de "Objective-C", la partie "++" de "C ++"). Sans le code C hérité et les fonctionnalités héritées de C ++ et d'Objective-C, nous n'aurions même plus besoin de mémoire virtuelle.
Jörg W Mittag
47

J'ai implémenté des coroutines dans l'assembleur et mesuré les performances.

La commutation entre les coroutines, alias les processus Erlang, prend environ 16 instructions et 20 nanosecondes sur un processeur moderne. En outre, vous connaissez souvent le processus vers lequel vous basculez (exemple: un processus recevant un message dans sa file d'attente peut être implémenté comme un transfert direct du processus appelant au processus de réception) afin que le planificateur n'entre pas en jeu, ce qui c'est une opération O (1).

Pour changer de thread de système d'exploitation, cela prend environ 500 à 1000 nanosecondes, car vous appelez le noyau. Le planificateur de threads du système d'exploitation peut s'exécuter dans le temps O (log (n)) ou O (log (log (n))), ce qui commencera à être perceptible si vous avez des dizaines de milliers, voire des millions de threads.

Par conséquent, les processus Erlang sont plus rapides et mieux évolutifs car à la fois l'opération fondamentale de commutation est plus rapide et le planificateur s'exécute moins souvent.

Surfer Jeff
la source
33

Les processus Erlang correspondent (approximativement) à des fils verts dans d'autres langues; il n'y a pas de séparation imposée par le système d'exploitation entre les processus. (Il peut bien y avoir une séparation imposée par la langue, mais c'est une protection moindre malgré qu'Erlang fasse un meilleur travail que la plupart des autres.) Parce qu'ils sont beaucoup plus légers, ils peuvent être utilisés beaucoup plus largement.

Les threads du système d'exploitation, d'autre part, peuvent être simplement planifiés sur différents cœurs de processeur et sont (principalement) capables de prendre en charge un traitement indépendant lié au processeur. Les processus du système d'exploitation sont comme les threads du système d'exploitation, mais avec une séparation renforcée du système d'exploitation. Le prix de ces fonctionnalités est que les threads du système d'exploitation et (encore plus) les processus sont plus chers.

Une autre façon de comprendre la différence est la suivante. Supposons que vous alliez écrire une implémentation d'Erlang au-dessus de la JVM (ce n'est pas une suggestion particulièrement folle) alors vous feriez de chaque processus Erlang un objet avec un état. Vous auriez alors un pool d'instances de Thread (généralement dimensionnées en fonction du nombre de cœurs dans votre système hôte; c'est un paramètre réglable dans les environnements d'exécution réels d'Erlang BTW) qui exécutent les processus Erlang. À son tour, cela répartira le travail à effectuer sur les ressources système réelles disponibles. C'est une façon assez soignée de faire les choses, mais qui dépend totalementsur le fait que chaque processus Erlang individuel ne fait pas grand-chose. C'est OK bien sûr; Erlang est structuré pour ne pas exiger que ces processus individuels soient lourds puisque c'est l'ensemble d'entre eux qui exécute le programme.

À bien des égards, le vrai problème est un problème de terminologie. Les choses qu'Erlang appelle processus (et qui correspondent fortement au même concept dans CSP, CCS, et en particulier le π-calcul) ne sont tout simplement pas les mêmes que les choses que les langages avec un héritage C (y compris C ++, Java, C #, et beaucoup d'autres) appellent un processus ou un fil. Il y a quelques similitudes (toutes impliquent une certaine notion d'exécution simultanée) mais il n'y a certainement pas d'équivalence. Soyez donc prudent lorsque quelqu'un vous dit «processus»; ils pourraient comprendre que cela signifiait quelque chose de complètement différent…

Boursiers Donal
la source
3
Erlang ne s'approche pas de Pi Calculus. Le calcul Pi suppose des événements synchrones sur des canaux qui peuvent être liés à des variables. Ce genre de concept ne correspond pas du tout au modèle Erlang. Essayez Join Calculus, Erlang est plus proche de cela même s'il doit toujours être capable de rejoindre nativement certains messages et autres. Il y avait un document de thèse (et un projet) nommé JErlang dédié qui l'a mis en œuvre.
Je donne des conseils terribles le
Tout dépend de ce que vous visualisez exactement le pi-calcul (et vous pouvez modéliser des canaux asynchrones avec des canaux synchrones plus des processus de tampon).
Donal Fellows
Vous dites simplement que les processus Erlang sont légers, mais vous n'expliquez pas pourquoi ils ont une empreinte plus petite (sont légers) et pourquoi ils ont de meilleures performances que les threads du système d'exploitation.
Jonas
1
@Jonas: Pour certains types de tâches (en particulier les tâches lourdes en calcul), les threads OS font mieux. Remarquez que ce ne sont généralement pas des tâches pour lesquelles Erlang est utilisé; Erlang se concentre sur un grand nombre de tâches de communication simples. L'un des avantages à faire cela est que dans le cas d'un groupe de tâches qui remettent un travail et attendent le résultat, tout cela peut être fait dans un seul thread OS sur un seul processeur, ce qui est plus efficace que avoir des changements de contexte.
Donal Fellows
Théoriquement, vous pouvez également rendre un thread OS très bon marché en utilisant une très petite pile et en contrôlant soigneusement le nombre d'autres ressources spécifiques aux threads allouées, mais c'est assez problématique en pratique. (Prédire les exigences de la pile est un peu un art noir.) Ainsi, à la place, les threads du système d'exploitation sont particulièrement conçus pour être optimaux dans le cas où ils sont moins nombreux (de l'ordre du nombre de cœurs de processeur) et où ils font plus quantités de traitement chacun.
Donal Fellows
3

Je pense que Jonas voulait quelques chiffres sur la comparaison des threads OS aux processus Erlang. L'auteur de Programming Erlang, Joe Armstrong, a testé il y a quelque temps l'évolutivité de la génération des processus Erlang vers les threads du système d'exploitation. Il a écrit un serveur Web simple dans Erlang et l'a testé contre Apache multi-thread (car Apache utilise des threads du système d'exploitation). Il existe un ancien site Web dont les données remontent à 1998. Je n'ai réussi à trouver ce site qu'une seule fois. Je ne peux donc pas fournir de lien. Mais l'information est là-bas. Le point principal de l'étude a montré qu'Apache maximisait un peu moins de processus 8K, tandis que son serveur Erlang écrit à la main traitait les processus 10K +.

Jurnell
la source
5
Je pense que vous parlez de celui-ci: sics.se/~joe/apachevsyaws.html Mais j'ai demandé comment erlang rend les threads si efficaces par rapport aux threads kerlenl.
Jonas
Le lien @Jonas est mort. Le dernier instantané est ici
alvaro g
1
L'article disait: "Apache meurt à environ 4 000 sessions parallèles. Yaws fonctionne toujours avec plus de 80 000 connexions parallèles."
Nathan Long
voir l'article complet sur citeseerx.ist.psu.edu/viewdoc/ ... En effet, il s'est avéré impossible de casser le serveur Erlang en utilisant 16 machines attaquantes - bien qu'il ait été facile d'arrêter le serveur Apache.
Bernhard
1

Parce que l'interpréteur Erlang n'a qu'à se soucier de lui-même, le système d'exploitation a beaucoup d'autres choses à craindre.

Francisco Soto
la source
0

l'une des raisons est que le processus erlang n'est pas créé dans le système d'exploitation, mais dans l'evm (machine virtuelle erlang), de sorte que le coût est moindre.

ratzily
la source