O que e onde estão a pilha e a pilha?

8105

Os livros de linguagens de programação explicam que os tipos de valor são criados na pilha e os tipos de referência são criados no heap , sem explicar o que são essas duas coisas. Eu não li uma explicação clara disso. Eu entendo o que é uma pilha . Mas,

  • Onde e o que eles estão (fisicamente na memória de um computador real)?
  • Até que ponto eles são controlados pelo SO ou pelo tempo de execução do idioma?
  • Qual é o seu escopo?
  • O que determina o tamanho de cada um deles?
  • O que torna um mais rápido?
mattshane
fonte
175
uma explicação realmente boa pode ser encontrada aqui Qual é a diferença entre uma pilha e uma pilha?
Songo
12
Também (realmente) é bom: codeproject.com/Articles/76153/… (a parte de pilha / pilha)
Ben
3
Relacionado, consulte Stack Clash . As correções do Stack Clash afetaram alguns aspectos das variáveis ​​e comportamentos do sistema rlimit_stack. Consulte também a Edição 1463241 da
jww
3
@mattshane As definições de pilha e pilha não dependem do tipo de valor e referência. Em outras palavras, a pilha e o heap podem ser totalmente definidos, mesmo que nunca existam tipos de valor e referência. Além disso, ao entender os tipos de valor e referência, a pilha é apenas um detalhe de implementação. Por Eric Lippert: A pilha é um detalhe da implementação, parte um .
Matthew

Respostas:

5966

A pilha é a memória reservada como espaço temporário para um encadeamento de execução. Quando uma função é chamada, um bloco é reservado no topo da pilha para variáveis ​​locais e alguns dados da contabilidade. Quando essa função retorna, o bloco fica sem uso e pode ser usado na próxima vez que uma função for chamada. A pilha é sempre reservada em uma ordem LIFO (último a entrar, primeiro a sair); o bloco reservado mais recentemente é sempre o próximo bloco a ser liberado. Isso torna muito simples acompanhar a pilha; libertar um bloco da pilha nada mais é do que ajustar um ponteiro.

O heap é a memória reservada para alocação dinâmica. Ao contrário da pilha, não há padrão imposto para a alocação e desalocação de blocos do heap; você pode alocar um bloco a qualquer momento e liberá-lo a qualquer momento. Isso torna muito mais complexo acompanhar quais partes do heap estão alocadas ou livres a qualquer momento; existem muitos alocadores de heap personalizados disponíveis para ajustar o desempenho do heap para diferentes padrões de uso.

Cada encadeamento obtém uma pilha, enquanto normalmente há apenas um heap para o aplicativo (embora não seja incomum ter vários heap para diferentes tipos de alocação).

Para responder suas perguntas diretamente:

Até que ponto eles são controlados pelo SO ou pelo tempo de execução do idioma?

O SO aloca a pilha para cada encadeamento no nível do sistema quando o encadeamento é criado. Normalmente, o sistema operacional é chamado pelo runtime do idioma para alocar o heap para o aplicativo.

Qual é o seu escopo?

A pilha é anexada a um encadeamento, portanto, quando o encadeamento sai, a pilha é recuperada. O heap geralmente é alocado na inicialização do aplicativo pelo tempo de execução e é recuperado quando o aplicativo (tecnicamente processo) sai.

O que determina o tamanho de cada um deles?

O tamanho da pilha é definido quando um segmento é criado. O tamanho do heap é definido na inicialização do aplicativo, mas pode aumentar conforme o espaço necessário (o alocador solicita mais memória do sistema operacional).

O que torna um mais rápido?

A pilha é mais rápida porque o padrão de acesso torna trivial alocar e desalocar memória (um ponteiro / número inteiro é simplesmente incrementado ou decrementado), enquanto o heap possui contabilidade muito mais complexa envolvida em uma alocação ou desalocação. Além disso, cada byte na pilha tende a ser reutilizado com muita frequência, o que significa que tende a ser mapeado para o cache do processador, tornando-o muito rápido. Outro problema de desempenho para o heap é que o heap, sendo principalmente um recurso global, geralmente precisa ser seguro com vários threads, ou seja, cada alocação e desalocação precisa ser - normalmente - sincronizada com "todos" outros acessos de heap no programa.

Uma demonstração clara:
Fonte da imagem: vikashazrati.wordpress.com

Jeff Hill
fonte
74
Boa resposta - mas acho que você deve adicionar que, enquanto a pilha é alocada pelo sistema operacional quando o processo é iniciado (supondo a existência de um sistema operacional), ela é mantida em linha pelo programa. Esse é outro motivo pelo qual a pilha é mais rápida: as operações push e pop são tipicamente uma instrução de máquina, e as máquinas modernas podem executar pelo menos três delas em um ciclo, enquanto alocar ou liberar heap envolve chamar o código do SO.
sqykly
276
Estou realmente confuso com o diagrama no final. Eu pensei que tinha conseguido até ver aquela imagem.
Sina Madani
10
@Anarelle, o processador executa instruções com ou sem um sistema operacional. Um exemplo próximo do meu coração é o SNES, que não tinha chamadas de API, nem sistema operacional como o conhecemos hoje - mas tinha uma pilha. Alocar em uma pilha é adição e subtração nesses sistemas e isso é bom para variáveis ​​destruídas quando elas são exibidas retornando da função que as criou, mas construa isso para, digamos, um construtor, cujo resultado não possa ser apenas jogar fora. Para isso, precisamos do heap, que não está vinculado à chamada e retorno. A maioria dos OS tem APIs uma pilha, não há razão para fazê-lo em seu próprio país
sqykly
2
"pilha é a memória reservada como espaço de trabalho". Legal. Mas onde é realmente "anulado" em termos de estrutura de memória Java? É a memória de memória Heap / Non-heap / Outros (estrutura de memória Java como por betsol.com/2017/06/... )
Jatin Shashoo
4
O @JatinShashoo Java runtime, como intérprete de bytecode, adiciona mais um nível de virtualização; portanto, o que você mencionou é apenas o ponto de vista do aplicativo Java. Do ponto de vista do sistema operacional, tudo isso é apenas um heap, em que o processo de tempo de execução Java aloca parte de seu espaço como memória "não heap" para o bytecode processado. O restante desse heap no nível do sistema operacional é usado como heap no nível do aplicativo, onde os dados do objeto são armazenados.
kbec 6/09/18
2350

Pilha:

  • Armazenado na RAM do computador, exatamente como a pilha.
  • As variáveis ​​criadas na pilha ficam fora do escopo e são desalocadas automaticamente.
  • Muito mais rápido para alocar em comparação com variáveis ​​no heap.
  • Implementado com uma estrutura de dados de pilha real.
  • Armazena dados locais, endereços de retorno, usados ​​para a passagem de parâmetros.
  • Pode haver um estouro de pilha quando muito da pilha é usada (principalmente de recursão infinita ou muito profunda, alocações muito grandes).
  • Os dados criados na pilha podem ser usados ​​sem ponteiros.
  • Você usaria a pilha se souber exatamente quantos dados precisa alocar antes do tempo de compilação e eles não são muito grandes.
  • Geralmente, o tamanho máximo já é determinado quando o programa é iniciado.

Montão:

  • Armazenado na RAM do computador, exatamente como na pilha.
  • No C ++, as variáveis ​​no heap devem ser destruídas manualmente e nunca ficam fora do escopo. Os dados são libertados com delete, delete[]ou free.
  • Mais lento para alocar em comparação com variáveis ​​na pilha.
  • Usado sob demanda para alocar um bloco de dados para uso do programa.
  • Pode ter fragmentação quando houver muitas alocações e desalocações.
  • Em C ++ ou C, os dados criados no heap serão apontados por ponteiros e alocados com newou mallocrespectivamente.
  • Pode ter falhas de alocação se for solicitado que um buffer muito grande seja alocado.
  • Você usaria o heap se não souber exatamente quantos dados precisará no tempo de execução ou se precisar alocar muitos dados.
  • Responsável por vazamentos de memória.

