[Kos-dev] Re: [Kos-announce] Nouveautes du Week End

[Christophe]

Actuellement, je tourne toujours sur Windows et je ne peux donc pas lire les
.dia et .eps. Quelqu'un peut le convertir en .pdf et me l'envoyer à
christophe.avoinne@laposte.net ?

----- Original Message -----
From: d2 <David.Decotigny@irisa.fr>
To: <kos-dev@enix.org>
Sent: Tuesday, August 28, 2001 10:07 AM
Subject: [Kos-dev] Re: [Kos-announce] Nouveautes du Week End


Pour la gestion du VM :

- chaque team à un espace virtuel local contenant les regions locales au
team
- chaque espace virtuel local hérite d'un espace virtual commun contenant
les regions communes au moins à deux teams

Il y a toujours un ordre d'hierarchie dans les espaces virtuels.

Un team A ayant un espace virtual A cree un team B; un nouvel espace local
pour A est crée avec les régions purement locaux à A (ces régions sont
retirées de l'ancien espace de A). Un nouvel espace local pour B est
également créé pour B avec les régions purement locaux à B. L'ancien espace
local de A devient l'espace commun de A et B et ne contient que les régions
communes à A et B.

Conclusion : chaque région pointe correctement sur le bon espace virtuel.

A noter que seuls les espaces locaux sont associés à un seul team et donc au
contexte de mémoire de ce team. Ces espaces sont en fait les noeud terminaux
d'un arbre hierarchique des espaces virtuels. Les noeuds non terminaux, les
espaces communs à plusieurs teams.

La structure d'un espace virtuel peut être la suivante :

typedef struct virtual_space {
  struct virtual_space *shadow; // "filature" : c'est ce lien qui faut
suivre pour retrouver la region qui nous permet de résoudre le défaut de
page
  struct virtual_space *sharer; // espace local  aux teams parents - ceux
qui donnent en partage
  struct virtual_space *sharee; // espace local aux teams fils - ceux qui
reçoivent en partage
  struct virtual_region *regions; // régions partagée entre les teams
parents et fils : si la région souhaité n'est pas là, il faut alors suivre
"shadow"
  ...
} virtual_space_t;

ATTENTION: le terme "shadow" ici est un terme que j'utilisais bien avant le
vôtre et que je continue d'utiliser... et qu'il n'a rien à voir avec votre
définition.

Il s'agit en fait d'un arbre binaire.

Au départ, on a :

space(A)->sharer == space(A)->sharee == 0;

car il s'agit d'un espace local appartenant au team A.

Quand on clone le team B :

    old_space = team(A)->space;
    team(A)->space = new virtual_space_t(); // noeud terminal, arbre des
régions vide
    team(B)->space = new virtual_space_t(); // noeud terminal, arbre des
régions vide
    old_space->sharer = team(A)->space;
    old_space->sharee = team(B)->space;
    team(A)->space->move_local_regions(old_space); // Déplace les regions
locaux de l'acien espace dans le nouvel espace de A
    ...

Quand une région locale est déplacée dans le nouvel espace, on n'oublie pas
de mettre à jour le champ "space" de la région en question.

Lors d'un défaut de page (mécanisme copy-on-write, par exemple), on ne
trouvera pas la région concernée dans l'espace local, mais on peut la
retrouver en la pistant indirectement via le lien "shadow" de cet espace.
Chaque lien "shadow" mène à un espace virtuel des régions communes qui
contiendra tôt ou tard la région recherchée. Le partage efficace des espaces
virtuels, des regions virtuelles réside justement sur le suivi de ce lien.

Pour exemple, j'ai le team A qui crée le team B, puis le team C, j'aurais
les trois arbres suivants :

A    =>   A'--->B  =>  A'--->B
                 \                    \
                 A                   A''--->C
                                         \
                                          A

Au final, A' contiendra les régions communes à A, B et C; A'' les régions
communes à A et C. Si A fait un défaut de page, je recherche la région
fautive dans l'espace A puis A'' puis A'; si B, dans l'espace B puis A'; si
C, dans l'espace C puis A'' puis A'. Ceci grâce au lien "shadow".

Pour autre exemple, j'ai le team A qui crée le team B, puis le team B crée
le team C, j'aurais les trois arbres suivants :

A    =>   A'--->B  =>  A'--->B'--->C
                 \                    \         \
                 A                   A       B

Au final, A' contiendra les régions communes à A, B et C; B' les régions
communes à B et C. Si A fait un défaut de page, je recherche la région
fautive dans l'espace A puis A'; si B, dans l'espace B puis B' puis A'; si
C, dans l'espace C puis B' puis A'. Ceci grâce au lien "shadow".

L'espace d'adresse d'un team est donc défini par la chaîne ordonnée des
espaces virtuelles liés par le lien "shadow".

Pour n teams, on devrait avoir au plus 2n-1 espaces virtuels dans l'arbre
binaire des espaces virtuels. Gageons que cela peut constituer une économie
de mémoire comparée à la duplication des régions communes aux teams sans
cette notion d'arbre binaire des espaces virtuels.

Si on considère que le team A a 20 régions dont 10 partageables en lecture
uniquement et 5 en lecture-écriture. Pour les teams A, B et C, on comptera
au mieux 10 (locales à A) + 10 (partagées en lecture uniquement pour A, B et
C) + 5 (partagées en lecture-écriture pour A, B et C), soit 25 régions au
lieu de 3*20 = 60 régions sans la notion de partage des espaces virtuels, ou
au pire, dans le cas où toutes les régions partagées en lecture uniquement
auraient été modifiées, on aura 10 (locales à A) + 10 (partagées en lecture
uniquement pour A, B et C) + 3*10 (dont une page au moins a été modifiée
localement) + 5 (partagées en lecture-écriture pour A, B et C), soit 45
régions - qui est toujours inférieur à 60 régions.

Remarque : les régions soumises au mécanisme de "copy-on-write" peuvent
également se servir d'un lien "shadow" dans leur structure.

A'--->B
   \
   A

Au départ, j'ai une région partagée en lecture uniquement entre A et B. B
fait un accès écriture : la région incriminée est trouvé dans A', on
duplique la région pour la mettre dans A et une autre pour la mettre en B.
La nouvelle region pour A pointe sur une autre ressource qui va contenir la
page modifiée. La région incriminée déplace la page en lecture seule
responsable du défaut de page dans la nouvelle region de B : si la ressource
de la région incriminée ne contient plus de page, la région est supprimé de
A'.

Imaginer que B fasse un autre accès écriture sur la même région (mais à une
page différente obligatoirement), la première région correspondante sera
trouvée dans B, mais la page n'est pas présente dans la resource de cette
région. On passe directement via le lien "shadow" à la région correspondante
dans A'. Là on trouve la page, et on procède de même qu'au-dessus. Ce lien
"shadow" sert de raccourci en évitant avantageusement de rechercher à
nouveau dans la chaîne des espaces virtuels, puisque l'on est normalement
sûr de la trouver à travers cette chaîne de région.

Voilà. Bonne réflexion.

Hlide