PROGETTO DI UN SIMULATORE DI STACK-MACHINE

/ Autore: Ettore Pasquini, sett.-ott. 1999

/ Sommario:
/ Obiettivo
/ Analisi di progetto
/ Implementazione e Codifica
1.1 The Machine
1.1.1 Segnali
1.1.2 Ciclo fetch-execute
1.2 Rappresentazione delle istruzioni
1.3 Code Segment e Data Segment
1.4 Registri e altri componenti hardware
2. L'applet
3. Sorgenti
4. Possibili aggiunte e modifiche

/ Obiettivo

Lo scopo di questo progetto non è solo la costruzione di un simulatore di una essenziale stack-machine, ma anche la definizione di un modello generale di "macchina": la barriera di astrazione che si vuole costruire dovrebbe mettere l'utilizzatore di fronte ad una entità dotata di caratteristiche, struttura e funzionamento simile a quello di un processore reale. Questo tipo di approccio viene suggerito dal paradigma O.O.: infatti, la macchina (l'oggetto del discorso) è per sua natura osservabile da 3 punti di vista:

  1. l'aspetto costitutivo: da cosa è composta la macchina ? Attraverso un meccanismo di classificazione si giunge alla definizione dell'oggetto (semantica dichiarativa).
  2. Il funzionamento: cosa fa la macchina ? Come si comporta ? In che modo elabora ? Vogliamo avere il pieno controllo delle micro-mosse compiute dalla macchina. E' implicita la presenza di uno stato interno, cha muta.
  3. L'interazione: la macchina dialoga con l'utente, ma anche con altre macchine, e con se stessa: essendo un oggetto composto, deve essere in grado di sincronizzare da sola i componenti di cui è formata, gestendone i malfunzionamenti indotti da un uso errato delle risorse. In definitiva, questo aspetto è forse il più importante per dare al sistema le necessarie caratteristiche di robustezza.
La necessità di dover attaccare il problema da tutte e 3 le direzioni propone la O.O.P. come un metodo risolutivo "ideale"; inoltre l'O.O.P. consente di risolvere fin dal principio l'intrinseca complessità del sistema, perchè è molto facile, servendosi di elementari conoscenze hardware, scomporre il sistema in moduli dal significato ovvio e intuitivo. Oltre a ciò, grazie alla diffusione degli applet Java, è possibile pensare alla creazione di una interfaccia grafica che fornisca le funzionalità della macchina a chiunque si affacci sul w.w.w..

/ Analisi di progetto

Il simulatore deve permettere l’esecuzione di istruzioni di un predefinito instruction-set, simulando ciò che avviene nel contempo all’interno di un processore reale. Accanto al processore, ed in stretto legame con esso, avremo due ulteriori fondamentali unità, logicamente distinte tra loro: la memoria dove risiede il codice e la memoria dati. Ulteriori dispositivi di contorno (ad es. per catturare il concetto di I/O – da/verso console, disco, ecc. - o per una gestione cache della memoria, ecc.) sono irrilevanti al fine di rappresentare l’elemento essenziale del sistema, cioè la computazione: tuttavia, siccome verrà garantita l’estendibilità, questi elementi potrebbero essere aggiunti in futuro.

L’idea è che il generico oggetto "machine" sia un contenitore di componenti: registri, a.l.u., stack, ecc.. Tali dispositivi saranno interconnessi tra loro al fine di poter realizzare le operazioni del set (che si è già progettato), in un modo che non interessa a chi usa la macchina: al programmatore in linguaggio assembly interessa conoscere, oltre al significato di ogni istruzione, solo lo stato della macchina, che in genere viene rappresentato da opportuni registri ed eventualmente segnalato all’esterno (per es. in caso di un errore) attraverso opportuni "pin " di interfacciamento. D’altra parte, all’interno della macchina viaggiano – tra i componenti – molti segnali che non riguardano il mondo esterno.

