🐱 👸🏽 👨🏻‍🎨 Planning in Go: Part II - The Go Scheduler 👩🏾‍⚕️ 🕌 🤞🏾

Bonjour, Habr! Il s'agit du deuxième article d'une série en trois parties, qui donnera une idée de la mécanique et de la sémantique du travail de l'ordonnanceur dans Go. Ce message concerne le planificateur Go.

Dans la première partie de cette série, j'ai expliqué les aspects du planificateur du système d'exploitation qui, à mon avis, sont importants pour comprendre et évaluer la sémantique du planificateur Go. Dans cet article, je vais expliquer à un niveau sémantique comment fonctionne le planificateur Go. Le Go Scheduler est un système complexe et les petits détails mécaniques ne sont pas importants. Il est important d'avoir un bon modèle de fonctionnement et de comportement de tout. Cela vous permettra de prendre les meilleures décisions d'ingénierie.

Votre programme démarre

Lorsque votre programme Go démarre, un processeur logique (P) lui est attribué pour chaque cœur virtuel défini sur la machine hôte. Si vous avez un processeur avec plusieurs threads matériels par noyau physique (Hyper-Threading), chaque thread matériel sera présenté à votre programme comme un noyau virtuel. Pour mieux comprendre cela, consultez le rapport système de mon MacBook Pro.

Vous pouvez voir que j'ai un processeur avec 4 cœurs physiques. Ce rapport ne divulgue pas le nombre de threads matériels par cœur physique. Le processeur Intel Core i7 dispose de la technologie Hyper-Threading, ce qui signifie que le noyau physique possède 2 threads matériels. Cela indique à Go que 8 cœurs virtuels sont disponibles pour exécuter des threads de système d'exploitation en parallèle. Pour vérifier cela, envisagez le programme suivant:

package main

import (
	"fmt"
	"runtime"
)

