La pile des appels

La pile des appels (aussi appelée "pile d'exécution", "call stack" ou, souvent, "le stack") est une zone de la mémoire (paginée par pages de 4 Ko) où on empile des contextes d'exécution (un grand terme qui signifie au fond des sous-programmes). Elle est accompagnée d'un pointeur d'exécution qui pointe vers le contexte du haut de la pile.

Une pile est une structure de données qui ne permet que deux (parfois trois) opérations:

• Push: on empile quelque chose en l'ajoutant sur le dessus de la pile, par-dessus ce qui est déjà là.
• Pop: on "dépile" en sortant de la pile l'objet qui est sur le dessus. On ne peut pas atteindre un objet ailleurs que sur le dessus de la pile.
• Peek (parfois): on regarde l'objet du dessus de la pile, sans le "dépiler".

La pile est donc une structure FILO (First In Last Out -- le premier entré est le dernier sorti) ou LIFO (Last In First Out -- le dernier entré est le premier sorti). Elle est particulièrement efficace par sa simplcité: les blocs mémoire sont toujours contigus, ne laissant pas de « trous », contrairement au tas. Elle est généralement considérée comme opposée à la structure file (FIFO). Pensez à une pile d'assiette dans un buffet chinois, versus une file d'attente à l'épicerie.

Un contexte d'exécution contient:

• Les paramètres à la fonction;
• L'adresse mémoire de l'appelant, donc où reprendre l'exécution lorsque la fonction sera terminée (ce qui nous permettra de revenir en arrière);
• Les variables locales à la fonction en cours d'exécution.

On ne peut jamais voir les contextes d'exécution qui se trouvent en dessous du contexte courant. On est donc toujours en train d'exécuter le contexte du dessus de la pile.

Lorsqu'on appelle une fonction, on empile son contexte: on empile les valeurs des paramètres qu'on lui passe, puis on empile l'adresse mémoire de la ligne qui vient d'appeler la fonction. On change le pointeur d'exécution.

La fonction va empiler ses variables locales sur le dessus de la pile, va prendre les valeurs de ses paramètres et va s'exécuter. Lorsqu'elle aura fini, elle va: "dépiler" le contexte d'exécution, empiler sa valeur de retour et changer le pointeur d'exécution pour le replacer à l'adresse mémoire qui lui a été fournie.

On se retrouvera donc de nouveau dans la fonction appelante. Cette fonction va prendre la valeur de retour sur le dessus de la pile et va en faire ce qu'elle veut, puis va poursuivre son exécution.

En empilant les contextes à l'appel et en les "dépilant" au retour, on sait toujours exactement où on est rendu et d'où on vient. Ça explique aussi pourquoi:

• Les variables locales des autres fonctions sont inaccessibles pour nous -- elles ne sont pas dans notre contexte, le seul qui est accessible;
• Nos variables locales ne seront plus accessibles aux autres lorsqu'on aura fini de s'exécuter -- elles vont disparaître de la pile dès la fin de notre exécution.

(source du graphique: Wikipedia)

Notez qu'on peut voir la pile des appels pendant qu'on est en débogage:

(si on ne la voit pas, on peut l'ouvrir en faisant Déboguer -> Fenêtres -> Pile des appels)

La pile nous montre quelle fonction est en exécution (en haut) et on peut suivre le chemin de retour en descendant la pile. Notez qu'il y a quelques trucs sous le main, qui font partie du framework et qui font en sorte que tout fonctionne -- le main est loin d'être réellement la première chose à être exécutée.

Questions et exercices

1- Prenez l'exercice 4.6 de votre cours d'algorithmie. Dessinez le contenu de la pile d'exécution une fois que le main a appelé GererMenu, que GererMenu a appelé AfficherMenu et qu'AfficherMenu est en train de s'exécuter. Imaginez les adresses des fonctions mais soyez cohérents!

2- En vous fiant sur votre dessin du numéro précédent, expliquez pourquoi est-ce que GererMenu, lorsqu'il est en exécution, ne peut pas accéder aux variables déclarées dans AfficherMenu.

3- Quel est le message d'erreur exact que vous obtenez en exécutant ce code en mode débogage? Pouvez-vous expliquer la situation? Qu'est-ce qui cause le "crash" exactement?

 

#include <iostream>
using namespace std;

int Factorielle(int Nombre);

int main()
{
	int Nombre;
	do
	{
		cout << "Entrez un nombre entier positif: ";
		cin >> Nombre;
		if (Nombre <= 0)
		{
			cout << "Votre nombre doit être plus grand que zéro" << endl;
		}
	} while (Nombre <= 0);

	cout << "La factorielle de votre nombre est: ";
	cout << Factorielle(Nombre) << endl;

	return 0;		 
}

int Factorielle(int Nombre)
{
	return Nombre * Factorielle(Nombre - 1);
}

 

---

Etienne Forest, 23 octobre, 2016