La CPU deve avere accesso diretto alla memoria, che è conveniente distingure in due unità logiche: Code Segment e Data Segment. Nel primo dovremo memorizzare le istruzioni in un formato conveniente: siccome è spontaneo pensare ad una gerarchia estendibile di processori, via via più potenti (ad es. essi potrebbero avere un set esteso di registri general purpose; oppure incorporare 2 A.L.U., per inserire un livello di parallelismo; ecc. ecc.), è altrettanto spontaneo pensare ad un set di istruzioni estendibile in due modi: (1) con istruzioni più potenti e complesse, e (2) con una ridefinizione delle interconnesioni tra i componenti "hardware" per permettere una realizzazione più efficiente – che tenga conto dei componenti HW aggiunti – della stessa istruzione (per es. su una register machine con un vasto set di registri la ADD sarà cablata in modo assai diverso rispetto ad una primitiva macchina ad accumulatore).

Potremmo quindi definire (con un probabile abuso di linguaggio) un iniziale information-space del nostro Machine-Simulator:

Da questo punto di vista il sistema appare convenientemente organizzabile attraverso l’O.O.P., e la scelta di Java è una delle possibili per cogliere tutti gli aspetti dell’Information Space or ora delineato.

/ Implementazione e Codifica

1.1 The Machine

E’ conveniente costruire una classe astratta "Machine" che catturi tutti gli elementi comuni: ad es., ogni cpu ha un Istruction Register, un Program Counter, un riferimento al codice e ai dati. Avremo inoltre un metodo fondamentale: go(), cioè il messaggio da inviare alla macchina affinchè essa inizi a computare, ossia ad eseguire il ciclo fetch – execute. 

abstract class Machine{
  protected ProgramCounter PC;
  protected InstructionRegister IR;
  protected CodeSegment CS;
  protected DataSegment DS;

  public abstract void init();
  public abstract void go();
  protected abstract void fetch();
  protected abstract void execute( Instruction i );
  public ProgramCounter PC() { return PC; }
  public CodeSegment getCodeSegment() { return CS; }
  public DataSegment getDataSegment() { return DS; }
  public void setCodeSegment( CodeSegment CSref ) { CS=CSref; }
  public void setDataSegment( DataSegment DSref ) { DS=DSref; }
}

La definizione di una "macchina" concreta procede quindi in 2 fasi principali:

Nel nostro caso, è necessario partire dalle specifiche di cui disponiamo, ossia il set di instruzioni usato dal compilatore in Prolog. Scriviamolo per esteso: 
PUSH PUSHC PUSHADD POP STORE ADD SUB MUL DIV AND OR IMPL JUMP JUMPLE JUMPLT JUMPGE JUMPGT JUMPEQ JUMPNE NOP HALT.

Tali istruzioni corrisponderanno ad opportune micro-sequenze di operazioni sui componenti, come ad es. il caricamento di un registro con un valore letto dallo stack, l’azionamento della a.l.u., e così via. Ma per ora osserviamo che in pratica abbiamo già stabilito l’interfaccia della macchina: 

