Inför tenta Flashcards
Computational models:
Turing machines
o En matematisk modell som definierar en abstrakt maskin. Denna manipulerar en finit mängd symboler på en oändlig rad minne enligt en uppsättning regler. Alla algoritmer kan (om än med viss möda) simuleras med en turingmaskin. Den:
- Ställer sig över en minnescell och läser in (skannar)
- Lokaliserar inskannad symbol på en Symbol table över egendefinierade instruktioner och:
a. Skriver en symbol, siffra eller bokstav från finit mängd (om detta tillåts)
b. Flyttar läsarhuvudet till intilliggande cell höger eller vänster
c. Enligt inläst symbol och läsarhuvudets position i programmet flyttas huvudet till följande minesscell, eller avbryter.
Computational models:
RAM machines
o Hyfsat lik en Turin-maskin, men med några viktiga skillnader:
♣ Har ett minne med ”intermediate output”, behöver alltså inte gå igenom allt närliggande minne för att komma till önskad minnescell
• Varje ”memory access” tar 1 ”time step”
♣ Varje simpel operation (+,-,*,/, etc) tar 1 ”time step”
Computational architecture:
Components of a simple von Neumann computer
o CPU: Ansvarar för att utföra instruktionerna i ett program. CPU:n innehåller ALU (Arithmetic and Logic Unit), CU (Control Unit) och ett antal register.
o ALU: Aritmetiska beräkningar genomförs här (add, sub) och (and, or, not), etc.
o CU: Kontrollerar operationen av datorns ALU, minne, input/output, och berättar hur de ska svara på programinstruktioner som just lästs in. Tillhandahåller också ”klocka” och ”control signals” som andra datorkomponenter behöver.
o Buses: Sättet att flytta data från en intern komponent till en annan.
o Memory Unit: Består av RAM. Olikt en hårddisk så är detta minne även åtkomligt direkt för CPU: n.
Computational architecture:
Registers, on-chip memory, cache, memory, disk: advantages and disadvantages
o Registers: Hög-hastighetsminne. All data måste lagras här innan den kan processeras.
o On-chip memory: Lagring i processorchipet för att undvika ”latency” för viktiga data.
o Cache: Snabbare än RAM, man tar lite saker som skrivits/sparats till RAM.
o Memory/disk:
♣ Ofta en kompromiss mellan hastighet och kapacitet. Register – snabb åtkomst, liten kapacitet. Hårddisk är motsatsen. RAM är i sammanhanget någonstans mitt emellan.
Computational architecture:
Structure of machine instruction and relation to assembler instruction
o Machine instruction: Något som datorn kan förstå och översätta till konkreta handlingar, ofta unikt för varje “klass” av processorer. Ser ut som en lång sträng av tecken, där för ex. NIC varje stycke av 4 tecken representerade en instruktion. Ger konkreta instruktioner, som ”ladda register 3 med konstanten 0x2”. Rent utseendemässigt kan det se ut som “2013f002701300000010”, där varje “instruktion” är 4 tecken.
o Assembler instruction: En hyfsat gemensam syntax som kan förstås av människor (med syntax som t.ex. ”loadc r3 0x1”). Olika språk kompilerar efter sin egen grammatik till assembler. Denna översätts sedan till machine instruction.
Computational architecture:
Program alignment (ej inlagd) vs word alignment
o Word alignment: Hur instruktioner ska brytas ned i block, och hur instruktioner som är kortare eller längre ska hanteras. T.ex. i NIC att alla ”word” är 2 block och ”instruction” 4 block
Computational architecture:
Program counter, status register, and how they work in an execution
o Program counter: Pekar på nästa instruktion. Generellt så ökar den inkrementellt efter varje bearbetad instruktion, men kan modiferas på andra sätt, t.ex. genom en for-loop.
o Status register: Ställer processorn i en viss ”status” och låter en instruktion ta handling utifrån utfallet av en tidigare instruktion.
Assembler:
Assembler directives vs instructions
o Directive: Styr assemblern under ”assembly phase”, bidrar inte till storlek på programmet. Indikerar hur en operand ska behandlas t.ex.
o Instruction: Genererar maskinkod, bidrar till storleken på programmet.
Program compiled with C:
Use of stack pointers: purpose, stackframes, content of a stackframe
o Stack pointer: Litet register som sparar adressen till senast anropat program i en stack.
o Stack frame: Samling av all data i stacken som associeras med ett subprogram call. Innehåller följande:
♣ ”Return address”
♣ ”Argument variables” som skickats till stacken
♣ Lokala variabler
♣ Sparade kopior av register som ändrats av subprogrammet som behöver återställas efteråt
Program compiled with C:
Program counter vs stack pointer
o Program counter: Berättar för CPU: n var den är. Ett register som innehåller adressen till nästa instruktion.
o Stack pointer: Berättar (ungefär) var CPU: n har varit, och vad den gjort. Ett litet register som innehåller adressen till det senast använda programmet i stacken.
Representation of data:
Typed and untyped data
o Typed:
♣ Finns egenskaper och metoder som gör det lättare att använda. En viktig skillnad är att ”error checking” görs vid design/kompilering snarare än vid exekvering, genom en medföljande .xsd fil.
o Untyped:
”error checking” görs under ”run time”, men ger snabbare prestanda och kan vara lättare att administrera.
Representation of data:
Purposes of typing data
o Det ger användarvänlighet, ger förhandsinformation om tänkt funktionalitet etc.
Representation of data:
Unsigned vs signed integer datatypes. Representations of integer data types in bits and how arithmetic works and can be implemented on a bit level
o ”Signed integer” innebär att t.ex. biten längst till vänster i ett tre bit tal, 101, representerar om talet är positivt eller negativt. Alltså får man endast hälften så stora tal men de kan istället vara negativa/positiva
♣ Unsigned integer: Kan endast innehålla positiva tal (men stora)
♣ Signed integer: Innehåller såväl positiva som negativa (men mindre)
o Arithmetic on bit level: Tänk i binära tal
Representation of data:
Other common data types in programming languages, e.g., characters/ASCII or strings
o ASCII: Alla tecken konverterats till ett nummer, som enkelt kan hanteras i kod.
Adresses and pointers in assembler and C:
Pass by value vs pass by reference
o PBV: Det skickas in en kopia av parametrarna i funktionen. Ursprungsvariablen påverkas INTE av vad funktionen utför med parametrarna.
o PBR: Ett ”nickname”, eller en referens, till ursprungsvariablerna (deras lagringsplats i minnet) skickas som paramterar. Alltså påverkar funktionens lokala arbete den ursprungsliga variablen.
