Un programme séquentiel est composé d'un ensemble de procédures qui s'appellent mutuellement. A chacune de ces procédures est associée une suite d'instructions, encore appelée le code de la procédure. Appelons activité le phénomène résultant de l'exécution ininterrompue d'une procédure unique. L'exécution d'un programme est donc une suite d'activités. Nous appelons contexte d'une activité l'ensemble des informations accessibles au processeur au cours de cette activité. Le contexte comprend donc un contexte du processeur (registres) et un contexte en mémoire (code et données). Le passage d'une activité à une autre est réalisé par des instructions spéciales, l'appel et le retour de procédure, qui réalisent une commutation du contexte.

Lors de l'appel d'une procédure q par une procédure p, il faut préparer les paramètres transmis à q par p, sauver le contexte de p pour le retrouver au retour, et remplacer ce contexte par celui de q. Au retour, il faut préparer les paramètres transmis par q à p, et restaurer le contexte de p. Le contexte de q est perdu. Cette sauvegarde et cette restauration utilisent une pile. Nous supposerons que les paramètres sont transmis par valeur; un résultat unique est rendu au retour. Les procédures peuvent être appelées récursivement directement ou indirectement.

A- Justifier l'utilisation d'une pile pour cette sauvegarde et cette restitution.

B- Comment passer les paramètres et le résultat.

C- Où peut-on mettre les locaux de la procédure appelée?

D- Décrire de façon détaillée les opérations d'appel et de retour, en précisant à chaque fois ce qui est fait par la procédure appelante et par la procédure appelée.

E- Pensez-vous que cette pile puisse être utile dans un contexte de multiprogrammation? d'appels au système? d'interruptions?

Remarque: S'il n'y a pas de récursivité, on peut réserver des emplacements fixes pour les contextes et paramètres des différentes procédures du programme. La pile n'est pas alors nécessaire. Cependant ceci conduit à réserver statiquement l'espace mémoire utilisé par les différentes procédures, même lorsqu'elles ne sont pas en cours d'exécution.

Le retour de procédure se fait en ordre inverse des appels. La restauration doit donc se faire en ordre inverse des sauvegardes. C'est bien la structure de pile qui offre cet ordre.

Les paramètres doivent être mémorisés quelque part par la procédure appelante, et pouvoir être accédés par la procédure appelée. La pile peut servir de zone d'échange puisque les deux procédures connaissent le sommet de pile au moment de l'appel. Par ailleurs, comme la procédure appelée normalement les utilise pendant toute la durée de son activité, c'est-à-dire jusqu'au retour, ils peuvent rester dans la pile jusqu'à ce moment là.

Un raisonnement analogue pour le résultat montre que celui-ci doit être également conservé dans la pile pendant toute la durée de l'exécution de la procédure, pour être transmis à l'appelante lors du retour.

Les locaux de la procédure doivent être créés lors du début de l'activité correspondante, et détruits lors de la fin de l'activité. Si on admet les appels récursifs, ces locaux ne peuvent être à une adresse fixe en mémoire, puisqu'une même procédure peut donner lieu à plusieurs activités qui doivent coexister ensembles, avec chacune des locaux différents. Leur création/destruction doit donc être dynamique. Comme la création correspond à l'appel et la destruction au retour, ils sont détruits en ordre inverse de leur création, toutes procédures confondues. On peut donc utiliser la pile pour cela.

L'évolution de la pile au cours d'un appel de procédure peut être décrit par le schéma donné ci après.

Comme les objets locaux sont à un emplacement variable de la pile, il est nécessaire de repérer la zone où ils se trouvent, pour une exécution donnée de la procédure. Dans le schéma ci-dessus, ce rôle est assuré par ce que nous avons dénoté base. En général, il s'agit d'un registre que les compilateurs réservent à cet effet, par convention. Nous laissons à la procédure appelée le soin de ranger ce registre (et de le restituer à la fin); certaines procédures n'ayant pas de locaux, peuvent ne pas s'en préoccuper, pourvu que le registre ait, au moment du retour, la même valeur qu'au moment de l'appel.

tant que il faut sauvegarder faire
	empiler (ce qu'il faut)
fait
réserver place résultat en pile
tant que il y a des paramètres faire
	empiler (valeur du paramètre)
fait
appel_proc
supprimer les paramètres de la pile, si nécessaire
dépiler (résultat)
tant que il faut restaurer faire
	dépiler (ce qu'il faut)
fait

empiler (base)
base := sommet
réservation des locaux { sommet := sommet - taille }
corps de la procédure
supprimer les locaux { sommet := sommet + taille }
dépiler (base)
retour_proc

Dans un contexte de multiprogrammation, lors de l'interruption d'un programme, il faut évidemment sauvegarder le contexte en cours. Ceci peut être fait dans la pile. Cependant, le système peut décider de réactiver un programme différent de celui qu'il vient d'interrompre. Dans ce cas, on ne peut plus rien dire sur l'ordre des retours vis-à-vis des appels. Ce que l'on peut affirmer, néanmoins, c'est que pour un programme donné, lorsqu'il sera réactivé, il faudra restituer le contexte qu'il avait lorsqu'il avait été suspendu. Il faut donc attribuer une pile par programme.

Lors d'un appel système ou d'une interruption, le système doit sauvegarder le contexte du programme dans sa pile, et mémoriser les registres base et sommet dans un emplacement réservé au programme. Il peut alors prendre une pile qui lui est propre pour continuer le travail. Lorsqu'il veut relancer un programme, il restitue d'abord les registres base et sommet du programme, et restaure ensuite le contexte à partir de cette pile.