¿Por qué la recursión infinita conduce a la falla seg? ¿Por qué el desbordamiento de pila conduce a un fallo seg? Estoy buscando una explicación detallada.¿Por qué la recursión infinita conduce a la falla seg
int f()
{
f();
}
int main()
{
f();
}
Cada vez que se llama a f(), se aumenta el tamaño de la pila - que es donde se almacena la dirección de retorno por lo que el programa sabe dónde ir a cuando f() finaliza. Como nunca sale de f(), la pila aumentará al menos una dirección de retorno en cada llamada. Una vez que el segmento de la pila está completo, se obtiene un error segfault. Obtendrás resultados similares en cada sistema operativo.
Excepto para los compiladores que optimizan las llamadas finales en bucle. Pero tu respuesta es correcta de todos modos, +1 de mí – qrdl
AFAIK: Los extremos de la pila están protegidos por direcciones que no son accesibles para el proceso. Esto evita que la pila crezca sobre las estructuras de datos asignadas, y es más eficiente que verificar el tamaño de la pila de manera explícita, ya que de todos modos debe verificar la protección de la memoria.
Esto tiene sentido – Pqr
Segmentation fault es una condición cuando su programa intenta acceder a una ubicación de memoria a la que no tiene acceso. La recursividad infinita hace que tu pila crezca. Y crecer Y crecer Eventualmente crecerá hasta un punto en que se derramará en un área de memoria a la que su programa tiene prohibido acceder mediante el sistema operativo. Entonces es cuando obtienes la falla de segmentación.
Diría que esta es la mejor respuesta. – Jeriko
He escuchado el término "colisión de pilas y montículos" utilizado para describir esto. – Maxpm
@Maxpm, eso tiene mucho sentido. La pila y el montón generalmente crecen uno hacia el otro. Entonces, si la pila crece demasiado, puede extenderse al montón. – Dima
Es todavía un stackoverflow ;-)
Lo que pasa es que el tiempo de ejecución de C no proporciona "instrumentalización" al igual que otros lenguajes administrados hacerlo (por ejemplo, Java, Python, etc.), por lo que escribir fuera del espacio designado para la pila en lugar de causar una excepción detallada solo se genera un error de nivel inferior, que tiene el nombre genérico de "falla de segmentación".
Esto es por motivos de rendimiento, ya que los watchdogs de acceso a la memoria se pueden configurar con soporte de hardware con poca o ninguna sobrecarga; No puedo recordar los detalles exactos ahora, pero generalmente se hace marcando las tablas de páginas de MMU o con los registros de compensaciones de segmentos mayormente obsoletos.
Es esencialmente el mismo principio que un desbordamiento de búfer; el sistema operativo asigna una cantidad fija de memoria para la pila, y cuando se agota (desbordamiento de pila) obtiene un comportamiento indefinido, que en este contexto significa un SIGSEGV.
La idea básica:
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);}
finalmente RSP mueve más allá del extremo de la pila y se intenta poner la siguiente dirección de retorno en el almacenamiento no asignado y sus barfs programa. Obviamente, los sistemas reales son un lote más complicado que eso, pero eso podría (y tiene) ocupar varios libros grandes.
En un nivel "bajo", la pila se "mantiene" a través de un puntero (el puntero de pila), guardado en un registro de procesador. Este registro apunta a la memoria, ya que la pila es memoria después de todo. Cuando empuja valores en la pila, su "valor" se reduce (el puntero de la pila se mueve de direcciones más altas a direcciones inferiores). Cada vez que ingresas a una función, se "toma" algo del espacio de la pila (variables locales); además, en muchas arquitecturas, la llamada a una subrutina empuja el valor de retorno en la pila (y si el procesador no tiene un puntero de pila de registro especial, es probable que se use un registro "normal", ya que la pila es útil incluso cuando las subrutinas pueden ser llamado con otros mecanismos), de modo que la pila sea al menos disminuida por el tamaño de un puntero (digamos, 4 u 8 bytes).
En un bucle de recursión infinito, en el mejor de los casos solo el valor de retorno ocasiona que la pila se reduzca ... hasta que apunta a una memoria a la que el programa no puede acceder.Y ves el problema de falla de segmentación.
Puede encontrar this page interesante.
algunas arquitecturas RISC almacenan la dirección de retorno en un registro ... pero esto no permite la recursión, ni llamar a otras subrutinas, a menos que permita usar registros diferentes; dado que los registros son usualmente limitados, al final se usaría lo que es más conveniente para permitir la recursión ... es decir, una pila ... o algunos otros mecanismos (como MMIX) que, sin embargo, consumen memoria, que pueden abordarse de alguna manera, y así el mismo problema surge tarde o temprano. – ShinTakezou
Una copia de programa o un puntero de instrucción es un registro que contiene el valor de la próxima instrucción que se ejecutará. En una llamada de función, el valor actual del contador de programa insertado en la pila y luego el contador de programa apunta a la primera instrucción de la función. El valor anterior aparece después de regresar de esa función y se asigna al contador del programa. En la recursión infinita, el valor se empuja una y otra vez y conduce al desbordamiento de la pila.
Los recursos de su sistema son limitados. Ellos son limitados. Incluso si su sistema tiene la mayor cantidad de memoria y almacenamiento en toda la Tierra, infinito es MUCHO MÁS GRANDE de lo que tiene. Recuerda eso ahora.
La única manera de hacer algo un "número infinito de veces" es "olvidarse" de la información anterior. Es decir, debes "olvidar" lo que se ha hecho antes. De lo contrario, tienes que recordar lo que sucedió antes y que se lleva el almacenamiento de una forma u otra (caché, memoria, espacio en el disco, escribir cosas en el papel, ...). Esto es inevitable. Si está almacenando cosas, tiene una cantidad limitada de espacio disponible. Recuerda, ese infinito es MUCHO MÁS GRANDE que lo que tienes. Si intenta almacenar una cantidad infinita de información, se le agotará el espacio de almacenamiento.
Cuando emplea recursividad, está almacenando implícitamente información previa con cada llamada recursiva. Por lo tanto, en algún momento agotarás tu almacenamiento si tratas de hacer esto un número infinito de tomas. Su espacio de almacenamiento en este caso es la pila. La pila es una pieza de memoria finita. Cuando lo usa todo e intenta acceder más allá de lo que tiene, el sistema generará una excepción que, en última instancia, puede dar como resultado un fallo seg si la memoria a la que intentó acceder estaba protegida contra escritura. Si no estaba protegido contra escritura, continuará, sobrescribiendo lo que sabe Dios hasta que intente escribir en la memoria que simplemente no existe, o intente escribir en otra parte de la memoria protegida contra escritura. , o hasta que corrompa tu código (en la memoria).
Consulte [¿Por qué este error de segmentación de fragmentos de código en C++?] (Http://stackoverflow.com/questions/2809014/why-does-this-c-code-snippet-segmentation-fault). –