Explique o conceito de um quadro de pilha em poucas palavras

200

Parece que eu tenho a idéia de pilha de chamadas no design da linguagem de programação. Mas não consigo encontrar (provavelmente, apenas não procuro o suficiente) qualquer explicação decente sobre o que é o quadro da pilha .

Então, eu gostaria de pedir a alguém que me explicasse em poucas palavras.

ikostia
fonte

Respostas:

195

Um quadro de pilha é um quadro de dados que é empurrado para a pilha. No caso de uma pilha de chamadas, um quadro de pilha representaria uma chamada de função e seus dados de argumento.

Se bem me lembro, o endereço de retorno da função é empurrado primeiro para a pilha, depois os argumentos e o espaço para variáveis ​​locais. Juntos, eles formam o "quadro", embora isso seja provavelmente dependente da arquitetura. O processador sabe quantos bytes existem em cada quadro e move o ponteiro da pilha conforme os quadros são empurrados e removidos da pilha.

EDITAR:

Há uma grande diferença entre as pilhas de chamadas de nível superior e a pilha de chamadas do processador.

Quando falamos sobre a pilha de chamadas de um processador, estamos falando sobre trabalhar com endereços e valores no nível de byte / palavra no código de montagem ou de máquina. Existem "pilhas de chamadas" quando se fala em idiomas de nível superior, mas são uma ferramenta de depuração / tempo de execução gerenciada pelo ambiente de tempo de execução, para que você possa registrar o que deu errado com seu programa (em um nível alto). Nesse nível, coisas como números de linhas e nomes de métodos e classes são frequentemente conhecidos. No momento em que o processador obtém o código, ele não tem absolutamente nenhum conceito dessas coisas.

Tony R
fonte
6
"O processador sabe quantos bytes existem em cada quadro e move o ponteiro da pilha conforme os quadros são empurrados e removidos da pilha". - Duvido que o processador saiba alguma coisa sobre a pilha, porque nós a manipulamos via subbing (alocação), push e popping. E aqui estão as convenções de chamada que explicam como devemos usar a pilha.
Victor Polevoy
78

Se você entender muito bem a pilha, entenderá como a memória funciona no programa e se entenderá como a memória funciona no programa entenderá como o armazenamento de funções no programa e se entenderá como o armazenamento de funções no programa entenderá como funciona a função recursiva e se você entende como a função recursiva funciona, entenderá como o compilador funciona e, se entender como o compilador funciona, sua mente funcionará como compilador e você depurará qualquer programa com muita facilidade.

Deixe-me explicar como a pilha funciona:

Primeiro você precisa saber como as funções são representadas na pilha:

O heap armazena valores alocados dinamicamente.
A pilha armazena valores automáticos de alocação e exclusão.

insira a descrição da imagem aqui

Vamos entender com o exemplo:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(4)

Agora entenda partes deste programa:

insira a descrição da imagem aqui

Agora vamos ver o que é pilha e o que são partes da pilha:

insira a descrição da imagem aqui

Alocação da pilha:

Lembre-se de uma coisa: se qualquer condição de retorno de uma função for satisfeita, independentemente de ter carregado as variáveis ​​locais ou não, ela retornará imediatamente da pilha com seu quadro de pilha. Isso significa que sempre que qualquer função recursiva satisfizer a condição base e colocarmos um retorno após a condição base, a condição base não esperará para carregar variáveis ​​locais que estão localizadas na parte “else” do programa. Ele retornará imediatamente o quadro atual da pilha, após o qual o próximo quadro está agora no registro de ativação.

Veja isso na prática:

insira a descrição da imagem aqui

Desalocação do bloco:

Portanto, agora, sempre que uma função encontra uma instrução de retorno, ela exclui o quadro atual da pilha.

Ao retornar da pilha, os valores retornarão na ordem inversa da ordem original em que foram alocados na pilha.

insira a descrição da imagem aqui