Exemplo:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;
Brian R. Bondy
fonte
31
O ponteiro pBuffer e o valor de b estão localizados na pilha e provavelmente são alocados na entrada da função. Dependendo do compilador, o buffer também pode ser alocado na entrada da função.
Andy
36
É um equívoco comum que o Cidioma, conforme definido pelo C99padrão de idioma (disponível em open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf ), exija uma "pilha". De fato, a palavra 'pilha' nem aparece no padrão. Isso responde às afirmações de que Co uso da pilha wrt / to é verdadeiro em geral, mas não é de forma alguma exigido pelo idioma. Veja knosof.co.uk/cbook/cbook.html para mais informações e, em particular, como Cé implementado em arquiteturas odd-ball como en.wikipedia.org/wiki/Burroughs_large_systems
Johne
55
@ Brian Você deve explicar por que o buffer [] e o ponteiro pBuffer são criados na pilha e por que os dados do pBuffer são criados no heap. Eu acho que algumas pessoas podem ficar confusas com a sua resposta, pois elas podem pensar que o programa está instruindo especificamente que a memória seja alocada na pilha versus pilha, mas esse não é o caso. É porque Buffer é um tipo de valor enquanto pBuffer é um tipo de referência?
Howiecamp
9
@Remover: Nenhum ponteiro possui um endereço e pode apontar para algo na pilha ou pilha igualmente. new, malloc e algumas outras funções semelhantes ao malloc alocadas no heap e retornam o endereço da memória que foi alocada. Por que você deseja alocar na pilha? Para que sua memória não fique fora do escopo e seja liberada até que você queira.
Brian R. Bondy
35
"Responsável por vazamentos de memória" - Os montões não são responsáveis ​​por vazamentos de memória! Preguiçoso / esquecido / ex-java codificadores / codificadores que não dão a mínima são!
Laz
1370

O ponto mais importante é que heap e stack são termos genéricos de maneiras pelas quais a memória pode ser alocada. Eles podem ser implementados de várias maneiras diferentes, e os termos se aplicam aos conceitos básicos.

  • Em uma pilha de itens, os itens ficam um em cima do outro na ordem em que foram colocados lá, e você só pode remover o superior (sem derrubar a coisa toda).

    Empilhar como uma pilha de papéis

    A simplicidade de uma pilha é que você não precisa manter uma tabela contendo um registro de cada seção da memória alocada; as únicas informações de estado necessárias são um único ponteiro para o final da pilha. Para alocar e desalocar, você apenas incrementa e diminui esse ponteiro único. Nota: às vezes, uma pilha pode ser implementada para iniciar no topo de uma seção da memória e se estender para baixo em vez de crescer para cima.

  • Em uma pilha, não há uma ordem específica para a maneira como os itens são colocados. Você pode acessar e remover itens em qualquer ordem, porque não há um item 'superior' claro.

    Montão como um monte de alcaçuz allsorts

    A alocação de heap requer a manutenção de um registro completo de qual memória está alocada e o que não é, além de alguma manutenção adicional para reduzir a fragmentação, encontrar segmentos de memória contíguos grandes o suficiente para caber no tamanho solicitado e assim por diante. A memória pode ser desalocada a qualquer momento, deixando espaço livre. Às vezes, um alocador de memória executa tarefas de manutenção, como desfragmentar a memória movendo a memória alocada ou coletando lixo - identificando em tempo de execução quando a memória não está mais no escopo e desalocando-a.

Essas imagens devem fazer um bom trabalho ao descrever as duas maneiras de alocar e liberar memória em uma pilha e uma pilha. Yum!

  • Até que ponto eles são controlados pelo SO ou pelo tempo de execução do idioma?

    Como mencionado, heap e stack são termos gerais e podem ser implementados de várias maneiras. Os programas de computador normalmente têm uma pilha chamado de pilha de chamadas que armazena informações relevantes para a função atual, como um ponteiro para qualquer função que foi chamado, e quaisquer variáveis locais. Como as funções chamam outras funções e depois retornam, a pilha cresce e diminui para reter informações das funções mais abaixo na pilha de chamadas. Um programa realmente não tem controle de tempo de execução; é determinado pela linguagem de programação, sistema operacional e até pela arquitetura do sistema.

    Heap é um termo geral usado para qualquer memória que é alocada dinâmica e aleatoriamente; ou seja, fora de ordem. A memória é normalmente alocada pelo sistema operacional, com o aplicativo chamando funções da API para fazer essa alocação. Há um pouco de sobrecarga necessária no gerenciamento de memória alocada dinamicamente, que geralmente é tratada pelo código de tempo de execução da linguagem ou ambiente de programação usado.

  • Qual é o seu escopo?

    A pilha de chamadas é um conceito de nível tão baixo que não se relaciona com 'escopo' no sentido de programação. Se você desmontar algum código, verá referências relativas ao estilo do ponteiro às partes da pilha, mas no que diz respeito a uma linguagem de nível superior, a linguagem impõe suas próprias regras de escopo. Um aspecto importante de uma pilha, no entanto, é que, quando uma função retorna, qualquer coisa local para essa função é imediatamente liberada da pilha. Isso funciona da maneira que você esperaria, dado o funcionamento de suas linguagens de programação. Em um monte, também é difícil de definir. O escopo é o que for exposto pelo sistema operacional, mas sua linguagem de programação provavelmente adiciona suas regras sobre o que é um "escopo" em seu aplicativo. A arquitetura do processador e o sistema operacional usam endereçamento virtual, que o processador converte em endereços físicos e há falhas de página, etc. Eles controlam quais páginas pertencem a quais aplicativos. Porém, você nunca precisa se preocupar com isso, porque apenas usa o método que sua linguagem de programação usa para alocar e liberar memória e verifica se há erros (se a alocação / liberação falhar por qualquer motivo).

  • O que determina o tamanho de cada um deles?

    Novamente, depende do idioma, compilador, sistema operacional e arquitetura. Uma pilha geralmente é pré-alocada, porque, por definição, deve ser memória contígua. O compilador de idiomas ou o sistema operacional determinam seu tamanho. Você não armazena grandes quantidades de dados na pilha, por isso será grande o suficiente para nunca ser totalmente utilizado, exceto em casos de recursão indesejada e interminável (portanto, "estouro de pilha") ou outras decisões de programação incomuns.

    Um heap é um termo geral para qualquer coisa que possa ser alocada dinamicamente. Dependendo de como você olha para ele, ele muda constantemente de tamanho. De qualquer maneira, nos processadores e sistemas operacionais modernos, a maneira exata como ela funciona é muito abstrata, então você normalmente não precisa se preocupar muito com a forma como ela funciona no fundo, exceto que (nos idiomas em que isso permite), você não deve usar memória que você ainda não alocou ou a memória liberada.

  • O que torna um mais rápido?

    A pilha é mais rápida porque toda a memória livre é sempre contínua. Nenhuma lista precisa ser mantida de todos os segmentos da memória livre, apenas um ponteiro para o topo atual da pilha. Os compiladores geralmente armazenam esse ponteiro em um registro especial e rápido para esse fim. Além disso, as operações subsequentes em uma pilha geralmente são concentradas em áreas muito próximas da memória, o que em um nível muito baixo é bom para otimização pelos caches no processador.

thomasrutter
fonte
20
David Não concordo que seja uma boa imagem ou que "pilha de empilhamento" seja um bom termo para ilustrar o conceito. Quando você adiciona algo a uma pilha, os outros conteúdos da pilha não são pressionados para baixo, eles permanecem onde estão.
thomasrutter
8
Esta resposta inclui um grande erro. Variáveis ​​estáticas não são alocadas na pilha. Veja minha resposta [link] stackoverflow.com/a/13326916/1763801 para obter esclarecimentos. você está equiparando variáveis ​​"automáticas" a variáveis ​​"estáticas", mas elas não são iguais
davec
13
Especificamente, você diz que "variáveis ​​locais alocadas estaticamente" são alocadas na pilha. Na verdade, eles são alocados no segmento de dados. Somente variáveis ​​alocadas automaticamente (que incluem a maioria, mas não todas as variáveis ​​locais, e também itens como parâmetros de função passados ​​por valor e não por referência) são alocados na pilha.
Davec 11/11
9
Acabei de perceber que você está certo - em C, a alocação estática é uma coisa separada e não um termo para qualquer coisa que não seja dinâmica . Eu editei minha resposta, obrigado.
thomasrutter
5
Não é apenas C. Java, Pascal, Python e muitos outros têm as noções de alocação estática versus automática versus dinâmica. Dizer "alocação estática" significa a mesma coisa em qualquer lugar. Em nenhum idioma alocação estática significa "não dinâmico". Você quer o termo alocação "automática" para o que está descrevendo (isto é, as coisas na pilha).
davec 12/11/12
727

(Eu mudei esta resposta de outra pergunta que era mais ou menos burra dessa.)

A resposta para sua pergunta é específica da implementação e pode variar entre os compiladores e as arquiteturas de processador. No entanto, aqui está uma explicação simplificada.

  • A pilha e o heap são áreas de memória alocadas do sistema operacional subjacente (geralmente a memória virtual que é mapeada para a memória física sob demanda).
  • Em um ambiente multithread, cada thread terá sua própria pilha completamente independente, mas eles compartilharão o heap. O acesso simultâneo deve ser controlado no heap e não é possível na pilha.

