gmp

L'une des plus grandes caractéristiques du langage Go est son support natif pour la concurrence. Il suffit d'un mot-clé pour démarrer une coroutine, comme le montre l'exemple ci-dessous.

import (
  "fmt"
  "sync"
)

func main() {
  var wg sync.WaitGroup
  wg.Add(2)

  go func() {
    defer wg.Done()
    fmt.Println("hello world!")
  }()
  go func() {
    defer wg.Done()
    fmt.Println("hello world too!")
  }()

  wg.Wait()
}

L'utilisation des coroutines de Go est si simple que pour les développeurs, il n'y a presque pas de travail supplémentaire à faire, c'est aussi l'une des raisons de sa popularité. Cependant, derrière cette simplicité se cache un ordonnanceur de concurrence très complexe qui soutient tout cela. Son nom, vous l'avez probablement déjà entendu, est composé de trois participants principaux : G (goroutine), M (thread système), P (processeur), d'où le nom d'ordonnanceur GMP. La conception de l'ordonnanceur GMP influence toute la conception du runtime Go, le GC, le poller réseau, on peut dire que c'est la pièce la plus centrale de tout le langage. En avoir une certaine compréhension pourrait être utile dans votre travail futur.

Histoire

Le modèle d'ordonnancement concurrent de Go n'est pas entièrement original, il a absorbé beaucoup d'expériences et de leçons du passé, à travers un développement et des améliorations constantes pour arriver à ce qu'il est aujourd'hui. Il s'est inspiré des langages suivants :

• Occam -1983
• Erlang - 1986
• Newsqueak - 1988
• Concurrent ML - 1993
• Alef - 1995
• Limbo - 1996

L'influence la plus importante vient du papier sur CSP (Communicate Sequential Process) publié par Hoare en 1978, dont l'idée fondamentale est que les processus échangent des données par communication. Parmi les langages de programmation ci-dessus, tous ont été influencés par la pensée CSP, Erlang étant l'exemple le plus typique d'un langage de programmation orienté messages, le célèbre middleware de file de messages open source RabbitMQ est écrit en Erlang. Aujourd'hui, avec le développement de l'informatique et d'Internet, le support de la concurrence est devenu un standard pour les langages modernes, et le langage Go, combinant la pensée CSP, est ainsi né.

Modèle d'ordonnancement

Commençons par une brève présentation des trois membres de GMP :

• G, Goroutine, désigne les coroutines du langage Go
• M, Machine, désigne les threads système ou threads de travail (worker thread), dont l'ordonnancement est assuré par le système d'exploitation
• P, Processor, ne désigne pas un processeur CPU, c'est un concept abstrait par Go, désignant un processeur travaillant sur un thread système, chargé d'ordonnancer les coroutines sur chaque thread système

Une coroutine est un thread plus léger, de plus petite taille, nécessitant moins de ressources, dont la création, la destruction et l'ordonnancement sont tous gérés par le runtime Go et non par le système d'exploitation, donc son coût de gestion est bien inférieur à celui des threads. Cependant, les coroutines sont aussi attachées aux threads, le temps d'exécution nécessaire aux coroutines vient des threads, et le temps d'exécution des threads vient du système d'exploitation. Le basculement entre différents threads a un certain coût, et la clé de la conception est de permettre aux coroutines d'utiliser efficacement le temps d'exécution des threads.

1:N

La meilleure façon de résoudre un problème est de l'ignorer. Puisque le basculement de threads a un coût, il suffit de ne pas basculer. Attribuer toutes les coroutines à un seul thread noyau, ainsi seul le basculement entre coroutines est concerné.

La relation entre threads et coroutines est 1:N. Cela a un inconvénient très évident : les ordinateurs modernes ont presque tous des CPU multi-cœurs, et une telle allocation ne peut pas utiliser pleinement la performance des CPU multi-cœurs.

N:N

Une autre méthode : un thread correspond à une coroutine, une coroutine peut profiter de tout le temps d'exécution de ce thread, et plusieurs threads peuvent aussi utiliser la performance des CPU multi-cœurs. Cependant, le coût de création et de basculement des threads est relativement élevé, et avec une relation un-à-un, on n'utilise pas l'avantage de la légèreté des coroutines.

M:N

M threads correspondent à N coroutines, avec M inférieur à N. Plusieurs threads correspondent à plusieurs coroutines, chaque thread correspond à plusieurs coroutines, et le processeur P est responsable de l'ordonnancement de la façon dont les coroutines G utilisent le temps d'exécution des threads. C'est une méthode relativement meilleure, et c'est le modèle d'ordonnancement que Go utilise encore aujourd'hui.

M ne peut exécuter des tâches qu'après avoir été associé à un processeur P. Go crée GOMAXPROCS processeurs, donc le nombre réel de threads pouvant exécuter des tâches est GOMAXPROCS, dont la valeur par défaut est le nombre de cœurs logiques du CPU de la machine actuelle. Nous pouvons aussi définir manuellement sa valeur.

