Limite da pilha

10

Recentemente, testei o limite de uma pilha em três dispositivos com sistemas operacionais diferentes (por limite, quero dizer o número máximo de níveis que a pilha pode ter) e notei que toda vez que atingi 2 ^ 16 níveis, isso me dava erro de estouro, e quando coloco 2 ^ 16-1, ele funciona corretamente.

Então, minha pergunta é - isso é verdade? A pilha possui o limite máximo 2 ^ 16-1 por definição ou depende do sistema operacional?

Anonymus
fonte
5
here i mean by limit the maximum number of levels that can the stack haveo que é um nível?
precisa saber é
3
Como você está testando? Você está usando um byte de 2 bytes (dword) como entrada?
pro3carp3
6
Qual linguagem de programação você está usando? Um limite tão acentuado em um número fixo indica que é uma limitação deliberada pelo tempo de execução específico do seu idioma e não pelo tamanho da pilha que o SO alocou. Por exemplo, o python parece impor um limite de 1000 por padrão, para impedir que você atinja um estouro de pilha real (recuperar de um estouro de pilha real é difícil)
#

Respostas:

20

É fortemente específico do sistema operacional (e específico do computador) e, em alguns sistemas operacionais, você tem algumas maneiras de configurar (e até aumentar) o limite. É ainda específico do compilador (ou da sua implementação da linguagem de programação), pois alguns compiladores (incluindo o GCC recente para algum tipo limitado de código C) são capazes de otimizar algumas chamadas finais .

(algumas especificações da linguagem de programação exigem otimizações de chamada de cauda, ​​por exemplo, R5RS )

Não sei se sua pergunta faz sentido (e certamente não é o seu limite de 2 16 ). Na minha área de trabalho Linux (Debian / Sid / x86-64, kernel Linux 4.9, 32Gb de RAM, Intel i5-4690S), eu posso ter uma pilha de chamadas de até 8 megabytes (e eu poderia aumentar esse limite, se realmente quisesse )

Multi-threading e ASLR estão tornando sua pergunta muito mais complexa . Veja, por exemplo, pthread_attr_setstack (3) . Leia também sobre pilhas divididas (geralmente usadas por implementações Go ) e sobre o estilo de passagem de continuação . Veja também esta resposta.

Pelo que vale a pena, tentei apenas o seguinte código C99 (e também C11):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void recfun(int x, int d) {
  printf("start recfun x=%d d=%d\n", x, d);
  fflush(NULL);
  if (d>0)
    recfun(x+1, d-1);
  printf("end recfun x=%d d=%d\n", x, d);
}

int main(int argc, char**argv) {
  int md = argc>1?atoi(argv[1]):10000;
  printf ("start md=%d\n", md);
  recfun(0, md);
  printf("end md=%d clock=%ld µs\n", md, clock());
}    
// eof recur.c

e pude executar esse recurprograma (compilado com o GCC 6 as gcc -Wall -O recur.c -o recur) como recur 161000 (muito acima do seu limite de 2 16 ). Com recur 256000isso também funcionou. Com recur 456000ele caiu (com um estouro de pilha por nível x=272057). Não tenho paciência para outros testes. Tente isso no seu computador. Não se esqueça de pedir otimizações.

Uma regra prática (para desktops, laptops, tablets) pode ser manter sua pilha de chamadas abaixo de um megabyte.

Ao passar também -fstack-usage para gcc estou obtendo o seguinte recur.suarquivo (os números são em bytes, consistentes com a minha intuição de limite de pilha de 8 Mb; não esqueça o mainquadro de chamada e, mais importante, o layout inicial da pilha, instalado pelo kernel ao executar o execve (2 ) ..., para crt0 ):

 recur.c:5:10:recfun    32  static
 recur.c:13:9:main  16  static

PS. Meu Arduino possui um Atmega328 com apenas 2Kbytes de RAM, portanto, certamente não pode se repetir tanto. Eu acho que apenas algumas centenas de frames de pilha são praticamente possíveis no Arduinos.

Basile Starynkevitch
fonte
3

O tamanho da pilha para o encadeamento principal de um processo Windows é definido pelo vinculador. O padrão é 1 MB, mas pode ser ajustado com a opção / STACK. Os threads criados posteriormente podem usar o parâmetro dwStackSize da função CreateThread.

Então .. se você estiver testando vários sistemas operacionais Windows, todos eles têm o mesmo tamanho de pilha padrão desde pelo menos NT4.0.

Eric
fonte