Perché lo stack di chiamate ha una dimensione massima statica?

È possibile scrivere un sistema operativo che non richiede stack contigui nello spazio degli indirizzi. Fondamentalmente è necessario un po 'di confusione extra nella convenzione di chiamata, per garantire che:

1. se non c'è abbastanza spazio nell'estensione dello stack corrente per la funzione che stai chiamando, allora crei una nuova estensione dello stack e sposta il puntatore dello stack in modo che punti all'inizio di esso come parte del chiamare.

2. quando si ritorna da quella chiamata si ritorna alla dimensione dello stack originale. Molto probabilmente manterrai quello creato a (1) per uso futuro dalla stessa discussione. In linea di principio si potrebbe rilasciarlo, ma in questo modo si trovano casi piuttosto inefficienti in cui si continua a saltare avanti e indietro lungo il confine in un ciclo, e ogni chiamata richiede allocazione di memoria.

3. setjmp e longjmp , o qualsiasi altra cosa equivalente al tuo sistema operativo per il trasferimento di controllo non locale, sono in atto e possono tornare correttamente alla dimensione della pila precedente quando richiesto.

Dico "convenzione di chiamata" - per essere precisi, penso che sia probabilmente meglio farlo in un prologo di funzione piuttosto che da chi chiama, ma il mio ricordo di ciò è confuso.

Il motivo per cui parecchie lingue specificano una dimensione fissa dello stack per un thread, è che vogliono lavorare usando lo stack nativo, su sistemi operativi che non fanno. Come dicono le risposte di tutti gli altri, partendo dal presupposto che ogni stack deve essere contiguo nello spazio degli indirizzi e non può essere spostato, è necessario riservare un intervallo di indirizzi specifico da utilizzare per ogni thread. Ciò significa scegliere una taglia in anticipo. Anche se lo spazio degli indirizzi è enorme e la dimensione scelta è molto grande, devi ancora sceglierla non appena hai due thread.

"Aha" tu dici "quali sono questi sistemi operativi supposti che usano stack non contigui? Scommetto che è un oscuro sistema accademico che non mi è di alcuna utilità!". Bene, è un'altra domanda che fortunatamente è già stata fatta e ha risposto.

Queste strutture dati hanno tipicamente proprietà che lo stack del sistema operativo non ha:

• Gli elenchi collegati non richiedono spazio di indirizzamento contiguo. In questo modo possono aggiungere un pezzo di memoria da qualsiasi luogo quando crescono.

• Anche le collezioni che necessitano di storage contiguo, come il vettore di C ++, hanno un vantaggio sugli stack del sistema operativo: possono dichiarare invalidi tutti i puntatori / iteratori ogni volta che crescono. D'altra parte lo stack del sistema operativo deve mantenere validi i puntatori allo stack fino a quando la funzione al cui frame appartiene il target ritorna.

Un linguaggio di programmazione o un runtime possono scegliere di implementare i propri stack che non sono contigui o mobili per evitare le limitazioni degli stack del sistema operativo. Golang usa tali stack personalizzati per supportare un numero molto elevato di co-routines, originariamente implementate come memoria non contigua e ora tramite stack mobili grazie al puntatore del tracking (vedere il commento di hobb). Python senza pila, Lua ed Erlang potrebbero anche usare pile personalizzate, ma non l'ho confermato.

Sui sistemi a 64 bit puoi configurare stack relativamente grandi con costi relativamente bassi, dato che lo spazio degli indirizzi è abbondante e la memoria fisica viene allocata solo quando effettivamente la usi.

In pratica, è difficile (e talvolta impossibile) far crescere lo stack. Per capire perché richiede una certa comprensione della memoria virtuale.

In Ye Olde Days di applicazioni a thread singolo e memoria contigua, tre erano tre componenti di uno spazio di indirizzamento del processo: il codice, l'heap e lo stack. Il modo in cui i tre erano disposti dipendeva dal sistema operativo, ma in genere il codice veniva prima, iniziando dal fondo della memoria, il mucchio si avvicinava e cresceva, e lo stack iniziava nella parte superiore della memoria e cresceva verso il basso. C'era anche un po 'di memoria riservata al sistema operativo, ma possiamo ignorarlo. I programmi in quei giorni avevano overflow dello stack un po 'più drammatici: lo stack si sarebbe schiantato nell'heap e, a seconda di quale aggiornamento si sarebbe aggiornato, avresti lavorato con dati errati o tornato da una subroutine in qualche parte arbitraria della memoria.

La gestione della memoria ha cambiato questo modello in qualche modo: dal punto di vista del programma c'erano ancora i tre componenti di una mappa della memoria di processo, e generalmente erano organizzati nello stesso modo, ma ora ciascuno dei componenti era gestito come un segmento indipendente e la MMU segnalerebbe il sistema operativo se il programma ha tentato di accedere alla memoria al di fuori di un segmento. Una volta che avevi memoria virtuale, non c'era bisogno di o desiderio di dare a un programma l'accesso all'intero spazio degli indirizzi. Quindi ai segmenti sono stati assegnati dei limiti fissi.

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.

A questo punto, presupponendo uno spazio di indirizzamento virtuale sufficiente, potrebbe estendere questi segmenti se necessario, e il segmento di dati (heap) cresce effettivamente nel tempo: si inizia con un segmento di dati di piccole dimensioni e quando l'allocatore di memoria richiede più spazio quando è necessario. A questo punto, con uno stack singolo, sarebbe stato fisicamente possibile estendere il segmento dello stack: il sistema operativo potrebbe intrappolare il tentativo di spingere qualcosa al di fuori del segmento e aggiungere più memoria. Ma neanche questo è particolarmente auspicabile.

Inserisci multi-threading. In questo caso, ogni thread ha un segmento di stack indipendente, di nuovo una dimensione fissa. Ma ora i segmenti sono disposti uno dopo l'altro nello spazio degli indirizzi virtuali, quindi non c'è modo di espandere un segmento senza spostarne un altro, cosa che non si può fare perché il programma avrà potenzialmente dei puntatori alla memoria che vive nello stack. In alternativa potresti lasciare uno spazio tra i segmenti, ma quello spazio sarebbe sprecato in quasi tutti i casi. Un approccio migliore era quello di mettere il peso sullo sviluppatore dell'applicazione: se davvero avevi bisogno di stack profondi, puoi specificarlo durante la creazione del thread.

Oggi, con uno spazio di indirizzi virtuali a 64 bit, potremmo creare stack infinitamente efficaci per un numero infinito di thread. Ma ancora una volta, ciò non è particolarmente auspicabile: in quasi tutti i casi, uno stack overflow indica un bug con il tuo codice. Fornendoti uno stack da 1 GB, puoi semplicemente rinviare la scoperta di quel bug.

Lo stack con una dimensione massima fissa non è onnipresente.

È anche difficile avere ragione: le profondità dello stack seguono una distribuzione di Power Law, il che significa che non importa quanto piccole siano le dimensioni dello stack, ci sarà comunque una significativa frazione di funzioni con stack ancora più piccoli (quindi, rifiuti spazio), e non importa quanto grande lo si crei, ci saranno comunque funzioni con stack ancora più grandi (quindi si impone un errore di overflow dello stack per le funzioni che non hanno errori). In altre parole: qualsiasi dimensione tu scelga, sarà sempre troppo piccola e troppo grande allo stesso tempo.

Puoi risolvere il primo problema consentendo agli stack di iniziare in piccolo e crescere dinamicamente, ma poi hai ancora il secondo problema. E se permetti allo stack di crescere in modo dinamico comunque, perché mettere un limite arbitrario su di esso?

Esistono sistemi in cui gli stack possono crescere dinamicamente e non avere dimensioni massime: Erlang, Go, Smalltalk e Scheme, ad esempio. Esistono molti modi per implementare una cosa del genere:

• stack mobili: quando lo stack contiguo non può crescere più perché c'è qualcos'altro nel modo, spostalo in un'altra posizione in memoria, con più spazio libero
• stack discontinui: invece di allocare l'intero stack in un singolo spazio di memoria contiguo, allocarlo in più spazi di memoria
• stack allocati su heap: invece di avere aree di memoria separate per stack e heap, basta allocare lo stack sull'heap; come ti sei accorto, le strutture dati allocate su heap tendono a non avere problemi a crescere e a ridursi se necessario
• non utilizzare pile: è anche un'opzione, ad es. invece di tenere traccia dello stato della funzione in una pila, fare in modo che la funzione passi una continuazione al callee

Non appena disponi di potenti costrutti di flusso di controllo non locali, l'idea di un singolo stack contiguo esce comunque dalla finestra: le eccezioni e le continuazioni ripristinabili, ad esempio, "imposteranno" lo stack, quindi in realtà finirà con una rete di stack (ad esempio implementata con una pila di spaghetti). Inoltre, i sistemi con stack modificabili di prima classe, come Smalltalk, richiedono praticamente stack di spaghetti o qualcosa di simile.

Il sistema operativo deve fornire un blocco contiguo quando viene richiesto uno stack. L'unico modo in cui può farlo è se viene specificata una dimensione massima.

Ad esempio, supponiamo che la memoria assomigli a questo durante la richiesta (Xs rappresenta usato, Os inutilizzato):