• Via le code runtime.GOMAXPROCS(N), et peut être ajusté dynamiquement pendant l'exécution, l'appel provoque un STW direct.
• Définir la variable d'environnement export GOMAXPROCS=N, statique.

En pratique, le nombre de M sera supérieur au nombre de P, car le runtime a besoin qu'ils traitent d'autres tâches comme certains appels système, avec un maximum de 10000.

Ces trois participants GMP ainsi que l'ordonnanceur lui-même ont tous leur type correspondant dans le runtime, ils se trouvent tous dans le fichier runtime/runtime2.go. Leurs structures seront brièvement présentées ci-dessous pour faciliter la compréhension.

G

G est représenté dans le runtime par la structure runtime.g, c'est l'unité d'ordonnancement la plus basique du modèle d'ordonnancement. Sa structure est montrée ci-dessous, avec beaucoup de champs supprimés pour faciliter la compréhension.

type g struct {
    stack stack // offset known to runtime/cgo

    _panic   *_panic // innermost panic - offset known to liblink
    _defer   *_defer // innermost defer
    m        *m      // current m; offset known to arm liblink
    sched    gobuf

    goid       uint64
    waitsince  int64      // approx time when the g become blocked
    waitreason waitReason // if status==Gwaiting

    atomicstatus atomic.Uint32

    preempt       bool // preemption signal, duplicates stackguard0 = stackpreempt
    startpc       uintptr         // pc of goroutine function

    parentGoid uint64  // goid of goroutine that created this goroutine
    waiting    *sudog  // sudog structures this g is waiting on (that have a valid elem ptr); in lock order
}

Le premier champ est l'adresse de début et de fin de la mémoire de pile appartenant à cette coroutine.

type stack struct {
  lo uintptr
  hi uintptr
}

_panic et _defer sont des pointeurs vers les piles panic et defer respectivement.

_panic   *_panic // innermost panic - offset known to liblink
_defer   *_defer // innermost defer

m est le thread exécutant actuellement la coroutine g.

m        *m      // current m; offset known to arm liblink

preempt indique si la coroutine actuelle doit être préemptée.

preempt       bool // preemption signal, duplicates stackguard0 = stackpreempt

atomicstatus stocke la valeur d'état de la coroutine G, avec les valeurs possibles suivantes :

Nom	Description
_Gidle	Juste alloué, et non initialisé
_Grunnable	Indique que la coroutine actuelle peut s'exécuter, située dans la file d'attente
_Grunning	Indique que la coroutine actuelle exécute du code utilisateur
_Gsyscall	Un M lui a été attribué pour exécuter un appel système
_Gwaiting	Coroutine bloquée, la raison du blocage est indiquée ci-dessous
_Gdead	Indique que la coroutine actuelle n'est pas utilisée, peut venir de se terminer, ou d'être initialisée
_Gcopystack	Indique que la pile de la coroutine est en cours de déplacement, pendant cette période n'exécute pas de code utilisateur, ni ne se trouve dans la file d'attente
_Gpreempted	Se bloque pour entrer en préemption, attend d'être réveillé par le préempteur
_Gscan	Le GC scanne l'espace de pile de la coroutine, peut coexister avec d'autres états

sched stocke les informations de contexte de la coroutine pour restaurer le contexte d'exécution de la coroutine.

type gobuf struct {
  sp   uintptr
  pc   uintptr
  g    guintptr
  ctxt unsafe.Pointer
  ret  uintptr
  lr   uintptr
  bp   uintptr // for framepointer-enabled architectures
}

goid et parentGoid représentent les identifiants uniques de la coroutine actuelle et de la coroutine parente, startpc représente l'adresse de la fonction d'entrée de la coroutine actuelle.

M

M est représenté dans le runtime par la structure runtime.m, c'est une abstraction du thread de travail.

type m struct {
    id            int64
    g0 *g // goroutine with scheduling stack
    curg          *g           // current running goroutine
    gsignal       *g           // signal-handling g
    goSigStack    gsignalStack // Go-allocated signal handling stack
    p             puintptr     // attached p for executing go code
    nextp         puintptr
    oldp          puintptr // the p that was attached before executing a syscall
    mallocing     int32
    throwing      throwType
    preemptoff    string // if != "", keep curg running on this m
    locks         int32
    dying         int32
    spinning      bool // m is out of work and is actively looking for work
    tls           [tlsSlots]uintptr
    ...
}

Les champs principaux sont :

• id, l'identifiant unique de M
• g0, la coroutine avec la pile d'ordonnancement
• curg, la coroutine utilisateur en cours d'exécution sur le thread de travail
• gsignal, la coroutine responsable du traitement des signaux du thread
• p, l'adresse du processeur P
• spinning, indique que M est en état d'inactivité et disponible à tout moment

P

P est représenté dans le runtime par runtime.p, responsable de l'ordonnancement entre M et G.

type p struct {
    id     int32
    status uint32 // one of pidle/prunning/...
    schedtick   uint32     // incremented on every scheduler call
    syscalltick uint32     // incremented on every system call
    m      muintptr // back-link to associated m (nil if idle)
    runqhead uint32
    runqtail uint32
    runq     [256]guintptr
    runnext guintptr
    gFree struct {
        gList
        n int32
    }
    preempt bool
    ...
}

