Simulere en enkel CPU

Introduksjon

Little Man Computer (LMC) er en enkel modell av en datamaskin. Den simulerer en CPU som jobber i 10-tallsystemet, med 100 minneplasser, en programteller som peker på neste instruksjon, og en akkumulator som brukes i regneoperasjoner. Instruksjoner og data ligger i det samme minnet.

Dere kan finne LMC-simulatoren her.

I denne oppgaven skal dere implementere minnet (Hovedminne-klassen) og selve prosessoren (LMC-klassen). Programlasteren, som leser et LMC-program fra en tekstfil og bygger opp minnebildet som en liste med tall, er gitt i filen programlaster.py.

Datamaskinen skiller ikke på hva som er data og hva som er instruksjoner. Filen selvmodifiserendekode.txt viser et eksempel på kode som endrer seg etterhvert som programmet kjører. Dette er en kjent svakhet i CPU-arkitektur, og en vanlig måte systemer blir hacket på.

Kort om LMC og instruksjoner

Et dataprogram er helt kort bare en liste av instruksjoner. Når datamaskinen skal kjøre et program laster den inn programmet i minnet, og setter en programteller til å holde styr på hvor i listen den neste instruksjonen befinner seg. Instruksjonen til LMC er alltid det første sifferet i tallkoden (IO-operasjonene bruker også de to andre sifferne for å avgjøre hva som blir gjort).

LMC henter instruksjonen på adressen programtelleren peker på, utfører den og går videre til neste instruksjon. En instruksjon kan også hoppe til en annen adresse, og dermed endre verdien til programtelleren direkte. Programmet kjører til det møter HLT (alle instruksjoner som starter med 0).

Format på programfilen

Hver linje inneholder én instruksjon, eventuelt etterfulgt av en minneadresse. Store og små bokstaver skal behandles likt.

Eksempel (add.txt):

INP
STA 99
INP
ADD 99
OUT
HLT

En instruksjon med adresse består av en operasjonskode og en adresse. For eksempel blir ADD 99 tallet 199. Instruksjoner uten adresse bruker bare operasjonskoden. INP blir 901.

Programfilen kan også bruke merker. Merkene viser til minneadresser og kan brukes som argument til instruksjoner:

          INP
          STA first
          INP
          ADD first
          OUT
          HLT
first     DAT 0

Programmet ber om to heltall og skriver ut summen. Bruk den utdelte Programlaster-klassen i programlaster.py til å gjøre teksten om til et minnebilde.

Instruksjonskoder

OPPERASJONSKODER = {
   "inp": 901,
   "out": 902,
   "otc": 922,
   "lda": 500,
   "sta": 300,
   "add": 100,
   "sub": 200,
   "brp": 800,
   "brz": 700,
   "bra": 600,
   "hlt": 0,
   "dat": 0,
}

Klassegrensesnitt

Programlasteren er utdelt i programlaster.py og oversetter tekst til en liste med tall. Hovedminne lagrer listen og gir tilgang til verdiene på hver minneadresse, og LMC kjører programmet som ligger i minnet. I denne oppgaven skal dere implementere Hovedminne og LMC.

les_program i den utdelte programlasteren returnerer minnebildet som en liste.

from programlaster import Programlaster

programlaster = Programlaster()
minne = programlaster.les_program("add.txt")

hovedminne = Hovedminne(100)
hovedminne.last_innhold(minne)

lmc = LMC(hovedminne)
lmc.interpret()

Del 1: Hovedminne

1. Implementer Hovedminne. Den skal holde på hovedminnet og kontrollere at adresser er gyldige og la dere hente og lagre verdier.

2. Implementer last_innhold(innhold). Den skal kontrollere at minnebildet får plass og lagre hver verdi i hovedminnet. Dere kan teste at dette fungerer som det skal ved å opprette et hovedminne med veldig liten plass.

3. Bruk den utdelte Programlaster-klassen til å lese add.txt, og last minnebildet inn i hovedminnet med last_innhold.

4. Kontroller resultatet ved å lese add.txt. De første seks verdiene skal være:

   901, 399, 901, 199, 902, 0
   

Del 2: LMC

Målet er å kjøre et lite program som leser inn to tall og skriver ut summen. Dere skal implementere grunnleggende instruksjoner og stoppe når programmet kommer til HLT.

1. Legg kjøringen i en metode på LMC, for eksempel interpret().

2. Hent instruksjonen fra adressen i hovedminnet som programtelleren peker på. Øk programtelleren før neste instruksjon utføres.

3. Del instruksjonen i operasjonskode og minneadresse med heltallsdivisjon og rest:

   operasjonskode = instruksjon // 100  # heltallsdivisjon
   minneadresse   = instruksjon %  100   # rest
   

4. Implementer disse instruksjonene:

   Instruksjon	Kode	Virkning
   HLT	0xx	Avslutter programmet
   ADD	1xx	Legger verdien i minnet til akkumulatoren
   SUB	2xx	Trekker verdien i minnet fra akkumulatoren
   STA	3xx	Lagrer akkumulatoren i minnet
   LDA	5xx	Henter en verdi fra minnet til akkumulatoren
   INP	901	Leser inn et heltall til akkumulatoren
   OUT	902	Skriver ut akkumulatoren

5. Hold verdien i akkumulatoren mellom -999 og 999. Bruk samme 1000-komplementregel som i hovedminnet når en regneoperasjon går utenfor dette området.

6. Kjør add.txt med inputtene 7 og 5. Programmet skal skrive ut 12 og deretter stoppe.

Tips

• Se gjerne på hvordan Programlaster er bygget opp, men dere trenger ikke endre den.
• Bruk hent_innhold og sett_innhold for all tilgang til minnet, slik at adressene alltid kontrolleres.
• Instruksjonens første siffer angir operasjonen; de to siste angir minneadressen.
• Alle instruksjonsmetodene kan bruke de samme registrene i LMC og hente data gjennom hovedminnet.
• Kontroller at programtelleren flyttes videre etter hver instruksjon, også når instruksjonen ikke endrer akkumulatoren.
• Dere kan sammenligne minnebildet med add.txt i LMC-simulatoren.
• Dere kan definere __str__(self)-metoden i Hovedminne-klassen for å printe ut innholdet med print()

Utvidelser

• Gi en tydelig feilmelding dersom dere prøver å hente eller lagre utenfor minnet, eller laster et minnebilde som ikke får plass. Dette skal resultere i at programmet avslutter.
• Python har ingen begrensning på hvor store tall kan være, men en prosessor kan jobbe med antallet siffer den har tilgjengelig. I dette tilfellet er det 3. I LMC vil tall flyte over fra 999 til -999. Lag en metode i Hovedminne-klassen som sørger for at verdiene holder seg innenfor disse grensene.
• Implementer BRA, BRP og BRZ for å hoppe til en annen minneadresse.
• Legg til OTC, som skriver ut akkumulatoren som et ASCII-tegn.
• Kjør factorial.txt og undersøk resultatet for input 5 og 7.

Fullt instruksjonssett: