[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home] [volume] [parte]


Capitolo 545.   Organizzazione della memoria

Questo capitolo introduce il problema dell'organizzazione della memoria, da un punto di vista molto vicino a quello della realtà fisica dell'elaboratore. In particolare, viene utilizzata la pseudocodifica, già descritta nel capitolo 543, per dimostrare in parte il funzionamento e l'utilizzo della pila dei dati, di cui, normalmente, ogni programma dispone.

545.1   Pila per salvare i dati

Quando si scrive con un linguaggio di programmazione molto vicino a quello effettivo del microprocessore, si ha normalmente a disposizione una pila di elementi omogenei (stack), usata per accumulare temporaneamente delle informazioni, da espellere poi in senso inverso. Questa pila è gestita attraverso un vettore, dove l'ultimo elemento (quello superiore) è individuato attraverso un indice noto come stack pointer e tutti gli elementi della pila sono comunque accessibili, in lettura e in sovrascrittura, se si conosce la loro posizione relativa.

Figura 545.1. Una pila che può contenere al massimo nove elementi, rappresentata nel modo tradizionale, oppure distesa, come si fa per i vettori. Gli elementi che si trovano oltre l'indice (lo stack pointer) non sono più disponibili, mentre gli altri possono essere letti e modificati senza doverli estrarre dalla pila.

pila

Per accumulare un dato nella pila (push) si incrementa di una unità l'indice e lo si inserisce in quel nuovo elemento. Per estrarre l'ultimo elemento dalla pila (pop) si legge il contenuto di quello corrispondente all'indice e si decrementa l'indice di una unità.

Tra le altre cose, la pila può servire quando si dispone di una quantità limitata di variabili e si devono accumulare temporaneamente dei valori.

545.2   Chiamate di funzioni

I linguaggi di programmazione più vicini alla realtà fisica della memoria di un elaboratore, possono disporre solo di variabili globali ed eventualmente di una pila, realizzata attraverso un vettore, come descritto nella sezione precedente. In questa situazione, la chiamata di una funzione può avvenire solo passando i parametri in uno spazio di memoria condiviso da tutto il programma. Ma per poter generalizzare le funzioni e per consentire la ricorsione, ovvero per rendere le funzioni rientranti, il passaggio dei parametri deve avvenire attraverso la pila in questione.

Per mostrare un esempio iniziale che consenta di comprendere il meccanismo, si può supporre di poter utilizzare delle variabili locali nelle funzioni, mentre per il passaggio dei valori si deve usa la pila. Si vuole trasformare il codice della pseudocodifica seguente in modo da utilizzare tale pila. Si consideri che il programma inizia e finisce nella funzione MAIN, all'interno della quale si fa la chiamata della funzione SOMMA:

SOMMA (X, Y)
    LOCAL Z INTEGER
    Z := X + Y
    RETURN Z
END SOMMA

MAIN ()
    LOCAL A INTEGER
    LOCAL B INTEGER
    LOCAL C INTEGER
    A := 3
    B := 4
    C := SOMMA (A, B)
END MAIN

Il programma si trasforma in modo da accumulare nel vettore PILA i valori dei parametri della chiamata:

GLOBAL PILA[1000] INTEGER
GLOBAL SP         INTEGER
SP := -1

SOMMA ()
    LOCAL X := PILA[SP]         # Copia il valore del primo parametro.
    LOCAL Y := PILA[SP - 1]     # Copia il valore del secondo parametro.

    LOCAL Z INTEGER
    Z := X + Y

    SP++                        #
    PILA[SP] := Z               # Accumula il risultato della somma.

END SOMMA

MAIN ()
    LOCAL A INTEGER
    LOCAL B INTEGER
    LOCAL C INTEGER
    A := 3
    B := 4

    SP++                #
    PILA[SP] := B       # Accumula il secondo parametro nella pila.

    SP++                #
    PILA[SP] := A       # Accumula il primo parametro nella pila.

    SOMMA ()            # Chiama la funzione SOMMA().
    
    C := PILA[SP]       #
    SP--                # Estrae il risultato.

    SP--                # Elimina il primo parametro della chiamata.
    SP--                # Elimina il secondo parametro della chiamata.
    
END MAIN

