Por que as pilhas normalmente crescem para baixo?

95

Eu sei que nas arquiteturas com as quais estou pessoalmente familiarizado (x86, 6502, etc), a pilha normalmente cresce para baixo (ou seja, cada item colocado na pilha resulta em um SP diminuído, não um incrementado).

Estou me perguntando sobre o fundamento histórico para isso. Eu sei que em um espaço de endereço unificado, é conveniente iniciar a pilha na extremidade oposta do segmento de dados (digamos), então só haverá um problema se os dois lados colidirem no meio. Mas por que a pilha tradicionalmente fica com a parte superior? Especialmente considerando como isso é o oposto do modelo "conceitual"?

(E observe que na arquitetura 6502, a pilha também cresce para baixo, embora seja limitada a uma única página de 256 bytes, e essa escolha de direção parece arbitrária.)

Ben Zotto
fonte

Respostas:

52

Quanto ao fundamento histórico, não posso dizer com certeza (porque não fui eu que os projetei). Minha opinião sobre o assunto é que as primeiras CPUs tiveram seu contador de programa original definido como 0 e era um desejo natural começar a pilha na outra extremidade e crescer para baixo, já que seu código cresce naturalmente para cima.

Como um aparte, observe que esta configuração do contador do programa para 0 na reinicialização não é o caso para todas as CPUs anteriores. Por exemplo, o Motorola 6809 buscaria o contador do programa em endereços 0xfffe/fpara que você pudesse começar a executar em um local arbitrário, dependendo do que foi fornecido naquele endereço (normalmente, mas de forma alguma limitado a, ROM).

Uma das primeiras coisas que alguns sistemas históricos fariam seria varrer a memória do topo até encontrar um local que leria de volta o mesmo valor escrito, de modo que soubesse a RAM real instalada (por exemplo, um z80 com espaço de endereço de 64K não necessariamente tinha 64K ou RAM, na verdade 64K teria sido enorme nos meus primeiros dias). Depois de encontrar o endereço real superior, ele definiria o ponteiro da pilha apropriadamente e poderia então começar a chamar as sub-rotinas. Essa verificação geralmente seria feita pela CPU executando o código na ROM como parte da inicialização.

Com relação ao crescimento das pilhas, nem todas crescem para baixo, veja esta resposta para detalhes.

paxdiablo
fonte
1
Gosto da história da estratégia de detecção de RAM do Z80. Faz algum sentido que os segmentos de texto sejam dispostos crescendo para cima - os programadores de outrora tinham um contato um pouco mais direto para lidar com as implicações disso do que com a pilha. Obrigado, paxdiablo. O ponteiro para o conjunto de formas alternativas de implementações de pilha também é muito interessante.
Ben Zotto
A memória dos primeiros dias não tem uma maneira de notificar seu tamanho e temos que calculá-la manualmente?
phuclv
1
@ LưuVĩnhPhúc, devo presumir que você está uma geração (ou duas) atrás de mim. Ainda me lembro do método TRS-80 modelo 3 para obter a data e a hora sendo solicitá-lo ao usuário no momento da inicialização. Ter um scanner de memória para definir o limite superior de memória era considerado um estado da arte naquela época :-) Você pode imaginar o que aconteceria se o Windows perguntasse a hora, ou quanta memória você tinha, toda vez que inicializasse?
paxdiablo
1
De fato, a documentação do Zilog Z80 diz que a parte é inicializada configurando o registro do PC para 0000h e executando. Ele define o modo de interrupção para 0, desabilita interrupções e define os registradores I e R para 0 também. Depois disso, ele começa a ser executado. Em 0000h, ele começa a executar o código. ESSE código deve inicializar o ponteiro da pilha antes de poder chamar uma sub-rotina ou habilitar interrupções. Qual fornecedor vende um Z80 que se comporta da maneira que você descreve?
MikeB de
1
Mike, desculpe, eu deveria ter sido mais claro. Quando eu disse que a CPU escaneia a memória, não quis dizer que era um recurso da própria CPU. Na verdade, era controlado por um programa em ROM. Vou esclarecer.
paxdiablo
21

Uma boa explicação que ouvi foi que algumas máquinas no passado só podiam ter offsets não assinados, então você gostaria que a pilha diminuísse para que pudesse atingir seus locais sem ter que perder a instrução extra para falsificar um offset negativo.

anq
fonte
7

Stanley Mazor (arquiteto 4004 e 8080) explica como a direção do crescimento da pilha foi escolhida para 8080 (e eventualmente para 8086) em "Microprocessadores Intel: 8008 a 8086" :

