Changes between Initial Version and Version 1 of replication_distribution

Timestamp:

May 19, 2016, 7:19:31 PM (8 years ago)

Author:

alain

Comment:

--

replication_distribution

@@ +1 @@
+= Politique de réplication / distribution =
+
+La politique de réplication / distribution vise deux objectifs: renforcer la localité, et SURTOUT minimiser la contention.
+ * Pour les données non partagées ou read-only, (segments de type CODE, STACK) on cherche à les répliquer dans tous les clusters de l’architecture pour les rapprocher des thread utilisateurs.
+ * Pour les données partagées ( segments DATA, HEAP, MMAP), on cherche à les distribuer le plus uniformément possible dans tous les clusters pour éviter la contention.
+
+On fait l’hypothèse que - pour chaque processus P - le descripteur du processus P, et certaines structures qu’il contient
+telles que la table des pages (PT) et la liste des vsegs (VSL) sont répliquées dans tous les cluster qui contiennent
+au moins un thread de P. 
+
+1)  pour un processus utilisateur P
+
+Un vseg désigne une zone mémoire contigüe 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 
+s”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 public est enregistrés dans la liste des segments et dans la table des pages de tous les clusters actifs 
+(i.e. tous les clusters qui contiennent un thread de P).
+Pour maintenir la cohérence entre les tables de pages, chaque vseg public possède un cluster de référence, qui est le cluster 
+propriétaire du processus (i.e. le cluster Z où a été créé le processus). 
+Les réplicas du descripteurs de processus (et surtout les tables
+associées) autres que celui contenu dans le cluster de référence peuvent être considérées comme des caches read-only.
+
+- Un vseg peut être localised (toutes les pages du vseg sont mappées dans le même cluster),
+ou distributed (différentes pages sont mappées dans différents clusters en utilisant par exemple les bits de poids
+faibles comme clé de distribution). Les vsegs privés sont toujours localised. 
+
+Il existe sept types de vsegs, correspondant à des politiques de réplication/distribution différentes : 
+
+- CODE :           private / plusieurs vsegs / mêmes adresses virtuelles, même contenu, un vseg par cluster actif
+- STACK :          private / plusieurs vsegs / un vseg par thread de P, mappé dans le cluster hébergeant le thread 
+- DATA :             public  / un seul vseg / distributed
+- HEAP :            public  / un seul vseg / distributed 
+- REMOTE :      public  / plusieurs vsegs / chaque vseg localised (dans le cluster concerné par le remote_malloc(x,y) )
+- FILE :              public  / plusieurs vsegs / chaque vseg localised (dans le cluster contenant le fichier concerné par le mmap() )
+- ANON :           public  / plusieurs vsegs / chaque vseg distributed (associé à un mmap() anonyme )
+
+2) pour 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.
+
+- 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.
+
+Dans un segment public, le noyau peut définir des  structures répliquées homologues. 
+Si N est le nombre de clusters, une structure répliquées homologue est un ensemble de N structures identiques,
+de longueur fixe, implantées à des adresses physiques ne différant entre elles que par les bits de poids fort 
+définissant les coordonnées du cluster.
+
+On identifie (pour l’instant) les segments suivants
+
+- KDATA :     private
+- KCODE :   private
+- KSTACK :  private
+- KHEAP :    private
+- SHARED :  public
+
+———————————————————————————————
+B) Construction dynamique des tables de pages d’un processus
+———————————————————————————————
+
+1) Descripteur de vseg
+
+Un descripteur de vseg contient les informations suivantes :
+- TYPE : définit la politique de réplication/distribution (CODE / STACK / DATA / HEAP / HEAPXY / FILE / ANON)
+- FLAGS : définit les droits d’accès
+- VBASE : adresse virtuelle  de base
+- LENGTH : longueur du segment
+- BIN : pathname to the .elf file. (seulement pour les types DATA et CODE)
+- X,Y : coordonnées du cluster où est mappé le vseg (seulement pour un vseg localised)
+- MAPPER : radix-tree contenant les pages physiques allouées à ce vseg (seulement pour les types CODE, DATA, FILE).
+
+2) Descripteur de processus
+
+Dans chaque cluster, les différentes informations associées à un processus P sont regroupées dans le descripteur de processus. 
+Le PID (Process Identifier) est codé sur 32 bits, et il est unique dans le système : les 8 bits de poids fort contiennent 
+les coordonnées (X,Y) du cluster propriétaire Z, les 24 bits de poids faibles (LPID) contiennent le numéro local dans le cluster Z.
+Le descripteur d’un processus P et les tables qui lui sont associées ne sont répliqués que dans les clusters qui contiennent
+au moins un thread de P (appelés clusters actifs de P).
+
+Les principale informations stockées dans le descripteur processus sont les suivantes:
+- PID :  processus identifier (contient les coordonnées du cluster propriétaire)
+- PPID : parent processus identifier,
+- XMIN, XMAX, YMIN, YMAX : recrangle recouvrant tous les clusters actifs
+- PT : table des pages du processus,
+- VSL : liste des vsegs du processus,
+- FDT : table des fichiers ouverts du processus,
+- TRDL : liste des threads du processus,
+- ENV : variables d’environnement du processus,
+
+Le contenu des tables de pages évolue au cours du temps, et  n’est pas identique dans tous les clusters.
+En effet le contenu des tables P évolue différemment dans les clusters en fonction des
+défauts de pages causés par les threads de P s’exécutant dans les différents clusters. 
+De plus  le mapping des segments private (CODE et STACKS) varie d’un cluster à un autre.
+Pour ce qui concerne les vsegs public, seul le cluster de référence contient l’état complet du mapping.
+
+De même, le contenu des listes de vsegs évolue au cours du temps, et n’est pas identique dans tous les clusters.
+En effet chaque vseg private n’est enregistré que dans un seul cluster. 
+En revanche toutes les listes de vsegs doivent être identiques pour ce qui concerne les vsegs public.
+Pour ce qui concerne les vsegs public, tout ajout dynamique d’un nouveau vseg public ou toute extension
+doit être répercuté dans tous les clusters actifs.
+
+3) Enregistrement et destruction des vsegs
+ 
+La politique d’enregistrement et de destruction des vsegs dans les VSL(P,X) dépend du type de vseg:
+
+3.1) DATA 
+Ce type de vseg est enregistré dans la VSL(P,Z)) du cluster Z  propriétaire du processus P au moment de la création de P.
+Il est enregistré dans la VSL(P,A) d’un autre cluster A chaque fois qu’un thread de P est créé dans le cluster A,
+si ce cluster ne contenait pas encore de thread du processus P.
+La longueur est définie par le fichier .elf contenant le code binaire du processus.
+Il n’y a pas de cluster de mapping pour un vseg distributed.
+Ce type de vseg n’est détruit que lors de la destruction du processus.
+
+3.2) CODE
+Ce type de vseg est enregistré dans la VSL(P,Z) du cluster Z  propriétaire du processus P au moment de la création de P.
+Il est enregistré dans la VSL(P,A) d’un autre cluster A chaque fois qu’un thread de P est créé dans le cluster A,
+si ce cluster ne contenait pas encore de thread du processus P.
+La longueur est définie par le fichier .elf contenant le code binaire du processus.
+Le cluster de mapping est toujours le cluster local pour un vseg private.
+Ce type de vseg n’est détruit que lors de la destruction du processus.
+
+3.3) STACK
+Un vseg de type STACK est enregistré dans la VSL(P,X) du cluster X chaque fois qu’un thread est crée dans le cluster X 
+par le processus P. Les VSL(P,Y) des autres clusters Y n’ont pas besoin d’être mises a jour car un vseg STACK 
+dans un cluster X n’est ni connu ni accédé depuis un autre cluster Y. 
+La longueur est définie par un paramètre global de l’OS : MIN_STACK_SIZE.
+Le cluster de mapping est toujours le cluster local pour un vseg private.
+Ce type de vseg est éliminé de la VSL(P,X) lors de la destruction du thread.
+
+3.4) HEAP 
+Ce type de vseg est enregistré dans la VSL(P,Z) du cluster Z propriétaire du processus P au moment de la création de P.
+Il est enregistré dans la VSL(P,A) d’un autre cluster A chaque fois qu’un thread de P est créé dans le cluster A,
+si celui-ci ne contenait pas encore de thread du processus P.
+La longueur est un paramètre global de l’OS : STANDARD_MALLOC_HEAP_SIZE.
+Il n’y a pas de cluster de mapping pour un vseg distributed.
+Ce type de vseg n’est détruit que lors de la destruction du processus.
+
+3.5) REMOTE
+Ce type de vseg est enregistré dans la VSL(P,A) de tous les clusters A qui contiennent au moins un thread de P,
+au moment où un thread quelconque de P exécute un remote_malloc(x,y) dans un cluster K. 
+Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P, si un vseg de type REMOTE 
+n’existe pas déjà dans la VSL(P,K). Les arguments sont le PID, le type du vseg, les coordonnées (x,y), … To Be Completed … 
+Si ce type de vseg n’existe pas déjà dans la VSL(P,Z), le noyau de Z broadcaste une VSEG_REGISTER_BCRPC vers tous les
+clusters actifs de P.   
+La longueur est un paramètre global de l’OS : REMOTE_MALLOC_HEAP_SIZE.
+Le cluster de mapping est défini par les arguments (x,y) du remote_malloc().
+Ce type de vseg n’est détruit que lors de la destruction du processus.
+
+3.6) FILE 
+Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
+au moment où un thread quelconque de P exécute un mmap(file , size) dans un cluster K. 
+Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
+le type de vseg, le descripteur de fichier, la taille … To be completed …
+Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
+La longueur du vseg est définie par l’argument size du mmap().
+Le cluster de mapping est défini par l’argument file, et il est quelconque puisque le cache d’un fichier peut être placé
+sur n’importe quel cluster (répartition uniforme). 
+Ce type de vseg est  détruit lors de l’exécution du munmap(), en utilisant un mécanisme en deux RPC comme pour la création.
+
+3.7) ANON
+Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
+au moment où un thread quelconque de P exécute un mmap(anonyme , size) dans un cluster K. 
+Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
+le type de vseg, le descripteur de fichier, la taille … To be completed …
+Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
+La longueur du vseg est définie par l’argument size du mmap().
+Il n’y a pas de cluster de mapping pour un vseg distributed. 
+Ce type de vseg est  détruit lors de l’exécution du munmap(), en utilisant un mécanisme en deux RPC comme pour la création.
+
+4) Introduction d’une nouvelle entrée dans une Table de Pages PT(P,K)
+
+L’ajout d’une entrée dans une PT(P,K), pour un processus P dans un cluster K est la conséquence d’un défaut de page
+causé par n’importe quel thread du processus P s’exécutant dans le cluster K, sur le principe du “on-demand paging”. 
+Tous les threads d’un processus P placés dans un cluster K utilisent exclusivement la PT(P,K) locale, et reportent 
+le défaut de page  à l’instance locale du noyau. Le traitement du défaut de page dépend du type du segment :
+
+4.1) CODE 
+Il existe un vseg de ce type dans la VSL de tous les clusters contenant au moins un thread du processus P.
+Si le cluster K qui détecte le défaut de page est différent du cluster propriétaire du processus Z, le noyau du cluster K doit allouer 
+une page physique dans le cluster K. Pour initialiser cette page, il envoie une PT_MISS_RPC au cluster Z propriétaire du processus.
+Quand il obtient  le PTE stocké dans la PT(P,Z), il effectue un remote_memcpy() pour copier le contenu de la page physique 
+du cluster Z vers la page physique du cluster K. Il termine en introduisant le PTE manquant dans la PT(P,K).
+Si le cluster K est le cluster propriétaire de Z, il alloue une page physique, initialise cette page en s’adressant au système de fichier, 
+pour récupérer le contenu de la page manquante dans le cache du fichier .elf, et met à jour la PT(P,Z).
+
+QUESTION : dans le cluster propriétaire Z, faut-il faire une copie de la page du cache de fichier vers une autre page physique ? [AG]
+
+4.2) STACK
+Les vsegs STACK associées aux thread placées dans un cluster X sont mappées dans le cluster X,
+et sont gérés indépendamment les uns des autres dans les différents clusters.
+Le noyau du cluster X doit allouer une page physique, et l’enregistrer dans la PT (P,X) locale sans l’initialiser.
+Si l’adresse demandée tombe dans la dernière page disponible pour le vseg, la longueur du vseg STACK peut être dynamiquement
+localement augmentée dans la VSL(P,X) locale, si il y a de la place dans dans la zone de l’espace virtuel utilisée pour les piles.
+Comme suggéré par Franck, on peut imaginer une politique d’allocation par dichotomie utilisant deux arguments : MAX_STACK_SIZE
+définissant la longueur totale de la zone réservée aux piles, et MIN_STACK_SIZE définissant la longueur minimale d’une pile particulière.
+
+4.3) DATA
+Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
+Si le cluster K qui détecte le défaut de page est différent du cluster propriétaire Z, le noyau du cluster K envoie une PT_MISS_RPC
+au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante. 
+Quand il reçoit la réponse, il met à jour la PT(P,K). 
+Si le cluster qui détecte le défaut de page est le cluster propriétaire Z, il sélectionne un cluster cible M à partir des bits 
+de poids faible du VPN, et envoie au cluster M une RPC_PMEM_GET_SPP pour obtenir le PPN d’une page physique du cluster M.
+En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
+Le noyau du cluster Z s’adresse au système de fichier, pour récupérer le contenu de la page manquante dans le cache du fichier .elf,
+et initialise la page physique dans M au moyen d’un remote_memcpy(). Finalement, il met à jour la PT (P,Z).
+
+4.4) HEAP
+Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
+Si le cluster K qui détecte le défaut de page est différent du cluster propriétaire Z, le noyau du cluster K envoie une PT_MISS_RPC
+au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante. 
+Quand il reçoit la réponse, il met à jour la PT(P,K). 
+Si le cluster qui détecte le défaut de page est le cluster propriétaire Z, il sélectionne un cluster cible M à partir des bits 
+de poids faible du VPN, et envoie au cluster M RPC_PMEM_GET_SPP pour obtenir le PPN d’une page physique du cluster M.
+En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
+Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
+
+4.5) REMOTE
+Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
+Si le cluster K qui détecte le défaut de page est différent du cluster propriétaire Z, le noyau du cluster K envoie une PT_MISS_RPC
+au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante. 
+Quand il reçoit la réponse, il met à jour la PT(P,X). 
+Si le cluster qui détecte le défaut de page est le cluster propriétaire Z, il envoie au cluster M une RPC_PMEM_GET_SPP pour obtenir
+le PPN d’une page physique du cluster M.
+En réponse à cette RPC, le noyau du cluster M alloue une page physique, et renvoie le PPN de celle-ci.
+Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
+
+4.6) FILE
+Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
+Si le cluster qui détecte le défaut de page K est différent du cluster propriétaire Z, le noyau du cluster K envoie une PT_MISS_RPC
+au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante. 
+Quand il reçoit la réponse, il met à jour la PT(P,K).
+Si le cluster qui détecte le défaut de page est le cluster propriétaire Z, il envoie au cluster M qui contient le cache du fichier
+une GET_FILE_CACHE_RPC pour obtenir le PPN. Les arguments sont le PID, le descripteur du fichier, et l’index de la page dans le mapper.
+En réponse à cette RPC, le noyau du cluster M accède au mapper du vseg et retourne le PPN correspondant.
+Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
+
+4.7) ANON
+Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
+Le traitement d’un défaut de page est le même que pour un vseg HEAP.
+
+QUESTION : Les mécanismes décrits ci-dessus pour  les types DATA, HEAP, REMOTE et ANON utilisent une RPC_PMEM_GET_SPP,
+qui suppose que le noyau d’un cluster (M) peut “transmettre la propriété” d’une ou plusieurs pages physiques
+à un autre cluster (Z) pour la durée de vie d’un processus. Il faut définir une politique d’allocation/libération de pages de
+mémoire physique entre clusters… [AG]
+
+
+5) Invalidation d’une entrée dans une Table de Pages
+
+Dans un cluster Z, propriétaire d’un processus P, le noyau peut décider d’invalider une entrée d’une PT(P,Z). 
+Cela peut se produire par exemple en cas de pénurie de mémoire dans le cluster Z, ou simplement en cas de munmap(). 
+Sauf si le vseg concerné est de type STACK, l’entrée invalidée dans la PT(P,Z) doit aussi être invalidée
+dans les PT(P,K) des autre clusters. 
+Pour ce faire, le noyau du cluster Z doit broadcaster une PT_INVAL_BCRPC vers tous les autres clusters actifs de P.
+
+6) Optimisation des RPC broadcast
+
+Dans une RPC broadcast, tous les clusters destinataires (même ceux qui ne sont pas concernés)
+signalent la terminaison en incrémentant de façon atomique un compteur de réponses,  qui est scruté par le cluster initiateur.
+
+Pour réduire le nombre de destinatiares, le descripteur du processus P du cluster propriétaire Z peut maintenir quatre variables
+XMIN, XMAX, YMIN, YMAX définissant le rectangle minimal recouvrant tous les clusters actifs de P à tout instant. 
+Dans ce cas une RPC broadcast ne doit être envoyée qu’a (XMAX - XMIN + 1) * (YMAX - YMIN +1) destinataires.
+Ces variables sont mises à jour à chaque création de thread.
+
+7 ) Optimisation du traitement des PT_MISS
+
+Pour réduire le nombre de RPC causés par les défauts de page, le noyau d’un cluster X qui détecte un défaut de page peut
+utiliser un remote_read() dans la table PT(P,Z) du cluster de référence au lieu d’une PT_MISS_RPC. Ceci impose cependant d’utiliser un lock multi-lecteurs pour éviter un état incohérent dans le cas d’une transaction PT_INVAL_BC_RPC simultanée
+initiée par le cluster Z : Ce lock doit être pris systématiquement par le cluster propriétaire avant un PT_INVAL_BC_RPC, et par les autres clusters avant  un remore_read(). Il garantit que le PT_INVAL_BC_RPC  ne sera lancé qu’après la fin de tous les remote_read() en cours. Il garantit qu’aucun nouveau remote_read() ne sera plus accepté avant la completion du PT_INVAL_BC_RPC.