Loading AI tools
Em ciência da computação, uma pilha de chamada (ou pilha de execução) é uma pilha que armazena informações sobre as sub-rotinas ativas num programa de computador. Seu principal uso é registrar o ponto em que cada sub-rotina ativa deve retornar o controle de execução quando termina de executar.
Por exemplo, se uma sub-rotina DesenhaQuadrado chama (invoca) a sub-rotina DesenhaLinha em quatro pontos diferentes, o código de DesenhaLinha deve saber como retornar a DesenhaQuadrado. Isso geralmente é feito adicionando o endereço de retorno na pilha de chamada após a chamada da sub-rotina.
Sendo organizada como uma pilha, quem invoca a sub-rotina empilha o endereço de retorno. Quando termina sua execução, a sub-rotina invocada desempilha o endereço de retorno, desviando a execução para aquele endereço. Se durante sua execução a sub-rotina invocada também invocar outra sub-rotina, o endereço de retorno também será empilhado, e assim por diante. Quando esse processo de empilhamento consome todo o espaço alocado para a pilha de chamada, ocorre um erro chamado estouro de pilha.
Existe um pilha de chamada para cada thread sendo executada, ainda que mais pilhas possam ser criadas para o tratamento de sinais ou para multitarefa cooperativa.
Em linguagens de alto nível, detalhes da pilha de chamada são geralmente escondidos do programador. Eles têm acesso somente a lista de sub-rotinas empilhadas, e não à memória da pilha de chamada em si. Por outro lado, a maioria das linguagens de montagem requerem que programador manipule a pilha de chamada.
Uma das principais atribuições duma pilha de chamada é armazenar o endereço de retorno. Quando uma sub-rotina é chamada, a localização da instrução a ser retornada deve ser salva. Usar uma pilha para salvar o endereço de retorno possui importantes vantagens. Uma delas é que cada tarefa possui sua própria pilha, o que permite reentrância. Outro benefício é o suporte automático a recursividade.
Outra atribuição é o armazenamento de variáveis locais. Uma sub-rotina frequentemente precisa de memória para armazenar variáveis locais, aquelas que são usadas somente durante a execução da sub-rotina. Geralmente aloca-se espaço na própria pilha de chamada para tal, o que é muito rápido comparado a alocação dinâmica de memória. Também relacionado a variáveis locais está a passagem de parâmetros, mais uma atribuição. Uma sub-rotina frequentemente precisa ser alimentada por parâmetros quando é invocada, e é comum usar a pilha de chamada para tal. De forma geral, se há poucos e pequenos parâmetros, registradores do processador são usados para passar os parâmetros. Mas se há muitos parâmetros, ou se eles ocupam muito espaço, a pilha de chamada é usada.
Operandos de operações aritméticas ou lógicas são manipulados a partir de registradores, de onde são calculados. Mas para casos específicos deve-se usar uma profundidade específica de operandos, algo que somente registradores não conseguem armazenar. A pilha de operações aritméticas e lógicas pode estar localizada na pilha de chamada.
Algumas linguagens orientadas a objeto armazenam o ponteiro this junto aos parâmetros dos métodos sendo invocados. Esse ponteiro indica a instância associada ao método sendo invocado, sendo essencial para fornecer contexto a execução. Também relacionado a contexto, algumas linguagens de programação suportam sub-rotinas aninhadas, permitindo que a rotina aninhada acesse o contexto externo, da rotina que a aninhou (parâmetros, variáveis locais). Tais linguagens geralmente aceitam a chamada recursiva da sub-rotina aninhada, sendo que todas as chamadas recursivas apontam para o mesmo contexto externo.
Além do endereço de retorno, alguns ambientes podem suportar outros estados que são restaurados no retorno duma sub-rotina, como níveis de privilégio, informação para o tratamento de exceções, entre outros.
Uma pilha de chamada é composta por quadros (muitas vezes chamados de registros de ativação[1]), estruturas de dados que dependem da implementação e que contêm informações sobre o estado da sub-rotina. Cada quadro da pilha corresponde a uma chamada de sub-rotina que ainda não retornou. Por exemplo, se uma sub-rotina DesenhaLinha está em execução, e foi chamada por DesenhaQuadrado, o topo da pilha de chamada pode ser estruturada da seguinte forma:
| Ponteiro da pilha → | topo da pilha | |
| Variáveis locais de DesenhaLinha | Quadro de DesenhaLinha | |
| Ponteiro do quadro → | Endereço de retorno | |
| Parâmetros de DesenhaLinha | ||
| Variáveis locais de DesenhaQuadrado | Quadro de DesenhaQuadrado | |
| Endereço de retorno | ||
| Parâmetros de DesenhaQuadrado | ||
| . . . |
O quadro de pilha no topo da pilha se refere a sub-rotina em execução. Geralmente o quadro inclui espaço para as variáveis locais, o endereço de retorno para a sub-rotina que invocou a outra (quadro de pilha seguinte) e os parâmetros passados para a sub-rotina. A pilha é geralmente acessada através do registrador "ponteiro da pilha", que também serve para indicar o topo da pilha. Alternativamente, a memória do quadro pode ser acessada por outro registrador, o "ponteiro do quadro", que geralmente aponta para um ponto específico do quadro, como o endereço de retorno.
Cada quadro possui um tamanho específico, determinado pelo número e tamanho de parâmetros e variáveis locais, ainda que o tamanho seja fixo para diferentes chamadas duma mesma sub-rotina. Entretanto, algumas linguagens suportam alocação dinâmica de memória para variáveis locais na pilha de chamada, de forma que o tamanho do quadro duma sub-rotina não seja fixo, variando de acordo com a chamada. Com esse tipo de alocação dinâmica, o tamanho do quadro não pode ser obtido em tempo de compilação. Portanto, o acesso ao quadro é feito pelo ponteiro de quadro ao invés do ponteiro da pilha.
Em alguns sistemas o quadro de pilha possui um campo que contém o valor anterior do registrador "ponteiro de quadro", isto é, o valor desse registrador enquanto o quadro anterior estava em execução. Por exemplo, no diagrama anterior, o quadro de DesenhaLinha teria uma área de memória para o valor do ponteiro de quadro de DesenhaQuadrado. Isso permite que se acesse por código os quadros abaixo do atual. Linguagens de programação que suportam sub-rotinas aninhadas possuem um campo no quadro que aponta para o quadro da sub-rotina que começou o aninhamento. Isso permite que as sub-rotinas aninhadas acessem as variáveis locais e os parâmetros da sub-rotina que as invocou.
Quando a pilha de chamada usa mais memória do que suporta, ocorre um estouro de pilha. Em diversas linguagens de programação a pilha de chamada possui uma área limitada de memória, geralmente determinada no início do programa. O resultado do uso excessivo de memória é o estouro, o que geralmente resulta no aborto do programa.[2]
Uma das causas mais comuns desse bug é a recursividade infinita, em que o ponto de parada da recursividade não ocorre antes do enchimento da pilha. Outra causa é a tentativa de alocar mais memória na pilha do que ela suporta. Como variáveis locais e parâmetros são alocados na pilha de chamada, o uso excessivo de memória nesses casos pode levar ao estouro da pilha. Uma alternativa é alocar a memória dinamicamente.[3]
Como programas com suporte a threads geralmente possuem uma área de pilha menor que programas sem suporte, o bug geralmente se manifesta mais nesses ambientes multitarefa. Da mesma forma, no desenvolvimento de núcleo é desencorajado o uso de algoritmos recursivos ou de buffers muito grandes na pilha de chamada.[4][5]
Exemplos
Segue abaixo alguns exemplos em C:
- Recursividade infinita
void f(void);
void g(void);
int main(void) { f(); return 0; }
void f(void) { g(); }
void g(void) { f(); }
f() invoca g(), que invoca f() e assim por diante. Em dado momento a pilha de chamada estoura.
- Alocação excessiva de memória
int main(void) {
int n[10000000]; /* vetor muito grande */
int j = 0; /* endereço de j excede o limite da pilha, erro */
}
- GUEZZI, Carlo; JAZAYERI, Mehdi (1998). Programming Languages Concepts (em inglês) 3ª ed. New York: John Wiley & Sons. 52 páginas. ISBN 0-471-10426-4
- James Craig Burley (1 de junho de 1991). «Using and Porting GNU Fortran» (em inglês). Consultado em 9 de julho de 2008. Arquivado do original em 5 de outubro de 2012
- Howard Feldman (23 de novembro de 2005). «Modern Memory Management, Part 2» (em inglês)
- «Kernel Programming Guide: Performance and Stability Tips» (em inglês). Apple Inc. 7 de novembro de 2006
- Randy Dunlap (19 de maio de 2005). «Linux Kernel Development: Getting Started» (PDF) (em inglês). Consultado em 9 de julho de 2008. Arquivado do original (PDF) em 27 de fevereiro de 2012
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