A pilha

  • O heap contém uma lista vinculada de blocos usados ​​e livres. Novas alocações no heap (por newou malloc) são atendidas criando um bloco adequado a partir de um dos blocos livres. Isso requer a atualização da lista de blocos na pilha. Essa meta-informação sobre os blocos na pilha também é armazenada na pilha frequentemente em uma pequena área logo à frente de cada bloco.
  • À medida que a pilha cresce, novos blocos são frequentemente alocados de endereços mais baixos para endereços mais altos. Assim, você pode pensar na pilha como uma pilha de blocos de memória que aumentam de tamanho à medida que a memória é alocada. Se o heap for muito pequeno para uma alocação, o tamanho poderá ser aumentado com a aquisição de mais memória do sistema operacional subjacente.
  • Alocar e desalocar muitos blocos pequenos pode deixar o heap em um estado em que existem muitos pequenos blocos livres intercalados entre os blocos usados. Uma solicitação para alocar um bloco grande pode falhar porque nenhum dos blocos livres é grande o suficiente para satisfazer a solicitação de alocação, mesmo que o tamanho combinado dos blocos livres possa ser grande o suficiente. Isso é chamado de fragmentação de heap .
  • Quando um bloco usado adjacente a um bloco livre é desalocado, o novo bloco livre pode ser mesclado ao bloco livre adjacente para criar um bloco livre maior, reduzindo efetivamente a fragmentação do heap.

A pilha

A pilha

  • A pilha geralmente trabalha em conjunto com um registro especial na CPU chamado ponteiro da pilha . Inicialmente, o ponteiro da pilha aponta para o topo da pilha (o endereço mais alto da pilha).
  • A CPU possui instruções especiais para inserir valores na pilha e retirá- los da pilha. Cada push armazena o valor no local atual do ponteiro da pilha e diminui o ponteiro da pilha. Um pop recupera o valor apontado pelo ponteiro da pilha e depois aumenta o ponteiro da pilha (não se confunda com o fato de que adicionar um valor à pilha diminui o ponteiro da pilha e remover um valor o aumenta . Lembre-se de que a pilha cresce para o fundo). Os valores armazenados e recuperados são os valores dos registros da CPU.
  • Quando uma função é chamada, a CPU utiliza instruções especiais que pressionam o ponteiro de instrução atual , ou seja, o endereço do código em execução na pilha. A CPU então salta para a função configurando o ponteiro de instrução no endereço da função chamada. Posteriormente, quando a função retornar, o ponteiro de instruções antigo será exibido na pilha e a execução continuará no código logo após a chamada para a função.
  • Quando uma função é inserida, o ponteiro da pilha é diminuído para alocar mais espaço na pilha para variáveis ​​locais (automáticas). Se a função tiver uma variável local de 32 bits, quatro bytes serão reservados na pilha. Quando a função retorna, o ponteiro da pilha é movido de volta para liberar a área alocada.
  • Se uma função tiver parâmetros, eles serão enviados para a pilha antes da chamada para a função. O código na função é capaz de navegar pela pilha a partir do ponteiro atual da pilha para localizar esses valores.
  • As chamadas de função de aninhamento funcionam como um encanto. Cada nova chamada alocará parâmetros de função, o endereço de retorno e o espaço para variáveis ​​locais e esses registros de ativação podem ser empilhados para chamadas aninhadas e serão desenrolados da maneira correta quando as funções retornarem.
  • Como a pilha é um bloco limitado de memória, você pode causar um estouro de pilha chamando muitas funções aninhadas e / ou alocando muito espaço para variáveis ​​locais. Freqüentemente, a área de memória usada para a pilha é configurada de forma que a escrita abaixo da parte inferior (o endereço mais baixo) da pilha desencadeie uma interceptação ou exceção na CPU. Essa condição excepcional pode ser capturada pelo tempo de execução e convertida em algum tipo de exceção de estouro de pilha.

A pilha

Uma função pode ser alocada no heap em vez de uma pilha?

Não, os registros de ativação das funções (variáveis ​​locais ou automáticas) são alocados na pilha usada não apenas para armazenar essas variáveis, mas também para controlar as chamadas de funções aninhadas.

Como o heap é gerenciado depende realmente do ambiente de tempo de execução. C usa malloce C ++ new, mas muitas outras linguagens têm coleta de lixo.

No entanto, a pilha é um recurso de nível mais baixo intimamente ligado à arquitetura do processador. Aumentar o heap quando não há espaço suficiente não é muito difícil, pois pode ser implementado na chamada da biblioteca que lida com o heap. No entanto, aumentar a pilha geralmente é impossível, pois o excesso de pilha só é descoberto quando é tarde demais; e desligar o encadeamento de execução é a única opção viável.

Martin Liversage
fonte
35
@ Martin - Uma resposta / explicação muito boa do que a resposta aceita mais abstrata. Um programa de montagem de amostra mostrando indicadores / registros de pilha sendo usados ​​em relação a chamadas de função seria mais ilustrativo.
Bikal Lem
3
Todo tipo de referência é composição de tipos de valor (int, string etc.). Como é dito, esses tipos de valores são armazenados na pilha do que como eles funcionam quando fazem parte do tipo de referência.
Nps
15
Essa resposta foi a melhor na minha opinião, porque me ajudou a entender o que realmente é uma declaração de retorno e como ela se relaciona com esse "endereço de retorno" que eu me deparo de vez em quando, o que significa colocar uma função na pilha, e por que as funções são colocadas nas pilhas. Ótima resposta!
19414 Alex
3
Este é o melhor na minha opinião, ou seja, para mencionar que o heap / stack é muito específico da implementação. As outras respostas assumem muitas coisas sobre o idioma e o ambiente / sistema operacional. +1
Qix - MONICA FOI ERRADA EM
2
O que você quer dizer com "O código na função é capaz de navegar pela pilha a partir do ponteiro atual da pilha para localizar esses valores." ? Você pode elaborar isso por favor?
Koray Tugay
404

No seguinte código C #

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Veja como a memória é gerenciada

Imagem de variáveis ​​na pilha

Local Variablesisso só precisa durar enquanto a chamada da função for colocada na pilha. O heap é usado para variáveis ​​cuja vida útil não conhecemos realmente, mas esperamos que elas durem um tempo. Na maioria dos idiomas, é fundamental sabermos, em tempo de compilação, qual o tamanho de uma variável, se queremos armazená-la na pilha.

Os objetos (que variam em tamanho à medida que os atualizamos) ficam acumulados porque não sabemos no momento da criação quanto tempo eles durarão. Em muitos idiomas, o heap é coletado como lixo para localizar objetos (como o objeto cls1) que não possuem mais referências.

Em Java, a maioria dos objetos entra diretamente no heap. Em linguagens como C / C ++, estruturas e classes geralmente podem permanecer na pilha quando você não está lidando com ponteiros.

Mais informações podem ser encontradas aqui:

A diferença entre alocação de pilha e memória heap «timmurphy.org

e aqui:

Criando objetos na pilha e na pilha

Este artigo é a fonte da imagem acima: Seis conceitos importantes do .NET: Stack, heap, tipos de valor, tipos de referência, boxe e unboxing - CodeProject

mas esteja ciente de que pode conter algumas imprecisões.

Snowcrash
fonte
15
Isto está incorreto. ie cls não são variáveis ​​"estáticas". eles são chamados de variáveis ​​"locais" ou "automáticas". É uma distinção muito importante. Consulte [link] stackoverflow.com/a/13326916/1763801 para obter esclarecimentos
davec
9
Eu não disse que eram variáveis estáticas . Eu disse que int e cls1 são itens estáticos . Sua memória é alocada estaticamente e, portanto, eles ficam na pilha. Isso contrasta com um objeto que requer alocação dinâmica de memória que, portanto, continua na pilha.
Snowcrash
12
Cito "Itens estáticos ... vá para a pilha". Isso é totalmente errado. Itens estáticos vão no segmento de dados, itens automáticos vão para a pilha.
davec 21/11/12
14
Além disso, quem escreveu esse artigo sobre o projeto de código não sabe do que está falando. Por exemplo, ele diz que "os primitivos precisam de memória de tipo estático", o que é completamente falso. Nada impede que você aloque primitivas na pilha dinamicamente, basta escrever algo como "int array [] = new int [num]" e pronto, primitivas alocadas dinamicamente no .NET. Essa é apenas uma das várias imprecisões.
davec 21/11/2012
8
Editei sua postagem porque você cometeu graves erros técnicos sobre o que há na pilha e na pilha.
Tom Leys
209

A pilha Quando você chama uma função, os argumentos para essa função mais alguma outra sobrecarga são colocados na pilha. Algumas informações (como para onde ir no retorno) também são armazenadas lá. Quando você declara uma variável dentro de sua função, essa variável também é alocada na pilha.

Desalocar a pilha é bem simples, porque você sempre desaloca na ordem inversa em que aloca. O material da pilha é adicionado quando você insere funções, os dados correspondentes são removidos quando você os sai. Isso significa que você tende a permanecer em uma pequena região da pilha, a menos que chame muitas funções que chamam muitas outras funções (ou crie uma solução recursiva).

