Pilha de chamada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.

Atribuições[editar | editar código-fonte]

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.

Estrutura[editar | editar código-fonte]

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.

Estouro de pilha[editar | editar código-fonte]

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 na 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[editar | editar código-fonte]

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 */
}

Referências

  1. GUEZZI, Carlo; JAZAYERI, Mehdi (1998). Programming Languages Concepts (em inglês) 3ª ed. (New York: John Wiley & Sons). p. 52. ISBN 0-471-10426-4. 
  2. James Craig Burley (1 de junho de 1991). «Using and Porting GNU Fortran» (em inglês). 
  3. Howard Feldman (23 de novembro de 2005). «Modern Memory Management, Part 2» (em inglês). 
  4. «Kernel Programming Guide: Performance and Stability Tips» (em inglês). Apple Inc. 7 de novembro de 2006. 
  5. Randy Dunlap (19 de maio de 2005). «Linux Kernel Development: Getting Started» (PDF) (em inglês).