ALMOS-MK Specification

1) Politique de réplication et/ou de distribution des segments

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, (vsegs 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 (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.

C) Création dynamique des processus et des thread