A pilha A pilha é um nome genérico para onde você coloca os dados que você cria em tempo real. Se você não souber quantas naves espaciais seu programa criará, provavelmente usará o novo operador (ou malloc ou equivalente) para criar cada nave espacial. Essa alocação permanecerá por um tempo, portanto é provável que liberemos as coisas em uma ordem diferente da que as criamos.

Assim, o heap é muito mais complexo, porque acaba havendo regiões de memória que não são utilizadas, intercaladas com pedaços que são - a memória fica fragmentada. Encontrar memória livre do tamanho necessário é um problema difícil. É por isso que o heap deve ser evitado (embora ainda seja usado com frequência).

Implementação A implementação da pilha e da pilha geralmente depende do tempo de execução / SO. Muitas vezes, jogos e outros aplicativos críticos para o desempenho criam suas próprias soluções de memória que capturam uma grande parte da memória da pilha e a distribuem internamente para evitar a dependência de memória do sistema operacional.

Isso só é prático se o uso da memória for bastante diferente da norma - ou seja, para jogos nos quais você carrega um nível em uma grande operação e pode jogar tudo em outra grande operação.

Localização física na memória Isso é menos relevante do que você pensa devido a uma tecnologia chamada Memória virtual que faz com que seu programa pense que você tem acesso a um determinado endereço onde os dados físicos estão em outro lugar (mesmo no disco rígido!). Os endereços que você obtém para a pilha estão em ordem crescente à medida que sua árvore de chamadas fica mais profunda. Os endereços da pilha são imprevisíveis (ou seja, específicos da implementação) e francamente não são importantes.

Tom Leys
fonte
16
Uma recomendação para evitar o uso da pilha é bastante forte. Os sistemas modernos têm bons gerenciadores de heap, e as linguagens dinâmicas modernas usam o heap extensivamente (sem que o programador realmente se preocupe com isso). Eu diria que use a pilha, mas com um alocador manual, não se esqueça de liberar!
Greg Hewgill 17/09/08
2
Se você pode usar a pilha ou a pilha, use a pilha. Se você não pode usar a pilha, realmente não há escolha. Eu uso muito, e é claro, usando std :: vector ou similar atinge a pilha. Para um iniciante, você evita a pilha porque a pilha é simplesmente tão fácil!
Tom Leys
Se o seu idioma não implementar a coleta de lixo, os ponteiros inteligentes (objetos alocados separadamente que envolvem um ponteiro que fazem referência à contagem de blocos de memória alocados dinamicamente) estão intimamente relacionados à coleta de lixo e são uma maneira decente de gerenciar o heap de uma maneira segura. e maneira livre de vazamento. Eles são implementados em várias estruturas, mas também não são tão difíceis de implementar para seus próprios programas.
21916 BenPen
1
"É por isso que a pilha deve ser evitada (embora ainda seja usada com frequência)." Não tenho certeza do que isso praticamente significa, especialmente porque a memória é gerenciada de maneira diferente em muitos idiomas de alto nível. Como esta pergunta é marcada como independente de idioma, eu diria que esse comentário / linha específico está mal colocado e não é aplicável.
LintfordPickle
2
Bom ponto @JonnoHampson - Enquanto você faz uma observação válida, eu diria que, se você está trabalhando em uma "linguagem de alto nível" com um GC, provavelmente não liga para os mecanismos de alocação de memória - e, portanto, não até se importa com o que a pilha e a pilha são.
22618 Tom Leys
194

Para esclarecer, esta resposta tem informações incorretas ( thomas corrigiu sua resposta após comentários, legal :)). Outras respostas evitam explicar o que significa alocação estática. Então, explicarei as três principais formas de alocação e como elas geralmente se relacionam com o heap, a pilha e o segmento de dados abaixo. Também mostrarei alguns exemplos em C / C ++ e Python para ajudar as pessoas a entender.

Variáveis ​​"estáticas" (AKA alocadas estaticamente) não são alocadas na pilha. Não assuma isso - muitas pessoas fazem isso apenas porque "estático" soa muito como "pilha". Na verdade, eles não existem nem na pilha nem na pilha. Eles fazem parte do chamado segmento de dados .

No entanto, geralmente é melhor considerar " escopo " e " tempo de vida " em vez de "empilhar" e "heap".

Escopo refere-se a quais partes do código podem acessar uma variável. Geralmente pensamos no escopo local (somente pode ser acessado pela função atual) versus no escopo global (pode ser acessado em qualquer lugar), embora o escopo possa se tornar muito mais complexo.

Vida útil refere-se a quando uma variável é alocada e desalocada durante a execução do programa. Geralmente pensamos em alocação estática (a variável persistirá durante toda a duração do programa, tornando-a útil para armazenar as mesmas informações em várias chamadas de função) versus alocação automática (a variável persiste apenas durante uma única chamada para uma função, tornando-a útil para armazenar informações que são usadas apenas durante a sua função e que podem ser descartadas quando você terminar) versus alocação dinâmica (variáveis ​​cuja duração é definida no tempo de execução, em vez do tempo de compilação como estático ou automático).

Embora a maioria dos compiladores e intérpretes implementem esse comportamento da mesma forma em termos de uso de pilhas, pilhas, etc., um compilador às vezes pode quebrar essas convenções se desejar, desde que o comportamento esteja correto. Por exemplo, devido à otimização, uma variável local pode existir apenas em um registro ou ser removida totalmente, mesmo que a maioria das variáveis ​​locais exista na pilha. Como foi apontado em alguns comentários, você é livre para implementar um compilador que nem usa pilha ou heap, mas alguns outros mecanismos de armazenamento (raramente são feitos, pois pilhas e pilhas são ótimas para isso).

Fornecerei um código C anotado simples para ilustrar tudo isso. A melhor maneira de aprender é executar um programa em um depurador e observar o comportamento. Se você preferir ler python, pule para o final da resposta :)

// Statically allocated in the data segment when the program/DLL is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in the code
int someGlobalVariable;

// Statically allocated in the data segment when the program is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in this particular code file
static int someStaticVariable;

// "someArgument" is allocated on the stack each time MyFunction is called
// "someArgument" is deallocated when MyFunction returns
// scope - can be accessed only within MyFunction()
void MyFunction(int someArgument) {

    // Statically allocated in the data segment when the program is first loaded
    // Deallocated when the program/DLL exits
    // scope - can be accessed only within MyFunction()
    static int someLocalStaticVariable;

    // Allocated on the stack each time MyFunction is called
    // Deallocated when MyFunction returns
    // scope - can be accessed only within MyFunction()
    int someLocalVariable;

    // A *pointer* is allocated on the stack each time MyFunction is called
    // This pointer is deallocated when MyFunction returns
    // scope - the pointer can be accessed only within MyFunction()
    int* someDynamicVariable;

    // This line causes space for an integer to be allocated in the heap
    // when this line is executed. Note this is not at the beginning of
    // the call to MyFunction(), like the automatic variables
    // scope - only code within MyFunction() can access this space
    // *through this particular variable*.
    // However, if you pass the address somewhere else, that code
    // can access it too
    someDynamicVariable = new int;


    // This line deallocates the space for the integer in the heap.
    // If we did not write it, the memory would be "leaked".
    // Note a fundamental difference between the stack and heap
    // the heap must be managed. The stack is managed for us.
    delete someDynamicVariable;

    // In other cases, instead of deallocating this heap space you
    // might store the address somewhere more permanent to use later.
    // Some languages even take care of deallocation for you... but
    // always it needs to be taken care of at runtime by some mechanism.

    // When the function returns, someArgument, someLocalVariable
    // and the pointer someDynamicVariable are deallocated.
    // The space pointed to by someDynamicVariable was already
    // deallocated prior to returning.
    return;
}

// Note that someGlobalVariable, someStaticVariable and
// someLocalStaticVariable continue to exist, and are not
// deallocated until the program exits.

Um exemplo particularmente pungente de por que é importante distinguir entre vida útil e escopo é que uma variável pode ter escopo local, mas estático - por exemplo, "someLocalStaticVariable" no exemplo de código acima. Tais variáveis ​​podem tornar nossos hábitos de nomenclatura comuns, mas informais, muito confusos. Por exemplo, quando dizemos " local ", geralmente queremos dizer " variável alocada automaticamente com escopo local " e quando dizemos global, geralmente queremos dizer " variável alocada estaticamente com escopo global ". Infelizmente, quando se trata de " variáveis ​​alocadas estaticamente no escopo do arquivo ", muitas pessoas dizem ... " hein ??? ".

Algumas opções de sintaxe no C / C ++ exacerbam esse problema - por exemplo, muitas pessoas pensam que as variáveis ​​globais não são "estáticas" devido à sintaxe mostrada abaixo.

int var1; // Has global scope and static allocation
static int var2; // Has file scope and static allocation

