Aides sur les algos de gestion d'un cache ( un cache peut en cacher un autre . . . )

**smyley** · 30/11/2007, 04h08

J'ai développé une base de donnée et pour ne pas avoir à tout charger en mémoire ( les données pouvant faire plusieurs dizaines de méga, voir plus ), j'y ai rajouté un système pour stoquer les données sur le disque, dans un fichier cache. Lors de la lecture/écriture, j'accède donc à un fichier pour en tirer ce que je veux.
Les données stoquées peuvent faire quelques octets mais aussi plusieurs méga ( cependant il y en a plus qui font 1 octet que 1 Mo ). J'utilise donc des blocs de taille variable en fonction de l'espace disponible dans le cache et la demande ( par exemple, pour une donnée de 10 octets je peut prendre deux blocs libres de 4 octets et alouer 2 octets supplémentaires au cache ). Lorsque je supprime une donnée, l'opération libère les blocs alloués ( contigues ou non ).

Mon problème est qu'au final après quelques centaines d'opérations mon cache est hyper fragmenté : je me retrouve avec des données de 2 Mo organisées en des milliers de blocs de 1 octet et c'est un vrai calvaire.

Je voudrais donc savoir, y a t il des algos spéciales qui pourraient me permettre de gérer mon problème de fragmentation, ou plutot, des théories sur la création d'un cache pour des données de taille variables en ayant beaucoup de petits blocs mais de très gros blocs ?

Merci d'avance ...

**pseudocode** · 30/11/2007, 10h50

Tu as utilisé quel algo pour choisir l'emplacement libre que tu va allouer ? Si tu as utilisé un first-fit (ou pire un best-fit) c'est normal que ca soit très fragmenté.

Généralement on utilise un worst-fit pour eviter d'avoir plein de petits trous entre les blocs alloués. Si ca ne suffit pas, il faut défragmenter de temps en temps le cache.

**smyley** · 30/11/2007, 12h16

Envoyé par pseudocode

Tu as utilisé quel algo pour choisir l'emplacement libre que tu va allouer ? Si tu as utilisé un first-fit (ou pire un best-fit) c'est normal que ca soit très fragmenté.

J'ai pas vraiment utilisé d'algo j'ai fait un peut au feeling, mais je crois que ça correspond à un first-fit :
Je regarde si il y a des blocs de free dispo, je prend le premier s'il existe
Sinon j'en crée un nouveau à la fin du cache et j'y écrit mes données

Envoyé par pseudocode

Généralement on utilise un worst-fit pour eviter d'avoir plein de petits trous entre les blocs alloués. Si ca ne suffit pas, il faut défragmenter de temps en temps le cache.

Donc worst-fit : je m'arrange pour choisir le bloc free le plus gros ?
Mais même, je me retrouve souvent avec plein de blocs libres de taille 1 ... faudrait peut être que je compacte le tout mais c'est chaud de défragmenter un truc avec des blocs qui n'ont pas une longueur fixe, du moins, je vois pas comment faire ...

**pseudocode** · 30/11/2007, 14h40

Envoyé par smyley

Donc worst-fit : je m'arrange pour choisir le bloc free le plus gros ?

Oui, c'est ca. Tu alloues le début du plus gros bloc vide.

Mais même, je me retrouve souvent avec plein de blocs libres de taille 1 ...

Tu peux mélanger les heuristiques, du genre:
- si c'est une petite allocation, tu fais un best fit.
- si c'est une grande allocation, tu fais un worst fit.

faudrait peut être que je compacte le tout mais c'est chaud de défragmenter un truc avec des blocs qui n'ont pas une longueur fixe, du moins, je vois pas comment faire ...

Tu maintiens une liste des blocs vides. C'est rapide pour l'allocation, il suffit de parcourir cette liste, de trouver le meilleur bloc vide et de modifier les infos du bloc (nouveau debut/fin/taille).

C'est un peu plus compliqué au moment de la libération, car tu dois eventuellement fusionner avec les blocs vides adjacents avant/apres.

Pour la defragmentation, il faut faire glisser les blocs occupés afin de consolider l'espace libre.

**smyley** · 30/11/2007, 15h15

J'ai éssayé de faire un nouveau système pour mes tests :
J'utilise un buffer fixe de 512 Ko et je fait des allocations d'une taille de 10 à 1000 octets aléatoirement pour en faire une chaine ( comme un fichier avec les secteurs ) et je fusionne les chaines qui sont dans la continuité du fichier ( par exemple, je choisis que le bloc à la position 5 sera le début du fichier, et le bloc 12 correspondra au début de 4 octet du fichier, etc ... ).

Pour me débarasser des "trous", j'ai fait une méthode Pack qui les supprime en déplaçant les blocs mais seulement voilà, au bout d'une dizaine de boucles je me retrouve encore avec un fichier de 200 ko fractionné en 4000 blocs dont la plupart ont une taille entre 2 et 8 octets ...

De plus, pour faire une défragmentation il faudrai que je copie toute les données vers un nouvel espace de mémoire ? car je ne vois pas trop comment faire autrement ...

**pseudocode** · 30/11/2007, 17h02

Envoyé par smyley

Pour me débarasser des "trous", j'ai fait une méthode Pack qui les supprime en déplaçant les blocs mais seulement voilà, au bout d'une dizaine de boucles je me retrouve encore avec un fichier de 200 ko fractionné en 4000 blocs dont la plupart ont une taille entre 2 et 8 octets ...

??

Hum, ca me parrait étrange que ca soit autant fragmenté. Le worst-fit n'a pas trouvé mieux que 4000 blocs ? Etrange.

Lorsque la mémoire retournée est trop fragmentée, annule l'allocation et fait un Pack, puis refait l'allocation.

Autre solution: fait 2 buffers. Un pour les petites allocations et un pour les grandes.

**smyley** · 21/12/2007, 00h54

Envoyé par pseudocode

Lorsque la mémoire retournée est trop fragmentée, annule l'allocation et fait un Pack, puis refait l'allocation.

Donc voilà au final j'ai utilisé une méthode simillaire :
à chaque fois que le nombre de blocs libres arrive à 100 -> Pack
Pour la gestion des blocs vide, je traite une liste rangée et lors de l'allocation je commence toujours par le bloc le plus gros. Avec ça j'ai à peut près réussit à fréiner la fragmentation. Dans mes petits tests, sans cette méthode j'arrive à la fin avec ~250 blocs alloués et avec cette méthode j'y arrive avec ~60 blocs aloués pour la même taille finale de cache.

On va dire que c'est bon pour l'instant

pour tout pseudocode