Por que a pilha de chamadas tem um tamanho máximo estático?

41

Tendo trabalhado com algumas linguagens de programação, sempre me perguntei por que a pilha de encadeamentos tem um tamanho máximo predefinido, em vez de expandir automaticamente conforme necessário.

Em comparação, certas estruturas de alto nível muito comuns (listas, mapas, etc.) que são encontradas na maioria das linguagens de programação são projetadas para crescer conforme necessário, enquanto novos elementos são adicionados, sendo limitados em tamanho apenas pela memória disponível ou limites computacionais (por exemplo, endereçamento de 32 bits).

Não estou ciente de nenhuma linguagem de programação ou ambiente de execução em que o tamanho máximo da pilha não seja pré-limitado por alguma opção padrão ou compilador. É por isso que muita recursão resultará muito rapidamente em um erro / exceção onipresente de estouro de pilha, mesmo quando apenas uma porcentagem mínima da memória disponível para um processo for usada para a pilha.

Por que é que os ambientes de tempo de execução (se não todos) definem um limite máximo para o tamanho que uma pilha pode aumentar em tempo de execução?

    
por Lynn 09.09.2016 / 16:00
fonte

7 respostas

13

É possível escrever um sistema operacional que não requer que as pilhas sejam contíguas no espaço de endereço. Basicamente, você precisa de alguma confusão extra na convenção de chamada, para garantir que:

  1. Se não houver espaço suficiente na extensão da pilha atual para a função que você está chamando, crie uma nova extensão de pilha e mova o ponteiro da pilha para apontar para o início como parte da criação da pilha. ligar.

  2. quando você retorna da chamada, transfere de volta para a extensão da pilha original. O mais provável é que você mantenha o criado em (1) para uso futuro pelo mesmo thread. Em princípio, você poderia liberá-lo, mas, dessa forma, há casos ineficientes em que você continua pulando para frente e para trás através do limite em um loop, e toda chamada requer alocação de memória.

  3. setjmp e longjmp , ou qualquer equivalente que seu sistema operacional tenha para transferência não local de controle, estão em ação e podem voltar corretamente para a extensão de pilha antiga quando necessário.

Eu digo "convenção de chamada" - para ser específico, acho que é provavelmente melhor feito em um prólogo de função do que pelo chamador, mas minha memória é nebulosa.

O motivo pelo qual algumas linguagens especificam um tamanho fixo de pilha para um encadeamento, é que elas querem trabalhar usando a pilha nativa, em SOs que não fazem isso. Como as respostas de todos os outros dizem, supondo que cada pilha precise ser contígua no espaço de endereço e não possa ser movida, é necessário reservar um intervalo de endereços específico para ser usado por cada encadeamento. Isso significa escolher um tamanho na frente. Mesmo que seu espaço de endereçamento seja enorme e o tamanho escolhido seja muito grande, você ainda terá que escolhê-lo assim que tiver dois tópicos.

"Aha" você diz, "quais são esses supostos sistemas operacionais que usam pilhas não-contíguas? Aposto que é um sistema acadêmico obscuro que não me serve!" Bem, essa é outra pergunta que felizmente já foi feita e respondida.

    
por 10.09.2016 / 01:18
fonte
36

Essas estruturas de dados geralmente possuem propriedades que a pilha do sistema operacional não possui:

  • As listas vinculadas não exigem espaço de endereço contíguo. Assim, eles podem adicionar um pedaço de memória de onde quiserem quando crescerem.

  • Mesmo as coleções que precisam de armazenamento contíguo, como o vetor do C ++, têm uma vantagem sobre as pilhas do SO: elas podem declarar todos os ponteiros / iteradores inválidos sempre que crescerem. Por outro lado, a pilha do sistema operacional precisa manter os ponteiros válidos para a pilha até que a função a cujo quadro o alvo pertence retorne.

Uma linguagem de programação ou tempo de execução pode optar por implementar suas próprias pilhas, que são não-contíguas ou móveis, para evitar as limitações de pilhas do SO. Golang usa tais pilhas personalizadas para suportar números muito altos de co-rotinas, originalmente implementadas como memória não-contígua e agora via pilhas móveis graças ao rastreamento de ponteiro (veja o comentário de hobb). Python sem pilha, Lua e Erlang também podem usar pilhas personalizadas, mas eu não confirmei isso.

Em sistemas de 64 bits, você pode configurar pilhas relativamente grandes com custo relativamente baixo, já que o espaço de endereço é suficiente e a memória física só é alocada quando você realmente a usa.

    
por 09.09.2016 / 16:36
fonte
25

Na prática, é difícil (e às vezes impossível) aumentar a pilha. Para entender por que requer alguma compreensão da memória virtual.