int main() {return 0;}

Observe que colocar a palavra-chave "estático" na declaração acima impede que var2 tenha escopo global. No entanto, o var1 global tem alocação estática. Isso não é intuitivo! Por esse motivo, tento nunca usar a palavra "estática" ao descrever o escopo e, em vez disso, digo algo como o escopo "arquivo" ou "arquivo limitado". No entanto, muitas pessoas usam a frase "estático" ou "escopo estático" para descrever uma variável que só pode ser acessada a partir de um arquivo de código. No contexto da vida útil, "estático" sempre significa que a variável é alocada no início do programa e desalocada quando o programa é encerrado.

Algumas pessoas pensam nesses conceitos como específicos de C / C ++. Eles não são. Por exemplo, o exemplo do Python abaixo ilustra todos os três tipos de alocação (existem algumas diferenças sutis possíveis em linguagens interpretadas que não abordarei aqui).

from datetime import datetime

class Animal:
    _FavoriteFood = 'Undefined' # _FavoriteFood is statically allocated

    def PetAnimal(self):
        curTime = datetime.time(datetime.now()) # curTime is automatically allocatedion
        print("Thank you for petting me. But it's " + str(curTime) + ", you should feed me. My favorite food is " + self._FavoriteFood)

class Cat(Animal):
    _FavoriteFood = 'tuna' # Note since we override, Cat class has its own statically allocated _FavoriteFood variable, different from Animal's

class Dog(Animal):
    _FavoriteFood = 'steak' # Likewise, the Dog class gets its own static variable. Important to note - this one static variable is shared among all instances of Dog, hence it is not dynamic!


if __name__ == "__main__":
    whiskers = Cat() # Dynamically allocated
    fido = Dog() # Dynamically allocated
    rinTinTin = Dog() # Dynamically allocated

    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

    Dog._FavoriteFood = 'milkbones'
    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

# Output is:
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is milkbones
# Thank you for petting me. But it's 13:05:02.256000, you should feed me. My favorite food is milkbones
davec
fonte
Eu me referiria a uma variável estática declarada dentro de uma função como tendo apenas acessibilidade local , mas geralmente não usaria o termo "escopo" com ela. Além disso, pode ser interessante notar que o único aspecto de pilha / pilha com o qual as linguagens têm essencialmente flexibilidade zero: uma linguagem que salva o contexto de execução em uma pilha não pode usar a mesma pilha para armazenar coisas que precisam sobreviver aos contextos em que são criadas . Alguns idiomas PostScripttêm várias pilhas, mas possuem um "heap" que se comporta mais como uma pilha.
Supercat 9/13 /
@ supercat Isso tudo faz sentido. I definido escopo como "o que partes do código pode acessar uma variável" (e sinto que esta é a definição mais standard) então eu acho que nós concordamos :)
davec
Eu consideraria o "escopo" de uma variável delimitado pelo tempo e pelo espaço. Uma variável no escopo do objeto de classe é necessária para manter seu valor enquanto o objeto existir. Uma variável dentro de um escopo de contexto de execução é necessária para manter seu valor enquanto a execução permanecer nesse contexto. Uma declaração de variável estática cria um identificador cujo escopo é limitado ao bloco atual, que é anexado a uma variável cujo escopo é ilimitado.
Supercat
@ supercat É por isso que uso a palavra tempo de vida, que é como chamo o que você chama de escopo de tempo. Reduz a necessidade de sobrecarregar a palavra "escopo" com tantos significados. Até onde eu sei, parece não haver consenso total sobre definições exatas, mesmo entre fontes canônicas. Minha terminologia é extraída parcialmente da K&R e parcialmente do uso predominante no primeiro departamento de CS em que estudei / ensinei. É sempre bom ouvir outra visão informada.
Davidec 28/12
1
Você deve estar brincando. você pode realmente definir variável estática dentro de uma função?
Zaeem Sattar
168

Outros responderam muito bem aos traços largos, então vou dar alguns detalhes.

  1. Pilha e pilha não precisam ser singulares. Uma situação comum em que você tem mais de uma pilha é se você tiver mais de um encadeamento em um processo. Nesse caso, cada thread tem sua própria pilha. Você também pode ter mais de um heap, por exemplo, algumas configurações de DLL podem resultar em DLLs diferentes alocadas de heaps diferentes, e é por isso que geralmente é uma má idéia liberar memória alocada por uma biblioteca diferente.

  2. Em C, você pode obter o benefício da alocação de comprimento variável através do uso de alloca , que é alocado na pilha, em oposição à alocação, que é alocada no heap. Essa memória não sobreviverá à sua declaração de retorno, mas é útil para um buffer temporário.

  3. Criar um buffer temporário enorme no Windows que você não usa muito não é gratuito. Isso ocorre porque o compilador gera um loop de detecção de pilha que é chamado toda vez que sua função é inserida para garantir que a pilha exista (porque o Windows usa uma única página de proteção no final da pilha para detectar quando precisa aumentar a pilha. Se você acessar a memória em mais de uma página no final da pilha, irá travar). Exemplo:

void myfunction()
{
   char big[10000000];
   // Do something that only uses for first 1K of big 99% of the time.
}
Don Neufeld
fonte
Re "em oposição a alocar": você quer dizer "em oposição a malloc"?
Peter Mortensen
Quão portátil é alloca?
Peter Mortensen
@ PeterMortensen não é POSIX, portabilidade não garantida.
31717 Don Neufeld
135

Outros responderam diretamente à sua pergunta, mas, ao tentar entender a pilha e a pilha, acho útil considerar o layout da memória de um processo UNIX tradicional (sem threads e mmap()alocadores baseados em). A página da web Glossário de gerenciamento de memória possui um diagrama desse layout de memória.

A pilha e o heap estão tradicionalmente localizados em extremidades opostas do espaço de endereço virtual do processo. A pilha cresce automaticamente quando acessada, até um tamanho definido pelo kernel (que pode ser ajustado com setrlimit(RLIMIT_STACK, ...)). O heap cresce quando o alocador de memória chama a chamada brk()ou sbrk()system, mapeando mais páginas de memória física no espaço de endereço virtual do processo.

Em sistemas sem memória virtual, como alguns sistemas incorporados, o mesmo layout básico geralmente se aplica, exceto que a pilha e o heap são de tamanho fixo. No entanto, em outros sistemas incorporados (como os baseados nos microcontroladores Microchip PIC), a pilha de programas é um bloco de memória separado que não é endereçável por instruções de movimentação de dados e só pode ser modificado ou lido indiretamente através das instruções de fluxo de programa (chamada, retorno etc.). Outras arquiteturas, como os processadores Intel Itanium, têm várias pilhas . Nesse sentido, a pilha é um elemento da arquitetura da CPU.

bk1e
fonte
117

O que é uma pilha?

Uma pilha é uma pilha de objetos, normalmente um que está organizado de maneira ordenada.

Digite a descrição da imagem aqui

Pilhas em arquiteturas de computação são regiões da memória em que os dados são adicionados ou removidos da maneira que entra e sai primeiro.
Em um aplicativo multithread, cada thread terá sua própria pilha.

O que é uma pilha?

Uma pilha é uma coleção desarrumada de coisas empilhadas ao acaso.

Digite a descrição da imagem aqui

Nas arquiteturas de computação, o heap é uma área da memória alocada dinamicamente, gerenciada automaticamente pelo sistema operacional ou pela biblioteca do gerenciador de memória.
A memória no heap é alocada, desalocada e redimensionada regularmente durante a execução do programa, e isso pode levar a um problema chamado fragmentação.
A fragmentação ocorre quando os objetos de memória são alocados com pequenos espaços entre eles que são muito pequenos para armazenar objetos de memória adicionais.
O resultado líquido é uma porcentagem do espaço de heap que não é utilizável para alocações de memória adicionais.

Ambos juntos

Em um aplicativo multithread, cada thread terá sua própria pilha. Mas todos os diferentes threads compartilharão o heap.
Como os diferentes encadeamentos compartilham o heap em um aplicativo com vários encadeamentos, isso também significa que deve haver alguma coordenação entre os encadeamentos para que eles não tentem acessar e manipular o (s) mesmo (s) pedaço (s) de memória no heap em o mesmo tempo.

O que é mais rápido - a pilha ou a pilha? E porque?

A pilha é muito mais rápida que a pilha.
Isso ocorre pela maneira como a memória é alocada na pilha.
Alocar memória na pilha é tão simples quanto mover o ponteiro da pilha para cima.

Para quem é iniciante em programação, provavelmente é uma boa ideia usar a pilha, pois é mais fácil.
Como a pilha é pequena, você poderá usá-la quando souber exatamente quanta memória precisará para seus dados ou se souber que o tamanho dos dados é muito pequeno.
É melhor usar o heap quando você sabe que precisará de muita memória para seus dados ou simplesmente não tem certeza da quantidade de memória necessária (como em uma matriz dinâmica).