Aaditya Ura
fonte
3
a pilha cresce para baixo e a pilha cresce para cima, você as inverte no seu diagrama. DIAGRAMA CORRETO AQUI
Rafael
@ Rafael desculpe pela confusão, eu estava falando sobre a direção do crescimento, eu não estava falando sobre a direção do crescimento da pilha. Há diferença entre a direção do crescimento e a direção do crescimento da pilha. Veja aqui stackoverflow.com/questions/1677415/…
Aaditya Ura 7/16
2
Rafael está certo. Também a primeira imagem está errada. Substitua-o por outra coisa (pesquise no google pictures por "heap stack").
Nikos
Então, se eu entendi corretamente, no seu terceiro diagrama, existem 3 quadros de pilha porque hello() chamou recursivamente o hello()que chamou (novamente) recursivamente hello()e o quadro global é a função original que chamou o primeiro hello()?
Andy J
1
Onde os links nos levam? Como uma séria preocupação de segurança, esses links devem ser removidos o mais rápido possível.
Shivanshu
45

Um rápido encerramento. Talvez alguém tenha uma explicação melhor.

Uma pilha de chamadas é composta por 1 ou muitos quadros de pilha. Cada quadro de pilha corresponde a uma chamada para uma função ou procedimento que ainda não foi finalizado com um retorno.

Para usar um quadro de pilha, um thread mantém dois ponteiros, um é chamado Stack Pointer (SP) e o outro é chamado Frame Pointer (FP). O SP sempre aponta para o "topo" da pilha e o FP sempre aponta para o "topo" do quadro. Além disso, o thread também mantém um contador de programa (PC) que aponta para a próxima instrução a ser executada.

Os seguintes itens são armazenados na pilha: variáveis ​​locais e temporários, parâmetros reais da instrução atual (procedimento, função, etc.)

Existem diferentes convenções de chamada em relação à limpeza da pilha.

ervinbosenbacher
fonte
7
Não esqueça que o endereço de retorno da sub-rotina fica na pilha.
Tony R
4
Quadro ponteiro é também apontador da base em termos x86
peterchaula
1
Gostaria de enfatizar que um ponteiro de quadro aponta para o início do quadro de pilha para a encarnação do procedimento atualmente ativo.
Servidor Khalilov
13

"Uma pilha de chamadas é composta por quadros de pilha ..." -  Wikipedia

Um quadro de pilha é algo que você coloca na pilha. São estruturas de dados que contêm informações sobre sub-rotinas a serem chamadas.

Waleed Khan
fonte
Desculpe, eu não tenho idéia de como eu perdi isso no wiki. Obrigado. Entendo corretamente que, em idiomas dinâmicos, o tamanho do quadro não é um valor constante, pois os locais da função não são exatamente conhecidos?
Ikostia
O tamanho e a natureza de um quadro dependem muito da arquitetura da máquina. De fato, o próprio paradigma de uma pilha de chamadas é específico da arquitetura. Tanto quanto sei, é sempre variável, porque diferentes chamadas de função terão diferentes quantidades de dados de argumento.
Tony R
Observe que o tamanho do quadro da pilha deve ser conhecido pelo processador quando está sendo manipulado. Quando isso está acontecendo, o tamanho dos dados já está determinado. Linguagens dinâmicas são compiladas para código de máquina, assim como linguagens estáticas, mas geralmente são feitas na hora certa para que o compilador possa manter o dinamismo e o processador possa trabalhar com tamanhos de quadro "conhecidos". Não confunda linguagens de nível superior com código de máquina / assembly, que é onde essas coisas estão realmente acontecendo.
Tony R
Bem, mas os idiomas dinâmicos também têm suas pilhas de chamadas, não têm? Quero dizer, se, digamos, o Python quiser executar algum procedimento, os dados sobre esse procedimento serão armazenados dentro da estrutura de algum interpretador do Python, estou correto? Portanto, quero dizer que a pilha de chamadas está presente não apenas em um nível baixo.
Ikostia
Depois de ler um pouco desse artigo da Wikipedia, fico corrigido (um pouco). O tamanho do quadro da pilha pode permanecer desconhecido no tempo de compilação . Porém, quando o processador estiver trabalhando com ponteiros de pilha + quadro, ele precisará saber quais são os tamanhos. O tamanho pode ser variável, mas o processador sabe o tamanho, é o que eu estava tentando dizer.
Tony R
5

Os programadores podem ter perguntas sobre os quadros de pilha não em um termo amplo (que é uma entidade única na pilha que serve apenas uma chamada de função e mantém o endereço de retorno, argumentos e variáveis ​​locais), mas em um sentido restrito - quando o termo stack frames é mencionado em contexto das opções do compilador.

