Changes between Version 1 and Version 2 of WikiStart


Ignore:
Timestamp:
May 19, 2016, 7:15:37 PM (8 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • WikiStart

    v1 v2  
    1 = Welcome to Trac 1.0.9 =
    2 
    3 Trac is a '''minimalistic''' approach to '''web-based''' management of
    4 '''software projects'''. Its goal is to simplify effective tracking and handling of software issues, enhancements and overall progress.
    5 
    6 All aspects of Trac have been designed with the single goal to
    7 '''help developers write great software''' while '''staying out of the way'''
    8 and imposing as little as possible on a team's established process and
    9 culture.
    10 
    11 As all Wiki pages, this page is editable, this means that you can
    12 modify the contents of this page simply by using your
    13 web-browser. Simply click on the "Edit this page" link at the bottom
    14 of the page. WikiFormatting will give you a detailed description of
    15 available Wiki formatting commands.
    16 
    17 "[wiki:TracAdmin trac-admin] ''yourenvdir'' initenv" created
    18 a new Trac environment, containing a default set of wiki pages and some sample
    19 data. This newly created environment also contains
    20 [wiki:TracGuide documentation] to help you get started with your project.
    21 
    22 You can use [wiki:TracAdmin trac-admin] to configure
    23 [http://trac.edgewall.org/ Trac] to better fit your project, especially in
    24 regard to ''components'', ''versions'' and ''milestones''.
    25 
    26 
    27 TracGuide is a good place to start.
    28 
    29 Enjoy! [[BR]]
    30 ''The Trac Team''
    31 
    32 == Starting Points ==
    33 
    34  * TracGuide --  Built-in Documentation
    35  * [http://trac.edgewall.org/ The Trac project] -- Trac Open Source Project
    36  * [http://trac.edgewall.org/wiki/TracFaq Trac FAQ] -- Frequently Asked Questions
    37  * TracSupport --  Trac Support
    38 
    39 For a complete list of local wiki pages, see TitleIndex.
     1= ALMOS-MK Specification =
     2
     3[[PageOutline]]
     4
     5== 1) [wiki:replication_distribution Politique de réplication et/ou de distribution des segments] ==
     6
     7La politique de réplication / distribution vise deux objectifs: renforcer la localité, et SURTOUT minimiser la contention.
     8- Pour les données non partagées ou read-only, (vsegs de type CODE, STACK) on cherche à les répliquer dans tous
     9les clusters de l’architecture pour les rapprocher des thread utilisateurs.
     10- Pour les données partagées (DATA, HEAP, MMAP), on cherche à les distribuer le plus uniformément possible
     11dans tous les clusters pour éviter la contention.
     12
     13On fait l’hypothèse que - pour chaque processus P - le descripteur du processus P, et certaines structures qu’il contient
     14telles que la table des pages (PT) et la liste des vsegs (VSL) sont répliquées dans tous les cluster qui contiennent
     15au moins un thread de P.
     16
     171)  pour un processus utilisateur P
     18
     19Un vseg désigne une zone mémoire contigüe dans l’espace virtuel d’un processus, auxquels sont attachés
     20certains attributs (droit d’accès, politique de réplication/distribution dans les différents clusters, cachabilité, etc.).
     21
     22- Un vseg est public quand il peut être accédé par n’importe quel thread du processus,
     23quel que soit le cluster dans lequel le thread s’exécute. Il est private quand il n’est accédé que par les threads
     24s”exécutant dans le même cluster que le cluster ou est mappé le vseg.
     25
     26- Un vseg private est entièrement mappé dans la mémoire physique du cluster K dans lequel il est accessible.
     27Il est enregistré dans liste des segments et dans la table des pages du cluster K, mais  pas dans les autres clusters.
     28
     29- Un vseg public est enregistrés dans la liste des segments et dans la table des pages de tous les clusters actifs
     30(i.e. tous les clusters qui contiennent un thread de P).
     31Pour maintenir la cohérence entre les tables de pages, chaque vseg public possède un cluster de référence, qui est le cluster
     32propriétaire du processus (i.e. le cluster Z où a été créé le processus).
     33Les réplicas du descripteurs de processus (et surtout les tables
     34associées) autres que celui contenu dans le cluster de référence peuvent être considérées comme des caches read-only.
     35
     36- Un vseg peut être localised (toutes les pages du vseg sont mappées dans le même cluster),
     37ou distributed (différentes pages sont mappées dans différents clusters en utilisant par exemple les bits de poids
     38faibles comme clé de distribution). Les vsegs privés sont toujours localised.
     39
     40Il existe sept types de vsegs, correspondant à des politiques de réplication/distribution différentes :
     41
     42- CODE :           private / plusieurs vsegs / mêmes adresses virtuelles, même contenu, un vseg par cluster actif
     43- STACK :          private / plusieurs vsegs / un vseg par thread de P, mappé dans le cluster hébergeant le thread
     44- DATA :             public  / un seul vseg / distributed
     45- HEAP :            public  / un seul vseg / distributed
     46- REMOTE :      public  / plusieurs vsegs / chaque vseg localised (dans le cluster concerné par le remote_malloc(x,y) )
     47- FILE :              public  / plusieurs vsegs / chaque vseg localised (dans le cluster contenant le fichier concerné par le mmap() )
     48- ANON :           public  / plusieurs vsegs / chaque vseg distributed (associé à un mmap() anonyme )
     49
     502) pour le noyau,
     51
     52Les différentes instances du noyau ne travaillant qu’en adressage physique, les segments kernel sont définis dans
     53l’espace d’adressage physique.
     54
     55- un segment kernel est private quand il ne peut être accédé que par l’instance locale du noyau.
     56il est public quand il peut être accédé par n’importe quel instance du noyau.
     57
     58Dans un segment public, le noyau peut définir des  structures répliquées homologues.
     59Si N est le nombre de clusters, une structure répliquées homologue est un ensemble de N structures identiques,
     60de longueur fixe, implantées à des adresses physiques ne différant entre elles que par les bits de poids fort
     61définissant les coordonnées du cluster.
     62
     63On identifie (pour l’instant) les segments suivants
     64
     65- KDATA :     private
     66- KCODE :   private
     67- KSTACK :  private
     68- KHEAP :    private
     69- SHARED :  public
     70
     71———————————————————————————————
     72B) Construction dynamique des tables de pages d’un processus
     73———————————————————————————————
     74
     751) Descripteur de vseg
     76
     77Un descripteur de vseg contient les informations suivantes :
     78- TYPE : définit la politique de réplication/distribution (CODE / STACK / DATA / HEAP / HEAPXY / FILE / ANON)
     79- FLAGS : définit les droits d’accès
     80- VBASE : adresse virtuelle  de base
     81- LENGTH : longueur du segment
     82- BIN : pathname to the .elf file. (seulement pour les types DATA et CODE)
     83- X,Y : coordonnées du cluster où est mappé le vseg (seulement pour un vseg localised)
     84- MAPPER : radix-tree contenant les pages physiques allouées à ce vseg (seulement pour les types CODE, DATA, FILE).
     85
     862) Descripteur de processus
     87
     88Dans chaque cluster, les différentes informations associées à un processus P sont regroupées dans le descripteur de processus.
     89Le PID (Process Identifier) est codé sur 32 bits, et il est unique dans le système : les 8 bits de poids fort contiennent
     90les 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.
     91Le descripteur d’un processus P et les tables qui lui sont associées ne sont répliqués que dans les clusters qui contiennent
     92au moins un thread de P (appelés clusters actifs de P).
     93
     94Les principale informations stockées dans le descripteur processus sont les suivantes:
     95- PID :  processus identifier (contient les coordonnées du cluster propriétaire)
     96- PPID : parent processus identifier,
     97- XMIN, XMAX, YMIN, YMAX : recrangle recouvrant tous les clusters actifs
     98- PT : table des pages du processus,
     99- VSL : liste des vsegs du processus,
     100- FDT : table des fichiers ouverts du processus,
     101- TRDL : liste des threads du processus,
     102- ENV : variables d’environnement du processus,
     103
     104Le contenu des tables de pages évolue au cours du temps, et  n’est pas identique dans tous les clusters.
     105En effet le contenu des tables P évolue différemment dans les clusters en fonction des
     106défauts de pages causés par les threads de P s’exécutant dans les différents clusters.
     107De plus  le mapping des segments private (CODE et STACKS) varie d’un cluster à un autre.
     108Pour ce qui concerne les vsegs public, seul le cluster de référence contient l’état complet du mapping.
     109
     110De même, le contenu des listes de vsegs évolue au cours du temps, et n’est pas identique dans tous les clusters.
     111En effet chaque vseg private n’est enregistré que dans un seul cluster.
     112En revanche toutes les listes de vsegs doivent être identiques pour ce qui concerne les vsegs public.
     113Pour ce qui concerne les vsegs public, tout ajout dynamique d’un nouveau vseg public ou toute extension
     114doit être répercuté dans tous les clusters actifs.
     115
     1163) Enregistrement et destruction des vsegs
     117 
     118La politique d’enregistrement et de destruction des vsegs dans les VSL(P,X) dépend du type de vseg:
     119
     1203.1) DATA
     121Ce 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.
     122Il 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,
     123si ce cluster ne contenait pas encore de thread du processus P.
     124La longueur est définie par le fichier .elf contenant le code binaire du processus.
     125Il n’y a pas de cluster de mapping pour un vseg distributed.
     126Ce type de vseg n’est détruit que lors de la destruction du processus.
     127
     1283.2) CODE
     129Ce 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.
     130Il 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,
     131si ce cluster ne contenait pas encore de thread du processus P.
     132La longueur est définie par le fichier .elf contenant le code binaire du processus.
     133Le cluster de mapping est toujours le cluster local pour un vseg private.
     134Ce type de vseg n’est détruit que lors de la destruction du processus.
     135
     1363.3) STACK
     137Un 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
     138par le processus P. Les VSL(P,Y) des autres clusters Y n’ont pas besoin d’être mises a jour car un vseg STACK
     139dans un cluster X n’est ni connu ni accédé depuis un autre cluster Y.
     140La longueur est définie par un paramètre global de l’OS : MIN_STACK_SIZE.
     141Le cluster de mapping est toujours le cluster local pour un vseg private.
     142Ce type de vseg est éliminé de la VSL(P,X) lors de la destruction du thread.
     143
     1443.4) HEAP
     145Ce 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.
     146Il 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,
     147si celui-ci ne contenait pas encore de thread du processus P.
     148La longueur est un paramètre global de l’OS : STANDARD_MALLOC_HEAP_SIZE.
     149Il n’y a pas de cluster de mapping pour un vseg distributed.
     150Ce type de vseg n’est détruit que lors de la destruction du processus.
     151
     1523.5) REMOTE
     153Ce type de vseg est enregistré dans la VSL(P,A) de tous les clusters A qui contiennent au moins un thread de P,
     154au moment où un thread quelconque de P exécute un remote_malloc(x,y) dans un cluster K.
     155Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P, si un vseg de type REMOTE
     156n’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 …
     157Si 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
     158clusters actifs de P.   
     159La longueur est un paramètre global de l’OS : REMOTE_MALLOC_HEAP_SIZE.
     160Le cluster de mapping est défini par les arguments (x,y) du remote_malloc().
     161Ce type de vseg n’est détruit que lors de la destruction du processus.
     162
     1633.6) FILE
     164Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
     165au moment où un thread quelconque de P exécute un mmap(file , size) dans un cluster K.
     166Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
     167le type de vseg, le descripteur de fichier, la taille … To be completed …
     168Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
     169La longueur du vseg est définie par l’argument size du mmap().
     170Le cluster de mapping est défini par l’argument file, et il est quelconque puisque le cache d’un fichier peut être placé
     171sur n’importe quel cluster (répartition uniforme).
     172Ce 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.
     173
     1743.7) ANON
     175Ce type de vseg est enregistré dans la VSL(P,A) de tous les cluster A qui contiennent au moins un thread de P,
     176au moment où un thread quelconque de P exécute un mmap(anonyme , size) dans un cluster K.
     177Le noyau du cluster K envoie une VSEG_REQUEST_RPC vers le cluster Z propriétaire de P. Les arguments sont le PID,
     178le type de vseg, le descripteur de fichier, la taille … To be completed …
     179Le noyau du cluster Z broadcaste une VSEG_REGISTER_BCRPC vers tous les autres clusters actifs de P.
     180La longueur du vseg est définie par l’argument size du mmap().
     181Il n’y a pas de cluster de mapping pour un vseg distributed.
     182Ce 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.
     183
     1844) Introduction d’une nouvelle entrée dans une Table de Pages PT(P,K)
     185
     186L’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
     187causé par n’importe quel thread du processus P s’exécutant dans le cluster K, sur le principe du “on-demand paging”.
     188Tous les threads d’un processus P placés dans un cluster K utilisent exclusivement la PT(P,K) locale, et reportent
     189le défaut de page  à l’instance locale du noyau. Le traitement du défaut de page dépend du type du segment :
     190
     1914.1) CODE
     192Il existe un vseg de ce type dans la VSL de tous les clusters contenant au moins un thread du processus P.
     193Si 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
     194une page physique dans le cluster K. Pour initialiser cette page, il envoie une PT_MISS_RPC au cluster Z propriétaire du processus.
     195Quand il obtient  le PTE stocké dans la PT(P,Z), il effectue un remote_memcpy() pour copier le contenu de la page physique
     196du cluster Z vers la page physique du cluster K. Il termine en introduisant le PTE manquant dans la PT(P,K).
     197Si 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,
     198pour récupérer le contenu de la page manquante dans le cache du fichier .elf, et met à jour la PT(P,Z).
     199
     200QUESTION : dans le cluster propriétaire Z, faut-il faire une copie de la page du cache de fichier vers une autre page physique ? [AG]
     201
     2024.2) STACK
     203Les vsegs STACK associées aux thread placées dans un cluster X sont mappées dans le cluster X,
     204et sont gérés indépendamment les uns des autres dans les différents clusters.
     205Le noyau du cluster X doit allouer une page physique, et l’enregistrer dans la PT (P,X) locale sans l’initialiser.
     206Si l’adresse demandée tombe dans la dernière page disponible pour le vseg, la longueur du vseg STACK peut être dynamiquement
     207localement 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.
     208Comme suggéré par Franck, on peut imaginer une politique d’allocation par dichotomie utilisant deux arguments : MAX_STACK_SIZE
     209dé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.
     210
     2114.3) DATA
     212Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
     213Si 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
     214au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     215Quand il reçoit la réponse, il met à jour la PT(P,K).
     216Si 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
     217de 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.
     218En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
     219Le 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,
     220et initialise la page physique dans M au moyen d’un remote_memcpy(). Finalement, il met à jour la PT (P,Z).
     221
     2224.4) HEAP
     223Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
     224Si 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
     225au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     226Quand il reçoit la réponse, il met à jour la PT(P,K).
     227Si 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
     228de poids faible du VPN, et envoie au cluster M RPC_PMEM_GET_SPP pour obtenir le PPN d’une page physique du cluster M.
     229En réponse à cette RPC, le noyau du cluster M alloue une page physique et renvoie le PPN de celle-ci.
     230Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
     231
     2324.5) REMOTE
     233Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
     234Si 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
     235au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     236Quand il reçoit la réponse, il met à jour la PT(P,X).
     237Si 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
     238le PPN d’une page physique du cluster M.
     239En réponse à cette RPC, le noyau du cluster M alloue une page physique, et renvoie le PPN de celle-ci.
     240Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
     241
     2424.6) FILE
     243Ce vseg étant localised, les coordonnées du cluster de mapping M sont enregistrées dans le descripteur de vseg.
     244Si 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
     245au cluster Z, pour obtenir  le PTE stocké dans la PT(P,Z). Les arguments sont le PID et le VPN de la page manquante.
     246Quand il reçoit la réponse, il met à jour la PT(P,K).
     247Si 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
     248une 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.
     249En réponse à cette RPC, le noyau du cluster M accède au mapper du vseg et retourne le PPN correspondant.
     250Quand le noyau du cluster Z obtient le PPN, il met à jour la PT (P,Z).
     251
     2524.7) ANON
     253Ce vseg étant distributed, les pages physiques sont distribuées sur tous les clusters suivant les bits de poids faible du VPN.
     254Le traitement d’un défaut de page est le même que pour un vseg HEAP.
     255
     256QUESTION : Les mécanismes décrits ci-dessus pour  les types DATA, HEAP, REMOTE et ANON utilisent une RPC_PMEM_GET_SPP,
     257qui suppose que le noyau d’un cluster (M) peut “transmettre la propriété” d’une ou plusieurs pages physiques
     258à 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
     259mémoire physique entre clusters… [AG]
     260
     261
     2625) Invalidation d’une entrée dans une Table de Pages
     263
     264Dans un cluster Z, propriétaire d’un processus P, le noyau peut décider d’invalider une entrée d’une PT(P,Z).
     265Cela peut se produire par exemple en cas de pénurie de mémoire dans le cluster Z, ou simplement en cas de munmap().
     266Sauf si le vseg concerné est de type STACK, l’entrée invalidée dans la PT(P,Z) doit aussi être invalidée
     267dans les PT(P,K) des autre clusters.
     268Pour ce faire, le noyau du cluster Z doit broadcaster une PT_INVAL_BCRPC vers tous les autres clusters actifs de P.
     269
     2706) Optimisation des RPC broadcast
     271
     272Dans une RPC broadcast, tous les clusters destinataires (même ceux qui ne sont pas concernés)
     273signalent la terminaison en incrémentant de façon atomique un compteur de réponses,  qui est scruté par le cluster initiateur.
     274
     275Pour réduire le nombre de destinatiares, le descripteur du processus P du cluster propriétaire Z peut maintenir quatre variables
     276XMIN, XMAX, YMIN, YMAX définissant le rectangle minimal recouvrant tous les clusters actifs de P à tout instant.
     277Dans ce cas une RPC broadcast ne doit être envoyée qu’a (XMAX - XMIN + 1) * (YMAX - YMIN +1) destinataires.
     278Ces variables sont mises à jour à chaque création de thread.
     279
     2807 ) Optimisation du traitement des PT_MISS
     281
     282Pour 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
     283utiliser 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
     284initié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.
     285
     286== C) Création dynamique des processus et des thread ==