Modelo de Memória Java

Digite a descrição da imagem aqui

A pilha é a área da memória em que as variáveis ​​locais (incluindo parâmetros do método) são armazenadas. Quando se trata de variáveis ​​de objeto, essas são apenas referências (ponteiros) para os objetos reais na pilha.
Toda vez que um objeto é instanciado, um pedaço de memória heap é separado para armazenar os dados (estado) desse objeto. Como os objetos podem conter outros, alguns desses dados podem conter referências a esses objetos aninhados.

Shreyos Adikari
fonte
115

A pilha é uma parte da memória que pode ser manipulada através de várias instruções da linguagem de montagem de chaves, como 'pop' (remover e retornar um valor da pilha) e 'push' (enviar um valor para a pilha), mas também chamar ( chamar uma sub-rotina - isso pressiona o endereço para retornar à pilha) e retornar (retornar de uma sub-rotina - isso retira o endereço da pilha e salta para ele). É a região da memória abaixo do registro do ponteiro da pilha, que pode ser configurada conforme necessário. A pilha também é usada para passar argumentos para sub-rotinas e também para preservar os valores nos registradores antes de chamar sub-rotinas.

O heap é uma parte da memória fornecida a um aplicativo pelo sistema operacional, geralmente por meio de um syscall como malloc. Nos sistemas operacionais modernos, essa memória é um conjunto de páginas às quais apenas o processo de chamada tem acesso.

O tamanho da pilha é determinado no tempo de execução e geralmente não aumenta após o lançamento do programa. Em um programa C, a pilha precisa ser grande o suficiente para armazenar todas as variáveis ​​declaradas em cada função. O heap crescerá dinamicamente conforme necessário, mas o sistema operacional fará a chamada (geralmente aumentará o heap em mais do que o valor solicitado pelo malloc, para que pelo menos alguns mallocs futuros não precisem voltar ao kernel para obter mais memória. Esse comportamento geralmente é personalizável)

Como você alocou a pilha antes de iniciar o programa, nunca é necessário fazer malloc antes de poder usá-la, portanto, essa é uma pequena vantagem. Na prática, é muito difícil prever o que será rápido e o que será lento nos sistemas operacionais modernos que possuem subsistemas de memória virtual, porque o modo como as páginas são implementadas e onde são armazenadas é um detalhe da implementação.

Daniel Papasian
fonte
2
Também vale a pena mencionar aqui que a Intel otimiza bastante os acessos de pilha, especialmente coisas como prever onde você retorna de uma função.
Tom Leys
113

Penso que muitas outras pessoas lhe deram respostas corretas sobre esse assunto.

Um detalhe que foi esquecido, no entanto, é que o "heap" provavelmente deve ser chamado de "free store". O motivo dessa distinção é que o armazenamento gratuito original foi implementado com uma estrutura de dados conhecida como "pilha binomial". Por esse motivo, a alocação de implementações iniciais de malloc () / free () foi alocada a partir de um heap. No entanto, atualmente, a maioria das lojas gratuitas é implementada com estruturas de dados muito elaboradas que não são pilhas binomiais.


fonte
8
Outro detalhe - a maioria das respostas (levemente) implica que o uso de uma "pilha" é exigido pelo Cidioma. Esse é um equívoco comum, embora seja o paradigma (de longe) dominante para a implementação C99 6.2.4 automatic storage duration objects(variáveis). Na verdade, a palavra "pilha" nem sequer aparece no C99padrão de linguagem: open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
Johne
[@Heath] Tenho um pequeno comentário sobre sua resposta. Dê uma olhada na resposta aceita para esta pergunta . Ele diz que a loja gratuita provavelmente é igual à pilha , embora não necessariamente seja.
OmarOthman
91

Você pode fazer algumas coisas interessantes com a pilha. Por exemplo, você tem funções como alloca (supondo que você possa passar por copiosos avisos sobre seu uso), que é uma forma de malloc que usa especificamente a pilha, e não a pilha, para memória.

Dito isto, erros de memória baseados em pilha são alguns dos piores que já experimentei. Se você usar memória heap e ultrapassar os limites do bloco alocado, terá uma chance decente de acionar uma falha no segmento. (Não é 100%: seu bloco pode ser incidentalmente contíguo com outro que você alocou anteriormente.) Mas, como as variáveis ​​criadas na pilha são sempre contíguas, a escrita fora dos limites pode alterar o valor de outra variável. Aprendi que sempre que sinto que meu programa parou de obedecer às leis da lógica, provavelmente é um estouro de buffer.

Pedro
fonte
Quão portátil é alloca? Por exemplo, isso funciona no Windows? É apenas para sistemas operacionais semelhantes ao Unix?
Peter Mortensen
89

Simplesmente, a pilha é onde as variáveis ​​locais são criadas. Além disso, toda vez que você chama uma sub-rotina, o contador do programa (ponteiro para a próxima instrução da máquina) e quaisquer registros importantes, e algumas vezes os parâmetros são pressionados na pilha. Em seguida, quaisquer variáveis ​​locais dentro da sub-rotina são empurradas para a pilha (e usadas a partir daí). Quando a sub-rotina termina, tudo isso volta à pilha. Os dados do PC e do registro são colocados e colocados de volta onde estavam, para que seu programa possa seguir em frente.

O heap é a área da memória em que as alocações de memória dinâmica são feitas (chamadas explícitas "novas" ou "alocadas"). É uma estrutura de dados especial que pode rastrear blocos de memória de tamanhos variados e seu status de alocação.

Nos sistemas "clássicos", a RAM era projetada de tal forma que o ponteiro da pilha começava na parte inferior da memória, o ponteiro da pilha começava na parte superior e cresciam um para o outro. Se eles se sobrepõem, você está sem memória RAM. Porém, isso não funciona com sistemas operacionais multithread modernos. Cada encadeamento precisa ter sua própria pilha e elas podem ser criadas dinamicamente.

TED
fonte
[@TED] Por que você disse "às vezes os parâmetros são pressionados na pilha"? O que eu sei é que eles sempre são. Poderia, por favor, elaborar mais?
OmarOthman
1
@ OmarOthman - digo isso porque depende inteiramente do escritor do seu compilador / intérprete o que acontece quando uma sub-rotina é chamada. O comportamento clássico do Fortran é não usar uma pilha. Alguns idiomas suportam coisas exóticas, como passagem por nome, que é efetivamente uma substituição textual.
TED
83

Do WikiAnwser.

Pilha

Quando uma função ou método chama outra função que, por sua vez, chama outra função, etc., a execução de todas essas funções permanece suspensa até a última função retornar seu valor.

Essa cadeia de chamadas de função suspensas é a pilha, porque os elementos na pilha (chamadas de função) dependem um do outro.

É importante considerar a pilha no tratamento de exceções e nas execuções de encadeamento.

Montão

A pilha é simplesmente a memória usada pelos programas para armazenar variáveis. O elemento da pilha (variáveis) não tem dependências entre si e sempre pode ser acessado aleatoriamente a qualquer momento.

devXen
fonte
"Gosto mais da resposta aceita, já que é um nível ainda mais baixo". Isso é uma coisa ruim, não é uma coisa boa.
Lightness Races in Orbit
54

Pilha

  • Acesso muito rápido
  • Não precisa desalocar explicitamente variáveis
  • O espaço é gerenciado com eficiência pela CPU, a memória não se fragmenta
  • Somente variáveis ​​locais
  • Limite no tamanho da pilha (dependente do SO)
  • Variáveis ​​não podem ser redimensionadas

Montão

  • Variáveis ​​podem ser acessadas globalmente
  • Não há limite no tamanho da memória
  • (Relativamente) acesso mais lento
  • Sem uso eficiente garantido do espaço, a memória pode se fragmentar ao longo do tempo à medida que os blocos de memória são alocados e liberados
  • Você deve gerenciar a memória (você é responsável por alocar e liberar variáveis)
  • As variáveis ​​podem ser redimensionadas usando realloc ()
desconhecido
fonte
50

OK, simplesmente e em poucas palavras, eles significam ordenado e não ordenado ...!

Pilha : Nos itens da pilha, as coisas se misturam, significa que será mais rápido e mais eficiente para ser processado! ...

Portanto, sempre há um índice para apontar o item específico, o processamento também será mais rápido, também há relação entre os itens! ...

Montão : nenhuma ordem, o processamento será mais lento e os valores serão alterados sem ordem ou índice específico ... existem aleatórios e não há relação entre eles ... portanto, o tempo de execução e uso pode variar ...

Também crio a imagem abaixo para mostrar como eles podem se parecer:

insira a descrição da imagem aqui

Alireza
fonte
49

Em resumo

Uma pilha é usada para alocação de memória estática e uma pilha para alocação de memória dinâmica, ambas armazenadas na RAM do computador.


