Synthèse

Vue d’ensemble

Un système informatique combine :

• un ou plusieurs processeurs (CPU) ;
• la mémoire principale ;
• des périphériques d’entrée/sortie ;
• un système d’exploitation, intermédiaire entre les applications et le matériel.

Le système d’exploitation fournit des abstractions communes aux programmes, partage les ressources et assure l’isolation entre les applications.

Processeur, interruptions et système d’exploitation

Rôle du processeur

Le processeur exécute des instructions machine selon le cycle :

fetch → decode → execute

Il peut notamment :

• lire et écrire des données entre la mémoire et ses registres ;
• effectuer des calculs et comparaisons sur les registres ;
• modifier le compteur de programme pour réaliser branchements, if, boucles, etc.

À retenir : le CPU est avant tout un exécuteur d’instructions. Il ne « convertit » pas directement les entrées des périphériques.

Interruptions matérielles

Les périphériques sont gérés par des contrôleurs disposant notamment de buffers.

Lorsqu’un événement doit être signalé au processeur, par exemple une touche de clavier :

1. le contrôleur reçoit l’information ;
2. il génère une interruption matérielle ;
3. le CPU suspend temporairement le flot d’instructions courant ;
4. l’état utile du processeur, dont les registres et le compteur de programme, est sauvegardé ;
5. une routine de traitement de l’interruption est exécutée ;
6. l’état est restauré ;
7. le programme interrompu reprend.

Mode utilisateur, noyau et appels système

Un programme utilisateur ne peut pas accéder librement à toute la mémoire ni reconfigurer le matériel : cela compromettrait l’isolation et le fonctionnement du système.

Lorsqu’un programme a besoin d’un service du système d’exploitation :

programme utilisateur → appel système → interruption logicielle (trap) → noyau → service → retour au programme

Le programme s’exécute normalement en mode utilisateur. Le noyau dispose d’un mode protégé permettant d’exécuter les instructions privilégiées.

Langage C — mémoire, pointeurs et bits

Le point de vue utile en systèmes est le suivant :

code C → types → représentation en bits → adresses mémoire → instructions processeur

Bits : lire visuellement une valeur

Une donnée en mémoire est une suite de bits. Le type C indique au compilateur comment interpréter ces bits et quelle quantité de mémoire manipuler.

Pour un octet :

Position du bit	7	6	5	4	3	2	1	0
Poids non signé	128	64	32	16	8	4	2	1
Exemple	1	0	1	1	0	1	1	0

Ici :

10110110₂
= 128 + 32 + 16 + 4 + 2
= 182

L’hexadécimal est pratique car un chiffre hexadécimal représente exactement 4 bits :

Binaire	Hex	Binaire	Hex
0000	0	1000	8
0001	1	1001	9
0010	2	1010	A
0011	3	1011	B
0100	4	1100	C
0101	5	1101	D
0110	6	1110	E
0111	7	1111	F

Donc :

0xB6 = 1011 0110₂

Entiers négatifs : complément à 2

Les entiers signés sont représentés en complément à 2.

Sur n bits :

non signé : 0  → 2ⁿ - 1
signé     : -2ⁿ⁻¹ → 2ⁿ⁻¹ - 1

Exemple sur 4 bits :

+3 = 0011
     ↓ inversion
     1100
     ↓ + 1
-3 = 1101

Le bit de poids fort n’est pas juste un « signe »

En complément à 2, il ne faut pas lire 1101 comme « signe négatif + 101 ».

Sur 4 bits, les poids sont :

bit	3	2	1	0
poids signé	-8	4	2	1
1101	1	1	0	1

Donc :

1101₂ = -8 + 4 + 1 = -3

C’est aussi pour cela que, sur 8 bits, l’intervalle est -128 ... 127 : il existe -128, mais pas +128.

Tableaux : une zone mémoire contiguë

int tab[4] = {10, 20, 30, 40};

Si un int occupe 4 octets, on peut visualiser :

tab
 │
 ▼
┌────────┬────────┬────────┬────────┐
│   10   │   20   │   30   │   40   │
└────────┴────────┴────────┴────────┘
 tab[0]   tab[1]   tab[2]   tab[3]
 +0 B     +4 B     +8 B     +12 B

Dans la plupart des expressions, tab permet d’accéder à l’adresse du premier élément.

tab[i] == *(tab + i)

