Desbordament de la pila
Al programari, es produeix un desbordament de la pila si el punter de la pila de crides supera el límit de la pila. La pila de crides pot consistir en una quantitat limitada d' espai d'adreces, sovint determinada a l'inici del programa. La mida de la pila de crides depèn de molts factors, com ara el llenguatge de programació, l'arquitectura de la màquina, el multiprocés i la quantitat de memòria disponible. Quan un programa intenta utilitzar més espai del que hi ha disponible a la pila de crides (és a dir, quan intenta accedir a la memòria més enllà dels límits de la pila de crides, que és essencialment un desbordament de memòria intermèdia), es diu que la pila es desborda, la qual cosa normalment resulta en un bloqueig del programa.[1]
Causes
[modifica]Recursió infinita
[modifica]La causa més comuna del desbordament de la pila és la recursivitat excessivament profunda o infinita, en què una funció s'anomena a si mateixa tantes vegades que l'espai necessari per emmagatzemar les variables i la informació associada a cada crida és més del que pot cabre a la pila.
Un exemple de recursivitat infinita en C:
int foo()
{
return foo();
}
La funció foo, quan s'invoca, continua invocant-se a si mateixa, assignant espai addicional a la pila cada vegada, fins que la pila es desborda provocant un error de segmentació. Tanmateix, alguns compiladors implementen l'optimització de la crida a la cua, permetent que es produeixi una recursió infinita d'un tipus específic— recursivitat de la cua— sense desbordament de la pila. Això funciona perquè les crides de recursivitat a la cua no ocupen espai de pila addicional.[2]
Algunes opcions del compilador C permetran efectivament l'optimització de la crida de cua ; per exemple, compilar el programa senzill anterior amb gcc amb -O1 donarà lloc a un error de segmentació, però no quan s'utilitza -O2 o -O3, ja que aquests nivells d'optimització impliquen l'opció del compilador -foptimize-sibling-calls.[3] Altres idiomes, com Scheme, requereixen que totes les implementacions incloguin la recurrència de la cua com a part de l'estàndard lingüístic.[4]
Recursivitat molt profunda
[modifica]Una funció recursiva que acaba en teoria però provoca un desbordament de memòria intermèdia de la pila de crides a la pràctica es pot solucionar transformant la recursivitat en un bucle i emmagatzemant els arguments de la funció en una pila explícita (en lloc de l'ús implícit de la pila de crides). Això sempre és possible perquè la classe de funcions recursives primitives és equivalent a la classe de funcions computables LOOP. Considereu aquest exemple en pseudocodi semblant a C++:
void function (argument)
{
if (condition)
function (argument.next);
}
|
stack.push(argument);
while (!stack.empty())
{
argument = stack.pop();
if (condition)
stack.push(argument.next);
}
|
Una funció recursiva primitiva com la del costat esquerre sempre es pot transformar en un bucle com al costat dret.
Una funció com l'exemple anterior a l'esquerra no seria un problema en un entorn que suporti l'optimització de la crida de cua; no obstant això, encara és possible crear una funció recursiva que pot provocar un desbordament de la pila en aquests idiomes. Considereu l'exemple següent de dues funcions simples d'exponenciació de nombres enters.
Variables de pila molt grans
[modifica]L'altra causa principal d'un desbordament de la pila resulta d'un intent d'assignar més memòria a la pila de la que s'adapta, per exemple, creant variables de matriu locals massa grans. Per aquest motiu, alguns autors recomanen que les matrius més grans d'uns pocs kilobytes s'assignin dinàmicament en comptes de ser una variable local.[5]
Referències
[modifica]- ↑ Burley, James Craig. «Using and Porting GNU Fortran» (en anglès), 01-06-1991. Arxivat de l'original el 2012-02-06.
- ↑ «An Introduction to Scheme and its Implementation» (en anglès), 19-02-1997. Arxivat de l'original el 2007-08-10.
- ↑ «Using the GNU Compiler Collection (GCC): Optimize Options» (en anglès). Arxivat de l'original el 2017-08-20. [Consulta: 20 agost 2017].
- ↑ Richard Kelsey; William Clinger; Jonathan Rees; Rozas, G.J.; Adams Iv, N.I.; 3 Higher-Order and Symbolic Computation, 11, 1, 8-1998, pàg. 7–105. DOI: 10.1023/A:1010051815785 [Consulta: 9 agost 2012].
- ↑ Feldman, Howard. «Modern Memory Management, Part 2» (en anglès), 23-11-2005. Arxivat de l'original el 2012-09-20. [Consulta: 14 agost 2007].