Se o autor da pergunta quis dizer isso ou não, mas o conceito de um quadro de pilha do aspecto das opções do compilador é uma questão muito importante, não abordada pelas outras respostas aqui.

Por exemplo, o compilador C / C ++ do Microsoft Visual Studio 2015 tem a seguinte opção relacionada a stack frames:

  • / Oy (omissão de ponteiro de quadro)

O GCC tem o seguinte:

  • -fomit-frame-pointer (Não mantenha o ponteiro de quadro em um registro para funções que não precisam de um. Isso evita as instruções para salvar, configurar e restaurar ponteiros de quadro; também disponibiliza um registro extra em muitas funções )

O compilador Intel C ++ possui o seguinte:

  • -fomit-frame-pointer (Determina se o EBP é usado como um registro de uso geral em otimizações)

que tem o seguinte alias:

  • / Oi

O Delphi tem a seguinte opção de linha de comando:

  • - $ W + (Gerar quadros de pilha)

Nesse sentido específico, da perspectiva do compilador, um quadro de pilha é apenas o código de entrada e saída da rotina , que lança uma âncora na pilha - que também pode ser usada para depuração e manipulação de exceções. As ferramentas de depuração podem varrer os dados da pilha e usar essas âncoras para rastreamento, enquanto localizam call sitesna pilha, ou seja, para exibir os nomes das funções na ordem em que foram chamadas hierarquicamente. Para a arquitetura Intel, é push ebp; mov ebp, espou enterpara entrada e / mov esp, ebp; pop ebpou leavesaída.

É por isso que é muito importante entender para um programador qual é o quadro de uma pilha quando se trata de opções do compilador - porque o compilador pode controlar se deseja gerar esse código ou não.

Em alguns casos, o quadro da pilha (código de entrada e saída da rotina) pode ser omitido pelo compilador e as variáveis ​​serão acessadas diretamente pelo ponteiro da pilha (SP / ESP / RSP), em vez do conveniente ponteiro base (BP / ESP / RSP). Condições para omissão do quadro da pilha, por exemplo:

  • a função é uma função folha (isto é, uma entidade final que não chama outras funções);
  • não há tentativa / finalmente ou tentativa / exceto construções semelhantes, ou seja, nenhuma exceção é usada;
  • nenhuma rotina é chamada com parâmetros de saída na pilha;
  • a função não possui parâmetros;
  • a função não possui código de montagem embutido;
  • etc ...

A omissão de quadros de pilha (código de entrada e saída para a rotina) pode tornar o código menor e mais rápido, mas também pode afetar negativamente a capacidade dos depuradores de rastrear os dados na pilha e exibi-los ao programador. Essas são as opções do compilador que determinam sob quais condições uma função deve ter o código de entrada e saída, por exemplo: (a) sempre, (b) nunca, (c) quando necessário (especificando as condições).

Maxim Masiutin
fonte
-1

O quadro de pilha é a informação compactada relacionada a uma chamada de função. Essas informações geralmente incluem argumentos passados ​​para a função, variáveis ​​locais e para onde retornar após o término. Registro de ativação é outro nome para um quadro de pilha. O layout do quadro da pilha é determinado na ABI pelo fabricante e todos os compiladores que suportam o ISA devem estar em conformidade com esse padrão, no entanto, o esquema do layout pode depender do compilador. Geralmente, o tamanho do quadro da pilha não é limitado, mas existe um conceito chamado "zona vermelha / protegida" para permitir que as chamadas do sistema ... etc. sejam executadas sem interferir no quadro da pilha.

Sempre existe um SP, mas em algumas ABIs (ARM e PowerPC, por exemplo), o FP é opcional. Os argumentos que precisavam ser colocados na pilha podem ser compensados ​​usando apenas o SP. Se um quadro de pilha é gerado ou não para uma chamada de função depende do tipo e número de argumentos, variáveis ​​locais e como as variáveis ​​locais são acessadas em geral. Na maioria dos ISAs, primeiro, os registros são usados ​​e, se houver mais argumentos do que registros dedicados a passar argumentos, eles são colocados na pilha (por exemplo, x86 ABI possui 6 registros para transmitir argumentos inteiros). Portanto, algumas vezes, algumas funções não precisam ser colocadas na pilha, apenas o endereço de retorno é colocado na pilha.

bule de chá bêbado
fonte