func main() {

    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

Lorsque j'exécute ce programme sur mon ordinateur, le résultat de l'appel de la fonction NumCPU () sera 8. Tout programme Go que j'exécute sur mon ordinateur obtiendra 8 (P).
Chaque P se voit attribuer un flux OS ( M ). Ce thread est toujours géré par l'OS, et l'OS est toujours responsable de placer le thread dans le noyau pour l'exécution. Cela signifie que lorsque je lance Go sur mon ordinateur, j'ai 8 threads disponibles pour faire mon travail, chacun étant lié individuellement à P.

Chaque programme Go reçoit également une Goroutine initiale ( G) Goroutine est essentiellement Coroutine, mais c'est Go, donc nous remplaçons la lettre C par G et obtenons le mot Goroutine. Vous pouvez considérer les Goroutines comme des threads au niveau de l'application, et ils ressemblent beaucoup aux threads du système d'exploitation. Tout comme les threads du système d'exploitation sont activés et désactivés par le noyau, les programmes de contexte sont activés et désactivés par le contexte.

Le dernier casse-tête concerne les files d'attente d'exécution. Il existe deux files d'attente d'exécution différentes dans le planificateur Go: la file d'attente d'exécution globale (GRQ) et la file d'attente d'exécution locale (LRQ). Chaque P se voit attribuer un LRQ qui contrôle les goroutins affectés à l'exécution dans le contexte de P. Ces goroutines s'allument et s'éteignent à partir du contexte M attribué à ce P. GRQ est destiné aux goroutines qui n'ont pas été attribuées à P. Il existe un processus pour déplacer les goroutines de GRQ à LRQ, dont nous discuterons plus tard.

L'image montre tous ces composants ensemble.

Planificateur coopératif

Comme nous l'avons dit dans le premier article, le planificateur OS est un planificateur préemptif. Essentiellement, cela signifie que vous ne pouvez pas prédire ce que le planificateur va faire à un moment donné. Le noyau prend des décisions et tout n'est pas déterministe. Les applications exécutées au-dessus du système d'exploitation ne contrôlent pas ce qui se passe à l'intérieur du noyau avec la planification, sauf si elles utilisent des primitives de synchronisation telles que des instructions atomiques et des appels mutex.

Le Go Scheduler fait partie du Go Runtime et le Go Runtime est intégré à votre application. Cela signifie que le planificateur Go fonctionne dans l'espace utilisateur du noyau. L'implémentation actuelle du planificateur Go n'est pas un préemptif, mais un planificateur interactif. Être un planificateur coopératif signifie que le planificateur a besoin d'événements clairement définis dans l'espace utilisateur qui se produisent à des points sûrs du code pour prendre des décisions de planification.

Ce qui est bien avec le planificateur collaboratif de Go, c'est qu'il a l'air et se sent proactif. Vous ne pouvez pas prédire ce que le planificateur Go va faire. Cela est dû au fait que la prise de décision pour ce planificateur ne dépend pas des développeurs, mais du temps d'exécution de Go. Il est important de considérer le planificateur Go comme un planificateur proactif, et puisque le planificateur n'est pas déterministe, il n'est pas trop difficile.

États de Gorutin

Tout comme les flux, les goroutines ont les mêmes trois états de haut niveau. Ils déterminent le rôle que le planificateur Go joue avec n'importe quel goroutine. Goroutin peut être dans l'un des trois états: en attente, prêt ou satisfaisant.

En attente : cela signifie que le goroutine est arrêté et attend que quelque chose continue. Cela peut se produire pour des raisons telles que l'attente du système d'exploitation (appels système) ou la synchronisation des appels (opérations atomiques et mutex). Ces types de retards sont la principale cause de mauvaises performances.

Préparation: cela signifie que goroutine veut du temps pour suivre les instructions assignées. Si vous avez beaucoup de goroutines qui ont besoin de temps, alors les goroutines devront attendre plus longtemps pour avoir du temps. De plus, le temps individuel que chaque goroutine reçoit est réduit à mesure que de plus en plus de goroutines se disputent le temps. Ce type de retard de planification peut également entraîner de mauvaises performances.

Accomplissement : cela signifie que la goroutine a été placée dans M et suit ses instructions. Le travail associé à la demande est terminé. C'est ce que tout le monde veut.

Changement de contexte

Le Go Scheduler nécessite des événements d'espace utilisateur bien définis qui se produisent à des points sécurisés du code pour changer de contexte. Ces événements et points de sécurité apparaissent dans les appels de fonction. Les appels de fonction sont essentiels aux performances du planificateur Go. Si vous exécutez des boucles étroites qui n'effectuent pas d'appels de fonction, vous provoquerez des retards dans le planificateur et la récupération de place. Il est impératif que les appels de fonction se produisent dans un délai raisonnable.

Il existe quatre classes d'événements qui se produisent dans vos programmes Go qui permettent au planificateur de prendre des décisions de planification. Cela ne signifie pas que cela se produira toujours lors de l'un de ces événements. Cela signifie que le planificateur obtient l'opportunité.

Utilisation du mot clé go
Éboueur
Appels système
Synchronisation

Utiliser le
mot clé go Le mot clé go est la façon dont vous créez goroutine. Dès qu'un nouveau goroutine est créé, il donne au planificateur la possibilité de prendre une décision de planification.

Garbage Collector (GC)
Puisque le GC fonctionne avec son propre ensemble de goroutines, ces gorutins ont besoin de temps sur M pour fonctionner. Cela oblige le GC à créer beaucoup de chaos dans la planification. Cependant, le planificateur est très intelligent dans ce que fait le goroutine, et il s'en servira pour prendre des décisions. Une solution raisonnable consiste à basculer le contexte vers goroutine, qui veut accéder à la ressource système, et à personne d'autre que lui pendant la récupération de place. Lorsque le GC fonctionne, de nombreuses décisions de planification sont prises.

Appels système
Si goroutine effectue un appel système qui le bloquera M, l'ordonnanceur peut basculer le contexte vers un autre goroutine, vers le même M.

Synchronisation
Si un appel à une opération atomique, un mutex ou un canal provoque le blocage de goroutine, l'ordonnanceur peut changer de contexte pour démarrer un nouveau goroutine. Une fois que le goroutine peut fonctionner à nouveau, il peut être mis en file d'attente et éventuellement revenir à M.

Appels système asynchrones

Lorsque le système d'exploitation sur lequel vous travaillez a la capacité de traiter un appel système de manière asynchrone, ce que l'on appelle un scrutateur réseau peut être utilisé pour traiter l'appel système plus efficacement. Ceci est réalisé en utilisant kqueue (MacOS), epoll (Linux) ou iocp (Windows) dans ces systèmes d'exploitation respectifs.

Les appels système réseau peuvent être traités de manière asynchrone par de nombreux systèmes d'exploitation que nous utilisons aujourd'hui. C'est là que le scrutateur de réseau se montre, car son objectif principal est de traiter les opérations réseau. En utilisant l'interrogateur de réseau pour les appels système réseau, le planificateur peut empêcher les goroutines de bloquer M pendant ces appels système. Cela permet de garder M disponible pour exécuter d'autres goroutines dans LRQ P sans avoir besoin de créer un nouveau M. Cela permet de réduire la charge de planification dans le système d'exploitation.

La meilleure façon de voir comment cela fonctionne est de regarder un exemple. La figure montre notre schéma de planification de base. Gorutin-1 est exécuté sur M, et 3 autres Gorutins attendent dans LRQ pour obtenir leur temps sur M. Le poller du réseau est inactif, et il n'a rien à faire.

Dans la figure suivante, Gorutin-1 (G1) souhaite effectuer un appel système réseau, donc G1 se déplace vers l'interrogateur réseau et est traité comme un appel système réseau asynchrone. Une fois que G1 a été déplacé vers le scrutateur réseau, M est maintenant disponible pour exécuter un autre goroutine à partir de LRQ. Dans ce cas, Gorutin-2 passe à M.

Dans la figure suivante, l'appel réseau système se termine par un appel réseau asynchrone et G1 revient à LRQ pour P. Après que G1 puisse être basculé à nouveau sur M, le code associé à Go, pour lequel il répond peut s'exécuter à nouveau. La grande victoire est qu'aucune Mme supplémentaire n'est requise pour effectuer des appels système réseau. Le poller réseau a un thread OS, et il traite via une boucle d'événement.

Appels système synchrones

Que se passe-t-il lorsque goroutine souhaite effectuer un appel système qui ne peut pas être exécuté de manière asynchrone? Dans ce cas, l'interrogateur réseau ne peut pas être utilisé, et le goroutine effectuant l'appel système bloquera M. C'est mauvais, mais il n'y a aucun moyen d'empêcher cela. Un exemple d'appel système qui ne peut pas être effectué de manière asynchrone est les appels système basés sur des fichiers. Si vous utilisez CGO, il peut y avoir d'autres situations où l'appel de fonctions C bloque également M.

Le système d'exploitation Windows peut effectuer des appels système asynchrones basés sur des fichiers. Techniquement, lorsque vous travaillez sous Windows, vous pouvez utiliser l'interrogateur réseau.

Voyons ce qui se passe avec un appel système synchrone (par exemple, des E / S de fichiers) qui bloquera M. La figure montre notre schéma de planification de base, mais cette fois G1 va effectuer un appel système synchrone qui bloquera M1.

Dans la figure suivante, le planificateur peut déterminer que G1 a provoqué un verrouillage M. À ce stade, le planificateur déconnecte M1 de P avec un blocage G1 toujours attaché. L'ordonnanceur introduit ensuite un nouveau M2 pour servir P. À ce stade, G2 peut être sélectionné dans LRQ et inclus dans le contexte M2. Si M existe déjà en raison d'un échange précédent, cette transition est plus rapide que la nécessité de créer un nouveau M.

L'étape suivante termine l'appel système de verrouillage effectué par G1. À ce stade, G1 peut retourner à LRQ et être servi à nouveau par P. M1 puis se met de côté pour une utilisation future si ce scénario devait être répété.

Vol de travail

Un autre aspect de l'ordonnanceur est qu'il s'agit d'un planificateur de vol de goroutine. Cela aide dans plusieurs domaines à soutenir une planification efficace. Premièrement, la dernière chose dont vous avez besoin est que M passe en état de veille, car dès que cela se produit, le système d'exploitation basculera M du noyau en utilisant le contexte. Cela signifie que P ne peut faire aucun travail, même s'il y a une Goroutine dans un état sain, jusqu'à ce que M revienne au noyau. Gorutin Theft aide également à équilibrer les intervalles de temps entre tous les Ps afin que le travail soit mieux réparti et exécuté plus efficacement.

Dans la figure, nous avons un programme Go multi-thread avec deux Ps servant chacun quatre G et un G dans GRQ. Que se passe-t-il si l'un des P dessert rapidement tous ses G?

De plus, P1 n'a plus de goroutines à exécuter. Mais il y a des goroutines en état de marche, aussi bien en LRQ pour P2 qu'en GRQ. C'est le moment où P1 a besoin de voler de la goroutine.

Les règles pour voler des goroutines sont les suivantes. Tout le code peut être consulté dans les sources d'exécution.

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

Ainsi, sur la base de ces règles, P1 devrait vérifier P2 la présence de goroutines dans son LRQ et prendre la moitié de ce qu'il trouve.

Que se passe-t-il si P2 finit de servir tous ses programmes et P1 n'a plus rien dans LRQ?

P2 a terminé tout son travail et doit maintenant voler les goroutines. Tout d'abord, il examinera le LRQ P1, mais ne trouvera aucun Goroutine. Il examinera ensuite GRQ. Là, il trouvera le G9.

P2 vole G9 à GRQ et commence à faire le travail. Ce qui est bien avec tout ce vol, c'est qu'il permet à M de rester occupé et de ne pas être inactif.

Exemple pratique

Avec la mécanique et la sémantique, je veux vous montrer comment tout cela se réunit pour que le planificateur Go puisse faire plus de travail au fil du temps. Imaginez une application multithread écrite en C, dans laquelle le programme gère deux threads de système d'exploitation qui s'envoient des messages. Il y a 2 fils dans l'image qui envoient le message dans les deux sens. Le thread 1 reçoit le noyau 1 contextuel et est maintenant en cours d'exécution, ce qui permet au thread 1 d'envoyer son message au thread 2.

De plus, lorsque le thread 1 termine d'envoyer le message, il doit maintenant attendre une réponse. Cela entraînera la déconnexion du thread 1 du contexte du noyau 1 et sa mise en attente. Dès que le thread 2 reçoit une notification de message, il passe dans un état sain. Maintenant, le système d'exploitation peut effectuer un changement de contexte et exécuter le thread 2 sur le noyau, qui se révèle être le noyau 2. Ensuite, le thread 2 traite le message et renvoie un nouveau message au thread 1.

Ensuite, le flux repasse au contexte lorsque le message du flux 2 est reçu par le flux 1. Maintenant, le flux 2 bascule de l'état d'exécution à l'état de veille, et le flux 1 passe de l'état de veille à l'état prêt et revient finalement à l'état d'exécution, ce qui lui permet de traiter et renvoyer un nouveau message. Tous ces changements de contexte et changements d'état prennent du temps, ce qui limite la vitesse du travail. Étant donné que chaque changement de contexte entraîne un délai d'environ 1000 nanosecondes et que nous espérons que le matériel exécute 12 instructions par nanoseconde, vous examinez 12 000 instructions qui ne sont plus ou moins exécutées lors de ces changements de contexte. Étant donné que ces flux se croisent également entre différents noyaux,La probabilité d'un délai supplémentaire de manque de ligne de cache est également élevée.

Sur la figure, il y a deux gorutins qui sont en harmonie l'un avec l'autre, transmettant le message d'avant en arrière. G1 obtient le commutateur de contexte M1, qui s'exécute sur Core 1, ce qui permet à G1 de faire son travail.

De plus, lorsque G1 a fini d'envoyer le message, il doit maintenant attendre une réponse. Cela entraînera la déconnexion de G1 du contexte M1 et sa mise en veille. Dès que G2 est averti du message, il passe dans un état sain. Le planificateur Go peut maintenant effectuer un changement de contexte et exécuter G2 sur M1, qui s'exécute toujours sur Core 1. Ensuite, G2 traite le message et renvoie un nouveau message à G1.

Dans l'étape suivante, tout bascule à nouveau lorsque le message envoyé par G2 est reçu par G1. Maintenant, le contexte G2 passe de l'état d'exécution à l'état d'attente, et le contexte G1 passe de l'état d'attente à l'état d'exécution et, enfin, revient à l'état d'exécution, ce qui lui permet de traiter et de renvoyer un nouveau message.

Les choses en surface ne semblent pas être différentes. Tous les mêmes changements de contexte et changements d'état se produisent, que vous utilisiez Streams ou Goroutines. Cependant, il existe une grande différence entre l'utilisation de Streams et de Gorutin, qui peut ne pas être évident à première vue.

Si goroutine est utilisé, les mêmes threads et noyau du système d'exploitation sont utilisés pour tous les traitements. Cela signifie que du point de vue du système d'exploitation, OS Flow ne passe jamais dans un état d'attente; jamais. Par conséquent, toutes ces instructions que nous avons perdues lors du changement de contexte lors de l'utilisation de flux ne sont pas perdues lors de l'utilisation de goroutin.

Essentiellement, Go a transformé le travail d'E / S / blocage en un travail lié au processeur au niveau du système d'exploitation. Étant donné que tout changement de contexte se produit au niveau de l'application, nous ne perdons pas les mêmes ~ 12 000 instructions (en moyenne) sur le changement de contexte que nous avons perdues lors de l'utilisation de flux. Dans Go, les mêmes changements de contexte vous coûtent ~ 200 nanosecondes ou ~ 2.4 mille commandes. Le planificateur permet également d'améliorer les performances de mise en cache des chaînes et de NUMA. C'est pourquoi nous n'avons pas besoin de plus de threads que de cœurs virtuels. Go peut faire plus de travail au fil du temps, car le planificateur Go essaie d'utiliser moins de threads et d'en faire plus sur chaque thread, ce qui permet de réduire la charge sur le système d'exploitation et le matériel.

Conclusion

Le Go Scheduler est vraiment incroyable dans la façon dont il prend en compte les subtilités du système d'exploitation et du matériel. La possibilité de transformer le fonctionnement des E / S / verrouillage en une opération liée au processeur au niveau du système d'exploitation nous permet d'obtenir de gros gains en utilisant plus de puissance du processeur au fil du temps. C'est pourquoi vous n'avez pas besoin de plus de threads d'OS que de noyaux virtuels. Vous pouvez raisonnablement vous attendre à ce que tout votre travail se fasse (avec liaison CPU et E / S / verrous) avec un thread OS par noyau virtuel. Cela est possible pour les applications réseau et autres applications qui n'ont pas besoin d'appels système qui bloquent les threads du système d'exploitation.

En tant que développeur, vous devez toujours comprendre ce que fait votre application en termes de type de travail. Vous ne pouvez pas créer un nombre illimité de goroutines et vous attendre à des performances incroyables. Moins c'est toujours plus, mais avec une compréhension de cette sémantique du planificateur Go, vous pouvez prendre de meilleures décisions d'ingénierie.

Planning in Go: Part II - The Go Scheduler