Architecture des systèmes informatiques
Pile d’exécution, appels de fonction, variables automatiques,
récursivité
Pile d’exécution
Le langage C est un langage à pile d’exécution (ou pile d’appels).
C’est aussi le cas de la plupart des langages impératifs.
La pile est un emplacement particulier de la mémoire associée à
chaque processus. C’est sur cet endroit précis que travaille le
processus dans l’avancement de son exécution.
Le fonctionnement de cette pile est régi par un certain nombre de
règles qui permettent de comprendre en profondeur le
fonctionnement du langage C et notamment des dispositifs comme
la récursivité.
Le langage C à la truelle
On peut résumer grossièrement un programme C comme un énorme
catalogue de fonctions (qui ont toutes le statut de variables globales)
qui s’articulent autour d’un main, point d’entrée du programme.
I Deux fonctions ne peuvent pas avoir le même nom.
I Une fonction ne peut pas être redéfinie. Pas de mécanisme de
surcharge.
I gcc *.c est une sorte de makefile universelle (SVP, compile tout
dans un sac mes fonctions et essaye de linker un
programme. . . )
I Pas de classe de visibilité. . . le seul confinement possible pour
une fonction est le modificateur static qui confine une fonction
dans un fichier.
.: En C, on met tout sur la table et on assemble :.
La pile d’exécution
La pile d’exécution est d’abord un emplacement de la mémoire qui
fonctionne comme une pile : LIFO Last In First Out ou encore
dernier arrivé, permier exécuté.
I À l’exécution du programme, la pile est initialisée par Unix avec
un appel original à main.
I Chaque nouvel appel de fonction s’empile au dessus de la
fonction qui l’appelle.
I La fonction qui s’exécute est toujours celle associée à l’appel
tout en haut de la pile.
I Quand une fonction retourne (elle rend sa valeur de retour. . . ),
son appel est dépilé. Toutes ses informations contextuelles
associées deviennent caduc car potentiellement écrasées par
d’autres appels.
I Quand l’appel originel à main est dépilé, c’est le programme
qui retourne et qui est censé retourner un entier Unix
compatible (0 pour OK, 1-255 pour les erreurs)
Valeur de retour d’un programme
$? est la variable mise à jour par le terminal qui contient le code de
retour du dernier programme exécuté.
nborie@bayer:$ cat pouet
cat: pouet: Aucun fichier ou dossier de ce type
nborie@bayer:$ echo $?
1
nborie@bayer:$ echo "Bonjour"
Bonjour
nborie@bayer:$ echo $?
0
Dans une commande pipée : cmd1 | cmd2 | cmd3 | cmd4, le
code de retour est celui de cmd4. cmd3 est fils de cmd4, cmd2
est fils de cmd3 et cmd1 est fils de cmd2. La commande maître
du programme parallélisé est la dernière.
Rappel sur le langage C
Toute variable C est caractérisée par 4 éléments :
I Un identificateur.
I Un type, donc une taille en octet.
I Un emplacement mémoire.
I Une valeur (même non initialisés, les bits ont toujours une
valeur résiduelle).
Le langage C est un langage typé statiquement fort mais affaibli par
les casts et pointeurs.
typage statique : types déclarés en dur par le programmeur avant
la compilation
typage fort : garantie des données contenues par rapport aux
contenants
Variables automatiques
une variable automatique est le nom général que l’on donne aux
variables à durée de vie limitée allouées et libérées automatiquement
lors de l’exécution des programmes.
I De nombreux langages ont des variables automatiques (C,
C++, Perl, Java, Python, . . . ),
I Les variables locales standards du C sont des variables
automatiques.
I Les variables locales statiques du C ne sont pas automatiques
(en vie durant tout un programme. . . ).
I Pareil pour les variables globales et globales statiques en C.
Elles sont aussi en allocation statique (début et fin du
programme) et pas automatique.
I Dans tous les cas, les retours et les arguments des fonctions en
C ont toujours une taille mémoire connue.
Mémoire contextuelle d’une fonction
En C, toute fonction a un type de retour (possiblement void) et
toute fonction possède des arguments typés (possiblement void).
Aussi toute fonction peut déclarer des variables locales dans leur
corps.
Une fonction composée de plusieurs blocs peut très bien y définir
des variables dans chaque sous bloc.
Pour éviter le coût de l’allocation dynamique (malloc) et pour éviter
de faire grossir trop largement la mémoire utilisée, toutes ces
données à utilité et durée de vie limitée sont positionnées sur la pile
d’exécution conjointement avec l’appel de fonction.
Appel de fonction sur la pile
Figure 1: Cadres des fonctions sur la pile d’appel
L’appel originel à main
Regardons l’initialisation de la pile d’appels lors du lancement d’un
programme.
I Le vrai visage d’un main Unix compatible est :
int main(int argc, char* argv[], char* env[])
argc est le nombre d’arguments transmis par Unix depuis la
console. argv est un tableau de chaîne de caractères C
contenant argc chaînes différentes. env est le tableau des
chaînes d’environnement, ce tableau marque sa fin via l’adresse
NULL.
I argc et argv sont suffisants dans 98% des cas. . . Les variables
d’environnement sont exploitées par les gros programmes
sérieux ayant un besoin important d’intégrations/interactions
avec le système.
Vrai visage de main
Programme true_main :
#include <stdio.h>
int main(int argc, char* argv[], char* env[]){
int i;
for (i=0 ; i<argc ; i++)
printf("argv[%d] : %s\n", i, argv[i]);
for (i=0; env[i] != NULL ; i++)
printf("%s ", env[i]);
printf("\n");
return 0;
}
Vrai visage de main
nborie@bayer:$ ./true_main 12 Salut "j'aime les frites!"
argv[0] : ./true_main
argv[1] : 12
argv[2] : Salut
argv[3] : j'aime les frites!
CLUTTER_IM_MODULE=xim LS_COLORS=rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so
35:do=01;35:bd=40;33;01:cd=40;33;01:or=40;31;01:mi=00:su=37;41:sg=30;43:
41:tw=30;42:ow=34;42:st=37;44:ex=01;32:*.tar=01;31:*.tgz=01;
...
LESSCLOSE=/usr/bin/lesspipe %s %s XDG_MENU_PREFIX=gnome-
LANG=fr_FR.UTF-8
DISPLAY=:0
GNOME_SHELL_SESSION_MODE=ubuntu
COLORTERM=truecolor
DESKTOP_AUTOSTART_ID=104d743654e8a58888155344115086884600000085990007
USERNAME=nborie
JAVA_HOME=/usr/lib/jvm/java-8-openjdk-amd64
...
OLDPWD=/home/nborie/Enseignements/Marne_2018_2019/Archi_systeme/nouveaux
_=./true_main
Petite visualisation de niveau I
#define STACK for(k=0 ; k<2*indent ; k++){putc(' ', stderr);} \
fprintf(stderr, "%s %d\n", __FUNCTION__, n); indent++;
#define return indent--; return
int indent=0;
int k;
int fibo(int n){
STACK
int ans;
if (n <= 1){
return 1;
}
ans = fibo(n-1) + fibo(n-2);
return ans;
}
int main(int argc, char* argv[]){
int n = atoi(argv[1]);
STACK
printf("fibo(%d) : %d\n", n, fibo(n));
return 0;
}
Traçage d’une petite exécution d’un Fibonacci récursif
nborie@bayer:$ ./fibo 5
main 5
fibo 5
fibo 4
fibo 3
fibo 2
fibo 1
fibo 0
fibo 1
fibo 2
fibo 1
fibo 0
fibo 3
fibo 2
fibo 1
fibo 0
fibo 1
fibo(5) : 8
Pile et performances
Il est crucial que la pile reste un organe permettant de garder des
programmes performants.
I Pas d’initialisation, ni de nettoyage !
I Les variables locales non initialisées ont des garbages values.
I Taille limitée à la création du processus associé
(ulimit -s : 8192 Ko)
I Explosion de la pile : erreur de segmentation, pas
d’augmentation dynamique de la pile
I Copies systématiques des valeurs pour les arguments
I Ne pas mettre de larges données sur la pile. . .
I Copier des adresses (64 bits), oui !
I Copier des contenus de tableaux, non !
I Les structures en argument ou en retour, toujours par adresses !
La mallocite aïgue
La mallocite aïgue est une maladie grave rependue chez les
programmeurs venant juste d’apprendre l’allocation dynamique.
Les symptômes sont les suivants : allouer dynamiquement tout ce
qu’on manipule sans discernement.
Traitement : montrer du doigt ces programmeurs en riant
sardoniquement. Il faut espérer que les trop nombreux appels à
malloc (souvent mal opérés) génèrent de plus amples erreurs dans
leur programmes.
.:Les antibiotiques Les variables locales, c’est automatique !:.
Pas d’allocation, pas de libération, pas de collision, pas d’appel à
une machinerie complexe. . . On utilise malloc quand on ne peut
pas faire autrement car c’est le mécanisme le plus complexe pour
obtenir de la mémoire.
Exploiter la mémoire en C
Mémoire Allocation Localisation Scope Durée de vie
Var locale automatique pile bloc 1 appel
Var locale statique statique data/bss bloc progr
Var globale statique data/bss full progr
Var globale statique statique data/bss fichier progr
Alloc dynamique dynamique tas ... à la demande
L’art de coder en C (le vrai pas la pataugeoire. . . .) consiste à
modéliser et structurer son code tout en manipulant le type de
mémoire le plus adapté à son problème.
Choisir le type de mémoire et Structurer en module sont deux
choix conjoints et interpédendants dans les implémentions en C.
Copies des arguments
I Les arguments SONT SYSTÉMATIQUEMENT copiés !
I Quand on fait un passage par adresse, c’est une copie d’adresse
que l’on manipule. Mais avec une copie de votre adresse
personnelle, je vous promet que je peux aller chez vous !
void libere_tableau(int* tab){
free(tab);
tab = NULL;
}
...
libere_tableau(tab);
if (tab != NULL)
printf("WTF ????");
WTF ???? Mettre la copie à NULL est juste inutile ! Pour modifier,
il faut monter d’un niveau d’indirection (adresse d’adresse pour
modifier l’adresse originale. . . )
Fonctions variadiques en C
I Une fonction variadique en C est une fonction qui accepte un
nombre non précisé d’arguments de type eux-aussi non précisé.
I Une fonction variadique POSSÈDE TOUJOURS au moins un
argument typé avant les argument variadique désigné par . . . .
I Les arguments variadiques sont empilés en mémoire contiguë et
octet pat octet au dessus du dernier argument nommé sur la
pile d’appel.
I C’est le code source de la fonction variadique appelée qui doit
déterminer les types.
I printf devine les types en parsant les %[d-u-f-g-s-p-o]
Nombre d’arguments variable
I . . . dans le prototype :
int printf(const char* format, ...);
I Type et macros définies dans la lib <stdarg.h>
I Le dernier argument nommé va être utilisé pour amorcer des
offsets
I on crée une variable de type va_list qui va parcourir les
paramètres empilés
I on l’initialise à partir du dernier paramètre connu avec
va_start
Nombre d’arguments variable
I on accède au prochain paramètre avec
va_arg(va_list, type)
I C’EST AU PROGRAMMEUR DE SAVOIR QUEL EST LE
TYPE DU PROCHAIN PARAMÈTRE !!!
I ⇒ Ce qui vous explique le coût et la nécessité d’un parsing
d’un format d’entrée/sortie pour la printf/scanf family.
I quand on a fini, on doit appeler une (et une seule fois)
va_end(va_list)
I La documentation précise que va_arg(va_end) peut être une
fonction ou même une macro. . . Étant donné le danger des
macros, pensez bien à fermer le parcours des arguments des
fonctions variadiques
Formatage de date
void print_date(const char* fmt, ...){
if (fmt==NULL) return ;
va_list args;
va_start(args, fmt);
int i=0, d;
while (fmt[i]!='\0'){
switch (fmt[i]){
case 'D': case 'M': case 'Y':
d = va_arg(args, int);
if (fmt[i]=='Y' && fmt[i+1]=='Y'){
printf("%04d", d);
i++;
} else printf("%02d", d%100);
break;
default: printf("%c", fmt[i]);
}
i++;
}
va_end(args);
}
int main(int argc, char* argv[]){
print_date("D/M/Y\n", 4, 11, 2006);
print_date("date: D-M-YY\n", 4, 11, 2006);
return 0; }
La magie de la récursivité
Non. . . .
Non, non et non !
Vraiment non !
Please god no !!!! NOOOOOOOOOOOO !!!
Il n’y a pas de magie dans un ordinateur ! Aucune ! Rien, nada. . .
I Nos ordinateurs sont déterministes. Leurs comportements sont
prévisibles. Leurs capacités actuelles sont la résultante d’une
collection incroyable d’astuces algorithmiques et techniques.
I Un ordinateur ne se rappelle pas magiquement de ce qu’il doit
faire, il ne devine pas non plus comment résoudre les problèmes.
Il exécute ce qu’on lui demande, point.
I Le cerveau de l’ordinateur est situé dans la boite crânienne de
son utilisateur.
Récursivité et pile d’appel
I Une fonction récursive est une fonction qui va empiler
possiblement plusieurs occurrences d’elle-même sur la pile
d’appels.
I Pour que la stratégie soit viable, les appels empilés sont
souvent fait avec des arguments décroissants
I Il faut aussi prévoir une stratégie de sortie (un cas limite) où la
fonction ne se rappelle pas mais retourne directement le
résultat.
I Les fonctions récursives font gonfler la pile d’exécution (Python
: max depth of recursion)
I Les fonctions récursives permettent de coder simplement des
problèmes très complexes.
I La pile est la TODO list dynamique du programme qui ainsi
modélise le travail à réaliser pour son utilisateur.
Backtracking (retour sur trace)
I Une fonction récursive est une fonction qui peut être amenée à
ce rappeler soi-même.
I Quand une fonction se rappelle soi-même dans sa définition, on
dit qu’elle opère un appel récursif.
I Le code placé avant un appel récursif est dit exécuté en
montée de récursion.
I Le code placé après un appel récursif est dit exécuté en
remontée de récursion.
def rec_func(args):
if (args petit):
return petite_solution
# code en montée de récursion
rec_func(args plus petits)
# code en remontée de récursion
return solution
Backtracking : permutations en C
#define SIZE 3
void permutations(int tab[SIZE], int current){
int i;
if (current > SIZE){
print_array(tab, SIZE); putchar('\n');
return ;
}
for (i=0 ; i<SIZE ; i++){
if (tab[i] == 0){
tab[i] = current;
permutations(tab, current+1);
tab[i] = 0; /* Action en remontée de récursion */
}
}
}
Backtracking : permutations en C
I Exécution et génération des permutations de taille 3
nborie@bayer:$ gcc -o test permutation.c -Wall -ansi
nborie@bayer:$ ./test
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[3, 1, 2]
[2, 3, 1]
[3, 2, 1]
En mémoire, état du tableau tab
[0,0,0] Appel originel
[1,0,0]
[1,2,0]
[1,2,3] --> affichage
[1,0,2]
[1,3,2] --> affichage
[0,1,0]
[2,1,0]
[2,1,3] --> affichage
[0,1,2]
[3,1,2] --> affichage
[0,0,1]
[2,0,1]
[2,3,1] --> affichage
[0,2,1]
[3,2,1] --> affichage