status représente l'état de P, avec les valeurs possibles suivantes :

Valeur	Description
_Pidle	P est en état d'inactivité, peut être assigné un M par l'ordonnanceur
_Prunning	P est associé à M et exécute du code utilisateur
_Psyscall	Indique que le M associé à P effectue un appel système
_Pgcstop	Indique que P est arrêté à cause du GC
_Pdead	La plupart des ressources de P sont retirées, ne sera plus utilisé

Initialisation

L'initialisation de l'ordonnanceur se situe dans la phase de démarrage du programme Go, responsable de ce démarrage est la fonction runtime.rt0_go, implémentée en assembleur dans le fichier runtime/asm_*.s.

La fonction runtime.schedinit est responsable de l'initialisation de l'ordonnanceur. Elle initialise les ressources nécessaires au fonctionnement de l'ordonnanceur au démarrage du programme.

Le nombre de P est par défaut le nombre de cœurs logiques du CPU, ensuite la valeur de la variable d'environnement. Enfin, la fonction runtime.procresize initialise les P.

Threads

Création

La création de M est effectuée par la fonction runtime.newm, qui accepte une fonction, un P et un id comme paramètres.

Sortie

Quand un thread doit sortir, il appelle runtime.mexit pour terminer le thread.

Pause

Quand M doit être mis en pause à cause de l'ordonnanceur, du GC, ou d'appels système, la fonction runtime.stopm est appelée pour mettre le thread en pause.

Coroutines

Le cycle de vie des coroutines correspond aux différents états de la coroutine. Comprendre le cycle de vie des coroutines est très utile pour comprendre l'ordonnanceur, car tout l'ordonnanceur est conçu autour des coroutines.

Création

La création d'une coroutine au niveau syntaxique ne nécessite qu'un mot-clé go suivi d'une fonction.

go doSomething()

Après compilation, cela devient un appel à la fonction runtime.newproc.

Sortie

Au moment de la création, Go a déjà placé la fonction runtime.goexit comme base de la pile de la coroutine, donc quand la coroutine termine son exécution, elle entre finalement dans cette fonction.

Appels système

Quand une coroutine G exécute du code utilisateur et effectue un appel système, des préparatifs sont nécessaires avant cela, effectués par la fonction runtime.entersyscall.

Suspension

Quand la coroutine actuelle est suspendue pour certaines raisons, son état passe de _Grunnable à _Gwaiting. Les raisons de suspension peuvent être un blocage sur un canal, select, un verrou, ou time.sleep.

Pile de coroutine

Les coroutines de Go sont des coroutines avec pile typiques. Chaque fois qu'une coroutine est démarrée, un espace de pile indépendant lui est alloué sur le tas, et il grandit ou rétrécit selon l'utilisation.

Allocation

Lors de la création d'une nouvelle coroutine, si aucune coroutine réutilisable n'est disponible, un nouvel espace de pile lui est alloué, avec une taille par défaut de 2KB.

Extension

La taille de pile par défaut des coroutines est de 2KB, suffisamment léger pour que le coût de création d'une coroutine soit très bas, mais ce n'est pas toujours suffisant. Quand l'espace de pile devient insuffisant, une extension est nécessaire.

Contraction

Quand G est dans les états _Grunnable, _Gsyscall, _Gwaiting, le GC scanne l'espace de pile de la coroutine. Quand l'espace de pile utilisé est inférieur à 1/4 de l'original, la pile est réduite à la moitié de sa taille originale.

Boucle d'ordonnancement

Dans la boucle d'ordonnancement, les sources de G selon leur priorité sont :

1. File locale de P
2. File globale
3. Poller réseau
4. Vol depuis la file locale d'autres P

Stratégie d'ordonnancement

Ordonnancement coopératif

L'idée de base de l'ordonnancement coopératif est de laisser G céder volontairement le droit d'exécution à d'autres G. Il y a deux méthodes principales :

1. Cession active dans le code utilisateur via runtime.Gosched()
2. Marquage de préemption avec insertion de code de détection dans l'en-tête des fonctions

Ordonnancement préemptif

Depuis Go 1.14, une stratégie d'ordonnancement préemptif basée sur les signaux a été ajoutée. C'est une stratégie de préemption asynchrone qui préempte les threads en envoyant des signaux via un thread asynchrone.

Résumé

En résumé, les moments de déclenchement de l'ordonnancement sont :

• Appels de fonction
• Appels système
• Surveillance système
• Ramasse-miettes, qui préempte aussi les coroutines s'exécutant trop longtemps
• Suspension de coroutine due à des canaux, verrous, etc.

Les stratégies d'ordonnancement sont principalement de deux grandes catégories : coopératif et préemptif. Le coopératif cède activement le droit d'exécution, le préemptif préempte de manière asynchrone le droit d'exécution. La coexistence des deux forme l'ordonnanceur actuel.