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