Le déplacement d’un pointeur dépend de son type :

int *p = tab;
p + 1;       // adresse suivante de int, donc + sizeof(int)

Si sizeof(int) == 4, p + 1 avance de 4 octets, pas d’un octet.

Expression	Sens
tab	accès à l’adresse du premier élément dans la plupart des expressions
&tab[0]	adresse du premier élément
tab[i]	élément i
*(tab+i)	même élément i
p++ pour int *p	avance vers l’int suivant

Tableau ≠ variable pointeur

int tab[4] réserve directement une zone pour 4 entiers.
int *p réserve une variable contenant une adresse.

On peut faire p++, mais pas tab++.

Pointeurs : adresse, déréférencement et pièges

int x = 42;
int *p = &x;

mémoire

0x1000   x = 42
          ▲
          │
0x2000   p = 0x1000

Expression	Signification
x	valeur de x
&x	adresse de x
p	adresse stockée dans le pointeur
*p	valeur située à l’adresse contenue dans p
*p = 8	écrit 8 dans la variable pointée

Piège fondamental :

int *p;
*p = 3;      // faux : p ne pointe vers aucune zone valide connue

Une initialisation sûre si le pointeur n’a encore aucune cible est :

int *p = NULL;

Puis on ne déréférence p qu’après lui avoir donné une adresse valide.

Autre piège : les arguments sont toujours passés par valeur.

void reset(int *p) {
    p = NULL;          // modifie seulement la copie locale de p
}

Pour modifier le pointeur de l’appelant, il faut passer son adresse :

void reset(int **pp) {
    *pp = NULL;
}

reset(&p);

Application : représenter une liste chaînée en C

C ne possède pas de type List intégré comme Java. Une liste chaînée se construit avec une structure contenant une valeur et un pointeur vers le nœud suivant.

struct Node {
    int value;
    struct Node *next;
};

Une liste vide :

struct Node *head = NULL;

Une liste 10 → 20 → 30 peut être initialisée, sans allocation dynamique, ainsi :

struct Node n3 = {30, NULL};
struct Node n2 = {20, &n3};
struct Node n1 = {10, &n2};

struct Node *head = &n1;

Visualisation :

head
 │
 ▼
┌────┬──────┐    ┌────┬──────┐    ┌────┬──────┐
│ 10 │   •──┼───▶│ 20 │   •──┼───▶│ 30 │ NULL │
└────┴──────┘    └────┴──────┘    └────┴──────┘
 value next

Parcours :

for (struct Node *p = head; p != NULL; p = p->next) {
    printf("%d\n", p->value);
}

p->value est un raccourci pour (*p).value.

Pourquoi un double pointeur apparaît souvent avec les listes ?

Si une fonction doit pouvoir changer head lui-même, elle doit recevoir son adresse :

void clear_head(struct Node **head) {
    *head = NULL;
}

clear_head(&head);

head est un struct Node *, donc &head est un struct Node **.

L’allocation dynamique des nœuds avec malloc vient avec la partie suivante du cours sur l’organisation et la gestion dynamique de la mémoire.

Manipulation de bits

Les opérateurs bit à bit travaillent bit par bit :

a	b	a & b	a | b	a ^ b
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

• ~x : inverse tous les bits ;
• x & mask : conserve uniquement les bits sélectionnés par le masque ;
• x | mask : force certains bits à 1 ;
• x ^ mask : inverse certains bits.

Exemple :

x    = 1011 0110
mask = 0000 1000
       ---------
x&mask=0000 0000   → le bit 3 vaut 0

Pour manipuler le bit de position k, on construit souvent le masque 1u << k :