XOOOXOOXOOOOOX

Se una richiesta per una dimensione di stack di 6, la risposta all'OS risponderà no, anche se sono disponibili più di 6. Se una richiesta di stack di dimensione 3, la risposta del sistema operativo sarà una delle aree di 3 spazi vuoti (Os) in una riga.

Inoltre, si può vedere la difficoltà di consentire la crescita quando il successivo slot contiguo è occupato.

Gli altri oggetti menzionati (elenchi, ecc.) non vanno in pila, finiscono nell'heap in aree non contigue o frammentate, quindi quando crescono prendono semplicemente spazio, non richiedono contiguità come sono gestiti in modo diverso.

La maggior parte dei sistemi imposta un valore ragionevole per le dimensioni dello stack, puoi sovrascriverlo quando il thread è costruito se è richiesta una dimensione maggiore.

Su Linux, questo è puramente un limite di risorse che esiste per uccidere i processi in fuga prima che consumino quantità dannose della risorsa. Sul mio sistema debian, il seguente codice

#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);
}

produce l'output

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

Nota che il limite rigido è impostato su RLIM_INFINITY : il processo è autorizzato ad aumentare il suo limite morbido a qualsiasi importo. Tuttavia, finché il programmatore non ha motivo di credere che il programma abbia davvero bisogno di quantità insolite di memoria dello stack, il processo verrà ucciso quando supera una dimensione di stack di otto mebibyte.

A causa di questo limite, un processo in fuga (ricorsione infinita non intenzionale) viene ucciso molto tempo prima che inizi a consumare così grandi quantità di memoria che il sistema è costretto a iniziare a scambiare. Questo può fare la differenza tra un processo in crash e un server in crash. Tuttavia, non limita i programmi con una legittima necessità di un grande stack, ma solo di impostare il limite flessibile su un valore appropriato.

Tecnicamente, gli stack crescono dinamicamente: quando il limite di flessibilità è impostato su otto mebibyte, ciò non significa che questa quantità di memoria sia stata effettivamente mappata. Ciò sarebbe piuttosto dispendioso in quanto la maggior parte dei programmi non si avvicina mai ai rispettivi limiti soft. Piuttosto, il kernel rileverà gli accessi sotto lo stack e si limiterà a mappare le pagine di memoria quando necessario. Pertanto, l'unica limitazione reale sulla dimensione dello stack è la memoria disponibile su sistemi a 64 bit (la frammentazione dello spazio degli indirizzi è piuttosto teorica con una dimensione dello spazio di indirizzamento di 16 zebibyte).

La dimensione dello stack massimo è statica perché quella è la definizione di "massima" . Qualsiasi tipo di massimo su qualsiasi cosa è un numero limitato e concordato. Se si comporta come un bersaglio che si muove spontaneamente, non è un massimo.

Le pile su sistemi operativi con memoria virtuale di fatto crescono dinamicamente, fino al massimo .

A proposito, non deve essere statico. Piuttosto, può essere configurabile, anche su una base per processo o per thread,.

Se la domanda è "perché c'è c'è una dimensione massima dello stack" (uno imposto artificialmente, di solito molto meno della memoria disponibile)?

Una ragione è che la maggior parte degli algoritmi non richiede un'enorme quantità di spazio nello stack. Una grande pila è un'indicazione di una possibile ricorsione in fuga . È bene interrompere la ricorsione in fuga prima di allocare tutta la memoria disponibile. Un problema che sembra una ricorsione in fuga è l'uso degenerato dello stack, forse causato da un caso di test inatteso. Ad esempio, supponiamo che un parser per un operatore binario, infisso, funzioni da ricorsivo sull'operando di destra: analizza il primo operando, l'operatore di scansione, analizza il resto dell'espressione. Ciò significa che la profondità dello stack è proporzionale alla lunghezza dell'espressione: a op b op c op d ... . Un enorme test case di questo modulo richiederà un enorme stack. Abortire il programma quando raggiunge un limite di stack ragionevole lo prenderà.

Un altro motivo per una dimensione massima fissa dello stack è che lo spazio virtuale per lo stack può essere prenotato tramite un tipo speciale di mappatura, e quindi garantito. Garantito significa che lo spazio non sarà assegnato ad un'altra allocazione che lo stack colliderà con esso prima di raggiungere il limite. Il parametro della dimensione massima dello stack è richiesto per richiedere questa mappatura.

I thread hanno bisogno di una dimensione massima dello stack per un motivo simile a questo. I loro stack sono creati dinamicamente e non possono essere spostati se si scontrano con qualcosa; lo spazio virtuale deve essere prenotato in anticipo e per tale allocazione è necessaria una dimensione.