------ Compte Rendu du TP "Allocation Memoire" Savas Ali Tokmen 06.dec.2005 ------ Ce compte rendu comporte 5 sections: 1- Organisation des fichiers 2- Organisation des definitions 3- Organisation des fonctions 4- Tests superficiels 5- Conclusions Vous trouverez ci-joint mon TP sur l'allocation memoire. Pendant sa realisation, j'ai choisi certaines pistes (qui n'etaient pas montres en TD) donc je vais les expliciter... 1) Organisation des fichiers Avant tout, j'ai reconstruit le Makefile: le mode "debug" a ete enleve (gdb ne me comprenant pas tres bien!) et j'ai cree des taches. La tache "sans" cree et execute le gestionnaire qui n'utilise pas de listes, et la tache "liste" cree et execute le gestionnaire qui utilise les listes pour chainer les espaces occupes et vides. J'ai aussi fait passe un coup de beautifuleur sur memshell.c (pour le rendre lisible de ma part -reindenter et enlever les tabs en gros) et ajoute une commande bien sympa: e, pour ecrire dans la memoire! Les definitions sont dans mem.h et les realisations dans mem.c 2) Organisation des definitions Le flag MODE_SANS_LISTE est defini si on veut compiler en mode sans chainage. Un bloc a 3 ou 4 composants (en fonction de MODE_SANS_LISTE): - Une signature "protect1", pour protection contre debordements - La taille, qui peut etre positive ou negative (si negative alors occupe, positive sinon) et qui exprime la taille du contenu (donc pas du bloc en entier) en pointeurs (et pas en octets) - Un pointeur vers le prochain si necessaire est (MODE_SANS_LISTE ou pas) - Une signature "protect2", pour protection contre debordements Le type pblock est un pointeur de bloc, et de divers #define sont ici pour remplacer les sizeof sur les divers structures concernant. 3) Organisation des fonctions Vu que la gestion et l'affichage depend du type d'organisation, les fonctions afficher_zones_libres, afficher_zones_occupes, mem_alloc et mem_free apellent la version avec ou sans chaines, en fonction de MODE_SANS_LISTE. La sortie de l'appel "m" a ete modifie pour montrer la memoire par taille de pointeurs (et pas par char comme a la version d'origine) J'ai generalement essaye de separer en mettant les definitions avec chaines suivi des definitions sans chaines, un professionnel aurait separe les deux fichers. En outre, on remarquera que les versions avec chaines "contiennent" en gros le meme code que les versions sans chaines, mais avec en plus la gestions des liens et des sauts entre blocs un peu plus rapides... 4) Tests superficiels Je vais faire quelques tests, mais ceux que j'ai faits ne se limitent pas a ca! Notez que l'on prendra une memoire de 128 pour pouvoir utiliser "m" Test de la version sans liste: > make sans rm -f *.o memshell *~ clear gcc -DMODE_SANS_LISTE *.c -o memshell ./memshell [ ... ] Init 29 * 4 = 116 OK Test des allocations a0 Echec de l'allocation a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 12 a2 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 28 a3 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 44 a4 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 60 a5 2 pointeurs (donc 8 octets) alloues avec succes Memoire allouee en 76 m 134522176 1 134522184 0 134522192 1 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 8 134522268 0 0 0 0 0 0 0 0 o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 28, taille 4 - Emplacement 44, taille 4 - Emplacement 60, taille 4 - Emplacement 76, taille 8 i Affichage des blocs inoccupes: - Emplacement 96, taille 32 Test de desallocation: a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 96 l60 Desallocation OK i Affichage des blocs inoccupes: - Emplacement 60, taille 4 - Emplacement 112, taille 16 o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 28, taille 4 - Emplacement 44, taille 4 - Emplacement 76, taille 8 - Emplacement 96, taille 4 m 134522176 1 134522184 0 134522192 1 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 1 134522268 0 134522276 4 134522284 0 0 0 0 Test de reallocation: a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 60 o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 28, taille 4 - Emplacement 44, taille 4 - Emplacement 60, taille 4 - Emplacement 76, taille 8 - Emplacement 96, taille 4 i Affichage des blocs inoccupes: - Emplacement 112, taille 16 m 134522176 1 134522184 0 134522192 1 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 1 134522268 0 134522276 4 134522284 0 0 0 0 Test de l'allocation "plus grande" car pas assez d'espace restante: a1 4 pointeurs (donc 16 octets) alloues avec succes Memoire allouee en 112 m 134522176 1 134522184 0 134522192 1 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 1 134522268 0 134522276 4 134522284 0 0 0 0 o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 28, taille 4 - Emplacement 44, taille 4 - Emplacement 60, taille 4 - Emplacement 76, taille 8 - Emplacement 96, taille 4 - Emplacement 112, taille 16 Second test de la desallocation et test de l'amalgamation: l28 Desallocation OK l60 Desallocation OK l96 Desallocation OK o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 44, taille 4 - Emplacement 76, taille 8 - Emplacement 112, taille 16 i Affichage des blocs inoccupes: - Emplacement 28, taille 4 - Emplacement 60, taille 4 - Emplacement 96, taille 4 m 134522176 1 134522184 0 134522192 1 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 1 134522268 0 134522276 4 134522284 0 0 0 0 l44 Desallocation OK o Affichage des blocs occupes: - Emplacement 12, taille 4 - Emplacement 76, taille 8 - Emplacement 112, taille 16 i Affichage des blocs inoccupes: - Emplacement 28, taille 36 - Emplacement 96, taille 4 m 134522176 1 134522184 0 134522192 9 134522200 0 134522208 1 134522216 0 134522224 1 134522232 0 134522240 2 134522248 0 0 134522260 1 134522268 0 134522276 4 134522284 0 0 0 0 Petit test final: desallocation d'adresse non-allouee l60 Cette adresse n'est pas allouee Voila... Ceci est a mon avis un bon "tour" des fonctionnalites du gestionnaire memoire. Notez que la version avec couleurs de "m" est plus comprehensible, donc je vous conseille de lancer le logiciel "pour de vrai" si vous avez des doutes (ou encore qui vous vous demandez ce que ca donne avec les couleurs) Maintenant la version avec listes (ou chainage): > make liste rm -f *.o memshell *~ clear gcc *.c -o memshell ./memshell [ ... ] Init 28 * 4 = 112 OK Test des allocations (le dernier etant une allocation "plus grande" car pas assez d'espace restante pour pouvoir mettre une entete de bloc) a0 Echec de l'allocation a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 16 a2 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 36 a3 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 56 a4 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 76 a5 2 pointeurs (donc 8 octets) alloues avec succes Memoire allouee en 96 m 134523456 1 134523476 134523468 0 134523476 1 134523496 134523488 0 134523496 1 134523516 134523508 0 134523516 1 134523536 134523528 0 134523536 2 0 134523548 0 0 134523560 2 0 134523572 0 0 o - Emplacement 16, taille 4 - Emplacement 36, taille 4 - Emplacement 56, taille 4 - Emplacement 76, taille 4 - Emplacement 96, taille 8 i - Emplacement 120, taille 8 Test de desallocation: l76 Desallocation OK Amalgamation OK i - Emplacement 76, taille 4 - Emplacement 120, taille 8 o - Emplacement 16, taille 4 - Emplacement 36, taille 4 - Emplacement 56, taille 4 - Emplacement 96, taille 8 m 134523456 1 134523476 134523468 0 134523476 1 134523496 134523488 0 134523496 1 134523536 134523508 0 134523516 1 134523560 134523528 0 134523536 2 0 134523548 0 0 134523560 2 0 134523572 0 0 Test de reallocation: a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 76 m 134523456 1 134523476 134523468 0 134523476 1 134523496 134523488 0 134523496 1 134523516 134523508 0 134523516 1 134523536 134523528 0 134523536 2 0 134523548 0 0 134523560 2 0 134523572 0 0 o - Emplacement 16, taille 4 - Emplacement 36, taille 4 - Emplacement 56, taille 4 - Emplacement 76, taille 4 - Emplacement 96, taille 8 Second test de la desallocation et test de l'amalgamation: l36 Desallocation OK Amalgamation OK l76 Desallocation OK Amalgamation OK i - Emplacement 36, taille 4 - Emplacement 120, taille 8 m 134523456 1 134523496 134523468 0 134523476 1 134523560 134523488 0 134523496 1 134523536 134523508 0 134523516 1 134523536 134523528 0 134523536 2 0 134523548 0 0 134523560 2 0 134523572 0 0 l56 Desallocation OK Amalgamation OK i - Emplacement 36, taille 24 - Emplacement 120, taille 8 m 134523456 1 134523536 134523468 0 134523476 6 134523560 134523488 0 134523496 1 134523536 134523508 0 134523516 1 134523536 134523528 0 134523536 2 0 134523548 0 0 134523560 2 0 134523572 0 0 Petit test final: desallocation d'adresse non-allouee l60 Cette adresse n'est pas allouee Aussi, un petit bonus: test de la protection des entetes, avec une ecriture "normale" et une ecriture "mauvaise" [ ... ] Init 28 * 4 = 112 OK a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 16 m 134523456 1 0 134523468 0 134523476 23 0 134523488 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 e 16 145 m 134523456 1 0 134523468 145 134523476 23 0 134523488 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 On a donc le droit d'ecrire des donnees dans les espaces alloues... a1 1 pointeurs (donc 4 octets) alloues avec succes Memoire allouee en 36 e 32 145 a1 La memoire est corrompue ! Echec de l'allocation l32 La memoire est corrompue ! Donc, la protection marche et s'active a chaque allocation et desallocation... 5) Conclusions Je penses avoir donc fait deux systemes d'allocation memoire qui marchent plus ou moins bien, a mon avis plutot plus bien que moins bien... Ce qui serait interessant a etudier est sans doute le nombre d'acces memoire pour chaque mode: en effet, mes tests personnels mais encore trop superflus (par manque de temps) montrent que: - En general, si la memoire est coupee en grosses parties occupes et inoccupes (en d'autres termes si les blocs occupes et inoccupes se suivent bien) les listes nous menent directement a l'endroit a allouer / desallouer donc la version en liste est clairement plus rapide que la version sans liste (ou sans chainage) - Par contre, si la memoire est formee de petits blocs d'occupation et d'inoccupation successifs, alors le parcours et surtout la mise a jour des pointeurs de chainage devient une tache importante a chaque allocation et desallocation; et on arrive a un cas ou la version non-chainee fait moins d'acces memoire que la version chainee! Il faudrait sans doute pousser cette etude plus loin pour en deduire une rigueur. Mais, je penses que vu qu'a chaque fois que l'on accede aux listes c'est probablement pour les modifier (car allocation / desallocation), on perd pas mal de temps a les mettre a jour plutot qu'a en tirer profit. Je penses donc que les listes sont peut-etre beaucoup trop precises pour cet usage, il vaudrait peut-etre mieux des indexations plus vagues pour en meme temps passer moins de temps a chercher et a mettre a jour. Je vous remercie d'avoir lu ce compte rendu jusqu'au bout. J'esperes que mon programme a un code source facilement lisible et comprehensible et que son executable est convivial et sans trop d'erreurs enervantes. Cordialement; S. Ali Tokmen http://ali.tokmen.com