Changes between Version 10 and Version 11 of replication_distribution


Ignore:
Timestamp:
Oct 12, 2016, 2:33:27 PM (6 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • replication_distribution

    v10 v11  
    1 = Politique de réplication / distribution =
     1= Data replication & distribution policy =
    22
    33[[PageOutline]]
    44
    5 La politique de réplication / distribution vise deux objectifs: renforcer la localité, et SURTOUT minimiser la contention.
    6  * Pour les informations read-only (segments de type CODE), on les réplique dans tous les clusters où elles sont utilisées.
    7  * Pour les données non partagées (segments de type STACK) on les place dans le même cluster que le thread utilisateur.
    8  * Pour les données partagées (segments de type DATA, HEAP, MMAP), on cherche à les distribuer le plus uniformément possible dans tous les clusters pour éviter la contention.
     5The replication / distribution policy has two goals: enforce locality (as much as possible), and avoid contention (as the main goal).
     6 * The read-only segments (type CODE) are replicated in all clusters whee they are used.
     7 * The private  segments (type STACK) are placed in the same cluster as the thread using it.
     8 * The shared segments (types DATA, HEAP, etc ) are distributed on all clusters as regularly as possible to avoid contention.
    99
    10 La technique générale permettant à l'OS de contrôler le placement et la réplication des informations sur les bancs mémoire physiques est la mémoire virtuelle paginée.
     10To actually control data placement on the physical memory banks, the kernel uses the paged virtual memory MMU.
    1111
    12 == 1)  Types de segments pour un processus utilisateur ==
     12This policy is implemented by the Virtual Memory Manager (vmm.h / vmm.c files), that is a service replicated in all clusters for all processes. The VMM(P,K) is the Virtual memory manager of process P in cluster K.
    1313
    14 Un '''vseg''' désigne une zone mémoire contigue 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.).
     14A '''vseg''' is a contiguous memory zone in the process virtual space. It is always an integer number of pages. Depending on its type, a '''vseg''' has some specific attributes regarding access rights, replication policy, and distribution policy. The vseg descriptor is defined by the structure vseg_t (in vseg.h file).
    1515
    16  * 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 exécutant dans le même cluster que le cluster ou est mappé le vseg.
     16The virtual memory manager VMM(P,K) contains a list of vsegs that can be accessed by the threads of P running in cluster K.
    1717
    18  * 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.
     18== 1)  User segments types  ==
    1919
    20  * Un vseg peut être ''localised'' (toutes les pages du vseg sont mappées dans le même cluster), ou ''distributed'' (différentes pages du même vseg sont mappées dans différents clusters en utilisant par exemple les bits de poids faibles comme clé de distribution). Un vseg ''private'' est toujours ''localised''.
     20 * A vseg is '''public''' when it can be accessed by any thread of the process, whatever the cluster where the thread is running.  It is '''private''' when it can only be accessed by the threads running in the cluster containing the physical memory bank where this vseg is mapped. A '''private''' vseg is entirely mapped in one single cluster K. It is registered in the VMM segment list but of cluster K, but not in the other clusters.
    2121
    22 Pour chaque processus P, le descripteur du processus est répliqué dans tous les cluster qui contiennent au moins un thread de P. Les structures contenues dans le descripteur de processus telles que la table des pages (PT) et la liste des vsegs (VSL) sont partiellement répliquées, ce qui pose un problème de cohérence pour les vsegs ''public''.
    23  * la copie locale de la liste des vsegs VSL(P,K) d'un process P dans un cluster K contient tous les vsegs ''private'' du cluster K, mais ne contient que les vsegs ''public'' qui ont effectivement été accédé par un thread de P s'exécutant dans le cluster K. Seul le cluster de référence contient la liste complète de tous les vsegs ''public'' définis pour le process P.
    24  * la copie locale de la table des pages PT(P,K) d'un processus P dans cluster K contient toutes les entrées correspondant aux pages ''private'' qui ont effectivement été mappées dans le cluster K, mais elle ne contient que entrées correspondant aux pages ''public''  qui ont effectivement été accédées par un thread de P s'exécutant dans K. Seule la table des pages du cluster de référence contient toutes les pages "public'' qui sont effectivement mappées en mémoire physique (quel que soit le cluster contenant la page physique).
     22 * A vseg can be '''localised''' (all vseg pages are mapped in the same cluster), or '''distributed''' (different pages are mapped on different clusters, using the virtual page number (VPN) LSB bits as distribution key). A '''private''' vseg is always '''localised'''.
    2523
    26 Les vsegs ''private'' sont donc enregistrés uniquement dans les tables du cluster auquel ils appartiennent, mais les vsegs ''public'' ne sont enregistrés de façon certaine que dans les tables du cluster de référence. Les descripteurs de processus de P autres que celui contenu dans le cluster de référence sont des replica incomplets, et les tables associées peuvent être considérées comme des caches read-only.
     24For each process P, the process descriptor is replicated in all clusters containing at least one thread of P (called active clusters). The virtual memory manager VMM[P,K] is stored in the process descriptor, and contains two main structures: VSL(P,K) is the list of all vsegs registerer for process P in cluster K. GPT(P,K) is the generic page table, defining the actual physical mapping of those vsegs.
     25The replication of the VSL and GPT structures creates a coherence problem for non private vsegs.
     26 * A VSL(P,K) contains all private vsegs in cluster K, but contains only the public vsegs that have been actually accessed by a thread of P running in cluster K. Only the '''reference''' process descriptor stored in the reference cluster Z contains the complete list VSL(P,Z) of all public vsegs for the P process.
     27 * A GPT(P,K) contains all contains all entries corresponding to private vsegs. For public vsegs, it contains only the entries corresponding to pages that have been accessed by a thread running in cluster K. Only the reference cluster Z contains the complete  GPT(P,Z) page table of all mapped pages in all clusters for process P.
    2728
    28 Il existe six types de vsegs, correspondant à des droits d'accès ou des politiques de réplication/distribution différentes :
     29Therefore, the process descriptors - other than the reference one - are used as read-only caches.
    2930
    30 || type        ||               ||                  ||   nombre                       ||    commentaire                                              ||
    31 || CODE     ||  private   || localised   || un par cluster actif        || mêmes adresses virtuelles, même contenu   ||
    32 || DATA       ||  public   || distributed || un par processus         || données globales partagées                          ||
    33 || STACK    ||  private  || localised    || un par thread                || dans le cluster hébergeant le thread             ||
    34 || HEAP      ||  public   || distributed || un par mmap(anon)      || utilisé aussi par la lib malloc()                        ||
    35 || REMOTE ||  public   || localised    || un par remote_malloc() || utilisé par remote_malloc()                            ||
    36 || FILE        ||  public   || localised    || un par MMAP(file)         || dans le cluster contenant le fichier file          ||
     31There exist six vseg types:
     32|| type        ||               ||                  ||       comment                                                                                ||
     33|| CODE     ||  private   || localised   || one per active cluster / same virtual addresses / same content    ||
     34|| DATA       ||  public   || distributed || one per process                                                                           ||
     35|| STACK    ||  private  || localised    || one per thread / in same cluster as the thread                              ||
     36|| HEAP      ||  public   || distributed || one per mmap(anon) / also used by the malloc() library                ||
     37|| REMOTE ||  public   || localised    || one per remote_malloc()                                                               ||
     38|| FILE        ||  public   || localised    || one per mmap(file) / in the same cluster as the file cache itsel     ||
    3739
    3840Pour un process P, les vsegs de type CODE et DATA sont enregistrés dans la VSL d'un cluster K au moment de la création du premier thread de P (main thread) dans le cluster K. Les vsegs de type STACK sont enregistrés dans dans la VSL d'un cluster K au moment de la création du thread dans le cluster K. Les vsegs de type HEAP, REMOTE, ou FILE sont enregistrés dans la VSL du cluster de référence Z lors des appels systèmes mmap() malloc(), car seul le cluster de référence peut allouer dynamiquement de la place dans l'espace virtuel du processus. Ils ne sont enregistrés dans la VSL des autres clusters que lors des défauts de page détectés par ceux-ci (''on demand registration'').