Algorithme des freres siamois.

Signaler
Messages postés
6
Date d'inscription
lundi 10 janvier 2005
Statut
Membre
Dernière intervention
8 mai 2005
-
Messages postés
6
Date d'inscription
lundi 10 janvier 2005
Statut
Membre
Dernière intervention
8 mai 2005
-
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
A voir également:

2 réponses

Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

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?
Messages postés
6
Date d'inscription
lundi 10 janvier 2005
Statut
Membre
Dernière intervention
8 mai 2005

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