Discussion :

[lludol]

Bonjour,

Je dois recoder malloc pour mon ecole, je n'ai le droit qu'a brk/sbrk pour allouer de la memoire (et j'ai aussi le droit a toute la libc) et j'ai une petite question.

J'ai donc trouve pleins d'algo different, j'ai compris comment malloc fonctionne et comment le recoder mais je n'arrive pas a comprendre quel taille devront avoir les differents bloc memoires.

Pour ceux qui ne savent pas comment malloc doit marcher, en gros c'est ca :
On alloue la memoire sous forme de bloc de X octets (en fonction du nombre d'octet demande et de la memoire que notre malloc a besoin).
On garde en memoire (souvent sous forme de liste chainee) les differents blocs alloues ou free (avec differentes infos comme l'adresse memoire du debut du bloc, sa taille, etc, etc).
Si un bloc est free et qu'un bloc adjacent est free, on les "colle".
Si un bloc est libre et qu'il correspond aux bon nombres d'octets qu'on a besoin, on le donne a l'utilisateur.
etc

Sur le net, j'ai trouve pas mal d'algo qui utilise les puissances de 2 ou les multiples de 4 (en gros, c'est jamais alloue au "pif", ca suit toujours une regle precise) pour allouer X octets par blocs.

Donc en gros, si l'utilisateur a besoin de 42 octets et que mon malloc a besoin de 32 octets pour fonctionner (donc pour stocker les differentes infos), le malloc doit regarder a quelle puissance de 2 cela correspond.

Pour l'exemple, ca fait 42 + 32 = 74 ce qui nous donne 2^7 = 128.
Donc je vais devoir allouer un bloc de 128 ou 128 - 74 = 54 octets seront libres.

Le probleme, c'est que si le mec demande 4 octets, je peux utiliser le bloc de 54, donc il restera 54 - (32 + 4) = 18 octets de libre.
Sauf que mon malloc a besoin de 32 octets donc au final, ce bloc de 18 octets ne sera jamais utilise.

Et donc, s'il y a de la memoire non utilisee c'est pas opti ! (en gros, si a la fin de chaque bloc y a genre ~20 octets non utilise je trouve pas du tout ca opti).
C'est ca que j'arrive pas a comprendre, dans tous les algos que j'ai trouve, a chaque fois on peut arriver a ce cas.

Est ce que j'ai rien compris ou c'est tout simplement normal ??


NB : Si on alloue trop d'octets a chaque fois, c'est justement pour appeler le moins de fois les fonctions sbrk/brk.
Et dsl pour les accents mais je suis en qwerty.

[Médinoc]

Tu n'as pas forcément besoin d'arrondir à la puissance de 2 supérieure. C'est fait parfois pour pouvoir mieux réutiliser la mémoire libérée (ex, si tu libères un buffer de 20, tu peux le réutiliser pour allouer 30) mais c'est loin d'être obligatoire.

[imperio]

Quand j'ai recode mon malloc, si mes souvenirs sont bons je m'y etais pris de cette facon :

- j'avais recupere la pagesize (elle n'est pas la meme partout)
- a chaque demande de malloc, je verifiais d'abord si je n'avais pas un bloc de la taille recherchee, si ce n'etait pas le cas j'appelais sbrk

Le seul moment ou je ramenais le "program break" etait quand free etait appele sur le dernier bloc memoire. A ce moment-la c'etait gros nettoyage mais sinon tu ne peux rien faire a ma connaissance... Donc avec mon algo tu pouvais avoir un programme de 200 Mo en RAM mais n'en utilisait que 1 ou 2 voire moins.

Comme l'a dit Médinoc, il ne me semble pas qu'il y ait besoin d'arrondir a la puissance de 2 superieure.

[lludol]

@Médinoc
Merci pour ta reponse, je pensais que ca devait forcement suivre une certaine regle mais au final on peut "faire comme on veut".

Au final, j'ai reflechi avec mon binome (ouai c'est un projet a faire a deux), et on s'est dit que si on pars sur les puissance de 2, on "l'optimiserais" un peu.

Exemple :
Le mec demande 70 octets. Ma struct fais 50 octets (c'est pas definitif) donc j'ai besoin de 70 + 50 = 120 octets.
Ca donne 2^7 = 128. Mais les 8 octets (128 - 120) ne pourront jamais etre reutilise (puisque j'ai besoin au minimum de 50 octets pour la struct).
Donc si on pars du principe qu'on a besoin de 70 + 50 * 2 (pour que le deuxieme bloc libre soit utilisable plus tard).
Donc au final ca fait : 70 + 50 * 2 = 170 donc 2^8 = 256 donc 256 - 120 - 50 = 86 octets de dispo pour le mec plus tard.
Certe on utilise trop d'octets mais au final on en gaspille moins...

Bien sur les puissances de 2 sont un exemple. Peut etre ce sera ce qu'on utilisera au final mais on est oblige d'avoir une "base" pour allouer "trop" de memoire pour appeler le moins de fois sbrk.

@imperio
Quand tu parles du pagesize, tu allouais un bloc de pagesize des que tu avais besoin de creer un bloc ??
Sur mon PC, il est egal a 4096 (getpagesize()).
Genre, si le mec a besoin de 10 octets, on en alloue 4096 ??

Ouai, pour le free, on a remarque ca avec mon binome, on a ecrit tous les cas de figure (du genre si tu free un bloc au milieu de deux blocs free, etc, etc).
Et ouai y a rien a faire, tu peux rien faire pour les mini blocs, sauf si le bloc d'a cote est free, dans ce cas la, faut les "assembler".

PS :
C'est peut etre a ca que sert le getpagesize(), dans notre ecole on a des "TP" avant des projets "complique" pour nous faire reflechir, et on nous parle justement de cette fameuse fonction getpagesize().
Et donc, suffirait d'allouer un bloc ayant une size multiple de getpagesize() (donc de 4096 sur mon PC). Donc en theorie, compare au puissance de 2, ca ferais X fois moins d'appel a sbrk.


EDIT :
Faut que j'arrete avec les puissances/multiples.
Suffit juste d'allouer SIZE + SIZE_STRUCT + getpagesize()
Donc en gros, pour chaque sbrk, j'aurais pagesize d'octet de libre.
Donc si le mec fait pleins de petit malloc (genre il demande 10 octets a chaque fois), j'appelerais moins de fois sbrk qu'avec les puissances de 2.

Et pour les gros programmes, je devrait appeler sbrk avec un nombre moins grand (moins on demande au systeme des octets plus c'est rapide ?).

Petite precision, je veux que le malloc soit opti au maximum parce que j'ai bien l'intention de le tester avec de vrais programmes genre Emacs, VLC, etc,etc.

[gangsoleil]

Bonjour,

Bienvenue dans les problemes de recherche operationnelle (si mes souvenirs sont bons, ca s'appelle comme ca).

Pour "allouer" une taille X, il y a deux grandes ecoles (et enormement d'autres possibilites) :

1. Tu alloues la plus petite taille suffisante pour stocker X : c'est un peu ce que tu evoques un peu dans le premier post : pour 42, tu as besoin de 74, donc tu cherches dans l'espace memoire libre le plus petit slot disponible de taille superieure a 74, et tu retournes cette adresse.
   Avantage : ca te laisse les grands slots si quelqu'un a besoin d'allouer une grande taille
   Inconvenient : accroissement de la fragmentation
2. Tu prends la memoire dans le plus grand slot disponible. Pour tes 74, tu vas les prendre dans le slot de 3Mo qu'il te reste a gauche, ce qui fait qu'il fera maintenant 3Mo - 74, ce qui reste grand.
   Avantage : moins de fragmentation
   Inconvenient : tu risques d'avoir des difficultes a allouer de grands blocs dans certains cas precis.

Enfin, sache que random est toujours une bonne solution. Je ne dis pas ca pour rire, un algorithme de placement qui fait quelques pourcents de mieux que random, c'est deja un tres bon algorithme.

[lludol]

Merci pour ta reponse.

Je pense que je vais prendre la 2e solution, des gros blocs de dispo (avec le pagesize).
Je pense qu'on aura une meilleur note (^^) si la memoire est moins fragmentee.


Pour le random, faudrait que j'alloue X octets (donc ce que le mec a besoin + un gros bloc) + X octets random ??

C'est pas bizarre/moins opti de gerer la memoire de facon random ?

[gangsoleil]

Pour le random, faudrait que j'alloue X octets (donc ce que le mec a besoin + un gros bloc) + X octets random ??

C'est pas bizarre/moins opti de gerer la memoire de facon random ?

Non, ce que je veux dire, c'est que tu vas avoir un segment memoire de par exemple 256 Mo a ta disposition, dans lequel tu vas pouvoir allouer ce que tu veux.
Tu vas commencer par allouer a partir de l'adresse 0, des blocs de la taille necessaire (demande + overhead). Et certains bouts de memoire vont finir par etre liberes, creant des trous (et des trous adjacents font un gros trou, nous sommes d'accord).
Tu te retrouves donc par exemple avec l'utilisation memoire suivante :

• 10 occupes par P1
• 2 libres
• 15 occcupes par P2
• 42 occupes par P3
• 37 libres
• 27 occupes par P4
• 18 libres
• etc ...

Et la, je te demande une allocation de 14, ce qui fait 17 avec ton overhead (je prends un overhead de 3 pour l'exemple).
Tu ne peux pas le placer dans le slot libre de 2, mais tu peux le mettre dans celui de 18 et avoir un bloc de 4 a disposition. Avec un overhead de 3, tu vois bien (mais c'est improgrammable simplement) que ce bloc de 4 est perdu.
Ou bien tu peux placer l'allocation dans le bloc de 37, ce qui te laissera un bloc de 20 pour la suite.
Mais si on te demande apres un bloc de 32, la premiere solution aurait finalement ete mieux

C'est la que random intervient : parmi les blocs libres suffisamment grand, tu ne "choisis" pas, c'est random qui choisit pour toi.
Et sache que cette solution est toujours une bonne solution. A titre d'exemple, un algorithme qui permet de faire mieux que random de quelques pourcents est un tres bon algorithme, qui permet souvent de faire une publication scientifique.

S'il y a des gens de la recherche operationnelle qui lisent ce sujet, ils ne manqueront pas de me corriger

[Médinoc]

Si j'ai bien compris, tu as donné deux solutions de "best-fit" opposées, plus un "random-fit".
Une autre solution est "first-fit": on alloue juste dans le premier espace assez grand qu'on trouve. Pour éviter que les performances se dégradent au fur et à mesure des allocations, il vaut mieux mémoriser l'adresse de la dernière allocation, et continuer à partir de là (en commençant par la dernière allocation et non pas en commençant à l'espace libre juste derrière: Ça évite de fragmenter la mémoire si elle a été libérée entretemps).

[gangsoleil]

Si j'ai bien compris, tu as donné deux solutions de "best-fit" opposées, plus un "random-fit".

C'est bien ca.

Une autre solution est "first-fit":

Effectivement, ca a l'avantage d'optimiser le temps de recherche du prochain emplacement vide.

[lludol]

A ok, je comprend mieux cette histoire de random.

Mais ca risque d'etre lent.
Soit je parcours toute la liste chainee, a la recherche de bloc libre et je les enregistre des que je les trouve. Et a la fin j'en choisis un "random".

Soit des que je trouve un bloc libre, je demande a random (0 ou 1) si je dois l'utiliser ou pas mais ca m'oblige a revenir en arriere si j'en trouve pas d'autre.

Sinon je fais une 2e struct qui contient les blocs "free" et donc c'est moins long a parcourir.

Je pense que je vais coder le malloc "normalement", donc avec les split, le pagesize, etc, etc.
J'ai deja coder la partie qui alloue de la memoire et split les blocs (et ca marche tres bien).

Et des qu'il fonctionnera a 100%, j'essayerais de l'optimiser.

Merci pour votre aide !

[Metalman]

Il n'y a pas vraiment de malloc "normal"...
Dans les linux, de temps en temps les algos changent (et c'est malheureux pour les projets qui ne vérifient pas assez avec valgrind les erreurs...), donc voilà

Tu as choisi le malloc "utilisant" l'alignement sur les pagesizes, et c'est simplement mieux adapté aux systèmes paginés.