Consignes

Ce TP donnera lieu à une évaluation. Vous pouvez travailler en binômes.

Les consignes pour envoyer votre TP à l'enseignant se trouvent dans la section Envoyer votre TP.

Liens utiles

Utiliser l'image fournie

Démarrer MINIX

L'archive fournie pour ce TP contient une image QEMU avec un MINIX déjà installé et configuré.

Pour l'utiliser, il suffit de télécharger l'image dans le répertoire /tmp et la décompresser :

$ cd /tmp/
$ mkdir TP2-OS
$ cd TP2-OS
$ wget http://lama.univ-savoie.fr/~hyvernat/Enseignement/1011/info502/minix.img.bz2
$ bunzip2 minix.img.bz2

Pour démarrer MINIX :

$ qemu -localtime -net user -net nic,model=rtl8139 -redir tcp:2232::22 -m 256 -hda minix.img

Le mot de passe pour l'utilisateur root est root, et le mot de passe pour l'utilisateur etu est etu. Pour ce TP, vous n'avez pas besoin du compte administrateur. (Sauf si vous voulez installer votre propre version de malloc() dans le système lors de la dernière question.)

Si vous êtes sur votre portable avec une version suffisamment récente de QEMU, vous pouvez remplacer la dernière ligne par

qemu -localtime -net user,hostfwd=tcp::2232-:22  -net nic,model=rtl8139 -m 256 -drive file=minix.img,if=ide,media=disk,cache=writeback

pour accélérer les entrées / sortie disques. (Ce n'est pas très important pour ce TP...)

Transfert de fichiers

La méthode la plus simple pour transférer des fichiers entre la machine Linux hôte et la machine virtuelle MINIX est d'utiliser ssh. L'image de MINIX fournie contient un serveur ssh et la commande QEMU donnée permet de rediriger le port 2232 de l'hôte vers le port ssh habituel (port 22) de la machine virtuelle MINIX.

Ainsi, si vous faite un

$ ssh -p 2232 etu@localhost

à partir de la machine hôte, vous pouvez vous connecter sur le compte "root" de la machine MINIX. (L'inverse serait également possible si on redirigeait un port de la machine virtuelle sur le port 22 de votre machine...)

Vous pouvez vous servir de ça pour transférer facilement des fichiers :

$ scp -P 2232 fichier_linux etu@localhost:fichier_minix

dans la machine hôte pour copier un fichier de l'hôte vers la machine virtuelle, ou

$ scp -P 2232 etu@localhost:fichier_minix fichier_linux

dans la machine hôte pour copier un fichier de la machine virtuelle vers l'hôte.

Envoyer votre TP

Votre TP devra être envoyé par email à votre enseignant (Pierre.Hyvernat@univ-savoie.fr ou Florian.Hatat@univ-savoie.fr). Le sujet de votre mail doit contenir la chaîne "info502".

Vous devez envoyer une unique archive tar contenant :

points importants :

  1. votre archive doit contenir un répertoire, pas seulement des fichiers en vrac. Mon repertoire de travail s'appelle "Pierre_Hyvernat-TP2" ; pour créer l'archive, la ligne de commande est :

    $ tar cvf Pierre_Hyvernat.tar Pierre_Hyvernat/
    
  2. tous vos fichiers doivent commencer par un entête contenant vos noms et prénoms, ainsi que votre filière.

Si ces consignes ne sont pas respectées, l'enseignant se réserve le droit de vous enlever 5 points (ou même plus) sur la note finale.

1. Modèle mémoire des processus sous MINIX (et Linux)

Sous MINIX, la mémoire (virtuelle) pour chaque processus est divisée en trois parties (« segments ») indépendants :

  1. le segment text (texte) contenant le texte (ie code exécutable) du programme,
  2. le segment stack (pile) contenant les données de taille fixe du programme, les arguments de la fonction en cours d'exécution, ...
  3. le segment data (données, tas) contenant les données de taille dynamique du programme.

1.1. Afficher des informations

Quand vous êtes sur la première console MINIX, les touches F1, F2, ... permettent d'afficher des information de débogage. En particulier :

Les fonctions sont reliées aux touches Fn dans le fichier /usr/src/servers/is/dmp.c.

  1. En regardant les fonctions "memmap_dmp()" (activée par F2, définie dans /usr/src/servers/is/dmp_kernel.c), décrivez brièvement ce qu'affiche cette fonction.
  2. Les adresses affichées par cette fonction sont-elles virtuelles ou physiques ?
  3. À quoi correspondent pc, sp et cr3 dans l'affichage correspondant à "memmap_dmp()" ?
  1. Écrivez un mini programme C adresses.c qui :
    • affiche quelques adresses appartenant au segment data,
    • affiche quelques adresses appartenant au segment stack.
  2. Est-ce que les adresses affichées sont des adresses virtuelles ou physiques ?
  3. Pouvez-vous afficher une adresse du segment text ?

Le programme adresses.c doit être du C valide et n'utiliser que des fonctions standards. (Pas besoin d'inclure des fichiers systèmes...) Par exemple, l'entête de mon propre fichier ne contient que

#include <stdio.h>
#include <stdlib.h>

1.2. Allouer de la mémoire aux processus

Préliminaires

Chaque processus peut, à tout moment, réclamer une portion de mémoire dans son tas (segment D) grâce à la fonction "malloc()". Cette fonction ne fait pas partie du noyau du système d'exploitation mais utilise des fonctions bas niveau ("brk()" et "sbrk()"). "malloc()" est une fonction de la bibliothèque standard du langage C et elle fait partie de la norme POSIX, alors que "brk()" et "sbrk()" n'en font pas partie.

La fonction est définie dans le fichier /usr/src/lib/libc/ansi/malloc.c.

"malloc(s)" va essayer d'allouer un bloc de s octets dans le tas. S'il y a déjà une zone libre suffisamment grande, elle est utilisée. On peut utiliser l'algorithme First-Fit par exemple pour la découvrir. Si aucune zone libre suffisamment grande n'est trouvée, "malloc()" va utiliser la fonction "brk()" qui permet d'agrandir le tas. (Bien entendu, s'il n'y a plus de mémoire disponible, "brk()" va échouer, ainsi que "malloc()".)

Les blocs, libres ou occupés, du tas sont gardés dans une liste chaînée. Un bloc est constitué :

Le pointeur pointe sur le début des données du bloc suivant :

La partie "Données" d'un bloc occupé contient ... des données.

La partie "Données" d'un bloc libre contient :

Le pointeur vers le zone libre suivante est écrasée par les données quand le bloc est utilisé.

Comprendre comment fonctionne l'allocation

Recopiez le fichier malloc.c dans /home/etu/malloc-comment.c. Ouvrez le fichier et commentez le pour expliquer ce qu'il se passe. (C'est une étape préliminaire à la question suivante...)

