Modalités de rendu
===================
Groupe de News: epita.cours.c++
Date de rendu: vendredi 31 janvier 2003 - 23:42:00
Répertoire de rendu: ~/rendu/cpp/new/
Droits sur le rep et les exos: 700 sur ~/rendu/cpp/, ~/rendu/cpp/new/
600 pour les fichiers
o+x ~/ ~/rendu/ ~/rendu/cpp/
Les informations ci-dessus peuvent changer jusqu'au 29/01/2003 12h00.
La tarball compressé avec bzip2 devra s'appeler login-new.tar.bz2 et
se decompresser dans le sous-repertoire login-new/.
Sujet
=====
Cet exercice est un exercice de transition entre les sujets
que vous ont donné les ACU et les sujets que vont vous donner les Yakas.A
L'objectif est de vous faire comprendre ce qu'est une politique
de gestion mémoire et ce que font l'operateur new et delete en C++.A
Dans ce sujet, comme dans les suivants que vous donneront les Yakas,
une importance toute particulière sera portée sur vos capacités à :
- effectuer des recherches par vous-mêmes ;
- livrer un code propre et commenté ;
- implémenter une solution performante ;
- réaliser un jeu de tests complet de votre projet.
Ces objectifs comptent pour moitié dans la notation : il est
impossible de dépasser 10/20 sans les avoir atteints.
Fonctions autorisés
===================
Bien entendu, vous n'êtes pas autorisé à utiliser malloc/realloc/free. Il
vous est fortement recommandé d'utiliser la fonction sbrk pour gérer votre
mémoire. L'objectif étant la vitesse, n'oubliez pas que derrière sbrk se
trouve un appel système, donc appelez sbrk de manière intelligente (en
allouant par exemple de gros morceaux d'un coup, les pools).
NB: Vous pouvez utiliser aussi la famille de fonctions m*map, mais ce n'est
pas recommandée et ce sera sûrement très mal payé.
Exercice
========
Le but de cet exercice est donc de réaliser une bibliothèque qui gérera les
opérateur suivant :
extern void* operator new (size_t);
extern void* operator new[] (size_t);
extern void operator delete (void*);
extern void operator delete[] (void*);
Pour vous permettre de gérer plus facilement et efficacement les pools,
on vous propose les prototypes suivant:
extern void* operator new (size_t, enum color_e);
extern void* operator new[] (size_t, enum color_e);
extern void operator delete (void*, enum color_e);
extern void operator delete[] (void*, enum color_e);
L'énumération color_e contient au moins les couleurs suivantes:
red, cyan, blue, yellow, purple, green, white, black
Le fait d'allouer deux objets en utilisant la même couleur, veut dire qu'ils
sont proches en terme d'usage et de type. De plus, les couleurs auront aussi
un sens au niveau de la taille maximum qui sera demandé à votre allocateur.
Ainsi:
* red, cyan => size_t <= 32 o
* blue, yellow => 32 o < size_t <= 4 Ko
* purple, green => 4 Ko < size_t
* white, black => aucune taille ne leur est spécifiquement allouée, ils
peuvent par exemple être utilisés par les opérateurs new et delete par
défaut.
Attention, le pointeur que retourne votre new doit être aligné (multiple de
sizeof (void *)). Sur x86, ca n'a d'impact que sur les performances, mais sur
Sun, ou tout autre architecture RISC, votre code ne marchera pas, donc pensez
à le tester sur Sun. L'alignement sera vérifié sur x86 aussi.
Ce sera votre fichier libnew.hh qui sera inclu lors des tests, donc vous
pouvez y rajouter toutes les informations que vous jugerez utiles.
Remarques
=========
Une part importante de la notation est consacrée aux performances de votre
allocateur. Si deux implémentations vont aussi vite, celle qui aura le
meilleur ratio données utilisées par votre allocateur par rapport aux
données réellement utilisées par l'application.
Le "make check" doit être complété et doit être le plus exaustif possible.
On attend un jeu de test évaluant aussi bien le bon fonctionnement de votre
allocateur que sa vitesse (Ne pensez pas qu'on va utiliser votre jeu de test
pour savoir si votre allocateur fait ce qu'on attend de lui). Pensez à
l'utiliser sur diverses plateformes.
Ne réinventez pas la roue, de nombreuses personnes ont déjà fait des
recherches sur le sujet, commencez par vous documenter avant d'implémenter
votre allocateur de mémoire.
Options
=======
Il existe une fonction : "DeallocateAll (enum color_e)" dans le fichier
libnew.hh qui permet de désallouer tous les objets alloués pour une
certaine couleur, c'est-à-dire un certain pool. (Mot clef: "deallocateall")
Gérer de manière différente chacune des tailles proposées. Mieux vous gérerez
cela, plus vous monterez votre note. Pour départager ceux qui ont les
meilleurs résultats, le rapport entre mémoire donnée au programme et
mémoire utilisée par l'allocateur sera regardé. Donc optimiser votre
utilisation de la mémoire aussi. (Mot clef: "multisize", à ne mettre que si
vous implémentez de différente manière la gestion de ces trois tailles)
Si vous avez une meilleure idée de prototype pour les opérateur new et
delete, vous pouvez l'implémenter. Et les extentions sont nombreuses, car
nous avons volontairement choisi de vous fournir un code encore proche du C,
donc il est possible de faire quelque de mieux conçu, si vous utilisez toute
la puissance du C++. Mais vous aurez des points que si la partie par défaut
fonctionne correctement. Bien entendu, n'oubliez pas de prendre
un jeu de test pour nous prouver son utilité. De plus si vous vous êtes
inspiré d'un travail déjà effectué venez avec vos liens ou pdf (si ce n'est
pas le cas pensez tout de même à vérifier, on est rarement le premier à
penser à quelque chose ;-) (Mot clef: "etendu")
Utiliser en même temps sbrk pour faire grossir le tas du process et m*map
pour gérer une partie de votre allocation mémoire. Nous attendons vraiment
que vous utilisiez les deux conjointements durant toute l'exécution du
process et pas uniquement pour initialiser mmap. (Mot clef: "mmap")
Le repertoire de rendu
======================
Le répertoire de rendu devra contenir obligatoirement les fichiers suivants
et sous cette forme. (Tous ces fichiers sont présents dans la tarball, il
vous reste juste à les mettre à jour, sauf ceux pour les options).
- AUTHORS
- LINKS
Contient :
#http://mon.site.web.interressant/
Titre Auteur
(Attention ne mettez pas de # dans les differentes descriptions)
- ChangeLog
Contient :
AAAA-MM-JJ Prenom NOM :
* libnew/libnew.hh: fait ca
- TODO
Contient :
La liste des choses qu'il reste à faire (ce n'est pas forcément vide...)
- Makefile
Contient :
- une règle "check" qui permet de lancer votre jeu de tests et signale les
tests problématiques.
- une règle "all" et une règle "clean" qui font travaille classique que
l'on attend de ces règles.
- test/
Répertoire contenant vos tests
- libnew/
Répertoire contenant vos sources
- libnew/libnew.a
Archive compilé par vos Makefile et qui sera utilisé par les tests des Yakas
- libnew/libnew.hh
Fichier header inclus dans les tests des Yakas.
- README
Décrivez en 5 lignes ce que fait votre allocateur de mémoire (Faites une
phrase avec au moins un sujet, un verbe et un complément).
Si vous faites des options (seul moyen d'être noté sur vos options) :
- options
Mettez une ligne contenant le mot clef spécifique à l'option, si ce n'est
pas fait ce n'est pas corrigé (Si une option implémanté n'a pas été prévu,
mettez le mot clef: "autre").
- descriptions
Si vous avez mis le mot clef "autre" ou "etendu", décrivez vos options
personnelles de manière précise ici.
Lecture
=======
* Memory Management in C++ by Nathan C. Myers
http://www.cantrip.org/wave12.html
* The Art of Computer Programming, by D. Knuth
|
