Institut de Formation Supérieure
Yüklə 215,64 Kb.
|
- Bu səhifədəki naviqasiya:
- Analyse des types fixes
- Alignement mémoire
- Principe général
- Un exemple d’utilisation
- L’alignement mémoire des objets
- L’alignement général des objets
- L’alignement des « structures »
- L’alignement des tableaux
- L’alignement des unions
- Les structures utilisées
- Analyse des types variables
MISE EN ŒUVREDans SDE, un type peut être défini de taille fixe ou de taille variable. Un type de taille fixe est en fait la déclaration d’un type dont la taille mémoire est connue à la compilation. Un type de taille variable est un type dont la taille ne sera connue qu’à l’exécution.
Dans SDE, les types créés par l’utilisateur sont modulaires. Un type modulaire est un type dont la description est éclatée dans plusieurs modules indépendants les uns des autres. Tout d’abord, il faut définir la partie globale du type qui est partagée par tous les modules dans un fichier suffixé par .idl : le type déclaré dans ces fichiers de spécification est défini indépendamment du langage et de l’architecture donnée. Ce fichier donne également le nom des services qui implémentent son allocation, son initialisation et son type d’allocation statique ou dynamique, ainsi qu’un certain nombre de drapeaux qui permettent de vérifier sa taille et son existence dans la mémoire. Ensuite, il est possible pour chaque module d’implémenter une partie privée pour le type, cette partie ne sera visible et utilisable que par le module qui l’a implémenté ; cette partie privée est définie dans un fichier suffixé par .imp. Un type peut-être défini à partir : - d’un type opaque : ce type est seulement constitué d’un nombre indiquant sa taille en octets (espace mémoire contigu et insécable). - d’un type externe : qui correspond à un type déclaré soit dans le même module soit dans un autre module. - d’un type composé : un type composé est, soit une structure (une liste de types), soit une union (l’union est discriminante : c’est une liste de types dont un seul est utilisé), soit un tableau (dont les éléments sont des types définis par l’utilisateur). Voici un exemple de type défini dans le module opérations.idl : 
et de leurs implémentations dans plusieurs modules:   Il s’agit d’analyser tous les fichiers de spécification et d’implémentation permettant de regrouper dans des structures adéquates tous les types définis dans ces différents fichiers. Ainsi, SDE peut allouer la mémoire pour le type dans son ensemble (pour les parties communes et privées). Exemple : liste de fusion de la partie globale et des parties privées des types de l’exemple précédent : l  iste
  
 
L’allocation mémoire d’un type <Type> crée par l’utilisateur s’effectue grâce à l’appel d’une fonction C : <Type>Alloc(…) qui contient un malloc. Il y a une seule allocation mémoire par type pour bénéficier d’une bonne efficacité d’accès aux champs de ce type; en effet cette efficacité est obtenue grâce à la localité spatiale de la mémoire des champs déclarés dans ce type (indispensable dans un contexte multitâche : mémoire moins fragmenté implique processus plus rapides).. Cette allocation mémoire renvoie une référence (sur l’emplacement mémoire du type créé) qui est accessible par l’utilisateur. Mais avant d’effectuer cette opération, il faut connaître la taille du type à allouer, nous effectuons donc un parcours de la liste contenant le type et nous itérons les diverses structures les unes après les autres en leur fixant un offset. Pour diverses raisons expliquées dans la prochaine section, le type doit être aligné ; ce qui implique que les offsets des différentes variables doivent être alignés. Voici sur l’exemple, l’organisation mémoire des types de taille fixe :   La taille de la partie fixe est de 16 pour le type int et nous avons donc réservé un espace mémoire de 16 octets. La taille de la partie fixe est de 3 pour le type short et nous avons donc réservé un espace mémoire de 3 octets. SDE génère également des macros qui servent à l’utilisateur pour accéder aux différents champs des types qu’il a créés. Ces macros ont la forme suivante : (global | Macros générés pour le type int : #define global_s1(ref,i0) ((char *)(ref)+i0*3) #define global_s2(ref,i0) ((char *)(ref)+i0*3+2) #define int_o_int_4(ref) ((char *)(ref)+12) #define int_o_int_2(ref) ((char *)(ref)+14) int.h M #define short_o_short_2(ref) ((char *)(ref)) #define short_o_short_1(ref) ((char *)(ref)+2) short.h acros générés pour le type short :
Le problème posé par ce développement réside en la création de bibliothèques de base tout en gardant modularité, efficacité et indépendance du langage utilisé. La partie suivante traite du problème de placement mémoire. En effet, les objets générés par le SDE existant ne sont pas stockés en mémoire de manière optimale : à savoir, une occupation mémoire minimale et un accès rapide au données stockées.
Dans l’actuel du SDE, les objets créés (entier, caractère, booléen, chaîne, tableaux…) sont tous stockés en mémoire de la même manière : ils sont alignés sur des adresses mémoire multiples de 4 octets. Pourtant, tout processeur propose un alignement favorisant l’accès à ces objets. Par la suite nous considérerons que cette proposition est une règle à ne pas violer. De plus, l’espace mémoire utilisé doit être minimal : il est donc nécessaire de trouver un algorithme qui limite au minimum l’espace perdu entre les objets placés. Règle 1 : L’adresse allouée à un objet placé en mémoire doit satisfaire (être multiple de) l’alignement dicté par le processeur utilisé. Optimisation 1 : L’espace restant entre deux objets placés en mémoire doit être minimal. Pour l’ensemble des exemples d’utilisation qui vont suivre, nous prendrons comme table de référence le tableau suivant pour calculer l’alignement mémoire des objets à placer selon un processeur .
Tableau 1 : Alignement mémoire dicté par le processeur . Par exemple, un objet de 2 octets sera placé à une adresse mémoire multiple de 2, un objet de 7 octets à une adresse mémoire multiple de 8.
Liste des objets à placer en mémoire :
Une solution d’un SDE utilisant un algorithme sans optimisation de la mémoire pourrait être la suivante (tous les objets sont alignés sur une adresse multiple de 4 octets) :  Espace mémoire utilisé : 28 octets.
Le but de l’algorithme d’optimisation de la mémoire est d’obtenir une solution du type :  Espace mémoire utilisé : 19 octets.
Liste des objets placés en mémoire :
La règle 1 vue précédemment impose à un objet d’être placé en mémoire à une adresse multiple de son alignement. La raison principale de cette règle provient du fait que certains processeurs interdisent la violation d’alignement. Nous utilisons donc une fonction appelée Alignement_processeur, qui donne l’alignement d’un objet en fonction de sa taille. Par la suite, cet objet est placé en mémoire à une adresse multiple de cet alignement. Cette fonction permet, en fonction de la taille de l’objet à placer, de trouver l’alignement correspondant selon un mode quelconque de récupération des données décrivant un processeur. Par exemple, il est possible de définir les données du processeur dans un fichier de description, que la fonction Alignement_processeur peut parcourir et retourner l’alignement correspondant (cf. section Perspectives du travail p.36). Le tableau 1 de la page 14 donne un exemple de ce que rend la fonction Alignement_processeur selon les caractéristiques d’un processeur . Une fois cet alignement récupéré, il faut alors rechercher l’emplacement mémoire approprié de l’élément. La fonction Recherche_offset permet, en fonction de la taille de l’objet donné, de connaître le plus petit offset, dans un espace mémoire borné, allouable à cet objet tout en respectant l’alignement placé en paramètre. (cf. Annexe 5.6.) Ces méthodes sont utilisées dans la fonction récursive Remplissage, qui implémente notre algorithme de placement mémoire. Cette fonction permet, étant donné un espace mémoire borné et une liste d’objets, de remplir ce dernier en occupant le moins de place possible, tout en suivant l’alignement imposé par le processeur utilisé; comme défini plus haut. Elle retourne la structure, de type Align_struct (cf. section Les structures utilisées p.23), qui englobe tous les objets placés. Cette structure retournée, utile à l’interface avec la partie analyse de type, contient les informations suivantes :
Notons de plus que chaque objet étant susceptible d’être composé d’une liste d’espaces mémoire non occupés, la structure retournée par cette fonction est donc mise à jour en ajoutant ces espaces à sa propre liste. (cf. Annexe 5.1.) Le champ alignement de la structure retourné par la fonction précédente nécessite un traitement particulier. En effet, l’alignement de la structure englobante correspond au plus petit commun multiple (ppcm) des alignements des objets composant la structure englobante. Chacun de ces objets doit respecter son alignement ou plus précisément, être multiple de son alignement (dicté par le processeur utilisé). Il en est de même pour cette structure. Or une fois l’offset final de la structure calculé (elle est placée en mémoire), chaque objet la composant voit son offset modifié. Pour que ces derniers soient corrects, l’offset de la structure doit être un multiple commun à l’alignement de chacun de ces objets. Pour des raisons d’optimisation (la taille de la mémoire utilisée doit être minimale), nous choisissons le plus petit de ces multiples : le ppcm.
La seule fonction permettant d’affecter l’emplacement mémoire réel d’un objet est la fonction Optimisation_mémoire_finale, qui permet, étant donnée une liste d’objets, de les placer en mémoire de façon à occuper le moins d’espace mémoire possible. La technique d’optimisation utilisée ici consiste à trier la liste des objets en paramètre selon leur taille décroissante, ce qui permet de placer d’abord les plus gros objets selon leur alignement, puis de placer les plus petits dans les espaces libres laissés par les premiers objets. Notons de plus que l’alignement des objets se fait dans une liste d’espaces libres (cf. section Les structures utilisées p.23), appelée ici liste_trous, triée elle aussi, mais selon leur adresse mémoire croissante, afin de placer l’ensemble des objets dans un espace mémoire proche pour faciliter les accès mémoire. (cf. Annexe 5.2.)
La raison de l'utilisation d'une liste de trous pour représenter l'espace mémoire est issue de l'adressage des objets manipulés. En effet, la règle 1 énoncée en introduction impose un certain adressage pour chaque objet. Ainsi, entre deux objets un espace mémoire peut rester libre (non occupé) : c’est un trou. Prenons par exemple une structure (représentant un élément de tableau ou d’union) composée des objets suivants :
Etat de la mémoire représentant la structure une fois les objets placés : 
 offsets 5 à 6
Liste des trous de la structure
offsets 13 à 14 offsets 19 à 20
Cette liste de trous, ainsi obtenue, permettra de mettre à jour l’espace mémoire dans le but d’adresser de nouveaux objets. Ces objets peuvent ainsi être placés à l’intérieur de ces trous et l’espace mémoire libre de cette structure est alors optimisé. La fonction Optimisation_mémoire_structure permet, étant donnée une liste d’objets, de les placer en mémoire de façon optimale de la même façon que la fonction définie précédemment. Cette fonction utilise Remplissage pour placer dans un espace mémoire fictif (de l’offset 0 à l’offset ) une liste d’objets. De plus, une structure de type Align_struct, représentant cet élément, est retournée par cette fonction.
Un tableau est composé d'un certain nombre d'éléments répartis dans des cases. Ces éléments sont soit eux-mêmes des tableaux, soit une structure d'objets. Cette structure est donc composée d'un ou plusieurs objets (entier, caractère, booléen, chaîne …)
Etat de la mémoire représentant un élément du tableau une fois les objets placés :  Notons que l'alignement d'un tel élément correspond au ppcm de l'alignement des objets internes, comme nous l’avons vu précédemment. Soit pour le cas qui nous intéresse ici : ppcm(2, 4, 8) 8 Si l'on considère que le tableau comprend deux éléments alors l'élément suivant sera aligné sur une adresse multiple de 8. Soit dans ce cas 16. On obtient alors : 
1er élément du tableau 
espace mémoire non utilisé (trou)
2ème élément du tableau C'est pourquoi nous retenons pour chaque tableau l'ensemble des trous existants afin de remplir cet espace ultérieurement. En effet, ces trous peuvent se répéter de nombreuses fois et peuvent être très grands. La fonction Optimisation_mémoire_sous_tableau récupère la structure englobante retournée par la fonction précédente et un nombre. Ce nombre correspond à la quantité d'éléments (représentés par cette structure) souhaitée dans le tableau. Elle retourne une structure représentant ce tableau. (cf. Annexe 5.4.)
Une union permet à l’utilisateur de choisir dynamiquement le type d’objet qu’il utilise. Ce sont des unions discriminantes. L’originalité des objets appartenant à une union est qu’ils doivent tous occuper le même emplacement mémoire ; ce qui signifie avoir tous le même offset (cf. exemple). Sachant qu’une union est un « type » récursif (il est possible d’avoir une union d’union, etc.), nous avons défini une fonction adaptée à ce « type ». La gestion de l’espace mémoire libre est ici spécifique aux unions. En effet, la liste des « trous » n’est pas la même pour chaque structure d’une union. Nous choisissons donc ici, l’intersection de toutes les listes de « trous » de chaque structure pour composer celle de la structure union.
Notons que l'alignement d'une telle union correspond au ppcm de l'alignement des structures qui la composent. Soit pour le cas qui nous intéresse ici : ppcm(4, 8, 8) 8
Liste des espaces restés libres de l’union : offsets 5 à 6 et offsets 13 à 16. La fonction Optimisation_mémoire_sous_union prend en paramètre la liste des objets composant une union et retourne la structure représentant l’union (Align_struct). (cf. Annexe 5.5.)
Comme nous l’avons vu dans la partie 3.1, les différents types utilisables par le SDE sont les opaques simples et les types structurés (structures, tableaux, unions). Afin de manipuler de manière abstraite les données, l’alignement des objets générés par le SDE se fait à l’aide d’une structure intermédiaire appelée Align_struct. Toutes les manipulations que nous effectuons pour allouer l’adresse mémoire se font par l’intermédiaire de cette structure. Composition de cette structure : Structure Align_struct champ1 size ; -- taille de l’objet champ2 offset ; -- offset de l’objet champ3 alignement ; -- alignement de l’objet champ4 ident ; -- étant donnée une liste d’objets, ce champ indique -- la position initiale de l’objet dans cette liste champ5 path ; -- chemin donnant l’adresse de l’objet champ6 liste_trous ; -- liste comprenant les espaces mémoire restés libres -- dans un objet complexe (structure, tableau, union)
La mémoire dans laquelle sont placés les objets générés par le SDE est structurée virtuellement comme une liste d’espaces non occupés. Avant le placement mémoire des objets, cette liste est composée d’un seul élément représentant toute la mémoire. Puis, au fur et à mesure de l’adressage, cet élément se découpe en plusieurs. Composition de cette structure : Structure Mem_list { qui hérite de l’objet java Vector } méthode Sort( ) : permet de trier par offset croissant des éléments de cette liste méthode Intersection( list ) : remplace la liste par l’intersection de cette dernière et une deuxième placée en paramètre
Pour représenter les éléments d’une liste définie comme précédemment, nous disposons d’une structure à deux champs appelée Doublet_int. Le premier champ correspond à l’adresse de début de l’espace mémoire, le second champ à celle de fin de l’espace mémoire. Composition de cette structure : Structure Doublet_int champ1 premier ; -- début de l’espace mémoire libre champ2 second ; -- fin de l’espace mémoire libre méthode : Is_equal( doublet ) : teste l’égalité entre deux doublets méthode : Is_empty( ) : teste si le premier champ est égal au deuxième méthode : Intersection( doublet ) : calcule l’intersection entre le doublet et celui passé en paramètre
Un type de taille variable est un type dont la taille ne sera connue qu’à l’exécution. Dans SDE, il y a deux façons de construire un type de taille variable, la première est d’utiliser le type composé Union, et la deuxième est d’utiliser le type composé Tableau.
Voici la déclaration du type Union : union [ { [ [ […] ] ] } Le type Union est une liste de tous les types possibles et le nom spécifié est utilisé pour accéder à un type spécifique d’une instance pendant l’exécution. C’est la fonction de sélection optionnelle qui rend le type variable car cette fonction (implémentée en « C » ) est appelée pour déterminer, au moment de l’allocation mémoire, le type de l’union qui sera vraiment utilisé. S’il n’y a pas de fonction de sélection spécifiée, alors la fonction d’allocation générée par SDE choisit la taille maximale et l’alignement maximal de tous les membres de l’union, ce qui nous conduit à une allocation statique décrite dans la première partie. Exemple de déclaration d’un type variable :  a  vec les déclarations suivantes des sous-types utilisés: Dans le cas où aucune fonction de sélection n’est indiquée, SDE alloue 4 octets pour le type frame ; ce qui correspond à la taille maximale de la liste composant l’union. Dans le cas contraire, SDE appelle la fonction selection qui détermine le type effectivement utilisé. Le résultat de la fonction selection est de type int, car cela permet à l’utilisateur de choisir un champ particulier de l’union en utilisant les macros générées par SDE.
Dans cet exemple, la taille allouée pour le frame est de 1 octet. Maintenant, examinons comment l’allocation mémoire est effectuée. Si le type sélectionné dans l’union est float, SDE ne peut pas le savoir lors de l’analyse du type, mais seulement à l’exécution quand la fonction d’allocation <type>Alloc(…) est appelée. Le contenu de cette fonction pour le type frame défini ci-dessus est : void frameAlloc(…) { …
switch (selection(…)) { case i_type: size+=2; /* taille int_2 */ break; case s_type: size+=1; /* taille string */ break; case f_type: size+=4; /* taille float */ } ref=malloc(size); …
frameAlloc.c SDE doit définir des macros d’accès aux champs du type. Ces macros ont la forme suivante pour l’exemple précédent : #define frame_i(ref) ((char *)(ref) …+offset) #define frame_s(ref) ((char *)(ref) …+offset) #define frame_f(ref) ((char *)(ref) …+offset) frame.h De même que la taille d’un type union, l’offset des macros ne peut se calculer qu’à l’exécution. C’est pour cela que SDE définit des pointeurs en direction d’emplacements mémoires. A chaque fois qu’un type union défini avec une fonction de sélection est rencontré lors de l’analyse, un emplacement mémoire de la taille d’un pointeur est réservé. Puis, une mise à jour de ces pointeurs est effectuée lors de l’exécution de la fonction <type>Alloc(…). Ainsi, l’offset est récupéré permettant l’implémentation complète des macros. R
void frameAlloc(…) { int size=0 /* taille fixe */ size+=taille(pointeur); switch (selection(…)) { case i_type: size+=2; /* taille int_2 */ break; case s_type: size+=1; /* taille string */ break; case f_type: size+=4; /* taille float */ } ref=malloc(size); *pointeur(ref)=20; } frameAlloc.c e contenu de la fonction d’allocation devient : #define pointeur(ref) ((char *)(ref)) #define frame_i(ref) ((char *)(ref)+*pointeur(ref)) #define frame_s(ref) ((char *)(ref)+*pointeur(ref)) #define frame_f(ref) ((char *)(ref)+*pointeur(ref)) frame.h L’alignement est géré localement pour les types de taille variable : Au moment de l’allocation mémoire d’un type, les champs de celui-ci sont alignés par rapport aux contraintes dues à l’architecture puis un emplacement mémoire est alloué au type. Une solution plus efficace en coût mémoire consisterait à implémenter les algorithmes utilisés pour l’alignement des types de taille fixe dans l’exécutable.
Dans SDE, il est possible de déclarer des types tableaux :
Voici, comment SDE effectue l’allocation mémoire :  void ThreadAlloc(…) { int size=5; /* taille fixe */ int i=0; for(i=0;i { size+=4; /* taille int_4 */ size+=1; /* taille string */ } for(i=0;i { size+=2; /* taille int_2 */ size+=1; /* taille string */ } ref=malloc(size); …
ThreadAlloc.c Une seule allocation mémoire est effectuée pour le type tableau. En effet, il est important de respecter la localité mémoire pour les champs composant le type et une efficacité lors de l’accès à ces champs. De manière identique aux types Union, SDE définit des macros pour accéder aux éléments de ce tableau. Sur l’exemple précédent, les macros générées sont : #define pointeur1(ref) ((char *)(ref)+4) #define pointeur2(ref) ((char *)(ref)+9) #define Thread_tableau_int_4_i(ref,i0) ((char *)(ref)+*pointeur1(ref)+i0*5) #define Thread_tableau_int_4_s(ref,i0) ((char *)(ref)+*pointeur1(ref)+i0*5+4) #define Thread_tableau_int_2_i(ref,i0) ((char *)(ref)+*pointeur2(ref)+i0*3) #define Thread_tableau_int_2_s(ref,i0) ((char *)(ref)+*pointeur2(ref)+i0*3+2) Thread.h En plus de la référence, l’utilisateur a besoin d’un index indiquant l’élément du tableau auquel il veut accéder. L’utilisation de pointeurs, comme pour les types Union de taille variable est indispensable. SDE effectue une mise à jour des pointeurs utilisés qui référencent alors les emplacements mémoires contiguës réservés pour le tableau. Nous avons donc sur l’exemple précédent : void ThreadAlloc(…) { …
int temp=13; /* variable temporaire (init. avec */ /*la taille fixe du type) utilisée pour */ /*calculer l’offset pointé par * pointeur2 */ *pointeur1(ref)=temp; /* offset pointé */ for(i=0;i { temp+=4; /* taille int_4 */ temp+=1; /* taille string */ } *pointeur2(ref)=temp; } ThreadAlloc.c Pour les mêmes raisons que pour le type Union, l’alignement d’un tableau est effectué localement pour chaque élément du tableau. Dans SDE, il existe un cas particulier de définition d’un type qui est très intéressant du point de vue de l’économie mémoire : un type tableau de taille variable dont tous les éléments peuvent être différents. Exemple : Considérons le type Object qui est utilisé dans la JVM. Ce type est la réunion de tous les types de base de Java, ce qui se traduit dans SDE par : a typedef Object { } Object.idl type Object { private : union { byte b; double d; short s; int i; boolean bo; float f; …
} Object.imp vec :  Nous observons que, avec la fonction de sélection spécifiée, nous évitons une perte de mémoire. En effet, sans cette fonction, SDE alloue un emplacement mémoire correspondant au type de taille maximale composant l’union (donc ici, 4 octets), ce qui est ennuyeux si le champ réellement utilisé est de type byte (de taille 1 octet), d’où une perte de mémoire assez conséquente. De même, grâce à la fonction de dimension du tableau, nous évitons une perte de mémoire : en effet, dans le cas où l’on veuille utiliser un seul champ du tableau, si la dimension est fixée à la compilation pour le tableau alors la perte mémoire est énorme ; alors qu’en utilisant la fonction de dimension, l’utilisateur peut déclarer un tableau de dimension 1 à l’exécution.
|
Int_4