Changes between Version 2 and Version 3 of replication_distribution


Ignore:
Timestamp:
May 20, 2016, 4:24:09 PM (6 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • replication_distribution

    v2 v3  
    88 * 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.
    99
    10 
    11 == 1)  pour un processus utilisateur P ==
     10== 1)  pour un processus utilisateur ==
    1211
    1312Un '''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.).
     
    2726|| type        ||               ||                  ||   nombre                ||    commentaire                                              ||
    2827|| CODE     ||  private   || localised   || un par cluster actif || mêmes adresses virtuelles, même contenu  ||
    29 || STACK    ||  private  ||  localised   || un par thread         || dans le cluster hébergeant le thread             ||
     28|| STACK    ||  private  || localised    || un par thread         || dans le cluster hébergeant le thread             ||
    3029|| DATA       ||  public   || distributed || un par processus   || données globales partagées                         ||
    3130|| HEAP      ||  public   || distributed || un par processus   || utilisé pour le malloc() standard                    ||
     
    3433|| ANON     ||  public   || distributed || un par MMAP(anon) || équivalent au type HEAP                             ||
    3534
    36 2) pour le noyau,
     35== 2) pour le noyau ==
    3736
    38 Les différentes instances du noyau ne travaillant qu’en adressage physique, les segments kernel sont définis dans
    39 l’espace d’adressage physique.
     37Les différentes instances du noyau ne travaillant qu’en adressage physique, les segments kernel sont définis dans  l’espace d’adressage physique.
    4038
    41 - un segment kernel est private quand il ne peut être accédé que par l’instance locale du noyau.
    42 il est public quand il peut être accédé par n’importe quel instance du noyau.
     39 * 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.
    4340
    4441Dans un segment public, le noyau peut définir des  structures répliquées homologues.
     
    5552- SHARED :  public
    5653
    57 ———————————————————————————————
    58 B) Construction dynamique des tables de pages d’un processus
    59 ———————————————————————————————
    60 
    61 1) Descripteur de vseg
    62 
    63 Un descripteur de vseg contient les informations suivantes :
    64 - TYPE : définit la politique de réplication/distribution (CODE / STACK / DATA / HEAP / HEAPXY / FILE / ANON)
    65 - FLAGS : définit les droits d’accès
    66 - VBASE : adresse virtuelle  de base
    67 - LENGTH : longueur du segment
    68 - BIN : pathname to the .elf file. (seulement pour les types DATA et CODE)
    69 - X,Y : coordonnées du cluster où est mappé le vseg (seulement pour un vseg localised)
    70 - MAPPER : radix-tree contenant les pages physiques allouées à ce vseg (seulement pour les types CODE, DATA, FILE).
    71 
    72 2) Descripteur de processus
    73 
    74 Dans chaque cluster, les différentes informations associées à un processus P sont regroupées dans le descripteur de processus.
    75 Le PID (Process Identifier) est codé sur 32 bits, et il est unique dans le système : les 8 bits de poids fort contiennent
    76 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.
    77 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
    78 au moins un thread de P (appelés clusters actifs de P).
    79 
    80 Les principale informations stockées dans le descripteur processus sont les suivantes:
    81 - PID :  processus identifier (contient les coordonnées du cluster propriétaire)
    82 - PPID : parent processus identifier,
    83 - XMIN, XMAX, YMIN, YMAX : recrangle recouvrant tous les clusters actifs
    84 - PT : table des pages du processus,
    85 - VSL : liste des vsegs du processus,
    86 - FDT : table des fichiers ouverts du processus,
    87 - TRDL : liste des threads du processus,
    88 - ENV : variables d’environnement du processus,
    89 
    90 Le contenu des tables de pages évolue au cours du temps, et  n’est pas identique dans tous les clusters.
    91 En effet le contenu des tables P évolue différemment dans les clusters en fonction des
    92 défauts de pages causés par les threads de P s’exécutant dans les différents clusters.
    93 De plus  le mapping des segments private (CODE et STACKS) varie d’un cluster à un autre.
    94 Pour ce qui concerne les vsegs public, seul le cluster de référence contient l’état complet du mapping.
    95 
    96 De même, le contenu des listes de vsegs évolue au cours du temps, et n’est pas identique dans tous les clusters.
    97 En effet chaque vseg private n’est enregistré que dans un seul cluster.
    98 En revanche toutes les listes de vsegs doivent être identiques pour ce qui concerne les vsegs public.
    99 Pour ce qui concerne les vsegs public, tout ajout dynamique d’un nouveau vseg public ou toute extension
    100 doit être répercuté dans tous les clusters actifs.
    101 
    102 3) Enregistrement et destruction des vsegs
    103  
    104 La politique d’enregistrement et de destruction des vsegs dans les VSL(P,X) dépend du type de vseg:
    105 
    106 3.1) DATA
    107 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.
    108 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,
    109 si ce cluster ne contenait pas encore de thread du processus P.
    110 La longueur est définie par le fichier .elf contenant le code binaire du processus.
    111 Il n’y a pas de cluster de mapping pour un vseg distributed.
    112 Ce type de vseg n’est détruit que lors de la destruction du processus.
    113 
    114 3.2) CODE
    115 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.
    116 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,
    117 si ce cluster ne contenait pas encore de thread du processus P.
    118 La longueur est définie par le fichier .elf contenant le code binaire du processus.
    119 Le cluster de mapping est toujours le cluster local pour un vseg private.
    120 Ce type de vseg n’est détruit que lors de la destruction du processus.
    121 
    122 3.3) STACK
    123 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
    124 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
    125 dans un cluster X n’est ni connu ni accédé depuis un autre cluster Y.
    126 La longueur est définie par un paramètre global de l’OS : MIN_STACK_SIZE.
    127 Le cluster de mapping est toujours le cluster local pour un vseg private.
    128 Ce type de vseg est éliminé de la VSL(P,X) lors de la destruction du thread.
    129 
    130 3.4) HEAP
    131 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.
    132 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,
    133 si celui-ci ne contenait pas encore de thread du processus P.
    134 La longueur est un paramètre global de l’OS : STANDARD_MALLOC_HEAP_SIZE.
    135 Il n’y a pas de cluster de mapping pour un vseg distributed.
    136 Ce type de vseg n’est détruit que lors de la destruction du processus.
    137 
    138 3.5) REMOTE
    139 Ce type de vseg est enregistré dans la VSL(P,A) de tous les clusters A qui contiennent au moins un thread de P,
    140 au moment où un thread quelconque de P exécute un remote_malloc(x,y) dans un cluster K.
    141 Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P, si un vseg de type REMOTE
    142 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 …
    143 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
    144 clusters actifs de P.   
    145 La longueur est un paramètre global de l’OS : REMOTE_MALLOC_HEAP_SIZE.
    146 Le cluster de mapping est défini par les arguments (x,y) du remote_malloc().
    147 Ce type de vseg n’est détruit que lors de la destruction du processus.
    148 
    149 3.6) FILE
    150 Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
    151 au moment où un thread quelconque de P exécute un mmap(file , size) dans un cluster K.
    152 Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
    153 le type de vseg, le descripteur de fichier, la taille … To be completed …
    154 Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
    155 La longueur du vseg est définie par l’argument size du mmap().
    156 Le cluster de mapping est défini par l’argument file, et il est quelconque puisque le cache d’un fichier peut être placé
    157 sur n’importe quel cluster (répartition uniforme).
    158 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.
    159 
    160 3.7) ANON
    161 Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
    162 au moment où un thread quelconque de P exécute un mmap(anonyme , size) dans un cluster K.
    163 Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
    164 le type de vseg, le descripteur de fichier, la taille … To be completed …
    165 Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
    166 La longueur du vseg est définie par l’argument size du mmap().
    167 Il n’y a pas de cluster de mapping pour un vseg distributed.
    168 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.
    169 
    170 4) Introduction d’une nouvelle entrée dans une Table de Pages PT(P,K)
    171 
    172 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
    173 causé par n’importe quel thread du processus P s’exécutant dans le cluster K, sur le principe du “on-demand paging”.
    174 Tous les threads d’un processus P placés dans un cluster K utilisent exclusivement la PT(P,K) locale, et reportent
    175 le défaut de page  à l’instance locale du noyau. Le traitement du défaut de page dépend du type du segment :
    176 
    177 4.1) CODE
    178 Il existe un vseg de ce type dans la VSL de tous les clusters contenant au moins un thread du processus P.
    179 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
    180 une page physique dans le cluster K. Pour initialiser cette page, il envoie une PT_MISS_RPC au cluster Z propriétaire du processus.
    181 Quand il obtient  le PTE stocké dans la PT(P,Z), il effectue un remote_memcpy() pour copier le contenu de la page physique
    182 du cluster Z vers la page physique du cluster K. Il termine en introduisant le PTE manquant dans la PT(P,K).
    183 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,
    184 pour récupérer le contenu de la page manquante dans le cache du fichier .elf, et met à jour la PT(P,Z).
    185 
    186 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]
    187 
    188 4.2) STACK
    189 Les vsegs STACK associées aux thread placées dans un cluster X sont mappées dans le cluster X,
    190 et sont gérés indépendamment les uns des autres dans les différents clusters.
    191 Le noyau du cluster X doit allouer une page physique, et l’enregistrer dans la PT (P,X) locale sans l’initialiser.
    192 Si l’adresse demandée tombe dans la dernière page disponible pour le vseg, la longueur du vseg STACK peut être dynamiquement
    193 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.
    194 Comme suggéré par Franck, on peut imaginer une politique d’allocation par dichotomie utilisant deux arguments : MAX_STACK_SIZE
    195 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.
    196 
    197 4.3) DATA
    198 Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    199 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
    200 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.
    201 Quand il reçoit la réponse, il met à jour la PT(P,K).
    202 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
    203 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.
    204 En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
    205 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,
    206 et initialise la page physique dans M au moyen d’un remote_memcpy(). Finalement, il met à jour la PT (P,Z).
    207 
    208 4.4) HEAP
    209 Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    210 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
    211 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.
    212 Quand il reçoit la réponse, il met à jour la PT(P,K).
    213 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
    214 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.
    215 En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
    216 Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    217 
    218 4.5) REMOTE
    219 Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
    220 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
    221 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.
    222 Quand il reçoit la réponse, il met à jour la PT(P,X).
    223 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
    224 le PPN d’une page physique du cluster M.
    225 En réponse à cette RPC, le noyau du cluster M alloue une page physique, et renvoie le PPN de celle-ci.
    226 Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    227 
    228 4.6) FILE
    229 Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
    230 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
    231 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.
    232 Quand il reçoit la réponse, il met à jour la PT(P,K).
    233 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
    234 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.
    235 En réponse à cette RPC, le noyau du cluster M accède au mapper du vseg et retourne le PPN correspondant.
    236 Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    237 
    238 4.7) ANON
    239 Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    240 Le traitement d’un défaut de page est le même que pour un vseg HEAP.
    241 
    242 QUESTION : Les mécanismes décrits ci-dessus pour  les types DATA, HEAP, REMOTE et ANON utilisent une RPC_PMEM_GET_SPP,
    243 qui suppose que le noyau d’un cluster (M) peut “transmettre la propriété” d’une ou plusieurs pages physiques
    244 à 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
    245 mémoire physique entre clusters… [AG]
    246 
    247 
    248 5) Invalidation d’une entrée dans une Table de Pages
    249 
    250 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).
    251 Cela peut se produire par exemple en cas de pénurie de mémoire dans le cluster Z, ou simplement en cas de munmap().
    252 Sauf si le vseg concerné est de type STACK, l’entrée invalidée dans la PT(P,Z) doit aussi être invalidée
    253 dans les PT(P,K) des autre clusters.
    254 Pour ce faire, le noyau du cluster Z doit broadcaster une PT_INVAL_BCRPC vers tous les autres clusters actifs de P.
    255 
    256 6) Optimisation des RPC broadcast
    257 
    258 Dans une RPC broadcast, tous les clusters destinataires (même ceux qui ne sont pas concernés)
    259 signalent la terminaison en incrémentant de façon atomique un compteur de réponses,  qui est scruté par le cluster initiateur.
    260 
    261 Pour réduire le nombre de destinatiares, le descripteur du processus P du cluster propriétaire Z peut maintenir quatre variables
    262 XMIN, XMAX, YMIN, YMAX définissant le rectangle minimal recouvrant tous les clusters actifs de P à tout instant.
    263 Dans ce cas une RPC broadcast ne doit être envoyée qu’a (XMAX - XMIN + 1) * (YMAX - YMIN +1) destinataires.
    264 Ces variables sont mises à jour à chaque création de thread.
    265 
    266 7 ) Optimisation du traitement des PT_MISS
    267 
    268 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
    269 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
    270 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.