Em detalhe

A pilha

A pilha é uma estrutura de dados "LIFO" (última entrada, primeira saída), que é gerenciada e otimizada pela CPU de perto. Toda vez que uma função declara uma nova variável, ela é "empurrada" para a pilha. Toda vez que uma função sai, todas as variáveis ​​colocadas na pilha por essa função são liberadas (ou seja, são excluídas). Depois que uma variável de pilha é liberada, essa região de memória fica disponível para outras variáveis ​​de pilha.

A vantagem de usar a pilha para armazenar variáveis ​​é que a memória é gerenciada por você. Você não precisa alocar a memória manualmente ou liberá-la quando não precisar mais dela. Além disso, como a CPU organiza a memória da pilha com tanta eficiência, a leitura e a gravação das variáveis ​​da pilha são muito rápidas.

Mais pode ser encontrado aqui .


The Heap

O heap é uma região da memória do computador que não é gerenciada automaticamente para você e não é gerenciada com tanta rigidez pela CPU. É uma região de memória mais flutuante (e é maior). Para alocar memória no heap, você deve usar malloc () ou calloc (), que são funções C internas. Depois de alocar memória no heap, você é responsável por usar free () para desalocar a memória quando não precisar mais dela.

Se você não conseguir fazer isso, seu programa terá o que é conhecido como vazamento de memória. Ou seja, a memória no heap ainda será reservada (e não estará disponível para outros processos). Como veremos na seção de depuração, existe uma ferramenta chamada Valgrind que pode ajudá-lo a detectar vazamentos de memória.

Diferentemente da pilha, o heap não possui restrições de tamanho em tamanho variável (além das óbvias limitações físicas do seu computador). A memória da pilha é um pouco mais lenta para ser lida e gravada, porque é necessário usar ponteiros para acessar a memória na pilha. Falaremos sobre indicadores em breve.

Diferentemente da pilha, as variáveis ​​criadas no heap são acessíveis por qualquer função, em qualquer lugar do seu programa. Variáveis ​​de heap são essencialmente globais em escopo.

Mais pode ser encontrado aqui .


As variáveis ​​alocadas na pilha são armazenadas diretamente na memória e o acesso a essa memória é muito rápido, e sua alocação é tratada quando o programa é compilado. Quando uma função ou método chama outra função que, por sua vez, chama outra função, etc., a execução de todas essas funções permanece suspensa até a última função retornar seu valor. A pilha é sempre reservada em uma ordem LIFO, o bloco reservado mais recente é sempre o próximo bloco a ser liberado. Isso torna muito simples acompanhar a pilha, liberar um bloco da pilha nada mais é do que ajustar um ponteiro.

As variáveis ​​alocadas no heap têm sua memória alocada em tempo de execução e o acesso a essa memória é um pouco mais lento, mas o tamanho do heap é limitado apenas pelo tamanho da memória virtual. Os elementos da pilha não têm dependências entre si e sempre podem ser acessados ​​aleatoriamente a qualquer momento. Você pode alocar um bloco a qualquer momento e liberá-lo a qualquer momento. Isso torna muito mais complexo acompanhar quais partes do heap estão alocadas ou livres a qualquer momento.

Digite a descrição da imagem aqui

Você pode usar a pilha se souber exatamente a quantidade de dados que precisa alocar antes do tempo de compilação e ela não for muito grande. Você pode usar o heap se não souber exatamente quantos dados precisará no tempo de execução ou se precisar alocar muitos dados.

Em uma situação multithread, cada thread terá sua própria pilha completamente independente, mas eles compartilharão o heap. A pilha é específica do segmento e a pilha é específica do aplicativo. É importante considerar a pilha no tratamento de exceções e nas execuções de encadeamento.

Cada encadeamento obtém uma pilha, enquanto normalmente há apenas um heap para o aplicativo (embora não seja incomum ter vários heap para diferentes tipos de alocação).

Digite a descrição da imagem aqui

No tempo de execução, se o aplicativo precisar de mais heap, ele poderá alocar memória da memória livre e se a pilha precisar de memória, poderá alocar memória da memória alocada para o aplicativo.

Ainda, mais detalhes são dados aqui e aqui .


Agora chegue às respostas da sua pergunta .

Até que ponto eles são controlados pelo SO ou pelo tempo de execução do idioma?

O SO aloca a pilha para cada encadeamento no nível do sistema quando o encadeamento é criado. Normalmente, o sistema operacional é chamado pelo runtime do idioma para alocar o heap para o aplicativo.

Mais pode ser encontrado aqui .

Qual é o seu escopo?

Já entregue no topo.

"Você pode usar a pilha se souber exatamente quantos dados precisa alocar antes do tempo de compilação e eles não forem muito grandes. Você pode usar o heap se não souber exatamente quantos dados precisará no tempo de execução ou se você precisa alocar muitos dados ".

Mais pode ser encontrado aqui .

O que determina o tamanho de cada um deles?

O tamanho da pilha é definido pelo SO quando um encadeamento é criado. O tamanho do heap é definido na inicialização do aplicativo, mas pode aumentar conforme o espaço necessário (o alocador solicita mais memória do sistema operacional).

O que torna um mais rápido?

A alocação de pilha é muito mais rápida, pois tudo o que realmente faz é mover o ponteiro da pilha. Usando pools de memória, você pode obter desempenho comparável com a alocação de heap, mas isso vem com uma leve complexidade adicional e suas próprias dores de cabeça.

Além disso, pilha versus pilha não é apenas uma consideração de desempenho; também informa muito sobre a vida útil esperada dos objetos.

Detalhes podem ser encontrados aqui .

Abrar Jahin
fonte
36

Na década de 1980, o UNIX propagou-se como coelhos, com grandes empresas produzindo seus próprios produtos. A Exxon tinha um, assim como dezenas de nomes de marcas perdidos na história. Como a memória foi distribuída ficou a critério de muitos implementadores.

Um programa C típico foi colocado na memória, com a oportunidade de aumentar, alterando o valor brk (). Normalmente, o HEAP estava logo abaixo desse valor de brk e o aumento de brk aumentava a quantidade de heap disponível.

A PILHA única era tipicamente uma área abaixo do HEAP, que era uma área de memória que não continha nada de valor até o topo do próximo bloco fixo de memória. Esse próximo bloco era frequentemente CODE, que podia ser sobrescrito pelos dados da pilha em um dos hacks famosos de sua época.

Um bloco de memória típico era o BSS (um bloco de valores zero) que acidentalmente não foi zerado na oferta de um fabricante. Outro foi o DATA contendo valores inicializados, incluindo strings e números. Um terceiro era o CODE contendo CRT (tempo de execução C), principal, funções e bibliotecas.

O advento da memória virtual no UNIX altera muitas das restrições. Não há razão objetiva para que esses blocos precisem ser contíguos, de tamanho fixo ou ordenados de uma maneira específica agora. Obviamente, antes do UNIX havia Multics, que não sofria com essas restrições. Aqui está um esquema que mostra um dos layouts de memória daquela época.

Um layout típico de memória de programa UNIX C do estilo dos anos 80

jlettvin
fonte
36

pilha , pilha e dados de cada processo na memória virtual:

pilha, pilha e dados estáticos

Yousha Aleayoub
fonte
26

Alguns centavos: eu acho que será bom desenhar a memória gráfica e mais simples:

Esta é minha visão da construção da memória do processo com simplificação para uma compreensão mais fácil do que está acontecendo


Setas - mostram onde a pilha de crescimento e a pilha, o tamanho da pilha de processos tem limite, definido no SO, os limites de tamanho da pilha de encadeamentos pelos parâmetros na API de criação de encadeamentos geralmente. Heap geralmente limitando pelo tamanho máximo da memória virtual do processo, por 32 bits de 2 a 4 GB, por exemplo.

Maneira simples: o heap do processo é geral para o processo e todos os threads internos, usando para alocação de memória em casos comuns com algo como malloc () .

A pilha é uma memória rápida para armazenamento em ponteiros e variáveis ​​de retorno de função de caso comum, processados ​​como parâmetros na chamada de função, variáveis ​​de função local.

Maxim Akristiniy
fonte
23

Uma vez que algumas respostas foram acertadas, vou contribuir com meu ácaro.

Surpreendentemente, ninguém mencionou que várias pilhas de chamadas (isto é, não relacionadas ao número de threads em execução no sistema operacional) devem ser encontradas não apenas em linguagens exóticas (PostScript) ou plataformas (Intel Itanium), mas também em fibras , threads verdes e algumas implementações de corotinas .

Fibras, fios verdes e corotinas são de muitas maneiras semelhantes, o que leva a muita confusão. A diferença entre fibras e fios verdes é que os primeiros usam multitarefa cooperativa, enquanto os últimos podem apresentar um cooperativo ou preventivo (ou ambos). Para a distinção entre fibras e corotinas, veja aqui .