Objectif	Expression
tester le bit k	x & (1u << k)
mettre le bit k à 1	`x
mettre le bit k à 0	x &= ~(1u << k)
inverser le bit k	x ^= (1u << k)
lire exactement 0 ou 1	(x >> k) & 1u

Exemple :

unsigned int flags = 0;

flags |=  (1u << 3);   // bit 3 = 1
flags |=  (1u << 1);   // bit 1 = 1
flags &= ~(1u << 3);   // bit 3 = 0
flags ^=  (1u << 1);   // inverse le bit 1

Décalages, extraction et rotations

Les opérateurs de décalage déplacent les bits :

x << n    // décale de n positions vers la gauche
x >> n    // décale de n positions vers la droite

Pour un entier non signé, les nouvelles positions libérées sont remplies par des 0.

Exemple sur 8 bits :

x      = 0110 1011

x >> 1 = 0011 0101
x << 1 = 1101 0110

Les bits qui sortent lors d’un shift sont perdus.

Extraire les bits de poids fort ou faible

Pour un uint32_t, les positions vont de 31 à 0.

Les 3 bits de poids fort sont aux positions 31, 30, 29. Pour les ramener aux positions 2, 1, 0 :

uint8_t high3 = x >> 29;

Pour conserver seulement les 4 bits de poids faible, aucun déplacement n’est nécessaire : on utilise un masque.

x     = .... .... 1101
mask  = 0000 .... 1111
        --------------
x&mask= 0000 .... 1101

uint8_t low4 = x & 0xF;

À retenir :

bits de poids fort  → décaler vers la droite
bits de poids faible → masquer avec &

Rotation circulaire

Une rotation n’est pas un simple décalage : les bits qui sortent d’un côté doivent revenir de l’autre.

Rotation gauche de n positions sur 32 bits :

x                = [ A ][ reste ]
x << n           = [ reste ][ 0 ]
x >> (32 - n)    = [   0   ][ A ]
                   ---------------- OR
rotation         = [ reste ][ A ]

On recolle donc les deux morceaux avec un OU bit à bit :

(x << n) | (x >> (32 - n))

Avant de faire la rotation, on normalise le nombre de positions :

n %= 32;

Une rotation de 32, 64, etc. positions revient à une rotation de 0.

Décaler d’autant de bits que la largeur du type

Sur un uint32_t, une expression comme x >> 32 n’est pas valide en C. Après n %= 32, il faut donc traiter séparément le cas n == 0 avant d’évaluer x >> (32 - n).

&& / || ne sont pas & / |

• && et || sont des opérateurs logiques et font du court-circuit ;
• & et | travaillent sur tous les bits et évaluent les deux opérandes.

(ptr != NULL) && (ptr->value > 0)   // sûr si ptr == NULL
(ptr != NULL) &  (ptr->value > 0)   // tente quand même de déréférencer ptr

Gestion dynamique de la mémoire — CM3 et TD3 (malloc)

Carte mentale : où va la mémoire ?

Un programme C voit un espace d’adressage organisé notamment en segments text (code), données initialisées, BSS (données globales non initialisées ou initialisées à zéro), stack (appels de fonctions et variables locales automatiques) et heap (mémoire dynamique).

int global = 5;            // données initialisées
int zero[10];              // BSS

int main(void) {
    int x = 3;             // variable locale : généralement stack
    int *p = malloc(4 * sizeof *p);
    // p : variable locale ; les 4 entiers pointés : heap
    free(p);
}

Cas particulier du projet P0

uint8_t MY_HEAP[64000] est un tableau global (donc dans le BSS s’il n’est pas initialisé explicitement), et pas le véritable segment heap. Il sert à simuler une réserve de mémoire : my_malloc et my_free gèrent les 64 000 octets déjà disponibles, sans appeler malloc, free, brk ou sbrk.

malloc n’est pas un appel système

malloc / free sont des fonctions de la bibliothèque C (libc), exécutées en mode utilisateur. L’allocateur conserve une réserve et gère des blocs libres ou occupés : un simple malloc(4) ne nécessite donc pas automatiquement une transition vers le noyau.

Si la réserve est insuffisante, la bibliothèque peut demander au système davantage de mémoire. Dans le modèle du CM3 :

• Le program break est la limite de fin du heap.
• brk(adresse) positionne le program break à l’adresse demandée.
• sbrk(n) décale cette limite de n octets ; sbrk(0) consulte sa position.
• Attention : en cas de succès, sbrk(n) retourne l’ancien program break (voir la page de manuel reproduite au slide 36), pas le nouveau.

Programme C
    │ malloc(4)                     fonction libc, mode utilisateur
    ▼
Allocateur : cherche un bloc libre
    ├─ bloc disponible → réserve ce bloc → retourne un pointeur
    └─ réserve insuffisante → peut demander plus de mémoire au noyau
                               (brk/sbrk dans le modèle du cours)

Nuance : les allocateurs modernes peuvent aussi obtenir des zones par mmap. L’important pour l’examen reste la différence entre gestion des blocs par la libc et demande de mémoire au noyau.

Bits, bytes, structures : calculer sans se tromper

1 bit vaut 0 ou 1 ; 1 byte = 1 octet = 8 bits. Ainsi, 32 bits = 4 octets, et non 32 octets.

Dans l’architecture 32 bits supposée par le TD3, un int et un pointeur occupent chacun 4 octets :

struct meta_data {
    int is_block_free;             // 4 octets
    int block_size;                // 4 octets
    struct meta_data *next_block;  // 4 octets
};                                // 12 octets dans ce modèle

Le header précède la zone remise au programme. Si une allocation demande 4 octets :

[   métadonnées : 12 B   ][ données : 4 B ]
<--------------- 16 octets --------------->
                            ↑
                pointeur rendu à l'utilisateur

Pour l’étape 2 du TD, on suppose explicitement que la zone de données fait exactement la taille demandée : on ignore l’alignement et le padding dans ces calculs.

Demande	Métadonnées	Total sans padding	Proportion de métadonnées
malloc(1)	12 B	13 B	12/13 ≈ 92,3 %
malloc(4)	12 B	16 B	12/16 = 75 %
malloc(100)	12 B	112 B	12/112 ≈ 10,7 %

Méthode : compter chaque champ en bits, convertir en octets, additionner, puis diviser taille_métadonnées / (taille_métadonnées + taille_données_réservées). Ici, les 12 octets sont l’hypothèse du TD en 32 bits, pas une taille universelle de tous les allocateurs.

Alignement et padding : deux notions différentes

L’alignement impose que les adresses retournées respectent un multiple donné (par exemple 16 octets dans l’exemple Linux du slide 39). Le padding est le remplissage ajouté pour respecter cette contrainte.

Exemple pédagogique : si l’allocateur arrondit une zone utile de 17 octets au multiple de 16 supérieur, il réserve 32 octets utiles arrondis : 15 octets de padding. Ce n’est pas nécessairement le coût total réel de malloc(17) : les headers et la stratégie de l’allocateur s’ajoutent éventuellement.

Le piège du TD3

Ne pas mélanger les hypothèses : la question sur les 12 octets suppose des données de taille exacte ; la simulation sur 16 octets peut utiliser un header compact de 4 octets et un alignement de 4 octets. Aucun « alignement par défaut à 16 » n’est imposé à ton allocateur pédagogique.

Dessiner un allocateur : header, pointeurs, états

Un bloc contient typiquement [header][données][padding éventuel]. Le header mémorise au moins sa taille (souvent header inclus) et son état libre/alloué. Le pointeur de my_malloc pointe au début des données, pas au header.

Simulation du TD3 : zone de 16 octets, header compact de 4 octets contenant taille totale du bloc + bit alloué, et découpage par blocs de 8 octets ; les adresses ci-dessous sont des décalages par rapport au début de la zone :

Après init()
offset  0                   4                              16
        [ H : libre, taille 16 ][      espace disponible      ]

a = my_malloc(4)
offset  0          4          8          12         16
        [H1 alloc.][  a : 4 B ][H2 libre ][ libre 4 B ]

b = my_malloc(4)
offset  0          4          8          12         16
        [H1 alloc.][  a : 4 B ][H2 alloc.][  b : 4 B ]
                     ↑ a=4                   ↑ b=12

my_free(a)
offset  0          4          8          12         16
        [H1 libre ][ ancien a ][H2 alloc.][  b : 4 B ]

Avec le choix « bit 0 = alloué », H1 encode initialement 16 (libre), puis 9 (= 8 octets + bit 1) après allocation, puis 8 après my_free(a). Le pointeur a vaut donc base + 4 ; si l’allocateur réutilise ce premier bloc libre, un prochain my_malloc(4) pourrait rendre la même adresse.

free ne met pas nécessairement les octets à zéro : il modifie le statut du bloc. L’ancien pointeur ne doit plus être déréférencé après la libération.

Comment un allocateur trouve-t-il de la place ?

Liste implicite : chaque bloc possède un header ; pour avancer, on ajoute la taille totale du bloc à l’adresse du header courant. La recherche parcourt potentiellement aussi les blocs occupés : coût de recherche proportionnel au nombre de blocs examinés.

Liste explicite : des pointeurs relient uniquement les blocs libres ; recherche souvent plus rapide, mais davantage de métadonnées et de travail pour tenir la liste à jour.

Choix du bloc (politique) :

Politique	Idée	Compromis
First fit	Premier bloc libre assez grand	Simple/rapide, fragmentation possible
Next fit	Repart de la dernière position	Parcours différent, fragmentation possible
Best fit	Plus petit bloc libre suffisant	Recherche plus coûteuse ; pas d’optimalité globale garantie

First fit est une politique possible, pas un comportement « par défaut » de tous les allocateurs.

Scission (split) : si un bloc libre est trop grand, le partager en bloc alloué et bloc libre résiduel, à condition que le reste puisse contenir ses propres métadonnées (et respecter l’alignement).

Fusion (coalescing) : après free, réunir les blocs libres adjacents. On ne peut pas déplacer arbitrairement les blocs encore alloués, car le programme détient déjà leurs adresses.

• Fragmentation interne : espace non utilisable dans les blocs réservés (padding et coût des métadonnées dans la convention du CM).
• Fragmentation externe : mémoire totale libre suffisante, mais dispersée en trous non contigus.

Réflexe pour un schéma de TP ou d’examen

Avant de calculer : préciser taille de la zone, taille du header, alignement, taille enregistrée dans le header, état initial et politique de placement. Puis dessiner dans l’ordre : init → malloc → malloc → free. Pour chaque opération, indiquer les offsets exacts, les métadonnées et les données utilisateur.

Shell et Bash

Shell, utilitaire et commande interne

Le shell est l’interpréteur de commandes. Il lance des programmes, gère les variables, les redirections, les pipes et les scripts.

• cat est un utilitaire externe.
• cd est une commande interne du shell, car elle doit modifier le répertoire courant du shell lui-même.

Flux standards

Chaque processus dispose notamment de trois flux standards :

Descripteur	Flux	Rôle
0	STDIN	entrée standard
1	STDOUT	sortie standard
2	STDERR	sortie d’erreur

Redirections principales :

cmd > fichier       # STDOUT vers fichier, écrase
cmd >> fichier      # STDOUT vers fichier, ajoute à la fin
cmd 2>&1            # STDERR vers le même endroit que STDOUT
cmd1 | cmd2         # STDOUT de cmd1 devient STDIN de cmd2

Exemple :

cmd > output.txt 2>&1

STDOUT est envoyé dans output.txt, puis STDERR est redirigé vers le même endroit.

Pipes et composition

La philosophie UNIX consiste à combiner de petits outils spécialisés.

cat file.txt | sort | uniq

• cat produit le contenu ;
• sort regroupe les lignes identiques en les triant ;
• uniq fusionne les lignes identiques adjacentes.

Le schéma général utile est :

commande → pipe → filtre → redirection

Variables et arguments Bash

$0      # nom/chemin utilisé pour lancer le script
$1      # premier argument
$2      # deuxième argument
$#      # nombre d'arguments
$?      # code de retour de la dernière commande

Un code de retour 0 indique généralement un succès ; une valeur non nulle signale une erreur ou un cas particulier.

Exemple :

if [ $# -ne 2 ]; then
    echo "Erreur" > /dev/stderr
    exit 2
fi

-ne signifie not equal pour une comparaison numérique.

Deux syntaxes à ne pas confondre

${VAR}       # valeur d'une variable
$(commande)  # sortie produite par une commande

Exemple :

for dossier in $(find "$DOSSIER" -type d)
do
    ...
done

awk : attention au sens de $1

Dans Bash, $1 est le premier argument du script.

Dans :

awk '{print $1, $2}'

$1 et $2 désignent les premier et deuxième champs de la ligne courante traitée par awk.

/dev/null et code de retour

/dev/null est un « trou noir » : les données écrites dedans sont ignorées.

grep "hello" fichier.txt > /dev/null

if [ $? -eq 0 ]; then
    echo "trouvé"
fi

Même si la sortie de grep est jetée, son code de retour reste disponible dans $?.

Méthodes et pièges fréquents

• Ne pas confondre CPU et contrôleur de périphérique.
• Ne pas confondre $1 de Bash avec $1 dans awk.
• Ne pas confondre ${VAR} avec $(commande).
• > écrase, >> ajoute.
• uniq ne supprime correctement les doublons dispersés que si les lignes identiques ont d’abord été regroupées, typiquement avec sort.
• Dans les tests Bash, les espaces autour de [ et ] sont significatifs.