Le but de cette séance est d’implémenter en python et tester certains des algorithmes d’allocation mémoire vu en cours. Votre code est à déposer, en individuel, sur AMetice pour le 11 février.

1. Méthodologie

La validation du code produit se fera de plusieurs manières

1. par une suite de tests
2. par des requêtes aléatoires
3. par comparaison avec l’algorithme optimal, si le temps le permet

On va commencer par définir une suite de tests : écrire un programme test-suite.py qui prend comme paramètre un nom d’algorithme (parmi les sections suivantes) et affiche et compare le résultat sur les données de l’exercice B du TD. Un message d’erreur devra être affiché si le résultat ne correspond pas à l’allocation attendue. NB vous ne pourrez exécuter ces tests que lorsque vous aurez écrit les parties suivantes.

2. Algorithmes

Implémenter les algorithmes suivants. On utilisera des listes d’entiers (représentant la mémoire en ko) pour représenter les entrées (bloc disponibles et requêtes). La liste de sortie correspondra aux allocations successives, avec les conventions suivantes:

• on numérote les blocs à partir de 0
• une impossibilité d’allocation est codée par le bloc -1

2.1. First-Fit

Mettre en place l’algorithme First-Fit.

2.2. Best-Fit

Mettre en place l’algorithme Best-Fit. On recherche d’abord les blocs disponibles par recherche séquentielle, comme précédemment. Proposer ensuite une seconde méthode qui utilisera min() avec la fonction lambda de python.

2.3. Worst-Fit

Mettre en place l’algorithme Worst-Fit. Comme précédemment, on pourra utiliser une méthode qui utilisera directement une fonction python adéquate.

3. Utilisation Dynamique

Afin de pouvoir prendre en compte allocation et désallocation, nous allons modifier la structure de données représentant les zones libres de la mémoire. La mémoire sera intégralement représentée avec toutes les zones allouées et non allouées. On utilisera donc une liste mémoire de couples (bool, int) où le premier élément indique si le bloc est alloué ou non, et le second indique la taille de la zone (en ko).

Convertir votre code précédent pour utiliser cette nouvelle structure de données (on pourra mettre les zones non allouées à la taille zéro pour l’instant). On pourra utiliser la fonction insert(index,value) sur la liste mémoire. Bien vérifier que test-suite.py fonctionne.

Ajouter une méthode désallouer(bloc) qui libère la mémoire du bloc de numéro bloc, et fusionne en un seul bloc les blocs précédents et suivants, s’ils étaient non alloués. Compléter test-suite.py pour tester cette méthode.

Ensuite, simuler l’utilisation, au long cours, de chacun de vos algorithmes, avec un programme simule.py qui prend comme paramètre un nom d’algorithme.

1. commencer avec 1Mo (ie mémoire = [(False,1024)] initialement) et allouer des blocs de taille aléatoire entre 50ko et 100ko
2. ajouter des désallocations aléatoires toutes les 4 allocations

Que constatez-vous ?