Pourquoi la récursion infinie conduit à une faute SEG? Pourquoi la pile débordement conduit à la défaillance de Seg. Je cherche une explication détaillée.
int f()
{
f();
}
int main()
{
f();
}
8 Réponses :
Chaque fois que vous appelez F (), vous augmentez la taille de la pile - c'est là que l'adresse de retour est stockée afin que le programme sait où aller à la fois F (). Comme vous ne quittez jamais F (), la pile va augmenter d'au moins une adresse de retour à chaque appel. Une fois le segment de pile rempli, vous obtenez une erreur Segfault. Vous obtiendrez des résultats similaires dans chaque système d'exploitation.
À l'exception des compilateurs qui optimisent les appels de la queue en boucle. Mais vous répondez est correct quand même, +1 de moi
AFAIK: Les extrémités de la pile sont protégées par des adresses qui ne sont pas accessibles au processus. Cela empêche la pile de développer des structures de données allouées et est plus efficace que la vérification de la taille de la pile explicitement, car vous devez vérifier la protection de la mémoire de toute façon.
Défaut de segmentation est une condition lorsque votre programme tente d'accéder à un emplacement de mémoire qu'il n'est pas autorisé à accéder. La récursion infinie provoque la croissance de votre pile. Et grandir. Et grandir. Finalement, il augmentera à un point lorsqu'il se répandra dans une zone de mémoire que votre programme est interdit d'accéder par le système d'exploitation. C'est quand vous obtenez la défaillance de la segmentation.
J'ai entendu le terme "collision de la pile-tas" utilisé pour décrire cela.
@Maxpm, ça fait un sens parfait. La pile et le tas poussent généralement l'un vers l'autre. Donc, si la pile devient trop grande, elle peut se déverser dans le tas.
C'est toujours un piquantflow; -)
La chose est que le temps d'exécution C ne fournit pas "instrumentalisation" comme d'autres langues gérées (par exemple, Java, Python, etc.), alors écrire en dehors de l'espace désigné pour la pile au lieu de provoquer une exception détaillée que Erreur de niveau inférieure, qui a le nom générique de "défaut de segmentation".
Ceci est destiné aux raisons de performances, car ces watchDogs d'accès à la mémoire peuvent être définis avec l'aide d'un support matériel avec peu ou aucun aérien; Je ne me souviens pas des détails exacts maintenant, mais il est généralement fait en marquant les tables de la page MMU ou avec les registres de décalage de segment essentiellement obsolètes.
C'est essentiellement le même principe qu'un débordement tampon; Le système d'exploitation alloue une quantité fixe de mémoire pour la pile et lorsque vous manquez (dépassement de pile), vous obtenez un comportement indéfini, lequel dans ce contexte signifie un SIGSEGV.
L'idée de base: p>
int stack[A_LOT];
int rsp=0;
void call(Func_p fn)
{
stack[rsp++] = rip;
rip = fn;
}
void retn()
{
rip = stack[--rsp];
}
/*recurse*/
for(;;){call(somefunc);}
à un niveau "bas", la pile est "maintenue" via un pointeur (le pointeur de pile), conservé dans un registre de processeur. Ce registre pointe vers la mémoire, car la pile est la mémoire après tout. Lorsque vous appuyez sur les valeurs sur la pile, sa "valeur" est décrémentée (le pointeur de pile passe des adresses supérieures aux adresses inférieures). Chaque fois que vous entrez une fonction, certains espaces sont "pris" de la pile (variables locales); De plus, sur de nombreuses architectures, l'appel à un sous-programme pousse la valeur de retour sur la pile (et si le processeur n'a pas de pointeur de pile de registre spécial, un registre «normal» est probablement utilisé à cet effet, car la pile est utile même lorsque les sous-routines peuvent être utiles. être appelé avec d'autres mécanismes), de sorte que la pile soit au moins diminuée de la taille d'un pointeur (par exemple, 4 ou 8 octets).
Dans une boucle de récursion infinie, seule la valeur de retour ne fait que décrémenter la pile ... jusqu'à ce qu'il pointe vers une mémoire qui ne peut pas être accessible par le programme. Et vous voyez le problème de défaut de segmentation.
Vous pouvez trouver intéressant Cette page .
Certaines architectures de RISC stockent l'adresse de retour dans un registre ... mais cela ne permet pas de récursion, ni d'appeler une autre sous-secteur, à moins que cela ne permet d'utiliser différents registres; Étant donné que les registres sont généralement limités, à la fin, on utiliserait ce qui est plus pratique pour permettre la récursion ... c'est-à-dire une pile ... ou certains autres mécanismes (comme MMIX) qui consomme cependant de la mémoire, qui peut être adressée à ce que Le même problème se pose bientôt ou plus tard.
Un copuneur de programme ou un pointeur d'instruction est un registre contenant la valeur de la prochaine instruction à exécuter. Dans un appel de fonction, la valeur actuelle du compteur de programme poussé dans la pile puis de programmer des points de compteur à la première instruction de la fonction. L'ancienne valeur est apparue après son retour de cette fonction et attribué au compteur de programme. Dans la récursion infinie, la valeur est encore poussée à nouveau et conduit au débordement de la pile.
Vos ressources système sont finies. Ils sont limités. Même si votre système a le plus de mémoire et de stockage sur toute la Terre, Infinite est bien plus grand que ce que vous avez. N'oubliez pas que maintenant.
Le seul moyen de faire quelque chose d'un "nombre infini de fois" est d'oublier les informations précédentes. C'est-à-dire que vous devez "oublier" ce qui a été fait auparavant. Sinon, vous devez vous rappeler ce qui s'est passé avant et que cela prend stockage d'une forme ou d'une autre (cache, mémoire, espace disque, écrivant des choses sur papier, ...) - Ceci est inévitable. Si vous stockez des choses, vous avez une quantité finie d'espace disponible. Rappelez-vous que infini est beaucoup plus grand que ce que vous avez. Si vous essayez de stocker une quantité infinie d'informations, vous manquerez d'espace de stockage.
Lorsque vous utilisez la récursivité, vous stockez implicitement des informations précédentes avec chaque appel récursif. Ainsi, à un moment donné, vous épuiserez votre stockage si vous essayez de le faire un nombre infini de prises. Votre espace de stockage dans ce cas est la pile. La pile est un morceau de mémoire finie. Lorsque vous l'utilisez tout et essayez d'accéder au-delà de ce que vous avez, le système générera une exception pouvant finalement entraîner une défaillance SEG si la mémoire qu'il a essayé d'accéder était protégée en écriture. Si ce n'était pas protégé en écriture, il continuera à continuer, écrasera Dieu-sait - ce que ce soit jusqu'à ce qu'il essaie d'écrire à la mémoire qui n'existe tout simplement pas, ou il essaie d'écrire à une autre pièce de mémoire protégée en écriture. , ou jusqu'à ce qu'il corrompre votre code (en mémoire).
Voir Pourquoi cette défaut de segmentation C ++ Code-Snippet? .