En informatique, un dépassement de pile se produit lorsque le pointeur de pile d'appels dépasse les limites de la pile . La pile d'appels peut contenir un espace d'adressage lim...
Worldlex WikiContenu en francaisLecture gratuite
de pile d'appels dépasse les limites de la pile . La pile d'appels peut contenir un espace d'adressage limité , souvent déterminé au démarrage du programme. Sa taille dépend de nombreux facteurs, notamment le langage de programmation, l'architecture machine, le multithreading et la quantité de mémoire disponible. Lorsqu'un programme tente d'utiliser plus d'espace que celui disponible sur la pile d'appels (c'est-à-dire lorsqu'il tente d'accéder à de la mémoire au-delà des limites de la pile d'appels, ce qui est similaire à un dépassement de tampon ), on dit que la pile déborde , ce qui entraîne généralement un plantage du programme . C :
erreur de segmentation . Cependant, certains compilateurs implémentent l'optimisation des appels terminaux , autorisant une récursion infinie d'un type spécifique — la récursion terminale — sans débordement de pile. Cela fonctionne car les appels de récursion terminale n'occupent pas d'espace supplémentaire sur la pile.
Certaines options du compilateur C activent l'optimisation des appels terminaux ; par exemple, la compilation du programme simple ci-dessus avec gcc avec l'option `--tail` -O1entraînera une erreur de segmentation, contrairement à l'utilisation de `--tail` -O2ou ` -O3--tail`, car ces niveaux d'optimisation impliquent l' -foptimize-sibling-callsoption `--tail` du compilateur. D'autres langages, comme Scheme , exigent que toutes les implémentations incluent la récursivité terminale, conformément à la norme du langage.
Récursivité très profonde
Une fonction récursive qui se termine en théorie mais provoque en pratique un dépassement de tampon de la pile d'appels peut être corrigée en transformant la récursion en une boucle et en stockant les arguments de la fonction dans une pile explicite (plutôt que d'utiliser implicitement la pile d'appels). Ceci est toujours possible car la classe des fonctions récursives primitives est équivalente à la classe des fonctions calculables par boucle. Prenons cet exemple en pseudo-code de type C++ :
l'optimisation des appels terminaux ; toutefois, il reste possible de créer une fonction récursive susceptible de provoquer un dépassement de capacité de la pile dans ces langages. Prenons l'exemple ci-dessous de deux fonctions simples d'exponentiation d'entiers.
int pow ( int base , int exp ) { return pow_accum ( base , exp , 1 ); }int pow_accum ( int base , int exp , int accum ) { if ( exp > 0 ) { return pow_accum ( base , exp - 1 , accum * base ); } else { return cumul ; } }
Les deux pow(base, exp)fonctions ci-dessus produisent un résultat équivalent ; cependant, celle de gauche est susceptible de provoquer un dépassement de capacité de la pile, car l’optimisation des appels terminaux n’est pas possible pour cette fonction. Lors de l’exécution, la pile de ces fonctions se présentera comme suit :
dynamiquement les tableaux de plus de quelques kilo-octets plutôt que de les stocker dans une variable locale.
Exemple de variable de pile très volumineuse en C :
des nombres flottants double précision de 8 octets , le tableau déclaré consomme 8 mégaoctets de données ; si cela dépasse la mémoire disponible sur la pile (telle que définie par les paramètres de création du thread ou les limites du système d'exploitation), un dépassement de pile se produira.
environnement contraint
Les débordements de pile sont aggravés par tout ce qui réduit la taille effective de la pile d'un programme donné. Par exemple, le même programme exécuté sans multithreading peut fonctionner correctement, mais dès que le multithreading est activé, il plante. En effet, la plupart des programmes utilisant des threads disposent d'un espace de pile par thread inférieur à celui d'un programme sans prise en charge du multithreading. Les noyaux étant généralement multithreadés, il est généralement déconseillé aux personnes débutant dans le développement de noyaux d'utiliser des algorithmes récursifs ou de grands tampons de pile.
Worldlex Wiki