Vous n'avez besoin de regarder que les fonctions "grow()" et "malloc()".

Faite un dessin (ascii art, pdf, png, ...) pour visualiser la mémoire d'un processus :

Modifier l'allocateur

La version MINIX de "malloc()" utilise un algorithme First-Fit pour chercher une zone libre. Modifier le fichier malloc.c pour avoir une recherche Worst-Fit ou Next-Fit. (au choix)

Pour tester votre fonction, le plus simple est de recopier le fichier malloc.c ainsi que les fichiers malloc-debug.{c,h} dans un répertoire de test. Vous pourrez ainsi compiler uniquement votre fichier malloc.c et le tester sur un petit programme. Il faudra pour ceci ajouter un fichier mon_malloc.h que vous inclurez à la place de stdlib.h. Pour forcer votre exécutable à utiliser votre version de malloc(), il faudra faire l'édition de liens avec votre fichier malloc.o.

Je vous conseille de faire un Makefile pour vous simplifier la vie. Et pour les fainéants, voici une archive tar...

ATTENTION : votre fichier malloc.c ne peut pas utiliser lui même la fonction malloc ou des fonctions qui l'utilisent indirectement (comme la fonction printf). Si vous voulez faire de l'affichage pour déboguer, je vous conseille d'utiliser uniquement les fonctions définies dans le fichier affiche.c (avec le fichier affiche.h correspondant).

Une fois que vous avez testé sur des programmes jouets, vous pouvez essayer sur des programmes plus conséquents, voir carrément en remplaçant la version standard par la votre. Ainsi, tous les appels à malloc utiliseront votre version !

Afficher des informations

Écrivez une fonction alloc_info() qui affiche la liste des bloc, la liste des blocs libre, leurs tailles, etc.

Écrivez quelques programmes en C qui créent des zones de mémoire et les libèrent, créant ainsi des trous.

Pour utilisez votre fonction alloc_info, vous pouvez vous utiliser la fonction getenv pour détecter la présence (ou non) d'une variable d'environnement. Si, par exemple, la variable DISPLAY_MALLOC_INFO est présente, vous utiliserez alors la fonction alloc_info à chaque appel de malloc et free.