public class StackMachine extends Machine{
public class StackMachine extends Machine{
  public StackMachine( String programstring ){
    [inizializzazione dei componenti]
    [caricamento del programma]
  }
  public void PUSH(int addr){...}
  public void PUSHC(int val){...}
  public void PUSHADD(int addr){...}
  public void STORE(){...}
  public void ADD(){...}
  (...)
}

La StackMachine non ha registri da fornire al programmatore, a parte quello usato per accedere ad un’area di memoria gestita come uno stack. Tale accesso avviene attraverso le istruzioni di PUSH e le varie operazioni di a.l.u. (che implicitamente fanno riferimento ai valori salvati sullo stack). Pertanto risulta intuitivo fare uso di alcune microistruzioni - riusabli - per la scrittura delle istruzioni più complesse. Di conseguenza, fissato un minimo di 3 registri temporanei interfacciati con la a.l.u., e un Flag-Register per gestire i salti condizionati, la scrittura dei passi elementari di ogni istruzione risulta molto semplice: consideriamo ad es. il caso della ADD. 

public classStackMachine extends Machine{

protected Register
TR1, TR2, TR3; //Temporary Registers
protected FlagRegister FR;
protected IntStack SR; //Lo stack principale
protected Alu ALU1;

(...)

public void ADD(){
    SR.pop(TR2);
    SR.pop(TR1);
    ALU1.enable(Alu.add, TR1, TR2, TR3);
    FR.setZ(TR3);
    FR.setN(TR3);
    SR.push(TR3);
    PC.inc();
}

Per quanto riguarda lo stack, esso concettualmente è simile al data segment: tuttavia è conveniente riusare i metodi push() e pop() della classe java.util.Stack, ridefiniti considerando che l’I/O avviene attraverso registri (volendo, è poi possibile definire un’interfaccia totalmente funzionale ( pop(TRx), oppure pop(SRx, TRy) nel caso siano presenti più stack)). Caricati i registri TR1, TR2 (collegati agli ingressi della a.l.u.), basterà abilitarla con l’opportuno opcode per avere il risultato in TR3 (che "campiona" l’uscita della a.l.u.), da salvare poi sullo stack.

Infine vi sono altri due registri speciali: CS e DS, per accedere al codice e ai dati. Come sono organizzati questi due blocchi per ora non ci interessa: ci basta sapere che con opportune micro-istruzioni fetch(), read(TRx), write(TR1,TR2) possiamo, rispettivamente: caricare sull’Instruction Register la prossima istruzione, leggere il dato contenuto all’indirizzo puntato dal registro TRx, scrivere il dato contenuto nel registro TR1 nella cella di memoria puntata da TR2.

Resta infine da implementare il metodo go() che era stato dichiarato astratto nella classe Machine. A questo proposito bisogna prima stabilire come avvenga l'elaborazione all'interno della macchina. Ispirandosi alla realtà, si può pensare alla presenza di segnali il cui compito è appunto di fare funzionare i vari componenti in modo armonioso e coordinato, nonchè quello di gestire i vari segnali d'errore. Infatti, sebbene il compilatore costruisca un codice che si suppone corretto, la macchina è indipendente da esso, quindi deve essere in grado di gestire un insieme di run-time-error (ad es. un uso scorretto dello stack). A tale scopo, lavorando in Java, si può definire una opportuna gerarchia di eccezioni.

1.1.1 Segnali

Avremo 2 categorie principali di segnali: messaggi, che segnalano l'avvenuta (e corretta) esecuzione di qualcosa; segnali d'errore (eccezioni ), in caso di problemi. Inoltre avremo un'altra distinzione, più particolare: segnali che non escono dalla macchina, e segnali che invece vengono spediti all'esterno.

class MachineSignal extends Exception{}
class MachineMessage extends MachineSignal{}
class MachineException extends MachineSignal{}

Chi lancia questi segnali ? Saranno le istruzioni stesse, o più precisamente i componenti usati dalle istruzioni. E' facile intuire che l'accesso alla memoria è una sorgente "privilegiata" di errori.

class HaltMessage extends MachineMessage{
/** Tale Messaggio è quello inviato quando viene incontrata l'istruzione
* HALT: la macchina esce dal ciclo fetch-execute (entra nell'idle state)
*/
}
class InvalidDataReadAddressException extends MachineException{}
class InvalidDataWriteAddressException extends MachineException{}
class InvalidCodeReadAddressException extends MachineException{}
class EmptyMachineStackException extends MachineException{}
class HaltNotFoundException extends MachineException{}
class NotRecognizedInstructionException extends MachineException{}

1.1.2 Ciclo fetch-execute

Una volta innescato, tale ciclo prosegue finchè non viene incontrata l'istruzione HALT, che invia un segnale di stop. Possono tuttavia verificarsi errori imprevisti, e in questi casi l’azione da prendere è quella di bloccare la macchina e segnalare l’errore.

public void go() throws MachineSignal{
Instruction i;
try{
do{
fetch();
i = IR.contents();
execute(i);
}while( true );

}catch( HaltMessage m ){
throw m;
}catch( InvalidDataReadAddressException e ){
throw e;
}catch( .... ) ....

1.2 Rappresentazione delle Istruzioni.

Avremo una gerarchia di istruzioni la cui radice sia la classe (astratta) Instruction. Ogni macchina particolare dovrà avere il suo set di istruzioni: avremo allora un’altra classe astratta StackMachineInstruction che raggruppa tutte le istruzioni relative alla StackMachine. Ognuna delle classi concrete dovrà avere un metodo exec(Machine m) la cui semantica è: "esegui l’istruzione Y sulla macchina M".
Più in particolare, le gerarchie Machine ed Instruction verranno estese in parallelo:

Machine Instruction

| |

StackMachine - - - - - - - - - - - StackMachineInstruction

| |

StackMachineV2 - - - - - - - - - StackMachineInstructionExp

| |

… …

Le istruzioni della nostra Stack Machine si dividono in 2 gruppi: quelle a 0 operandi e quelle ad 1 operando. Possiamo quindi scrivere una gerarchia del tipo:

abstract class Instruction implements Cloneable{
public abstract void exec( Machine m );
public Instruction copia(){…} /* vedi più avanti */
}//Instruction

abstract class StackMachineInstruction extends Instruction{
}//StackMachineInstruction

class ZeroOpStackMachineInstruction extends StackMachineInstruction{
public void exec(Machine m) throws MachineSignal{}
}

class OneOpStackMachineInstruction extends StackMachineInstruction {
int operand;

public OneOpStackMachineInstruction(int op){ operand=op; }
public void exec(Machine m) throws MachineSignal{}
}

class Push extends OneOpStackMachineInstruction{
public Push(int a){ super(a); }
public void exec( Machine m ) throws InvalidDataReadAddressException{
((StackMachine) m).PUSH(operand());
}
}//Push

class Pushc ……

Dal lato del creatore della lista di istruzioni del programma comunicato in input (tramite file o al limite da tastiera) può risultare comodo un’interfaccia funzionale del tipo make(String opcode, int[] operands), il cui significato è:

"crea un’Instruction la cui classe concreta si ricava dalla stringa opcode, e i cui operandi sono contenuti nel vettore operands ".

Questo risulta utile poichè il programma è comunicato attraverso una stringa (l’output del compilatore è un file di testo), il cui formato è:

<Opcode> <operands>

(…)

<Opcode> <operands>
datablock N

Quindi scriveremo:

public abstract class Instruction implements Cloneable{
(…)
public static Instruction make(String opcode, int[] operands){
return new NotRecognizedInstruction();
}
}//Instruction

abstract class StackMachineInstruction extends Instruction{
public static Instruction make( String opcode, int[] operands){
if (opcode.equals("push")) return new Push(operands[0]) ;
if (opcode.equals("pushc")) return new Pushc(operands[0]) ;
if (opcode.equals("pushadd")) return new Pushadd(operands[0]);
(…)
return Instruction.make(opcode, operands);
}
}//StackMachineInstruction

Come si può vedere, qualora l’istruzione letta non rientri nel set della StackMachine verrà creata un’istanza di "istruzione-non-riconosciuta", o meglio, pensando che il set potrà essere esteso (ad es. StackMachineV2InstructionExp relativo ad una StackMachineV2), la gerarchia Instruction verrà percorsa dal basso verso l’alto fino ad arrivare, in caso di insuccesso, alla radice, a cui corrisponde appunto "istruzione-non-riconosciuta". In tal modo l’espansione StackMachineInstructionExp si aggiunge semplicemente – ossia senza dover fare niente – al set precedente. Infatti il lexical-parser (metodo caricaCSDS della classe StackMachine) del file che contiene il programma in assembly language chiamerà un metodo makeInstruction() – che ogni sottoclasse di Machine deve ridefinire – contenente la chiamata al metodo make() della relativa classe nella gerarchia Instruction:

class StackMachine extends Machine{
(…)
protected Instruction makeInstruction( String opcode, int[] operands){
return StackMachineInstruction.make( opcode, operands);
}
(…)
}//StackMachine

In questo modo dal file in formato testo si passa ad una lista di istruzioni, istanze delle sottoclassi di Instruction, che la StackMachine può comodamente scorrere ed "eseguire".

1.3 Code Segment e Data Segment

Un segmento è un’area organizzata di memoria, schematizzabile come un vettore. Oltre al vettore, un segmento include per definizione un base-address che indica l’indirizzo assoluto di partenza dell’area di memoria coperta dal segmento stesso. Nel caso del codice l’indirizzo della prossima istruzione si ottiene con CS:PC (vedi la fetch()), l’accesso ai dati avverrà tramite DS:<addr>.

abstract class Segment{
private int base;
public int base(){ return base; }
public void setBase(int newbase){ base = newbase; }
public abstract int length();
public abstract void init();
}

Il Code e il Data Segment aggiungono i costruttori e metodi di lettura – scrittura. Per avere un accesso diretto è conveniente usare la classe java.util.Vector (specializzata in 2 sottoclassi CodeVector e DataVector).

class CodeSegment extends Segment{
protected CodeVector theprogram;

/**
* costruttori
*/

public CodeSegment( CodeVector V ){
setBase(0);
theprogram = new CodeVector();
}

public CodeSegment( CodeVector V, int codebase ){
setBase( codebase );
theprogram = new CodeVector();
}

/**
* metodi istanza
*/

public int length(){ return theprogram.size();}
public void init() {
theprogram.removeAllElements();
setBase(0);
}

public Instruction read( ProgramCounter PC ) throws InvalidCodeReadAddressException{
return theprogram.readInstructionAt(PC.contents());
}

(…)

}//CodeSegment

classCodeVector extends Vector{
public CodeVector(){ super(0); }

public Instruction readInstructionAt( int addr) throws InvalidCodeReadAddressException{
try{
return (Instruction) elementAt(addr);
}
catch( ArrayIndexOutOfBoundsException aioobe ){
throw new InvalidCodeReadAddressException();
}
}
}

[il DataSegment è analogo]

1.4 Registri e Altri Componenti Hardware

Un Registro è un oggetto il cui stato è il valore memorizzato:

class Register{
protected int contents;
public Register() { contents=0; }
public Register(int c) { contents=c; }
public void reset() { contents=0; }
public int contents() { return contents;}
public void setContents(int val){ contents=val; }
public String toString() { return Integer.toString( contents );}
}//Register

Nel FlagRegister abbiamo due flag: Zero e Negative. Quindi FlagRegister è una sottoclasse di Register in cui ci interessa leggere il contenuto bit x bit. Dovremo definire quindi alcune operazioni speciali di lettura/scrittura:

classFlagRegister extends Register{
//
// [..............NZ]
//
// Z: flag di zero (=true se risult. Alt è 0)
// N. flag di negativo (=true se risult. Alu è neg)
protected static final byte Z_mask = 1;
protected static final byte N_mask = 2;

public FlagRegister(){ super();}
public FlagRegister(boolean newZ, boolean newN){
super( (newN ? 2:0) + (newZ ? 1:0) );
}
public void reset(){ super.reset();}
public boolean Z(){ return ( (contents() & Z_mask) ? true:false ); }
public boolean N(){ return ( (contents() & N_mask) ? true:false ); }
public void setZ( Register TR ){
setContents( ( (TR.contents()==0) ? (contents()|Z_mask):0 );
}
public void setN( Register TR ){
setContents( ( (TR.contents()< 0) ? (contents()|N_mask):0 );
}
public String toString(){ return Integer.toBinaryString(contents());}
}//FlagRegister

Anche il program counter eredita da Register: esso in più è dotato di un "circuito dedicato" di somma unitaria in modo da potersi autoincrementare:

class ProgramCounter extends Register{
public void inc() { contents++; }
}//ProgramCounter

L’ instruction register è un registro particolare: il suo contenuto è un oggetto Instruction, letto all’indirizzo CS:PC. Per coerenza, sull’Instruction Register bisognerebbe avere una copia completa della generica istruzione letta dal code segment, non un semplice riferimento. Quindi si dovrà implementare l’interfaccia Cloneable nella classe Instruction. Nel complesso la sua interfaccia sarà leggermante diversa:

class InstructionRegister{
private Instruction I;
public InstructionRegister( Instruction inst ){ … }
public void setContents( Instruction newIref ){ … }
public Instruction contents(){ return I; }
public String toString(){ return I.toString(); }
}//InstructionRegister

La ALU è un componente che viene "abilitato" (comando enable) quando sono stati caricati gli operandi sui registri di input (TR1 e TR2). L’uscita della ALU è nel registro TR3.

class Alu{
// definitions of operation codes
public static final byte add = 0;
public static final byte sub = 1;
public static final byte mul = 2;
public static final byte div = 3;
public static final byte and = 4;
public static final byte or = 5;
public static final byte impl= 6;

public Alu(){}
public void reset(){}
public void enable(byte opcode,Register TR1,Register TR2,Register TR3){
switch( opcode ){
case add: TR3.setContents( TR1.contents() + TR2.contents() );
break;
case sub: (…)

(…)

}
}
}//Alu

2. L'applet

Pensando alla realizzazione di un'interfaccia grafica, possiamo organizzare lo spazio in 3 blocchi:

  1. area di input, dove si può inserire e modificare il file di codice fornito dal compilatore;
  2. area di output, dove vediamo lo stato interno della macchina;
  3. pannello di comando, dove si interagisce con il sistema.
La costruzione è resa facile dalle API fornite da Java. Può essere utile sottolineare che l'ascoltatore deputato all'esecuzione del ciclo fetch-execute sarà quello che dovrà intercettare tutti i segnali lanciati dalla macchina nel corso dell'esecuzione del programma (ossia nel "run-time interno"), stampando, eventualmente, opportuni messaggi d'errore.
Forse l'uso più logico è quello come applicazione stand-alone, che rende possibile il caricamento dal file-system locale: tuttavia, la classe TextArea dell'Api A.W.T. supporta il cut & paste in modo automatico.

Per vedere un esempio (essenziale) di una possibile applet, si può cliccare qui.
 

    3.    Sorgenti

Per la gerarchia Machine, nonchè per gli altri componenti (registri, alu, stack), si veda: StackMachine.java;
per la gerarchia Instruction, si veda: Instruction.java;
per la gerarchia Segment: CodeSegment.java e DataSegment.java;
per la gerarchia dei segnali lanciati dalla macchina, si veda: MachineSignal.java;
per un esempio di espansione del sistema: StackMachineV2.java;
per un esempio di front-end essenziale, sotto DOS: Testm.java;
per una minimale interfaccia grafica, sia come applet sia come stand-alone application: SMSmgui.java.
per un file zip comprendente i sorgenti del simulatore con i relativi bytecode già compilati: sms.zip

    4.     Possibili aggiunte e/o modifiche

Servendosi della classe java.util.Vector (vettori estendibili a run-time) lo spazio di indirizzamento della macchina è infinito. Per gestire un più realistico spazio di indirizzamento finito si potrebbe intordurre un controllo tramite eccezioni: data la memoria disponibile, la condizione che deve essere verificata ad ogni istante è che lo spazio occupato da codice, dati e stack non deve superare il totale disponibile: questa è quindi un invariante della classe Machine. Qualora si verifichi una violazione la macchina dovrà arrestare il suo funzionamento e lanciare un opportuno segnale d'errore all'esterno.
Nell'attuale versione di StackMachine non si ha mai né espansione né contrazione del memory-array (in particolare, del DataSegment): infatti non sono gestite le chiamate a procedura.
 

return