De qualquer forma, o objetivo de ambas as fibras, linhas verdes e corotinas é ter várias funções executadas simultaneamente, mas não em paralelo (consulte esta questão do SO para a distinção) em um único segmento no nível do sistema operacional, transferindo o controle para frente e para trás de forma organizada.

Ao usar fibras, linhas verdes ou corotinas, normalmente você tem uma pilha separada por função. (Tecnicamente, não apenas uma pilha, mas todo o contexto de execução é por função. Mais importante, a CPU é registrada.) Para cada encadeamento, há tantas pilhas quanto há funções em execução simultaneamente, e o encadeamento está alternando entre a execução de cada função. de acordo com a lógica do seu programa. Quando uma função é executada até o fim, sua pilha é destruída. Portanto, o número e a vida útil das pilhas são dinâmicos e não são determinados pelo número de threads no nível do SO!

Note que eu disse " normalmente tem uma pilha separada por função". Há dois somos stackful e Stackless implementações de couroutines. As implementações C ++ empilháveis ​​mais notáveis ​​são Boost.Coroutine e Microsoft PPL 's async/await. (No entanto, as funções recuperáveis ​​do C ++ (também conhecidas como " asynce await"), propostas para o C ++ 17, provavelmente usarão corotinas sem pilha.)

A proposta de fibras para a biblioteca padrão C ++ está próxima. Além disso, existem algumas bibliotecas de terceiros . Os threads verdes são extremamente populares em idiomas como Python e Ruby.

shakurov
fonte
19

Tenho algo a compartilhar, embora os principais pontos já estejam cobertos.

Pilha

  • Acesso muito rápido.
  • Armazenado na RAM.
  • As chamadas de função são carregadas aqui, juntamente com as variáveis ​​locais e os parâmetros de função passados.
  • O espaço é liberado automaticamente quando o programa sai do escopo.
  • Armazenado na memória seqüencial.

Montão

  • Acesso lento comparativamente ao Stack.
  • Armazenado na RAM.
  • As variáveis ​​criadas dinamicamente são armazenadas aqui, o que mais tarde requer a liberação da memória alocada após o uso.
  • Armazenado onde quer que a alocação de memória seja feita, acessada sempre pelo ponteiro.

Nota interessante:

  • Se as chamadas de função tivessem sido armazenadas na pilha, resultariam em 2 pontos confusos:
    1. Devido ao armazenamento seqüencial na pilha, a execução é mais rápida. O armazenamento no heap resultaria em um enorme consumo de tempo, tornando o programa inteiro mais lento.
    2. Se as funções fossem armazenadas na pilha (armazenamento confuso apontado pelo ponteiro), não haveria maneira de retornar ao endereço do chamador de volta (que a pilha fornece devido ao armazenamento seqüencial na memória).
Pankaj Kumar Thapa
fonte
1
conciso e limpo. bom :)
ingconti
13

Uau! Tantas respostas e eu não acho que uma delas acertou ...

1) Onde e o que eles estão (fisicamente na memória de um computador real)?

A pilha é a memória que começa como o endereço de memória mais alto alocado para a imagem do programa e depois diminui de valor a partir daí. É reservado para os parâmetros de função chamados e para todas as variáveis ​​temporárias usadas nas funções.

Existem dois montes: público e privado.

O heap privado começa em um limite de 16 bytes (para programas de 64 bits) ou em um limite de 8 bytes (para programas de 32 bits) após o último byte de código no seu programa e, em seguida, aumenta o valor a partir daí. Também é chamado de heap padrão.

Se o heap particular ficar muito grande, ele se sobrepõe à área da pilha, assim como a pilha se sobrepõe ao heap se ficar muito grande. Como a pilha começa em um endereço mais alto e desce para o endereço mais baixo, com hackers adequados, você pode tornar a pilha tão grande que invadirá a área de heap privada e se sobreporá à área de código. O truque é sobrepor o suficiente da área do código para que você possa conectar-se ao código. É um pouco complicado de fazer e você corre o risco de travar um programa, mas é fácil e muito eficaz.

O heap público reside em seu próprio espaço de memória fora do espaço de imagem do programa. É essa memória que será desviada para o disco rígido se os recursos de memória ficarem escassos.

2) Até que ponto eles são controlados pelo SO ou pelo tempo de execução do idioma?

A pilha é controlada pelo programador, a pilha privada é gerenciada pelo sistema operacional e a pilha pública não é controlada por ninguém porque é um serviço do sistema operacional - você faz solicitações e elas são concedidas ou negadas.

2b) Qual é o seu escopo?

Eles são todos globais para o programa, mas seu conteúdo pode ser privado, público ou global.

2c) O que determina o tamanho de cada um deles?

O tamanho da pilha e o heap privado são determinados pelas opções de tempo de execução do compilador. O heap público é inicializado em tempo de execução usando um parâmetro de tamanho.

2d) O que torna um mais rápido?

Eles não foram projetados para serem rápidos, foram projetados para serem úteis. Como o programador as utiliza determina se elas são "rápidas" ou "lentas"

REF:

https://norasandler.com/2019/02/18/Write-a-Compiler-10.html

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-getprocessheap

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-heapcreate

ar18
fonte
8

Muitas respostas estão corretas como conceitos, mas devemos observar que uma pilha é necessária pelo hardware (ou seja, microprocessador) para permitir sub-rotinas de chamada (CALL na linguagem assembly). (OOP caras chamam isso de métodos )

Na pilha, você salva os endereços de retorno e chama → pressionar / reter → pop é gerenciado diretamente no hardware.

Você pode usar a pilha para passar parâmetros .. mesmo que seja mais lento que o uso de registradores (diria um guru de microprocessador ou um bom livro do BIOS dos anos 80 ...)

  • Sem pilha não microprocessador pode funcionar. (não podemos imaginar um programa, mesmo em linguagem assembly, sem sub-rotinas / funções)
  • Sem a pilha que pode. (Um programa em linguagem assembly pode funcionar sem, pois o heap é um conceito de SO, como malloc, que é uma chamada de OS / Lib.

O uso da pilha é mais rápido como:

  • É hardware, e até push / pop são muito eficientes.
  • O malloc requer a entrada no modo kernel, usa o bloqueio / semáforo (ou outras primitivas de sincronização) executando algum código e gerencia algumas estruturas necessárias para acompanhar a alocação.
ingconti
fonte
O que é OPP? Você quer dizer OOP (programação orientada a objetos )?
Peter Mortensen
Você quer dizer que mallocé uma chamada de kernel?
Peter Mortensen
1) sim, desculpe .. OOP ... 2) malloc: escrevo em breve, desculpe ... malloc está no espaço do usuário .. mas pode desencadear outras chamadas .... o ponto é que o uso de heap PODE ser muito lento ...
ingconti
" Muitas respostas estão corretas como conceitos, mas devemos observar que uma pilha é necessária pelo hardware (ou seja, microprocessador) para permitir sub-rotinas de chamada (CALL na linguagem assembly ..) ". Você está confundindo a pilha da CPU (se houver uma na CPU moderna) e as pilhas de tempo de execução do idioma (uma por encadeamento). Quando os programadores falam sobre uma pilha, esta é a pilha de execução de threads do tempo de execução, por exemplo, uma pilha de threads NET), não estamos falando sobre a pilha de CPU.
mins
1

A pilha é essencialmente uma memória de fácil acesso que simplesmente gerencia seus itens como uma - bem - pilha. Somente itens cujo tamanho é conhecido antecipadamente podem ir para a pilha . Este é o caso de números, strings, booleanos.

A pilha é uma memória para itens dos quais você não pode predeterminar o tamanho e a estrutura exatos . Como objetos e matrizes podem ser alterados e alterados em tempo de execução, eles precisam ir para a pilha.

Fonte: Academind

NattyC
fonte
0

Obrigado por uma discussão muito boa, mas como um noob real eu me pergunto onde as instruções são mantidas? No início, os cientistas decidiam entre duas arquiteturas (von NEUMANN, onde tudo é considerado DATA e HARVARD, onde uma área de memória era reservada para instruções e outra para dados). Por fim, seguimos o design de von Neumann e agora tudo é considerado 'o mesmo'. Isso me tornou difícil quando eu estava aprendendo a montagem https://www.cs.virginia.edu/~evans/cs216/guides/x86.html, porque eles falam sobre registros e ponteiros de pilha.

Tudo acima fala sobre DATA. Meu palpite é que, uma vez que uma instrução é uma coisa definida com um espaço específico de memória, ela fica na pilha e, portanto, todos os registros 'discutidos em assembly estão na pilha. É claro que então veio a programação orientada a objetos com instruções e dados inseridos em uma estrutura dinâmica, e agora as instruções também eram mantidas na pilha?

aquagremlin
fonte