Macchina RAM
Il modello della macchina RAM è uno strumento classico per l'analisi delle procedure sequenziali. Questo modello è caratterizzato da una memoria ad accesso casuale formata da celle che possono contenere un intero qualsiasi; le istruzioni utilizzate sono quelle di un elementare linguaggio macchina che consente di eseguire istruzioni di input e di output, svolgere operazioni aritmetiche, accedere e modificare il contenuto della memoria, eseguire semplici comandi di salto.
La semplicità di questo modello, astrazione di un elaboratore, consente di comprendere procedure scritte mediante linguaggi ad alto livello e possono essere eseguiti su macchine RAM. Fra i limiti del modello si sottolinea che non è presente una gerarchia di memoria (memoria tampone, memoria di massa) e le istruzioni sono eseguite una alla volta su un unico processore.
Modello[modifica | modifica wikitesto]
Il modello della macchina RAM (macchina ad accesso casuale) è costituito da un nastro di ingresso, un nastro di uscita, un programma rappresentato da una sequenza finita di istruzioni, un contatore lc che indica l'istruzione corrente da eseguire e una memoria formata da infiniti registri R0,R1,... Rn. Ciascuno dei due nastri è rappresentato da infinite celle, numerate a partire dalla prima, ognuna delle quali può contenere un numero intero. Il nastro di ingresso è dotato di una testina di sola lettura mentre quello di uscita dispone di una testina di sola scrittura. Le due testine si muovono sempre da sinistra verso destra e nello stato iniziale sono posizionate sulla prima cella. Inizialmente tutte le celle del nastro di uscita sono vuote mentre il nastro di ingresso contiene l'input della macchina; questo è formato da un vettore di n interi x1,x2,...xn disposti ordinatamente nelle prime n celle del nastro.
Il programma è fissato e non può essere modificato durante l'esecuzione. Ciascuna istruzione è etichettata e il registro lc (Location counter) contiene l'etichetta dell'istruzione da eseguire. Le istruzioni molto semplici, si avvicinano molto ad un linguaggio Assembler.
Ogni registro Rk può contenere un numero arbitrario intero relativo. L'indirizzo del registro Rk è l'intero k. Il registro R0 è chiamato accumulatore ed è l'unico sul quale si possono svolgere operazioni aritmetiche.
Programmazione di una macchina RAM[modifica | modifica wikitesto]
Il programma di una macchina RAM è una sequenza finita di istruzioni:
ciascuna delle quali è una coppia formata da un codice di operazione e da un indirizzo. Un indirizzo a sua volta può essere un operando o un'etichetta. Le etichette sono associate solo a comandi di salto e servono per indicare istruzioni del programma cui passare eventualmente il controllo. Un operando può assumere tre forme diverse:
- =i indica l'intero i ∈ Z
- i indica il contenuto del registro Ri
- *i indica il contenuto del registro Rj, dove j è il contenuto del registro Ri