Em Dias Únicos de aplicativos de encadeamento único e memória contígua, três eram três componentes de um espaço de endereço do processo: o código, o heap e a pilha. O modo como esses três foram colocados dependiam do sistema operacional, mas geralmente o código vinha primeiro, começando na parte inferior da memória, o heap vinha em seguida e crescia para cima, e a pilha começava no topo da memória e crescia para baixo. Houve também alguma memória reservada para o sistema operacional, mas podemos ignorar isso. Programas naqueles dias tinham estouros de pilha um pouco mais dramáticos: a pilha colidia com a pilha e, dependendo de qual fosse a primeira atualização, você trabalharia com dados inválidos ou retornaria de uma sub-rotina para uma parte arbitrária da memória.

O gerenciamento de memória mudou este modelo: da perspectiva do programa, você ainda tinha os três componentes de um mapa de memória de processo e eles eram geralmente organizados da mesma maneira, mas agora cada um dos componentes era gerenciado como um segmento independente e a MMU sinalizaria o sistema operacional se o programa tentasse acessar a memória fora de um segmento. Uma vez que você tinha memória virtual, não havia necessidade ou desejo para dar acesso a um programa para todo o seu espaço de endereçamento. Então, os segmentos foram atribuídos limites fixos.

So why isn't it desirable to give a program access to its full address space? Because that memory constitutes a "commit charge" against the swap; at any time any or all of the memory for one program might have to be written to swap to make room for another program's memory. If every program could potentially consume 2GB of swap, then either you'd have to provide enough swap for all of your programs or take the chance that two programs would need more than they could get.

Neste ponto, assumindo espaço de endereço virtual suficiente, você poderá estender esses segmentos, se necessário, e o segmento de dados (heap) crescerá com o tempo: você começa com um pequeno segmento de dados e quando o alocador de memória solicita mais espaço quando é necessário. Neste ponto, com uma única pilha, seria fisicamente possível estender o segmento da pilha: o sistema operacional poderia prender a tentativa de empurrar algo para fora do segmento e adicionar mais memória. Mas isso também não é particularmente desejável.

Digite multithreading. Nesse caso, cada thread tem um segmento de pilha independente, novamente tamanho fixo. Mas agora os segmentos são dispostos um após o outro no espaço de endereço virtual, portanto não há como expandir um segmento sem mover outro - o que você não pode fazer porque o programa potencialmente terá ponteiros para a memória que está na pilha. Você poderia, alternativamente, deixar algum espaço entre os segmentos, mas esse espaço seria desperdiçado em quase todos os casos. Uma abordagem melhor era sobrecarregar o desenvolvedor do aplicativo: se você realmente precisasse de deep stacks, poderia especificar isso ao criar o thread.

Hoje, com um espaço de endereçamento virtual de 64 bits, podemos criar efetivamente pilhas infinitas para números efetivamente infinitos de encadeamentos. Mas, novamente, isso não é particularmente desejável: em quase todos os casos, um overflow de pilha indica um erro com seu código. Fornecer uma pilha de 1 GB simplesmente adia a descoberta desse bug.

    
por 09.09.2016 / 17:05
fonte
3

A pilha com um tamanho máximo fixo não é onipresente.

Também é difícil acertar: profundidades de pilha seguem uma Distribuição de Lei de Potência, o que significa que não importa quão pequeno você faça o tamanho da pilha, ainda haverá uma fração significativa de funções com pilhas menores (então, você desperdiça espaço), e não importa quão grande você faça, ainda haverá funções com pilhas maiores (então você força um erro de estouro de pilha para funções que não têm erro). Em outras palavras: qualquer tamanho que você escolha, sempre será pequeno e grande demais ao mesmo tempo.

Você pode corrigir o primeiro problema permitindo que as pilhas comecem pequenas e cresçam dinamicamente, mas você ainda tem o segundo problema. E se você permitir que a pilha cresça dinamicamente de qualquer maneira, então por que colocar um limite arbitrário nela?

Existem sistemas onde as pilhas podem crescer dinamicamente e não têm tamanho máximo: Erlang, Go, Smalltalk e Scheme, por exemplo. Existem várias maneiras de implementar algo assim:

  • pilhas móveis: quando a pilha contígua não pode mais crescer porque há algo mais no caminho, mova-a para outro local na memória, com mais espaço livre
  • pilhas descontínuas: em vez de alocar a pilha inteira em um único espaço de memória contígua, aloque-a em vários espaços de memória
  • pilhas alocadas em heap: em vez de ter áreas de memória separadas para pilha e heap, basta alocar a pilha no heap; como você percebeu, estruturas de dados alocadas em heap tendem a não ter problemas para crescer e encolher conforme necessário
  • não use pilhas de jeito nenhum: isso também é uma opção, por exemplo em vez de manter o controle do estado da função em uma pilha, faça com que a função passe uma continuação para o chamado

Assim que você tiver construções de fluxo de controle não-locais poderosas, a idéia de uma única pilha contígua sai da janela: exceções e continuações recuperáveis, por exemplo, "empilharão" a pilha, então você acaba com uma rede de pilhas (por exemplo, implementado com uma pilha de espaguete). Além disso, sistemas com pilhas modificáveis de primeira classe, como o Smalltalk, praticamente requerem pilhas de espaguete ou algo similar.

    
por 11.09.2016 / 22:28
fonte
1

