Exercices

Exercices sélectionnés

TP1 — Introduction au shell et aux scripts Bash

Énoncé

Créer un script backup.sh qui prend en entrée :

1. un répertoire à sauvegarder ;
2. un nom d’archive.

Le script doit :

• compresser le répertoire dans une archive .tar.gz ;
• parcourir récursivement ses sous-répertoires ;
• produire un fichier de log contenant les fichiers et leur taille ;
• trier ces informations par taille décroissante ;
• vérifier la validité des arguments et l’existence du répertoire.

Le fichier de log doit être placé dans le même répertoire que l’archive.

Étapes à savoir reconstruire

1. Préparer les entrées et vérifier les erreurs

Récupérer $1 et $2, vérifier le nombre d’arguments puis vérifier que le répertoire existe.

2. Créer l’archive et initialiser le log

Utiliser tar, créer/vider le log et y écrire la date du backup.

3. Parcourir récursivement les dossiers

Utiliser find pour obtenir les répertoires, puis une boucle pour traiter chacun d’eux.

4. Extraire puis trier les tailles

Composer les outils Unix avec un pipe : produire les informations avec ls, sélectionner les champs utiles avec awk, accumuler le résultat dans un fichier temporaire puis trier numériquement par taille.

5. Produire le log final

Écrire le résultat trié dans le log en conservant les informations déjà présentes.

Voir la solution

---

TP3 — Allocation dynamique : malloc (TD S3, version essentielle)

Objectif : savoir expliquer le rôle de l’allocateur, évaluer ses métadonnées et tracer l’état de la mémoire. Cette sélection regroupe les étapes les plus réutilisables du TD officiel en 3 étapes, sans refaire mécaniquement tout l’énoncé.

Énoncé — à faire sans correction

Étape 1 — Expliquer malloc et le rôle du noyau

Un étudiant affirme : « malloc est un appel système, et chaque malloc(4) demande exactement 4 octets à Linux. »

Explique pourquoi il a tort. Fais apparaître les rôles du programme C, de la libc, du heap, du noyau et du program break ; distingue brk(adresse), sbrk(n) et sbrk(0).

Étape 2 — Quantifier les métadonnées (machine 32 bits)

On considère le modèle exact du TD3 :

struct meta_data {
    int is_block_free;
    int block_size;
    struct meta_data *next_block;
};

Hypothèse de cet exercice : aucune taille de données n’est arrondie (pas de padding) ; un int et un pointeur font chacun 4 octets.

1. Combien d’octets occupent ces métadonnées ? Justifie la conversion bits → octets.
2. Combien d’allocations de 4 octets utiles tiennent dans une réserve de 16 octets ?
3. Quelle part de la mémoire consommée représentent les métadonnées pour malloc(1), puis malloc(100) ?
4. Pourquoi souhaiterait-on compacter ces métadonnées ?

Étape 3 — Tracer trois états de la mémoire

On dispose de 16 octets préexistants, numérotés de 0 à 15. Pour cette étape, choisis un header compact de 4 octets stockant la taille totale du bloc (header inclus) et un bit alloué/libre. Les blocs sont alignés sur 4 octets. La politique choisie est First Fit.

Dessine les 16 octets, avec leurs offsets et les pointeurs rendus, dans cet ordre :

1. Après init() : un seul bloc libre.
2. Après a = my_malloc(4), puis b = my_malloc(4).
3. Après my_free(a) : qu’est-ce qui est libre, qu’est-ce qui reste comme métadonnées ? Si on fait ensuite c = my_malloc(4), quelle adresse sera probablement rendue ?

À justifier : pourquoi free n’implique-t-il pas d’effacer les anciennes données ? Pourquoi la politique First Fit n’est-elle pas universelle ?

Voir la solution

---

Solution TP1

Une solution possible, construite dans l’ordre :

#!/bin/bash

