Changes between Version 46 and Version 47 of replication_distribution


Ignore:
Timestamp:
Dec 8, 2019, 8:57:45 PM (3 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • replication_distribution

    v46 v47  
    77To actually control data placement on the physical memory banks, the kernel uses the paged virtual memory MMU to map a virtual segment to a given physical memory bank in a given cluster.
    88
    9 A '''vseg''' is a contiguous memory zone in the process virtual space, where all adresses in this '''vseg''' can be accessed by the process without segmentation violation: if the corresponding is not mapped, the page fault will be handled by the kernel, and a physical page will be dynamically allocated and initialized if required. A '''vseg''' always contains  an integer number of pages. Depending on its type, a '''vseg''' has some specific attributes regarding access rights, replication policy, and distribution policy.
     9A '''vseg''' is a contiguous memory zone in the process virtual space, defined by the two (base, size) values. All adresses in this interval can be accessed by in this process without segmentation violation: if the corresponding is not mapped, the page fault will be handled by the kernel, and a physical page will be dynamically allocated (and initialized if required). A '''vseg''' always occupies always an integer number of pages, as a given page cannot be shared by two different vsegs.
     10
     11Depending on its type, a '''vseg''' has some specific attributes regarding access rights, and defining the replication and/or distribution policy:
     12 * A vseg is '''public''' when it can be accessed by any thread T of the involved process, whatever the cluster running the thread T.  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 defined and mapped.
     13 * For a '''public''' vseg, ALMOS-MKH implements a global mapping : In all clusters, a given virtual address is mapped to the same physical address. For a '''private''' vseg, ALMOS-MKH implements a local mapping : the same virtual address can be mapped to different physical addresses, in different clusters.
     14 * A '''public''' vseg can be '''localized''' (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 '''localized'''.
     15
     16To avoid contention, in case of parallel applications defining a large number of threads in one single process P, almos-mkh replicates, the process descriptor in all clusters containing at least one thread of P, and these clusters are called active clusters.
     17The virtual memory manager VMM(P,K) of process P in cluster K, contains two main structures:
     18 * The [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.h VSL(P,K)] is the list of all vsegs registered for process P in cluster K,
     19 * The [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.h GPT(P,K)] is the generic page table, defining the actual physical mapping of these vsegs.
     20
     21This replication is clearly a non-standard feature that creates several difficulties:
     22
     23For a given process P, all VMM(P,K) descriptors in different clusters can have different contents for several reasons :
     24 1. A '''private''' vseg can be registered in only one VSL(P,K) in cluster K, and be totally undefined in the others VSL(P,K').
     25 1. A '''public''' vseg can be replicated in deveral VSL(P,K), but the registration of a vseg in a given VSL(P,K) is ''on demand'': the vseg is only registered in VSL(P,K) when a thread of process P running in cluster K try to access this vseg.
     26 1. Similarly, the mapping of a given virtual page VPN of a given vseg (i.e. the allocation of a physical page PPN to a virtual page VPN, and the registration of this PPN in the GPT(P,K) is ''on demand'': the page table entry will be updated in the GPT(P,K) only when a thread of process P in cluster K try to access this VPN. 
     27 
     28Finally, we have the following rules:
     29 * The '''private''' vsegs, and  the corresponding entries in the page table are purely ''local'' : the VSL(P,K) and the GPT(P,K) are only shared by the threads of P running in cluster K, and these structures can be privately handled by the local kernel instance in cluster K.
     30
     31* For the '''public''' vsegs that are shared by all the threads of the process P, almos-mkh define a '''reference cluster KREF''', that is the cluster on which the main thread of the process has been created. Only the VSL(P,KREF) and the GPT(P,KREF) are complete: the VSL(P,KREF) contains all publics vsegs defined for the process P, and the GPT(P,KREF) contains all page table entries mapped for public vsegs in process P. Other VSL and GPT copies in other clusters are
     32only ''caches'' where an existing vseg, or a mapped page table entry can be missing, bur available in the reference cluster.
     33
     34For more details:
    1035
    1136The '''vseg''' API is defined in the [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vseg.h almos_mk/kernel/mm/vseg] and [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vseg.c almos-mkh/kernel/mm/vseg.c] files.
    12 
    13 To avoid contention, almos-mkh replicates, for each process P, the process descriptor in all clusters containing at least one thread of P, and these clusters are called active clusters. The virtual memory manager VMM(P,K) of process P in cluster K, contains two main structures:
    14  * The [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.h VSL(P,K)] is the list of all vsegs registered for process P in cluster K,
    15  * The [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.h GPT(P,K)] is the generic page table, defining the actual physical mapping of those vsegs.
    1637
    1738The Virtual Memory Manager API is defined in the [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.h almos_mkh/kernel/mm/vmm.h] and [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vmm.c almos-mkh/kernel/mm/vmm.c] files.
     
    1940== __1. User segments types__  ==
    2041
    21  * A vseg is '''public''' when it must be accessed by any thread T of the process, whatever the cluster running the thread T.  It is '''private''' when it needs only to 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.
    22  * For a '''public''' vseg, ALMOS-MKH implements a global mapping : In all clusters, a given virtual address is mapped to the same physical address. For a '''private''' vseg, ALMOS-MKH implements a local mapping : the same virtual address can be mapped to different physical addresses, in different clusters.
    23  * A '''public''' vseg can be '''localized''' (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 '''localized'''.
     42This section describes the six types of user virtual segments defined by almost-mkh:
    2443
    25 ALMOS-MK defines six vseg types in [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/mm/vseg.h#L41 vseg_type_t]:
    2644|| Type     ||           ||                  ||    Access     ||      Replication                                     ||    Placement                              ||  Allocation policy in user space                  ||
    2745|| STACK    ||  private  || localized   || Read Write || one physical mapping per thread        || same cluster as thread using it  || dynamic (one stack allocator per cluster)   ||
     
    3250|| REMOTE ||  public   || localized   || Read Write || same mapping for all threads              || cluster defined by user             || dynamic (one heap allocator per process)  ||
    3351
    34  1. '''CODE''' : This private vseg contains the user application code. ALMOS-MK creates one CODE vseg per active cluster. For a process P, the CODE vseg is registered in the VSL(P,Z) when the process is created in reference cluster Z. In the other clusters X, the CODE vseg is registered in VSL(P,X) when a page fault is signaled by a thread of P running in cluster X. In each active cluster X, the CODE vseg is localized, and physically mapped in cluster X.
     52 1. '''CODE''' : This private vseg contains the application code. ALMOS-MK creates one CODE vseg per active cluster. For a process P, the CODE vseg is registered in the VSL(P,Z) when the process is created in reference cluster Z. In the other clusters X, the CODE vseg is registered in VSL(P,X) when a page fault is signaled by a thread of P running in cluster X. In each active cluster X, the CODE vseg is localized, and physically mapped in cluster X.
    3553 1. '''DATA''' : This vseg contains the user application global data. ALMOS-MK creates one single DATA vseg per process, that is registered in the reference VSL(P,Z) when the process P is created in reference cluster Z.  In the other clusters X, the DATA vseg is registered  in VSL(P,X) when a page fault is signaled by a thread of P running in cluster X. To avoid contention, this vseg is physically distributed on all clusters, with a page granularity. For each page, the physical mapping is defined by the LSB bits of the page VPN.
    3654 1. '''STACK''' : This private vseg contains the execution stack of a thread. For each thread T of process P running in cluster X, ALMOS_MK creates one STACK vseg. This vseg is registered in the VSL(P,X) when the thread descriptor is created in cluster X. To enforce locality, this vseg is physically mapped in cluster X.
     
    5573 * The segments dynamically allocated by the [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/syscalls/sys_mmap.c] system call are placed  as described below.
    5674
    57 ==__ 3. 32 bits virtual space organisation__ ==
     75== __3. 32 bits virtual space organisation__ ==
    5876
    5977The virtual address space of an user process P is split in 5 fixed size zones, defined by configuration parameters in [https://www-soc.lip6.fr/trac/almos-mkh/browser/trunk/kernel/kernel_config.h].  Each zone contains one or several vsegs, as described below.