O ponteiro da pilha foi escolhido para funcionar "para baixo" (com a pilha avançando em direção à memória inferior) para simplificar a indexação na pilha a partir do programa do usuário (indexação positiva) e para simplificar a exibição do conteúdo da pilha a partir de um painel frontal.

roolebo
fonte
6

Uma possível razão pode ser que simplifica o alinhamento. Se você colocar uma variável local na pilha que deve ser colocada em um limite de 4 bytes, você pode simplesmente subtrair o tamanho do objeto do ponteiro da pilha e zerar os dois bits inferiores para obter um endereço alinhado corretamente. Se a pilha crescer para cima, garantir o alinhamento se torna um pouco mais complicado.

Jalf
fonte
1
Os computadores não subtraem; eles adicionam o elogio de 2. Tudo o que é feito subtraindo é realmente feito adicionando. Considere, os computadores têm somadores, não subtratores.
jww
1
@jww - isso é uma distinção sem diferença. Eu poderia muito bem afirmar que os computadores não adicionam, eles apenas subtraem! Para os fins desta resposta, isso realmente não importa - mas a maioria das ALUs usará um circuito que suporta adição e subtração com o mesmo desempenho. Ou seja, embora A - Bpossa ser conceitualmente implementado como A + (-B)(ou seja, uma etapa de negação separada para B), não é na prática.
BeeOnRope
@jww Seu detalhamento está errado para os primeiros computadores - levou algum tempo para o complemento de dois vencer, e até que isso acontecesse, havia computadores usando o complemento e sinal e magnitude de alguém e talvez outras coisas em vez disso. Com essas implementações, pode muito bem ter havido uma vantagem em adicionar versus subtrair. Portanto, na ausência de informações adicionais, é errado descartar isso como um possível fator que influencia as opções de esquema de endereçamento, como a direção da pilha.
mtraceur
4

IIRC a pilha cresce para baixo porque a pilha cresce para cima. Poderia ter sido o contrário.

Christian V
fonte
5
Um heap de crescimento para cima permite realocação eficiente em alguns casos, mas um heap de crescimento para baixo quase nunca permite.
Peter Cordes
@PeterCordes por quê?
Yashas
3
@Yashas: porque realloc(3)precisa de mais espaço após um objeto apenas para estender o mapeamento sem copiar. A realocação repetida do mesmo objeto é possível quando é seguido por uma quantidade arbitrária de espaço não utilizado.
Peter Cordes
2

Acredito que seja puramente uma decisão de design. Nem todos eles crescem para baixo - consulte este tópico do SO para uma boa discussão sobre a direção do crescimento da pilha em diferentes arquiteturas.

Kaleb Brasee
fonte
1

Acredito que a convenção começou com o IBM 704 e seu infame "registro de decremento". A fala moderna o chamaria de campo de deslocamento da instrução, mas o fato é que eles diminuíram , não aumentaram .

luser droog
fonte
1

Apenas 2c mais:

Além de todo o raciocínio histórico mencionado, tenho certeza de que não há razão válida para os processadores modernos. Todos os processadores podem ter deslocamentos assinados, e maximizar a distância heap / pilha é bastante discutível desde que começamos a lidar com vários threads.

Pessoalmente, considero isso uma falha de design de segurança. Se, digamos, os designers da arquitetura x64 tivessem invertido a direção do crescimento da pilha, a maioria dos estouros de buffer da pilha teria sido eliminada - o que é um grande negócio. (já que as cordas crescem para cima).

Ofek Shilon
fonte
0

Não tenho certeza, mas fiz alguma programação para o VAX / VMS naquela época. Parece que me lembro de uma parte da memória (a pilha ??) aumentando e a pilha diminuindo. Quando os dois se conheceram, você estava sem memória.

Martin
fonte
1
Isso é verdade, mas então por que a pilha cresce para cima e não o contrário?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
0

Uma vantagem do crescimento descendente da pilha em um sistema embarcado mínimo é que um único pedaço de RAM pode ser mapeado redundantemente na página O e na página 1, permitindo que variáveis ​​de página zero sejam atribuídas começando em 0x000 e a pilha crescendo para baixo de 0x1FF, maximizando o quantidade que teria que aumentar antes de substituir as variáveis.

Um dos objetivos do projeto original do 6502 era que ele pudesse ser combinado com, por exemplo, um 6530, resultando em um sistema de microcontrolador de dois chips com 1 KB de ROM de programa, temporizador, E / S e 64 bytes de RAM compartilhados entre as variáveis ​​da pilha e da página zero. Em comparação, o sistema embarcado mínimo da época baseado em 8080 ou 6800 seria de quatro ou cinco chips.

Milão
fonte