Changes between Version 11 and Version 12 of replication_distribution


Ignore:
Timestamp:
Oct 12, 2016, 5:00:14 PM (6 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • replication_distribution

    v11 v12  
    33[[PageOutline]]
    44
    5 The 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.
     5The replication / distribution policy has two goals: enforce locality (as much as possible), and avoid contention (it is the main goal).
     6 * The read-only segments (type CODE) are replicated in all clusters where they are used.
    77 * The private  segments (type STACK) are placed in the same cluster as the thread using it.
    88 * The shared segments (types DATA, HEAP, etc ) are distributed on all clusters as regularly as possible to avoid contention.
     9 * The pinned segments (type REMOTE) are placed in the user-specified cluster.
    910
    1011To actually control data placement on the physical memory banks, the kernel uses the paged virtual memory MMU.
    1112
    12 This 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.
     13This policy is implemented by the Virtual Memory Manager (vmm.h / vmm.c files).
    1314
    1415A '''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).
    1516
    16 The virtual memory manager VMM(P,K) contains a list of vsegs that can be accessed by the threads of P running in cluster K.
     17For each process P, the process descriptor is replicated in all clusters containing at least one thread of P (called active clusters). In each cluster K, the virtual memory manager VMM(P,K) is stored in the local process descriptor, and contains two main structures: VSL(P,K) is the list of all vsegs registered for process P in cluster K, and GPT(P,K) is the generic page table, defining the actual physical mapping of those vsegs on the distributed physical memory banks.
    1718
    18 == 1)  User segments types ==
     19== 1)  User segments types and attributes ==
    1920
    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.
     21 * 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(P,K) segment list, but not in the other VMM(P,X) segment lists.
    2122
    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'''.
     23 * 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) least significant bits as distribution key). A '''private''' vseg is always '''localised'''.
    2324
    24 For 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.
    25 The replication of the VSL and GPT structures creates a coherence problem for non private vsegs.
     25ALMOS-MK defines seven vseg types:
     26|| type        ||               ||                  ||                                                                                                     ||
     27|| CODE     ||  private   || localised   || one per active cluster / same virtual addresses / same content    ||
     28|| DATA       ||  public   || distributed || one per process / replicated in all active clusters                         ||
     29|| STACK    ||  private  || localised    || one per thread / in same cluster as the thread                              ||
     30|| MMAP     ||  public   || distributed || one per mmap(anon)                                                                    ||
     31|| FILE        ||  public   || localised    || one per mmap(file) / in same cluster as the file                             ||
     32|| MALLOC ||  public   || distributed || used by the malloc() library / dynamically extensible                    ||
     33|| REMOTE ||  public   || localised    || one per remote_malloc() / in cluster specified by user                  ||
     34
     35The replication of the VSL(P,K) and GPT(P,K) structures creates a coherence problem for non private vsegs.
     36
    2637 * 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.
    2738 * 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.
     
    2940Therefore, the process descriptors - other than the reference one - are used as read-only caches.
    3041
    31 There 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     ||
     42For a process P, the CODE and DATA vsegs are registered in the VSL(P,Z) when the process main thread is created in reference cluster Z. The STACK vsegs are registered in the VSL(P,K) when a thread of process P is created in cluster K. The HEAP, REMOTE, or FILE threads are registered in the VSL(P,Z) of the reference cluster Z, when any thread, running in any cluster X, makes a mmap(), malloc() or remote malloc() system call, because only the reference cluster can dynamically create a public vseg. The new vseg is then copied in the VSL(P,X) of the cluster X running the client thread. It is only registered in the VSL of other clusters in case of page-fault (on-demand registration).
    3943
    40 Pour 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'').
     44The GPT(P,K) page tables are progressively updated by the kernel as a response to a page-fault (on-demand paging). But a page fault detected in any cluster K must always be reported to the reference cluster Z, and the new mapping should be introduced in the reference GPT(P,Z), before to be copied in the client GPT(P,X).
    4145
    42 Les tables de page PT sont mises à jour progressivement en réponse aux défauts de page (''on demand paging'').
     46Finally, when a given vseg or a given entry in the page table must be removed by the kernel, this modification must be done first in the reference cluster, and broadcasted to all other clusters for update.
    4347
    4448== 2) User process virtual space organisation ==
     
    5256 1. The '''stack''' vzone has a fixed size, and is located in the upper part of the virtual space. It contains as many vsegs of type STACK as the max number of threads for a process in a single cluster. The total size is defined as CONFIG_VSPACE_STACK_SIZE * CONFIG_PTHREAD_MAX_NR.
    5357
    54  1. The '''heap''' vzone has a variable size, and occupies all space between the top of the '''elf''' vzone and the base of the '''stack''' zone. It contains all vsegs of type HEAP, REMOTE or FILE that are dynamically allocated by the reference VMM manager.
     58 1. The '''heap''' vzone has a variable size, and occupies all space between the top of the '''elf''' vzone and the base of the '''stack''' zone. It contains all vsegs of type MMAP, FILE, MALLOC, or REMOTE that are dynamically allocated by the reference VMM manager.
    5559 
    56 == 3) segments utilisés par le noyau ==
    57 
    58 Les différentes instances du noyau ne travaillant qu’en adressage physique, les segments kernel sont définis dans  l’espace d’adressage physique.
    59 Puisqu'il existe une instance du noyau par coeur, les différents segments du noyau - y compris les données globales - sont répliqués dans chaque cluster.
    60 
    61 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.
    62 
    63 On identifie (pour l’instant) les segments suivants
    64 
    65 - KDATA :     private
    66 - KCODE :   private
    67 - KSTACK :  private
    68 - KHEAP :    private
    69 - SHARED :  public