GDI III
GRUNDLAGEN DER INFORMATIK - WS 12/13 TU DARMSTADT
GRUNDLAGEN DER INFORMATIK - WS 12/13 TU DARMSTADT
Kartei Details
| Karten | 50 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Grundschule |
| Erstellt / Aktualisiert | 13.03.2013 / 14.06.2016 |
| Weblink |
https://card2brain.ch/box/gdi_iii
|
| Einbinden |
<iframe src="https://card2brain.ch/box/gdi_iii/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
allgemeine Definition einer Programmiersprache
Sprache zur Formulierung von Rechenvorschriften, die direkt oder indirekt von einem Rechner ausgeführt werden kann.
indirekt soll in diesem Zusammenhang bedeuten, dass vor einer Ausführung die Rechenvorschrift noch in ein für den Rechner verständliches Format umgesetzt werden muss.
Aufgabe des Destruktor
Der Destruktor gibt den reservierten Speicher der Variablen wieder frei. Bei dem verlassen des Scopes wird der Destruktor automatisch aufgerufen.
Deklaration des Destruktors: ~Klassenname();
Eigenschaften einer Programmiersprache
- eindeutige Syntax -> zugelassene Zeichenfolgen - eindeutige Semantik -> Auswirkung des Programms auf einem Rechner
Maximal 224 = 16777216.
Wie viele Bits werden zur Kodierung minimal benötigt, wenn das zu kodierende Alphabet 715 verschiedene Zeichen umfasst
Es werden minimal 10 Bit benötigt. (29 = 512 < 715 < 1024 = 210)
Wann ist es sinnvoll, Programme direkt in Assembler (statt in C oder JAVA) zu schreiben? Nenne zwei Gründe.
Bei knappem Speicherplatz, die Antwortzeiten von großer Relevanz sind (Echtzeitsysteme), direkter Zugriff auf den Prozessor notwendig ist oder Handoptimierung gebraucht wird.
Nennen Sie drei Vorteile einer Hochsprache wie Java gegenüber Assembler.
Kontrollstrukturen sind vorhanden, besseres Code Verständnis, Datenstrukturen sind vorhanden und Typen werden überprüft.
Was ist der Hauptunterschied einer Harvard- und einer von Neumann - Architektur?
Harvard-Architektur: Programm- und Datenspeicher sind getrennte Einheiten. Programmspeicher kann auch als Nur- Lese Speicher ausgeführt sein. Effizientes Pipelining möglich. von Neumann-Architektur: Programm- und Datenspeicher sind vereint. Für die meisten heute bekannten Computer bildet diese Architektur die Grundlage.
Erklären Sie die Begriffe Register, Maschinenbefehl, Operand und Addressierungsart.
Register - Ein Speicher innerhalb der CPU. Dieser Speicher ist sehr schnell, jedoch auch limitiert. Ein Register wird in einer Assemblersprache direkt über einen Namen angesprochen, viele Operationen arbeiten nur mit Registern. Manche Register haben auch eine spezielle Bedeutung (z.B. bei arithmetischen Operationen, oder als Adresszeiger in den Hauptspeicher). Maschinenbefehl - Eine Instruktion des jeweiligen Befehlssatzes (Maschinensprache) eines Prozessors. Eine Instruktion besteht aus einem oder mehreren Bytes, die den Befehl sowie etwaige Operanden repräsentieren. Eine solche Bytefolge ist für den Menschen schwer lesbar, deswegen wird in der Assemblersprache ein Befehl durch besser verständliche Abkürzungen, sogenannte Mnemonics, dargestellt. Beispiel: movl %ebx, %eax Operand - Ein Operand ist ein Parameter eines Maschinenbefehls. Befehle können keinen, einen oder mehrere Operanden haben. Üblicherweise ist die Anzahl der Operanden bei arithmetischen und Transportbefehlen innerhalb einer Maschinensprache konstant. Ein Operand kann ein konstanter Wert, ein Register oder eine Speicherstelle im Hauptspeicher sein. Addressierungsart - Bei der Angabe einer Speicherstelle als Operand für einen Maschinenbefehl existieren unterschiedliche Möglichkeiten zur Adressierung. Die Addressierung kann • absolute (direkte Adressangabe) • indirect (Angabe eines Registers, das die Adresse enthält.) • indexed (Angabe von zwei Registern: ein Basisregister, das an den Anfang eines Speicherbereichs zeigt, sowie ein Indexregister, das den Index innerhalb des Speicherbereichs angibt.) Es existieren auch Varianten, die die Angabe eines konstanten Offsets erlauben, sowie eine Skalierung des Indexregisters (Multiplikation mit einer Konstante).
Erklären Sie den Begriff Speicheradresse.
Die einzelnen Speicherzellen eines Computers sind durchnummeriert. Eine Speicheradresse ist eine solche Nummer, mit der sich eine Speicherzelle zum lesenden oder schreibenden Zugriff identifizieren lässt. Eine Speicherzelle hat üblicherweise die Größe von einem Byte.
Wie wird ein Array in Assembler realisiert, wie wird es im Speicher abgelegt?
Im Folgenden ist beispielhaft ein Array von fünf long Werten angegeben. arrayname: .long 42, 1337, 666, 0, 1 Im Speicher wird hierzu ein Bereich von 5 4=20 Byte angelegt. An der Adresse die dieses Array spezifiziert, liegt der erste Wert. Element n liegt demnach an Basisadresse+n 4. Eine weitere Möglichkeit besteht darin einen Speicherbereich von fixer Grösse zu reservieren: arrayname: .space 1024, 0 Im Speicher wird ein Bereich von 1024 Byte angelegt und mit 0 aufgefüllt.
Erklären Sie die Funktion der Befehle call und ret und wie sie den Stack verändern
call wird benutzt um eine Funktion / ein Unterprogramm aufzurufen. Dazu wird der Instruction-Pointer (eip) auf den ersten Befehl des Unterprogramms gesetzt. Außerdem wird die Adresse des auf call folgenden Befehls auf den Stack gepusht (die Rücksprungadresse). ret ist die letzte Instruktion in einem Unterprogramm, die die Rücksprungadresse vom Stack poppt und in den Instruction-Pointer schreibt. Anschließend geht die Verarbeitung mit der Instruktion nach dem Funktionsaufruf weiter.
Erklären Sie den Unterschied zwischen logischem und arithmetischem Shiften.
Beim arithmetischen Shiften nach rechts bleibt das Vorzeichen erhalten. Beim logischen Shiften wird das Most- Significant-Bit mit 0 aufgefüllt.
Was ist ein Systemcall?
Ein Systemcall ist ein spezieller Interrupt, der das Betriebssystem darum bittet eine bestimmte Aktion auszuführen. Was genau getan werden soll, wird dabei durch Laden von definierten Werten in die Register bestimmt. Befindet sich zur Zeit des Systemcalls beispielsweise eine 1 in eax, wird das Betriebssystem angewiesen das aufrufende Programm zu beenden. Der Wert der sich in ebx befindet wird dabei als Exit-Code zurück gegeben
Listen Sie die drei gebräuchlichen Taxonomien nach Flynn auf und beschreiben Sie kurz deren wesentliche Merkmale und Unterschiede.
• SISD - Single Instruction Single Data: typisch für sequentielle Rechner (Prinzip fast aller Systeme mit einem einzelnen Prozessor bzw. einzelnen Kern) • SIMD - Single Instruction Multiple Data: Ein Instruktionsstrom wird von mehreren Prozessoreinheiten ausgeführt (Parallelverarbeitung). Früher: Vektorprozessoren (Supercomputer, z.B. Cray), heute auch in x86- Architektur zu finden (Erweiterung des Befehlssatzes um SIMD Operationen: SSE). • MIMD - Multiple Instruction Multiple Data: Mehrere Einheiten, die einen getrennten Instruktions- und Datenstrom verarbeiten, sind über eine Netzwerkstruktur miteinander verbunden. Beispiele: Mehrkern-Prozessor (Verbindung auf dem Chip), über Netzwerk verbundener Rechnercluster. quasi-uabhängige Berechnungen, üblich in Mehrkernprozessoren
Skizzieren Sie die Konventionen, die bei Unterprogrammaufrufen eingehalten werden sollten. Gehen Sie insbesondere auf die Sicherung von Registerinhalten und Variablenübergabe ein.
Das aufrufende Programm reserviert Platz auf dem Stack für Funktionsargumente und Rückgabewerte, bevor es ein Unterprogramm aufruft. Das aufgerufene Programm sichert zunächst den vorherigen Base-Pointer auf dem Stack und setzt den Stack-Pointer zu diesem Zeitpunkt als neuen Base-Pointer. Danach werden die von diesem Programm gesicherten Register auf dem Stack gespeichert, das Programm wird ausgeführt, die gesicherten alten Registerinhalte (inklusive Base-Pointer) werden zurückgeschrieben und der Rücksprung wird durchgeführt.
Beschreiben Sie kurz den Aufbau der Floating Point Unit (FPU) und erklären Sie die Arbeitsweise ihrer Operationen
Die FPU ist aus acht 80-Bit-Datenregistern, sowie drei internen 16-Bit-Registern aufgebaut. Die Datenregister sind als Stack organisiert und Operationen auf mehreren FPU-Registern werden (wenn ohne abweichende Zielangabe) Stackaufwärts durchgeführt (die Ergebnisse einer Berechnung werden in das entsprechend zuvor beschriebene FPURegister gespeichert).
Erklären Sie knapp die Funktionsweise der SSE-Shuffle-Operationen.
Der shufps mask,src,dst-Befehl (shuffle packed single) rearrangiert die Inhalte von zwei 128-bit SSE Registern (src und dst, die auch identisch sein können) zu einem neuen 128 bitWert, der in dst gespeichert wird. Rearrangiert wird nach einem 8-Bit-Code (mask) der angibt, welches Datum (32-bit float Wert) aus src und dst an welche Stelle von dst geschrieben wird. Jedes Datum wird mit 2 bit in der Maske codiert, die unteren beiden Elemente des Zielregisters (Indizes 0 und 1) werden aus dst gelesen, die oberen beiden Elemente (Indizes 2 und 3) aus src. Beispiel: shuffle-swap (vertauscht die Reihenfolge von vier elementen eines Registers) shufps $00011011, %xmm0, %xmm0 %xmm0, 128-bit Register, enthält die 4 Werte x0 mit Index 0 (Bits 0-31), x1 (Index 1, Bits 32-63), x2 (Index 2, Bits 64- 95), x3 (Index 3, Bits 96-127). Nach dem Shuffle-Befehl enthält das Register die 4 Werte in umgekehrter Reihenfolge (aufsteigender Index): x3,x2,x1,x0.
Was bewirkt eine #include-Anweisung? Ist #include Bestandteil der Programmiersprache C? Erläutern Sie
#include ist also eine Präprozessor-Direktive: Mit #include "file" wird der Inhalt der Datei ’file’ vom Präprozessor in den Quelltext eingefügt. Der eigentliche C-Compiler sieht nur den verarbeiteten Quelltext. Wie alle Präprozessordirektiven ist #include kein Bestandteil der Sprache C, wird vom Compiler also nicht verstanden..
Nennen Sie einige Unterschiede sowie Vor- und Nachteile von C/C++ gegenüber Java?
C/C++ (+/-) maschinennah (-) nicht typsicher typsicher (-) Plattformunabhängigkeit beschränkt (unterschiedliche Compiler) Explizite Freigabe dynamische allozierten Speichers Templates Expliziter Zugriff auf Speicheradressen durch Pointer Java Plattformunabhängig durch Virtual Machine Generics Garbage Collection
Was enthält x nach der Ausführung des folgenden Code-Fragments? int* x; int y = 5; x = &y;
Nach der Ausführung des Code-Fragments enthält x die Adresse von y.
Was enthält x nach der Ausführung des folgenden Code-Fragments?
int x = 3; int* y; y = &x; *y = 42;
x hat nach Ausführung den Wert 42.
Geben Sie C oder C++ Code an, der ein Array von Integern der Länge vier erstellt und dieses mit den Werten 1-4 füllt. Geben Sie dabei drei unterschiedliche Varianten an, um die Initialisierung vorzunehmen: Mit Initialisierungslisten, mit dem []-Operator und sowie mit Zeigern.
int[] a = { 1, 2, 3, 4};
int a[4]; a[0] = 1; a[1] = 2; a[2] = 3; a[3] = 4; Mit Zeigern (bewusst kompliziert) int a[4]; int* b = a; *a = 1; b += 2; *b-- = 3; *b = 2; *(++(++b)) = 4;
Warum unterteilt man einen Compiler in Front-End und Back-End?
Die lexikalische, syntaktische, und semantische Analyse sind unabhängig von der Hardware – der Front-End kann somit für verschiedene Prozessortypen wiederverwendet werden.
Compiler übersetzen Programme von einer Programmiersprache A in eine andere Programmiersprache B. Es ist jedoch oft schwierig von der Sprache B wieder in die Sprache A zu übersetzen, wenn diese mächtiger ist als B. Welche Probleme treten auf, wenn IA32 Assembler Code nach C übersetzt werden soll? Ist es überhaupt möglich in diese Richtung zu übersetzen?
Diese Richtung ist prinzipiell nicht möglich. Allein die resultierende Leserlichkeit des C-Quellcodes ist nicht gegeben und auch ausgerollte Schleifen können nicht richtig detektiert werden. Weiterhin existiert, wie auch bei der Übersetzung von Maschinencode zu IA32 Assembler, das Problem, dass Informationen über Labels und Namen nicht in der Ausgangssprache enthalten sind. Es existieren jedoch Programme, die diese Übersetzungsrichtung durch die Anwendung von Heuristiken ausführen.
Worauf bezieht sich der Begriff ’kontextfrei’ bei einer kontextfreien Grammatik?
Ein zu ersetzendes Nichtterminal steht allein (kontextfrei) auf der linken Seite jeder Ersetzungsregel.
Was beschreibt konkret ein Parse-Baum? Wie ist er aufgebaut?
Ein Parse-Baum zeigt, wie das Startsymbol einer Grammatik einen String der Sprache ableitet. Der Wurzelknoten ist hierbei immer das Startsymbol der Grammatik. Jedes Blatt wird mit einem Terminal oder mit beschriftet. Jeder innere Knoten wird mit einem Nichtterminal beschriftet. Wenn A als Nichtterminal einen inneren Knoten bezeichnet und die Kinder des Knotens von links nach rechts mit x1, x2, ..., xn bezeichnet werden, dann muss es folgende Produktion geben: A ! X1 X2 ... Xn
Weshalb werden optimierende Compiler eingesetzt? Erklären Sie ihre Funktionalität.
Ein Parse-Baum zeigt, wie das Startsymbol einer Grammatik einen String der Sprache ableitet. Der Wurzelknoten ist hierbei immer das Startsymbol der Grammatik. Jedes Blatt wird mit einem Terminal oder mit beschriftet. Jeder innere Knoten wird mit einem Nichtterminal beschriftet. Wenn A als Nichtterminal einen inneren Knoten bezeichnet und die Kinder des Knotens von links nach rechts mit x1, x2, ..., xn bezeichnet werden, dann muss es folgende Produktion geben: A ! X1 X2 ... Xn
Welche Phasen der Codeübersetzung gibt es bei einem Compiler? Geben Sie zu jeder Phase ein Beispiel an.
Ausgangspunkt ist eine Grammatik für die Quellsprache. Mit der Grammatik wird die hierarische Struktur von Programmen beschrieben. Symbole stellen dabei Sprachkonstrukte der Grammatik dar. Ein Lexikalischer Scanner liest als Eingabe einzelne Zeichen und erstellt einen Tokenstream als Ausgabe. Die Syntaxanalyse (Parsing) wird dazu verwendet, beginnend mit dem Startsymbol einer Grammatik einen String mit Terminalen abzuleiten, indemein Nichtterminal durch den Rumpf einer seiner Produktionen ersetzt wrid. Der Parser erstellt einen Parse-Baum, in dem die Wurzel mit dem Startsymbol bezeichnet wird, jeder interne Knoten einer Produktion entspricht und jedes Blatt mit einem Terminal oder dem leeren String gekenntzeichnet wird. Die Syntaktische Übersetzung erfolgt, indem den Produktionen in einer Grammatik entweder Regeln oder Programmfragmente hinzugefüt werden. Das Ergebnis der Syntaxanalyse wird als Zwischencode bezeichnet.
Was ist die Aufgabe eines Assemblers?
Ein Assembler ist ein Programm, das die Aufgabe hat Assemblercode, also Assembleranweisungen (mnemonics) in textformat, in Maschinencode (Binärdatei) zu transformieren. Dabei müssen symbolische Namen (Labels) entsprechenden Maschinenadressen zugewiesen werden, und als Ergebnis werden eine oder mehrere Objektdateien erzeugt.
Was versteht man unter einer Template-Instanziierung? Warum kann eine Templatefunktion oder -klasse erst bei Instanziierung kompiliert werden? Erläutern Sie an einem konkreten Code-Beispiel!
Templatefunktionen bzw. Klassen sind lediglich „Schablonen“, die erst durch die konkrete Angabe eines Typs in eine echte Funktion umgewandelt werden. Diesen Vorgang nennt man Template-Instanziierung. Nehmen wir als Beispiel die Templatefunktion template <class T> T max(const T& a, const T& b) { return a > b ? a : b; }. Diese kann durch den Aufruf max(a, b); instanziiert werden, wobei a und b beispielsweise Variablen des Datentyps int sind. Erst bei der Instanziierung sind für den Compiler alle notwendigen Informationen bekannt, die benötigt werden, um die Funktion zu übersetzen und entsprechenden Maschinencode zu erstellen. Man beachte, dass der Compiler zwei verschiedene Funktionen erzeugt, wenn max zweimal mit unterschiedlichen Datentypen aufgerufen wird. Darüber hinaus kann der Compiler die semantische Korrektheit des Codes erst bei der Instanziierung prüfen. Sie können max theoretisch nicht nur für primitive Datentypen, sondern auch für Klassen instanziieren. Wenn diese Klassen jedoch nicht operator> überladen, ist der Code semantisch falsch, und der Compiler wird einen Fehler melden
Was ist ein ’relocatable object file’?
Ein relocatable object file ist eine Binärdatei mit Maschinencode-Anweisungen. Die Objektdatei besteht aus mehreren sections, die neben dem Maschinencode (.text section) auch das Datensegment (.data section) sowie weitere Informationen für den Linker (symboltabelle, evtl. debugging symbole) sowie Relokationsinformation enthält. Die Adressangaben von Maschinenbefehlen (.text section) beziehen sich relativ zum Start des jeweiligen Segments in der Objektdatei. Die Relokationsinformation dient zum Anpassen der (relativen) Adressen beim Zusammenfügen von mehreren Objektdateien (daher auch der Name relocatable object file).
Was ist die Aufgabe des Linkers?
Der Linker ist ein Programm das dafür zuständig ist, mehrere relocatable object files zu einem executable object file zusammenzuführen. Dazu müssen die (relativen) Adressangaben im Maschinencode angepasst werden, die hierfür notwendige Information wird in der Objektdatei mitgeführt.
Was ist der Unterschied zwischen statischem und dynamischem Linken?
statisch: der Linker kopiert den Inhalt der Eingabe-Objektdateien in ein executable object file und passt die Adressen an. dynamisch: oft verwendeter Standard-Bibliothekscode muß nicht jedesmal in ein Programm kopiert werden (Speicherverschwendung), daher wird beim dynamischen linken nur eine Referenz auf eine Funktion in einem sogenannten ’shared object file’ eingebunden, und zur Ladezeit des Programms wird die shared-object datei in den Speicher geladen (falls notwendig, es gibt nur eine Instanz des shared object files im Speicher), und die Referenzen aufgelöst.
Nennen Sie Vor- und Nachteile von SRAM und DRAM.
SRAM Pro: schneller, kein Refresh Kontra: Benötigt mehr Platz (sechs Transistoren pro Bit), höhere Stromaufnahme DRAM Pro: hohe Datendichte, kleine Chipfläche (ein Transistor pro Bit), preiswert Kontra: langsam, benötigen Refresh
Was bedeutet dynamisches Laden zur Laufzeit?
Dynamisches laden zur Laufzeit bedeutet dass das Programm zur Laufzeit nicht aufglöste Referenzen auf ein shared object file behält, und diese erst bei Verwendung zur Laufzeit aufgelöst werden. (Anwendungsfall z.B. Browser- Plugins). Hier liefert üblicherweise das Betriebssystem die notwendige Unterstützung damit dies effizient geschehen kann.
Beschreiben Sie stichpunktartig die Kommunikation zwischen CPU und Hauptspeicher bei Lese- bzw. Schreiboperation (movl A, %eax bzw movl %eax, A) auf einem System mit einem Bus, auf dem Daten und Adressen über dieselben Leitungen verschickt werden.
Lesen 1. CPU legt Adresse auf den Bus 2. Hauptspeicher legt Daten auf den Bus 3. CPU kopiert Daten vom Bus ins Register Schreiben 1. CPU legt Adresse auf den Bus. 2. CPU legt Daten auf den Bus. 3. Hauptspeicher transferiert Daten vom Bus in den gewünschten Speicherzellen.
Beschreiben Sie die zwei aus der Vorlesung bekannten Formen von Lokalität und nennen Sie jeweils ein Beispiel!
Zeitliche (bzw. temporale) Lokalität: Nach Zugriff auf einen bestimmten Datensatz wird mit großer Wahrscheinlichkeit bald erneut darauf zugegriffen Beispiel: Schleifen Räumliche Lokalität: Nach dem Zugriff auf einen bestimmten Datensatz wird mit großer Wahrscheinlichkeit auch auf einen Datensatz zugegriffen, der in unmittelbarer Nähe im Speicher steht Beispiel: sequentielle Instruktionsfolgen, Reihen, Matrizen
Wieviele Cache Lines besitzt ein 4-fach satzassoziativer Cache mit 16 Sätzen? Wie groß (in Bytes) ist der Cache, wenn die Blockgröße 64 Bit beträgt?
16 Sätze à 4 Cache Lines = 64 Cache Lines 64 Cache Lines à 8 Byte (64 Bit) = 512 Byte
Was versteht man unter einer Daisy-Chain? Was sind die Vor- und Nachteile dieser Struktur?
Die Daisy-Chain ist eine Bus-Struktur, bei der die Master, die den Bus verwenden dürfen, eine Prioritätskette bilden. Ein größerer Abstand vom Mikroprozessor bedeutet eine niedrigere Priorität. Wenn mehrere Master den Bus über das MBRQ-Signal anfordern, wird das das Bus Grant Signal BGT vom Mikroprozessor aus durchgereicht, bis es den Master höchster Priorität mit MBRQ erreicht. Vorteile: wenige Signalleitungen, dezentrale einfache Logik, weitere Master leicht anschließbar Nachteile: Bus-Totzeiten durch Kettenlaufzeit, Aushungerung von Mastern niedriger Priorität
