Changes between Version 1 and Version 2 of page_tables


Ignore:
Timestamp:
May 20, 2016, 5:56:05 PM (6 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • page_tables

    v1 v2  
    1 = Construction dynamique des tables de pages =
    2 
    3 1) Descripteur de vseg
    4 
     1= Réplication des tables de pages et des listes de vseg =
     2
     3== 1) Descripteur de vseg ==
     4
     5Puisque ALMOS-MK n'utilise pas la MMU paginée des processeurs, les table des pages ne sont utilisées que pour définir le mapping des vsegs des processus utilisateur.
    56Un descripteur de vseg contient les informations suivantes :
    6 - TYPE : définit la politique de réplication/distribution (CODE / STACK / DATA / HEAP / HEAPXY / FILE / ANON)
    7 - FLAGS : définit les droits d’accès
    8 - VBASE : adresse virtuelle  de base
    9 - LENGTH : longueur du segment
    10 - BIN : pathname to the .elf file. (seulement pour les types DATA et CODE)
    11 - X,Y : coordonnées du cluster où est mappé le vseg (seulement pour un vseg localised)
    12 - MAPPER : radix-tree contenant les pages physiques allouées à ce vseg (seulement pour les types CODE, DATA, FILE).
    13 
    14 2) Descripteur de processus
    15 
    16 Dans chaque cluster, les différentes informations associées à un processus P sont regroupées dans le descripteur de processus.
     7
     8 * TYPE : définit la politique de réplication/distribution (CODE / STACK / DATA / HEAP / HEAPXY / FILE / ANON)
     9 * FLAGS : définit les droits d’accès
     10 * VBASE : adresse virtuelle  de base
     11 * LENGTH : longueur du segment
     12 * BIN : pathname to the .elf file. (seulement pour les types DATA et CODE)
     13 * X,Y : coordonnées du cluster où est mappé le vseg (seulement pour un vseg localised)
     14 * MAPPER : radix-tree contenant les pages physiques allouées à ce vseg (seulement pour les types CODE, DATA, FILE).
     15
     16== 2) Tables de pages et listes de vsegs =
     17
     18Les différentes informations associées à un processus P sont regroupées dans le descripteur de processus (structure task_t). Ce descripteur de processus, ainsi que les structures qu'il contient, est - partiellement - répliqué dans tous les clusters contenant au moins un thread du processus P, appelés clusters actifs.
     19
     20La table des pages est utilisée par le noyau pour stocker le mapping de chaque page de chaque vseg d'un processus. cette table des pages fait partie des informations - partiellement - répliquées, et nous appelons PT(P,K) la table des pages du processus P dans le cluster K.
     21
     22La liste des vsegs définis pour un processus est utilisée par le noyau en cas de défaut de page pour vérifier que l'adresse virtuelle non happée correspond à un segment défini, et pour déterminer le type du segment. Cette liste fait également partie des informations - partiellement - répliquées , et nous appelons VSL(P,K) la liste des vsegs du processus P dans le cluster K.
     23
     24
    1725Le PID (Process Identifier) est codé sur 32 bits, et il est unique dans le système : les 8 bits de poids fort contiennent
    1826les 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.
     
    3038- ENV : variables d’environnement du processus,
    3139
    32 Le contenu des tables de pages évolue au cours du temps, et  n’est pas identique dans tous les clusters.
    33 En effet le contenu des tables P évolue différemment dans les clusters en fonction des
    34 défauts de pages causés par les threads de P s’exécutant dans les différents clusters.
    35 De plus  le mapping des segments private (CODE et STACKS) varie d’un cluster à un autre.
    36 Pour ce qui concerne les vsegs public, seul le cluster de référence contient l’état complet du mapping.
    37 
    38 De même, le contenu des listes de vsegs évolue au cours du temps, et n’est pas identique dans tous les clusters.
    39 En effet chaque vseg private n’est enregistré que dans un seul cluster.
    40 En revanche toutes les listes de vsegs doivent être identiques pour ce qui concerne les vsegs public.
    41 Pour ce qui concerne les vsegs public, tout ajout dynamique d’un nouveau vseg public ou toute extension
    42 doit être répercuté dans tous les clusters actifs.
    43 
    44 3) Enregistrement et destruction des vsegs
     40=== 2.1) Evolution des PT(P,K) ===
     41
     42Pour un même processus P, le contenu des différentes tables de pages PT(P,K) évolue au cours du temps, et il évolue différemment dans les différents clusters actifs:
     43D'une part, le contenu des tables P évolue dynamiquement dans les clusters en fonction des défauts de pages causés par les threads de P s’exécutant chaque cluster.
     44De plus  le mapping des segments ''private'' (CODE et STACKS) varie d’un cluster à un autre, puisqu'une même adresse virtuelle correspond à des adresses différentes suivant les clusters.
     45Pour ce qui concerne les vsegs ''public'', seul le cluster de référence contient l’état complet du mapping.
     46
     47=== 2.2) Evolution des VSL(P,K) ===
     48
     49De même, pour un même processus P, le contenu des différentes listes de vsegs VSL(P,K)  évolue au cours du temps, et n’est pas identique dans tous les clusters.
     50En effet les listes de vsegs doivent être identiques pour ce qui concerne les vsegs ''public'', mais chaque vseg ''private'' n’est enregistré que dans le cluster auquel il appartient.
     51Pour ce qui concerne les vsegs public, tout ajout dynamique d’un nouveau vseg public ou toute extension d'un vseg existant doit être répercuté dans tous les clusters actifs.
     52
     53== 3) Enregistrement et destruction des vsegs dans les VSL(P,K) ==
    4554 
    4655La politique d’enregistrement et de destruction des vsegs dans les VSL(P,X) dépend du type de vseg:
    4756
    48 3.1) DATA
     57=== 3.1) DATA ===
    4958Ce 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.
    50 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,
    51 si ce cluster ne contenait pas encore de thread du processus P.
     59Il 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.
    5260La longueur est définie par le fichier .elf contenant le code binaire du processus.
    53 Il n’y a pas de cluster de mapping pour un vseg distributed.
    54 Ce type de vseg n’est détruit que lors de la destruction du processus.
    55 
    56 3.2) CODE
     61Il n’y a pas de cluster de mapping pour un vseg ''distributed''.
     62Ce type de vseg n’est détruit que lors de la destruction du processus.
     63
     64=== 3.2) CODE ===
    5765Ce 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.
    58 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,
    59 si ce cluster ne contenait pas encore de thread du processus P.
     66Il 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.
    6067La longueur est définie par le fichier .elf contenant le code binaire du processus.
    61 Le cluster de mapping est toujours le cluster local pour un vseg private.
    62 Ce type de vseg n’est détruit que lors de la destruction du processus.
    63 
    64 3.3) STACK
    65 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
    66 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
    67 dans un cluster X n’est ni connu ni accédé depuis un autre cluster Y.
     68Le cluster de mapping est toujours le cluster local pour un vseg ''private''.
     69Ce type de vseg n’est détruit que lors de la destruction du processus.
     70
     71=== 3.3) STACK ===
     72Un 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 pour le processus P.
     73Les 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.
    6874La longueur est définie par un paramètre global de l’OS : MIN_STACK_SIZE.
    69 Le cluster de mapping est toujours le cluster local pour un vseg private.
     75Le cluster de mapping est toujours le cluster local pour un vseg ''private''.
    7076Ce type de vseg est éliminé de la VSL(P,X) lors de la destruction du thread.
    7177
    72 3.4) HEAP
     78=== 3.4) HEAP ===
    7379Ce 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.
    74 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,
    75 si celui-ci ne contenait pas encore de thread du processus P.
     80Il 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.
    7681La longueur est un paramètre global de l’OS : STANDARD_MALLOC_HEAP_SIZE.
    77 Il n’y a pas de cluster de mapping pour un vseg distributed.
    78 Ce type de vseg n’est détruit que lors de la destruction du processus.
    79 
    80 3.5) REMOTE
    81 Ce type de vseg est enregistré dans la VSL(P,A) de tous les clusters A qui contiennent au moins un thread de P,
    82 au moment où un thread quelconque de P exécute un remote_malloc(x,y) dans un cluster K.
    83 Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P, si un vseg de type REMOTE
    84 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 …
    85 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
    86 clusters actifs de P.   
     82Il n’y a pas de cluster de mapping pour un vseg ''distributed''.
     83Ce type de vseg n’est détruit que lors de la destruction du processus.
     84
     85=== 3.5) REMOTE ===
     86Ce 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.
     87Le 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 et le type du vseg manquant.
     88Si ce type de vseg n’existe pas déjà dans la VSL(P,Z), le noyau de Z broadcaste une VSEG_REGISTER_RPC vers tous les clusters actifs de P.   
    8789La longueur est un paramètre global de l’OS : REMOTE_MALLOC_HEAP_SIZE.
    8890Le cluster de mapping est défini par les arguments (x,y) du remote_malloc().
    8991Ce type de vseg n’est détruit que lors de la destruction du processus.
    9092
    91 3.6) FILE
    92 Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
    93 au moment où un thread quelconque de P exécute un mmap(file , size) dans un cluster K.
    94 Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
    95 le type de vseg, le descripteur de fichier, la taille … To be completed …
    96 Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
     93=== 3.6) FILE ===
     94Ce 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.
     95Le 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 et la taille.
     96Le noyau du cluster Z broadcaste une VSEG_REGISTER_RPC vers tous les autres clusters actifs de P.
    9797La longueur du vseg est définie par l’argument size du mmap().
    98 Le cluster de mapping est défini par l’argument file, et il est quelconque puisque le cache d’un fichier peut être placé
    99 sur n’importe quel cluster (répartition uniforme).
     98Le 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 (politique de répartition uniforme).
    10099Ce 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.
    101100
    102 3.7) ANON
     101=== 3.7) ANON ===
    103102Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
    104103au moment où un thread quelconque de P exécute un mmap(anonyme , size) dans un cluster K.
     
    110109Ce 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.
    111110
    112 4) Introduction d’une nouvelle entrée dans une Table de Pages PT(P,K)
     111== 4) Introduction d’une nouvelle entrée dans une PT(P,K) ==
    113112
    114113L’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
     
    117116le défaut de page  à l’instance locale du noyau. Le traitement du défaut de page dépend du type du segment :
    118117
    119 4.1) CODE
     118=== 4.1) CODE ===
    120119Il existe un vseg de ce type dans la VSL de tous les clusters contenant au moins un thread du processus P.
    121120Si 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
     
    128127QUESTION : dans le cluster propriétaire Z, faut-il faire une copie de la page du cache de fichier vers une autre page physique ? [AG]
    129128
    130 4.2) STACK
     129=== 4.2) STACK ===
    131130Les vsegs STACK associées aux thread placées dans un cluster X sont mappées dans le cluster X,
    132131et sont gérés indépendamment les uns des autres dans les différents clusters.
     
    137136dé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.
    138137
    139 4.3) DATA
    140 Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
     138=== 4.3) DATA ===
     139Ce vseg étant ''distributed'', les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    141140Si 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
    142141au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     
    148147et initialise la page physique dans M au moyen d’un remote_memcpy(). Finalement, il met à jour la PT (P,Z).
    149148
    150 4.4) HEAP
    151 Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
     149=== 4.4) HEAP ===
     150Ce vseg étant ''distributed'', les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    152151Si 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
    153152au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     
    158157Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    159158
    160 4.5) REMOTE
    161 Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
     159=== 4.5) REMOTE ===
     160Ce vseg étant ''localised'', les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
    162161Si 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
    163162au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     
    168167Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    169168
    170 4.6) FILE
     169=== 4.6) FILE ===
    171170Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
    172171Si 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
     
    178177Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
    179178
    180 4.7) ANON
     179=== 4.7) ANON ===
    181180Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
    182181Le traitement d’un défaut de page est le même que pour un vseg HEAP.
    183182
    184 QUESTION : Les mécanismes décrits ci-dessus pour  les types DATA, HEAP, REMOTE et ANON utilisent une RPC_PMEM_GET_SPP,
    185 qui suppose que le noyau d’un cluster (M) peut “transmettre la propriété” d’une ou plusieurs pages physiques
    186 à 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
    187 mémoire physique entre clusters… [AG]
    188 
    189 
    190 5) Invalidation d’une entrée dans une Table de Pages
     183== 5) Invalidation d’une entrée dans la table des pages ==
    191184
    192185Dans un cluster Z, propriétaire d’un processus P, le noyau peut décider d’invalider une entrée d’une PT(P,Z).
     
    196189Pour ce faire, le noyau du cluster Z doit broadcaster une PT_INVAL_BCRPC vers tous les autres clusters actifs de P.
    197190
    198 6) Optimisation des RPC broadcast
    199 
    200 Dans une RPC broadcast, tous les clusters destinataires (même ceux qui ne sont pas concernés)
    201 signalent la terminaison en incrémentant de façon atomique un compteur de réponses,  qui est scruté par le cluster initiateur.
     191== 6) Optimisation des RPC broadcast ==
     192
     193Dans une RPC broadcast, tous les clusters destinataires doivent signaler la terminaison en incrémentant de façon atomique un compteur de réponses,  qui est scruté par le cluster initiateur.
    202194
    203195Pour réduire le nombre de destinatiares, le descripteur du processus P du cluster propriétaire Z peut maintenir quatre variables
     
    206198Ces variables sont mises à jour à chaque création de thread.
    207199
    208 7 ) Optimisation du traitement des PT_MISS
    209 
    210 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
    211 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
    212 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.
     200== 7 ) Optimisation du traitement des défauts de page ==
     201
     202Pour 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 remote_read(). Il garantit que le PT_INVAL_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_RPC.
     203