Sujet Précédent Sujet Suivant

Algorithme des freres siamois.

cs_gildaso Messages postés 6 Date d'inscription lundi 10 janvier 2005 Statut Membre Dernière intervention 8 mai 2005 - 7 mai 2005 à 11:41
cs_gildaso Messages postés 6 Date d'inscription lundi 10 janvier 2005 Statut Membre Dernière intervention 8 mai 2005 - 8 mai 2005 à 12:44
Bonjour a tous j'aimerais savoir si quelqu'un connait precisement le fonctionnement de l'algorithme buddy system, appelé aussi algorithme des freres siamois. Je dois m'en servir pour implementer un systeme d'allocation dynamique de memoire efficace evitant la fragmentation. Je n'ai bien sur pas le droit d'utiliser malloc. Je me suis documenté sur les differents algorithmes qui font cela (best fit, worst fit, next fit etc..) et il semblerait que le buddy sytem soit relativement efficace. LE probleme est que je n'ai pas suffisament d'informations dessus pour l'implementer. Si quelqu'un a une quelconque idée de l'implementation de cet algo ou alors d'un autre algo tout aussi efficace, merci d'avance!
@+
Gildas

2 réponses

Réponse 1 / 2
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006
7 mai 2005 à 22:12
As-tu regardé du côté du slab allocator?

Cet allocateur mémoire est bien indiqué dans le cas ou les demandes
mémoire sont de tailles connue a l avance (par exemple dans un kernel
des inodes, descripteurs de pages, etc...). Pour une implementatioon de
cet algorithme dans un OS simple voir
http://sos.enix.org/wiki/upload/SOSDownload/sos-texte-art5.pdf.
(d'ailleurs ce site est le site d'un OS en construction, acccompagne
d'excellents articles decrivant la conception de cet OS).



Sinon pour l'algorithme buddy system, une implémentation doit se
trouver dans Linux, mais cela risque d etre assez complexe du fait que
Linux tourne sur de nombreuses architectures, mais pour un version
simple les 1eres versions doivent convenir.Peut etre ici :

http://www.cs.utexas.edu/users/wilson/papers/fragsolved.pdf



Et pourquoi pas dans "the art of computer progamming" par D.Knuth?
0
Réponse 2 / 2
cs_gildaso Messages postés 6 Date d'inscription lundi 10 janvier 2005 Statut Membre Dernière intervention 8 mai 2005
8 mai 2005 à 12:44
Merci beaucoup pour toutes tes infos, je vais jeter un coup d'oeil. Si quiconque a des informations à ce sujet la, qu'il me fasse signe. Je précise que mon allocateur de memoire doit fonctionner pour un processus donné.
MErci d'avance
0
Rejoignez-nous