# 1. Vérifications
if [ $# -ne 2 ]; then
    echo "Usage: $0 <dossier> <archive>" > /dev/stderr
    exit 1
fi

DOSSIER="$1"
ARCHIVE="$2"
LOG="${ARCHIVE}.log"
TEMP="temp.txt"

if [ ! -d "$DOSSIER" ]; then
    echo "Erreur : le dossier n'existe pas" > /dev/stderr
    exit 1
fi

# 2. Archive et log
tar -czf "$ARCHIVE" "$DOSSIER"
> "$LOG"
date >> "$LOG"
> "$TEMP"

# 3-4. Parcours, extraction des tailles
for dossier in $(find "$DOSSIER" -type d)
do
    ls -s "$dossier" | awk '{print $1, $2}' >> "$TEMP"
done

# 5. Tri et ajout au log
sort -n -r "$TEMP" >> "$LOG"

À retenir pour l’examen

• $#, $1, $2, $?
• ${VAR} ≠ $(commande)
• > écrase, >> ajoute
• cmd1 | cmd2
• find + boucle
• awk pour sélectionner des champs
• sort -n -r pour trier numériquement en ordre décroissant

---

Solution TP3 — Allocation dynamique

Étape 1 — Libc, noyau et program break

malloc est une fonction de la libc en mode utilisateur, pas un appel système. Elle cherche un bloc libre dans la réserve qu’elle gère ; elle n’appelle pas nécessairement le noyau à chaque allocation. Pour agrandir le heap, la bibliothèque peut utiliser des mécanismes du système, présentés par le CM3 avec brk/sbrk.

• brk(adresse) : demande de fixer le program break.
• sbrk(n) : demande de le déplacer de n octets.
• sbrk(0) : consulte la position actuelle.
• Sur succès, sbrk(n) retourne l’ancienne limite, et non la nouvelle.

Les demandes à malloc ne coïncident pas forcément avec la taille demandée au noyau : l’allocateur peut ajouter de l’overhead, appliquer de l’alignement et réserver de la mémoire à l’avance.

Étape 2 — Calculs sans padding

Sur le modèle 32 bits du TD, 32 bits / 8 = 4 octets. Deux int (4 + 4) et un pointeur (4) représentent 12 octets de métadonnées par bloc.

Une allocation de 4 octets utiles nécessite donc 12 + 4 = 16 octets : une seule allocation tient dans la réserve de 16 octets.

Allocation	Total consommé	Fraction métadonnées
malloc(1)	12+1=13 octets	12/13 ≈ 92,3 %
malloc(100)	12+100=112 octets	12/112 ≈ 10,7 %

Pour compacter, on peut exploiter le fait que certaines tailles alignées ont des bits de poids faible à zéro, et utiliser l’un d’eux comme drapeau libre/alloué. L’organisation de la liste de blocs peut également éviter de stocker un pointeur next dans chaque header.

Piège : l’alignement de 16 octets montré au CM ne doit pas être ajouté à ces calculs : le TD impose explicitement des données de taille exacte dans cette étape.

Étape 3 — États chronologiques (header de 4 octets)

On note H(t, état) le header d’un bloc de taille totale t. Les adresses affichées sont des offsets relatifs à la zone de 16 octets.

1. init()
offset   0                  4                           16
         [ H(16, libre)     ][      12 octets libres      ]

2a. a = my_malloc(4)
offset   0          4          8          12         16
         [H(8, occ)][ a : 4 B ][H(8, libre)][ libre 4 B ]
                      ↑ a = 4

2b. b = my_malloc(4)
offset   0          4          8          12         16
         [H(8, occ)][ a : 4 B ][H(8, occ)][ b : 4 B ]
                      ↑ a = 4              ↑ b = 12

3. my_free(a)
offset   0          4          8          12         16
         [H(8, libre)][ ancien a ][H(8, occ)][ b : 4 B ]

Après my_free(a), le premier bloc total de 8 octets est libre, mais son header de 4 octets existe toujours : seulement 4 octets sont utilisables comme données. Les anciens octets de a peuvent rester présents physiquement. Avec First Fit, my_malloc(4) peut rendre à nouveau l’offset 4.

First Fit est une politique choisie pour cet exercice, pas une règle universelle. Le point central de la simulation : les données utilisateurs ne sont jamais la totalité de la mémoire consommée.

Retour à l’exercice TP3