O sistema operacional precisa fornecer um bloco contíguo quando uma pilha é solicitada. A única maneira de fazer isso é se um tamanho máximo é especificado.

Por exemplo, digamos que a memória seja assim durante a solicitação (os Xs representam usados, Os não usados):

XOOOXOOXOOOOOX

Se uma solicitação para um tamanho de pilha de 6, a resposta do SO responderá não, mesmo se houver mais de 6 disponíveis. Se um pedido de uma pilha de tamanho 3, a resposta do sistema operacional será uma das áreas de 3 slots vazios (Os) em uma linha.

Além disso, pode-se perceber a dificuldade de permitir o crescimento quando o próximo espaço contíguo está ocupado.

Os outros objetos que são mencionados (Listas, etc.) não vão na pilha, eles acabam no heap em áreas não contíguas ou fragmentadas, então quando eles crescem eles simplesmente pegam espaço, eles não requerem contíguos como eles são gerenciados de maneira diferente.

A maioria dos sistemas define um valor razoável para o tamanho da pilha, você pode substituí-lo quando o encadeamento é construído, se for necessário um tamanho maior.

    
por 09.09.2016 / 22:36
fonte
1

No linux, isso é puramente um limite de recurso que existe para eliminar processos descontrolados antes que eles consumam quantidades prejudiciais do recurso. No meu sistema debian, o seguinte código

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

produz a saída

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Observe que o limite máximo está definido como RLIM_INFINITY : o processo pode aumentar seu limite flexível para qualquer valor. No entanto, desde que o programador não tenha motivos para acreditar que o programa realmente precise de quantidades incomuns de memória de pilha, o processo será eliminado quando exceder um tamanho de pilha de oito mebibytes.

Devido a esse limite, um processo de fuga (recursão infinita não intencional) é eliminado muito antes de começar a consumir quantidades tão grandes de memória que o sistema é forçado a iniciar a troca. Isso pode fazer a diferença entre um processo travado e um servidor com falha. No entanto, ele não limita os programas com uma necessidade legítima de uma pilha grande, eles só precisam definir o limite flexível para algum valor apropriado.

Tecnicamente, as pilhas crescem dinamicamente: quando o soft-limit é configurado para oito mebibyte, isso não significa que essa quantidade de memória tenha sido mapeada ainda. Isso seria um desperdício, já que a maioria dos programas nunca chega perto de seus respectivos limites. Em vez disso, o kernel detectará acessos abaixo da pilha e apenas mapeará as páginas da memória, conforme necessário. Assim, a única limitação real no tamanho da pilha é a memória disponível em sistemas de 64 bits (a fragmentação do espaço de endereço é bastante teórica com um tamanho de espaço de endereço de 16 zebibytes).

    
por 10.09.2016 / 12:12
fonte
0

O tamanho da pilha maximum é estático porque essa é a definição de "maximum" . Qualquer tipo de máximo em qualquer coisa é uma figura limitadora fixa e acordada. Se ele se comporta como um alvo em movimento espontâneo, não é um máximo.

As pilhas nos sistemas operacionais de memória virtual, de fato, crescem dinamicamente, até o máximo .

Falando nisso, não precisa ser estático. Em vez disso, pode ser configurável, por processo ou por thread, mesmo.

Se a pergunta for "por que existe há um tamanho máximo de pilha" (um tamanho artificialmente imposta, geralmente muito menor do que a memória disponível)?

Uma razão é que a maioria dos algoritmos não requer uma quantidade enorme de espaço na pilha. Uma pilha grande é uma indicação de uma possível recursão fugitiva . É bom parar a recursão descontrolada antes de alocar toda a memória disponível. Um problema que parece uma recursão descontrolada é o uso de pilha degenerada, talvez desencadeada por um caso de teste inesperado. Por exemplo, suponha que um analisador para um operador infixo binário funcione recorrendo no operando direito: analisar primeiro operando, varrer o operador, analisar o restante da expressão. Isso significa que a profundidade da pilha é proporcional ao comprimento da expressão: a op b op c op d ... . Um grande caso de teste desse formulário exigirá uma pilha enorme. Abortar o programa quando ele atingir um limite razoável de pilha irá capturar isso.

Outro motivo para um tamanho de pilha máximo fixo é que o espaço virtual para essa pilha pode ser reservado por meio de um tipo especial de mapeamento e, portanto, garantido. Garantido significa que o espaço não será dado a outra alocação que a pilha irá colidir com ele antes de atingir o limite. O parâmetro de tamanho máximo da pilha é necessário para solicitar este mapeamento.

Os segmentos precisam de um tamanho máximo de pilha por um motivo semelhante a isso. Suas pilhas são criadas dinamicamente e não podem ser movidas se colidirem com algo; o espaço virtual deve ser reservado antecipadamente e um tamanho é necessário para essa alocação.

    
por 10.09.2016 / 15:07
fonte

Tags