wiki:replication_distribution

Version 10 (modified by alain, 6 years ago) (diff)

--

Politique de réplication / distribution

La politique de réplication / distribution vise deux objectifs: renforcer la localité, et SURTOUT minimiser la contention.

  • Pour les informations read-only (segments de type CODE), on les réplique dans tous les clusters où elles sont utilisées.
  • Pour les données non partagées (segments de type STACK) on les place dans le même cluster que le thread utilisateur.
  • Pour les données partagées (segments de type DATA, HEAP, MMAP), on cherche à les distribuer le plus uniformément possible dans tous les clusters pour éviter la contention.

La technique générale permettant à l'OS de contrôler le placement et la réplication des informations sur les bancs mémoire physiques est la mémoire virtuelle paginée.

1) Types de segments pour un processus utilisateur

Un vseg désigne une zone mémoire contigue dans l’espace virtuel d’un processus, auxquels sont attachés certains attributs (droit d’accès, politique de réplication/distribution dans les différents clusters, cachabilité, etc.).

  • Un vseg est public quand il peut être accédé par n’importe quel thread du processus, quel que soit le cluster dans lequel le thread s’exécute. Il est private quand il n’est accédé que par les threads exécutant dans le même cluster que le cluster ou est mappé le vseg.
  • Un vseg private est entièrement mappé dans la mémoire physique du cluster K dans lequel il est accessible. Il est enregistré dans liste des segments et dans la table des pages du cluster K, mais pas dans les autres clusters.
  • Un vseg peut être localised (toutes les pages du vseg sont mappées dans le même cluster), ou distributed (différentes pages du même vseg sont mappées dans différents clusters en utilisant par exemple les bits de poids faibles comme clé de distribution). Un vseg private est toujours localised.

Pour chaque processus P, le descripteur du processus est répliqué dans tous les cluster qui contiennent au moins un thread de P. Les structures contenues dans le descripteur de processus telles que la table des pages (PT) et la liste des vsegs (VSL) sont partiellement répliquées, ce qui pose un problème de cohérence pour les vsegs public.

  • la copie locale de la liste des vsegs VSL(P,K) d'un process P dans un cluster K contient tous les vsegs private du cluster K, mais ne contient que les vsegs public qui ont effectivement été accédé par un thread de P s'exécutant dans le cluster K. Seul le cluster de référence contient la liste complète de tous les vsegs public définis pour le process P.
  • la copie locale de la table des pages PT(P,K) d'un processus P dans cluster K contient toutes les entrées correspondant aux pages private qui ont effectivement été mappées dans le cluster K, mais elle ne contient que entrées correspondant aux pages public qui ont effectivement été accédées par un thread de P s'exécutant dans K. Seule la table des pages du cluster de référence contient toutes les pages "public qui sont effectivement mappées en mémoire physique (quel que soit le cluster contenant la page physique).

Les vsegs private sont donc enregistrés uniquement dans les tables du cluster auquel ils appartiennent, mais les vsegs public ne sont enregistrés de façon certaine que dans les tables du cluster de référence. Les descripteurs de processus de P autres que celui contenu dans le cluster de référence sont des replica incomplets, et les tables associées peuvent être considérées comme des caches read-only.

Il existe six types de vsegs, correspondant à des droits d'accès ou des politiques de réplication/distribution différentes :

type nombre commentaire
CODE private localised un par cluster actif mêmes adresses virtuelles, même contenu
DATA public distributed un par processus données globales partagées
STACK private localised un par thread dans le cluster hébergeant le thread
HEAP public distributed un par mmap(anon) utilisé aussi par la lib malloc()
REMOTE public localised un par remote_malloc() utilisé par remote_malloc()
FILE public localised un par MMAP(file) dans le cluster contenant le fichier file

Pour un process P, les vsegs de type CODE et DATA sont enregistrés dans la VSL d'un cluster K au moment de la création du premier thread de P (main thread) dans le cluster K. Les vsegs de type STACK sont enregistrés dans dans la VSL d'un cluster K au moment de la création du thread dans le cluster K. Les vsegs de type HEAP, REMOTE, ou FILE sont enregistrés dans la VSL du cluster de référence Z lors des appels systèmes mmap() malloc(), car seul le cluster de référence peut allouer dynamiquement de la place dans l'espace virtuel du processus. Ils ne sont enregistrés dans la VSL des autres clusters que lors des défauts de page détectés par ceux-ci (on demand registration).

Les tables de page PT sont mises à jour progressivement en réponse aux défauts de page (on demand paging).

2) User process virtual space organisation

The virtual space of an user process P in a given cluster K is split in four zones called vzone. Each vzone contains one or several vsegs.

  1. The utils vzone has a fixed size, and is located in the lower part of the virtual space. It contains the three vsegs kentry, args, envs, whose sizes are defined by configuration parameters. These vsegs are set by the kernel each time a new process is created. The kentry vseg has CODE type and contains the code that must be executed to enter the kernel from user space. The args vseg has DATA type, and contains the process main() thread arguments. The envs vseg has DATA type and contains the process environment variables.
  1. The elf vzone has a variable size, and contains the text and and data vsegs containing the process binary code and global data. The size is defined in the .elf file and reported in the boot_info structure by the boot loader. It is located on top of the utils vzone
  1. The stack vzone has a fixed size, and is located in the upper part of the virtual space. It contains as many vsegs of type STACK as the max number of threads for a process in a single cluster. The total size is defined as CONFIG_VSPACE_STACK_SIZE * CONFIG_PTHREAD_MAX_NR.
  1. The heap vzone has a variable size, and occupies all space between the top of the elf vzone and the base of the stack zone. It contains all vsegs of type HEAP, REMOTE or FILE that are dynamically allocated by the reference VMM manager.

3) segments utilisés par le noyau

Les différentes instances du noyau ne travaillant qu’en adressage physique, les segments kernel sont définis dans l’espace d’adressage physique. Puisqu'il existe une instance du noyau par coeur, les différents segments du noyau - y compris les données globales - sont répliqués dans chaque cluster.

Un segment kernel est private quand il ne peut être accédé que par l’instance locale du noyau. Il est public quand il peut être accédé par n’importe quel instance du noyau.

On identifie (pour l’instant) les segments suivants

  • KDATA : private
  • KCODE : private
  • KSTACK : private
  • KHEAP : private
  • SHARED : public