Nella nuova versione della pseudocodifica, la chiamata della funzione SOMMA è preceduta dall'accumulo nella pila dei parametri, quindi è seguita dall'estrazione del risultato della somma e dall'eliminazione dei due parametri usati nella chiamata (con la sola riduzione del valore dell'indice del vettore). All'interno della funzione SOMMA si acquisiscono i parametri leggendo i dati corrispondenti dal vettore che li convoglia, sapendo che il primo è nella posizione dell'indice (in quanto è l'ultimo elemento inserito nella pila) e che il secondo è nella posizione precedente. Alla fine, dopo l'esecuzione della somma, il risultato viene inserito nella pila.

L'esempio seguente risolve il problema del calcolo del fattoriale, in modo ricorsivo, seguendo la modalità appena descritta:

GLOBAL PILA[1000] INTEGER
GLOBAL SP         INTEGER
SP := -1

FATTORIALE ()
    LOCAL X := PILA[SP]
    LOCAL W INTEGER

    IF X == 1
        THEN
            SP++                # Accumula il risultato da restituire,
            PILA[SP] := 1       # pari a uno.
        ELSE
            SP++                # Accumula il parametro di chiamata della
            PILA[SP] := X - 1   # funzione con un valore pari a X - 1.
            
            FATTORIALE ()
            
            W := PILA[SP]       # Recupera il risultato della chiamata
            SP--                # ricorsiva con un valore pari a X - 1.
            
            SP--                # Scarica il parametro usato per la chiamata.

            SP++                # Accumula il risultato del fattoriale
            PILA[SP] := X * W   # da restituire.
    END IF

END FATTORIALE

MAIN ()
    LOCAL F INTEGER
    F := 7

    SP++                # Accumula il valore di cui si vuole calcolare
    PILA[SP] := F       # il fattoriale.
    
    FATTORIALE ()       # Calcola il fattoriale.
    
    F := PILA[SP]       # Estrae il risultato del fattoriale e scarica
    SP--                # il valore dalla pila.
    
    SP--                # Scarica la pila del parametro usato nella chiamata.
    
END MAIN

Se non si possono gestire variabili locali, la pila va usata anche per salvare le variabili che altrimenti verrebbero sovrascritte con la chiamata ricorsiva:

GLOBAL PILA[1000] INTEGER
GLOBAL SP         INTEGER
SP := -1

GLOBAL X          INTEGER
GLOBAL W          INTEGER

FATTORIALE ()
    X := PILA[SP]

    IF X == 1
        THEN
            SP++                # Accumula il risultato da restituire,
            PILA[SP] := 1       # pari a uno.
        ELSE
            SP++                #
            PILA[SP] := X       # Salva il valore di X nella pila.

            SP++                # Accumula il parametro di chiamata della
            PILA[SP] := X - 1   # funzione con un valore pari a X - 1.
            
            FATTORIALE ()
            
            W := PILA[SP]       # Recupera il risultato della chiamata
            SP--                # ricorsiva con un valore pari a X - 1.
            
            SP--                # Scarica il parametro usato per la chiamata.

            X := PILA[SP]       # Recupera il valore di X prima della
            SP--                # chiamata ricorsiva.

            SP++                # Accumula il risultato del fattoriale
            PILA[SP] := X * W   # da restituire.
    END IF

END FATTORIALE
...
...

Come si vede nel nuovo esempio, prima della chiamata ricorsiva viene salvata nella pila solo la variabile X, perché il valore di W non dipende dall'elaborazione e tale variabile riceve un valore utile solo dopo la chiamata in questione. Naturalmente, si comprende che in questo caso particolare, non sarebbe stato nemmeno necessario salvare la variabile X, in quanto il suo valore corretto, dopo la chiamata ricorsiva, lo si può determinare semplicemente reincrementandolo di una unità. Ma qui si è preferito mostrare un esempio molto semplice, risolvendolo in modo generalizzato, anche se ciò non sarebbe necessario.

545.3   Funzioni attraverso le istruzioni di salto

Con l'uso di linguaggi di programmazione ragionevolmente evoluti, i salti (go to), condizionati o meno, vanno evitati, dal momento che esistono delle strutture per il controllo del flusso e si può disporre di chiamate di funzioni o procedure. Tuttavia, quando si deve scrivere con un linguaggio molto vicino alla realtà fisica dell'elaboratore, non si dispone più di questi ausilii, o comunque occorre fare i conti con un indice riferito alle istruzioni da eseguire.

In pratica, il programma viene a trovarsi disposto in un vettore, dove un indice serve a sapere qual è l'istruzione successiva da eseguire: instruction pointer. Nel momento in cui si esegue un'istruzione normale, l'indice viene incrementato automaticamente per posizionarsi all'inizio dell'istruzione successiva, mentre in presenza di un'istruzione di salto, l'esecuzione di tale istruzione sposta l'indice nella nuova destinazione.

In queste condizioni, per ottenere ciò che di solito si realizza con delle funzioni ricorsive, occorre gestire l'indice delle istruzioni direttamente. Per la precisione, prima di saltare all'inizio di una funzione, oltre che accumulare i parametri della chiamata nella pila già descritta, occorre accumulare l'indice delle istruzioni, in modo tale da poter riprendere dall'istruzione successiva alla chiamata dopo l'esecuzione di ciò che rappresenta tale funzione.

GLOBAL IP         INTEGER       # «Instruction pointer» (sola lettura).
GLOBAL RETURN     INTEGER       # Destinazione per il ritorno.
...
GLOBAL PILA[1000] INTEGER
GLOBAL SP         INTEGER
SP := -1
...
GLOBAL X          INTEGER
GLOBAL W          INTEGER
...
FATTORIALE ()
    X := PILA[SP - 1]           # Recupera il primo parametro.
                                # Si ricorda che "PILA[SP]" contiene
                                # l'indirizzo di ritorno.

    IF X == 1
        THEN
            RETURN := PILA[SP]  # Recupera l'indirizzo di ritorno.
            SP++                # Accumula il risultato da restituire,
            PILA[SP] := 1       # pari a uno.
            GO_TO RETURN        # Torna all'istruzione successiva alla chiamata.
        ELSE
            SP++                #
            PILA[SP] := X       # Salva il valore di X nella pila.

            SP++                # Accumula il parametro di chiamata della
            PILA[SP] := X - 1   # funzione con un valore pari a X - 1.
            
            SP++                # Accumula l'indirizzo dell'istruzione
            PILA[SP] := IP + 1  # successiva alla prossima.
            
            GO_TO FATTORIALE () # Salta all'inizio della funzione.

            SP--                # Scarica l'indirizzo di ritorno della
                                # funzione appena conclusa.
            
            W := PILA[SP]       # Recupera il risultato della chiamata
            SP--                # ricorsiva con un valore pari a X - 1.
            
            SP--                # Scarica il parametro usato per la chiamata.

            X := PILA[SP]       # Recupera il valore di X prima della
            SP--                # chiamata ricorsiva.

            RETURN := PILA[SP]  # Recupera l'indirizzo di ritorno.
            SP++                # Accumula il risultato del fattoriale
            PILA[SP] := X * W   # da restituire.
            GO_TO RETURN        # Torna all'istruzione successiva alla chiamata.
    END IF

END FATTORIALE
...
...

Nell'esempio mostrato si considera che la variabile IP sia accessibile in sola lettura e che contenga l'indice dell'istruzione successiva o di quella richiesta da un'istruzione di salto. Prima del salto all'inizio di una funzione, si accumula il valore di IP nella pila, ma incrementandolo di ciò che serve a raggiungere l'istruzione successiva al salto stesso (si suppone che l'incremento di una unità dia il risultato voluto). Nel momento appropriato, il valore dell'indice viene prelevato dalla pila e inserito in una variabile apposita, da usare per saltare alla posizione di ritorno.

545.4   Variabili e array

Con un linguaggio di programmazione molto vicino alla realtà fisica dell'elaboratore, la memoria centrale viene vista come un vettore di celle uniformi, corrispondenti normalmente a un byte. All'interno di tale vettore si distendono tutti i dati gestiti, compresa la pila descritta nelle prime sezioni del capitolo. In questo modo, le variabili in memoria si raggiungono attraverso un indirizzo che individua il primo byte che le compone ed è il programma che deve sapere di quanti byte sono composte complessivamente.

Figura 545.7. Esempio di mappa di una memoria di soli 256 byte, dove sono evidenziate alcune variabili. Gli indirizzi dei byte della memoria vanno da 0016 a FF16.

memoria

Nel disegno in cui si ipotizza una memoria complessiva di 256 byte, sono state evidenziate alcune aree di memoria:

Indirizzo Dimensione Indirizzo Dimensione
5416 4 byte 5816 4 byte
5C16 2 byte 5E16 4 byte
6216 8 byte 6A16 4 byte
6E16 1 byte 6F16 8 byte

Con una gestione di questo tipo della memoria, la rappresentazione degli array richiede un po' di impegno da parte del programmatore. Nella figura successiva si rappresenta una matrice a tre dimensioni; per ora si ignorino i codici numerici associati alle celle visibili.

Figura 545.9. La matrice a tre dimensioni che si vuole rappresentare, secondo un modello spaziale. I numeri che appaiono servono a trovare successivamente l'abbinamento con le celle di memoria utilizzate.

matrice

Dal momento che la rappresentazione tridimensionale rischia di creare confusione, quando si devono rappresentare matrici che hanno più di due dimensioni, è più conveniente pensare a strutture ad albero. Nella figura successiva viene tradotta in forma di albero la matrice rappresentata precedentemente.

Figura 545.10. La matrice a tre dimensioni che si vuole rappresentare, tradotta in uno schema gerarchico (ad albero).

matrice

Si suppone di rappresentare la matrice in questione nella memoria dell'elaboratore, dove ogni elemento terminale contiene due byte. Supponendo di allocare l'array a partire dall'indirizzo 7716 nella mappa di memoria già descritta, si potrebbe ottenere quanto si vede nella figura successiva. A questo punto, si può vedere la corrispondenza tra gli indirizzi dei vari componenti dell'array e le figure già mostrate.

Figura 545.11. Esempio di mappa di memoria in cui si distende un array che rappresenta una matrice a tre dimensioni con tre elementi contenenti ognuno due elementi che a loro volta contengono quattro elementi da due byte.

memoria

Si pone quindi il problema di scandire gli elementi dell'array. Considerando che array ha dimensioni «3,2,4» e definendo che gli indici partano da zero, l'elemento [0,0,0] corrisponde alla coppia di byte che inizia all'indirizzo 7716, mentre l'elemento [2,1,3] corrisponde all'indirizzo A516. Per calcolare l'indirizzo corrispondente a un certo elemento occorre usare la formula seguente, dove: le variabili I, J, K rappresentano la dimensioni dei componenti; le variabili i, j, k rappresentano l'indice dell'elemento cercato; la variabile A rappresenta l'indirizzo iniziale dell'array; la variabile s rappresenta la dimensione in byte degli elementi terminali dell'array.

A + (i*J*K*s + j*K*s + k*s)

A + (i*J*K*s + j*K*s + k*s)

Si vuole calcolare la posizione dell'elemento 2,0,1. Per facilitare i conti a livello umano, si converte l'indirizzo iniziale dell'array in base dieci: 7716 = 11910:

A + (i*J*K*s + j*K*s + k*s)

Il valore 15310 si traduce in base sedici in 9916, che corrisponde effettivamente all'elemento cercato: terzo elemento principale, all'interno del quale si cerca il primo elemento, all'interno del quale si cerca il secondo elemento finale.

545.5   Gestione alternativa degli indici

Quando si vuole disporre un array nella memoria, se quello che conta è solo raggiungere gli elementi terminali che lo compongono, non fa molta differenza se la gerarchia con cui si organizza è diversa. Per esempio, l'array che prima era strutturato in elementi di dimensione 3,2,4, potrebbe benissimo essere definito secondo la suddivisione 4,3,2, gestendo di conseguenza gli indici. Lo si può vedere nella figura successiva che riproduce la nuova gerarchia in forma di albero.

Figura 545.15. La stessa matrice, ma organizzata secondo una gerarchia differente.

matrice

Nella figura successiva si riprende l'esempio di mappa della memoria, dove l'array già apparso nella sezione precedente è disposto secondo la nuova suddivisione.

Figura 545.16. La nuova mappa della memoria.

mappa

Nella tabella successiva si mettono a confronto le coordinate calcolate per raggiungere gli elementi dell'array strutturato secondo le due gerarchie mostrate (quella della sezione precedente e quella attuale). Si può vedere che le celle di memoria vengono raggiunte nello stesso modo (nella tabella gli indirizzi sono annotati in base dieci). Viene anche mostrato cosa può accadere se si usano gli indici di accesso in modo non coincidente alla gerarchia prescelta.

Tabella 545.17. Confronto dell'indirizzamento della memoria utilizzando due modi diversi di organizzare gli elementi dell'array, con un esempio di cosa accade quando gli indici non combaciano con la struttura scelta.

indirizzamento degli array

545.6   Ordine dei byte

Come già descritto in questo capitolo, normalmente l'accesso alla memoria avviene conoscendo l'indirizzo iniziale dell'informazione cercata, sapendo poi per quanti byte questa si estende. Il microprocessore, a seconda delle proprie caratteristiche e delle istruzioni ricevute, legge e scrive la memoria a gruppetti di byte, più o meno numerosi. Ma l'ordine dei byte che il microprocessore utilizza potrebbe essere diverso da quello che si immagina di solito.

Figura 545.18. Confronto tra big endian e little endian.

little endian, big endian

A questo proposito, per quanto riguarda la rappresentazione dei dati nella memoria, si distingue tra big endian, corrispondente a una rappresentazione «normale», dove il primo byte è quello più significativo (big), e little endian, dove la sequenza dei byte è invertita (ma i bit di ogni byte rimangono nella stessa sequenza standard) e il primo byte è quello meno significativo (little). La cosa importante da chiarire è che l'effetto dell'inversione nella sequenza porta a risultati differenti, a seconda della quantità di byte che compongono l'insieme letto o scritto simultaneamente dal microprocessore, come si vede nella figura.

545.7   Stringhe, array e puntatori

Le stringhe sono rappresentate in memoria come array di caratteri, dove il carattere può impiegare un byte o dimensioni multiple (nel caso di UTF-8, un carattere viene rappresentato utilizzando da uno a quattro byte, a seconda del punto di codifica raggiunto). Il riferimento a una stringa viene fatto come avviene per gli array in generale, attraverso un puntatore all'indirizzo della prima cella di memoria che lo contiene; tuttavia, per non dovere annotare la dimensione di tale array, di norma si conviene che la fine della stringa sia delimitata da un byte a zero, come si vede nell'esempio della figura.

Figura 545.19. Stringa conclusa da un byte a zero (zero terminated string), a cui viene fatto riferimento per mezzo di una variabile che contiene il suo indirizzo iniziale. La stringa contiene il testo Ciao amore., secondo la codifica ASCII.

stringa

Nella figura si vede che la variabile scalare collocata all'indirizzo 5316 contiene un valore da intendere come indirizzo, con il quale si fa riferimento al primo byte dell'array che rappresenta la stringa (in posizione 7816). La variabile collocata in 5316 assume così il ruolo di variabile puntatore e, secondo il modello ridotto di memoria della figura, è sufficiente un solo byte per rappresentare un tale puntatore, dal momento che servono soltanto valori da 0016 a FF16.

545.8   Utilizzo della memoria

La memoria dell'elaboratore viene utilizzata sia per contenere i dati, sia per il codice del programma che li utilizza. Ogni programma ha un proprio spazio in memoria, che può essere reale o virtuale; all'interno di questo spazio, la disposizione delle varie componenti potrebbe essere differente. Nei sistemi che si rifanno al modello di Unix, nella parte più «bassa» della memoria risiede il codice che viene eseguito; subito dopo vengono le variabili globali del programma, mentre dalla parte più «alta» inizia la pila dei dati che cresce verso indirizzi inferiori. Si possono comunque immaginare combinazioni differenti di tale organizzazione, pur rispettando il vincolo di avere tre zone ben distinte per il loro contesto (codice, dati, pila); tuttavia, ci sono situazioni in cui i dati si trovano mescolati al codice, per qualche ragione.

Figura 545.20. Esempio di disposizione delle componenti di un programma in esecuzione in memoria, secondo il modello Unix.

memoria

545.9   Riferimenti


Appunti di informatica libera 2008 --- Copyright © 2000-2008 Daniele Giacomini -- <appunti2 (ad) gmail·com>


Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome organizzazione_della_memoria.htm

[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home]

Valid ISO-HTML!

CSS validator!

Gjlg Metamotore e Web Directory