Hallo Leute,
ich war heute bei der Einsichtsnahme, um meinen Test zu fotografieren. Für Lernzwecke habe ich meine Ausarbeitung "gelöscht" und bin jetzt dabei den Test korrekt auszuarbeiten. Wäre natürlich super, wenn ihr ergänzen bzw. verbessern könnt.
Link zum Vowi: https://vowi.fsinf.at/images/4/4e/TU..._C_SS2012_.pdf
LG.
Philipp
sogar die selbe gruppe wie ich!Originally Posted by Philipp H.
The Laughing Man
Beispiel 1:
a)
Netzadresse 192.168.0.0
Anzahl Hosts 2^11
Erklärung: die Netzadresse ist die erste Adresse des Subnets, und man bekommt sie durch binäre UND-Verknüpfung einer beliebigen Hostadresse des Netzes mit der Subnetmask. der Wert (255)10 in binär ist immer (1111 1111)2, was bei einer UND-Verknüpfung bedeutet, dass was immer man damit verknüpft, unverändert durchgeht, also 255&192=192, 168&255=168 usw...
Bei diesem Beispiel ist die Subnetmask (notwendig für die UND-Verknüpfung) in CIDR-Notation angeschrieben, das bedeutet die Anzahl der binären Einser am Anfang der Subnetmask wird mit einem / getrennt von der IP-Adresse angegeben, hier /21, das bedeutet 21 Einser am Anfang, und damit: 11111111.11111111.11111000.00000000
Diese Adresse in Dezimalschreibweise ist 255.255.248.0 (wiederum: 255 = 1111 1111 = erster und zweiter Teil, 248 = 1111 1000 = dritter Teil).
Die Subnetmask muss immer angegeben sein, um das Netzwerk zu identifizieren. Entweder sie steht als Dezimalkombination oder als CIDR-Notation zur Verfügung. Eine IPc4-Adresse hat immer 32 Bit (4 * 8Bit, wobei 8Bit der Bereich (0)10 bis (255)10 ist. Die größte Zahl in einer IPv4-Adresse ist also 255, die kleinste ist 0.
Die Anzahl der Hosts berechnet sich durch die Anzahl der Bits einer IPv4-Adresse (=32) abzüglich der Bits, die für die Subnetmask (und damit für die Identifizierung des Netzwerkes) verwendet werden. das Sind 32 - 21 = 11. Das Netz hat als 2^11 Hosts.
b)
Netzadresse 192::
Anzahl Hosts: 2^107
Bei diesem Beispiel ist eine IPv6-Adresse gegeben (erkennbar an den : Doppelpunkten ), und die Subnetmask wieder in CIDR-Notation /21. Eine IPv6-Adresse besteht allerdings nicht aus 32Bits sondern aus 128Bits, wodurch viel mehr Adressen möglich sind. Gleichzeitig sind die Ziffern hier keine Dezimalzahlen, sondern HEX-Zahlen.
Die Hostadresse 192:168:1::3/21 muss zuerst ins Binär-Format umgewandelt werden. IPv6-Adressen haben 128Bit, dadurch 8 Teile zu 4 Hex-Ziffern. Die gegebene Adresse ist in HEX geschrieben, weshalb jede Ziffer im Binärsystem 4 Stellen hat. Der erste Teil: (192)16 ist (0000 0001 1001 0010)2, da die führende 0 weggelassen wird, (1)16 = (0001)2, (9)16 = (1001)2 und (2)16 = (0010)2. Die gleiche Umwandlung für (168)16 gibt (0000 0001 0101 1000)2.
Das reicht schon, um die UND-Verknüpfung mit der Subnetmask durchzühren, diese war ja /21 und damit 1111 1111 1111 1111:1111 1000 0000 0000: xyz, der Rest interessiert uns nicht mehr. Durch UND-Verknüpfung der Subnetmask mit der Hostadresse erhalten wir
0000 0001 1001 0010:0000 0001 0101 1000
1111 1111 1111 1111:1111 1000 0000 0000
=================================
0000 0001 1001 0010:0000 0000 0000 0000 ... hier gehts noch weiter, ist aber alles 0, da in der Subnetmask keine Einser mehr sind...
das Ergebnis ist also: 192:0000:0000: .... Bei IPv6 dürfen zusammenhängende 0er-Blöcke weggelassen werden, dadurch reicht als Ergebnis:
192::
Die Anzahl der Hosts berechnet sich wie bei IPv4 durch Subtraktion: 128Bit von IPv6 - 21Bit Subnet = 107Bit Host-Teil. Also 2^107 Hosts.
a) 192.168.1.3/21
Netzadresse = IP & Subnet-Maske
1100 0000.1010 1000.0000 0001.0000 0011
1111 1111.1111 1111.1111 1000.0000 0000 &
------------------------------------------
1100 0000.1010 1000.0000 0000.0000 0000 = 192.168.0.0 = Netzadresse
Anzahl der Hosts: IPv4 Adresse besteht aus 32 Bit. 21 Bit Netzanteil => 32 - 21 = 11 => 2^11 Hosts
b) 192:168:1::3/21 = 0192:0168:0001:0000:0000:0000:0000:0003/21
Netzadresse = IP & Subnet-Maske = 192::
Anzahl der Hosts: IPv6 Adresse besteht aus 8x2 Hex-Tupel = 128 Bit => 128 - 21 = 107 => 2^107 Hosts
edit: da war wohl wer schneller, aber habe das gleiche ergebnis bekommen
Last edited by Philipp H.; 02-07-2012 at 18:10.
a)
Zeit F D E S 1 ADD 2 PUSH ADD 3 PUSH ADD 4 PUSH ADD 5 MULT PUSH 6 SLL MULT PUSH 7 SUB SLL MULT PUSH 8 SUB SLL MULT 9 SUB SLL 10 POP SUB 11 DIV POP SUB 12 DIV POP SUB 13 DIV POP 14 DIV 15 16
b) 14 Takte
c) 14 / 7 = 2 ns pro Insktruktion
Beispiel 2:
a)
Hier gehts um RAW-Hazards, die treten auf, wenn ein Wert gelesen wird, bevor ein laufender Schreibvorgang beendet wurde. Dadurch würde ein nicht mehr gültiger Wert ausgelesen, womit Dateninkonsistenz auftreten würde.
Es sind 7 Instruktionen gegeben, die nacheinander abgearbeitet werden sollen. Die Notation der Instruktionen sieht folgendermaßen aus:
1) welche Operation
2) welcher Datensatz dient als Ergebnis
3) welcher Datensatz ist der erste Operations-Parameter
4) welcher Datensatz ist der zweite Operations-Parameter
Manche Instruktionen, die keine Daten verändern, haben nur einen Datensatz als Parameter, etwa Push und Pop.
Man kann sich die Instruktionen wie mathematische Anweisungen vorstellen, was beim Verständnis helfen kann:
ADD R1 = R2 + R2
PUSH R1
MULT R2 = R4 * R4
SLL R1 = R4 um 1 Stelle nach links
SUB R4 = R4 - R1
POP R2
DIV R2 = R5 : R1
Betrachtet man die Operationen auf diese Weise erkennt man leicht, dass links neben dem = immer geschrieben wird, und rechts neben dem = gelesen wird, bei ADD wird also R2 (zweimal) gelesen, und R1 einmal geschrieben. Dies muss man erkennen, um zu beurteilen, wo ein Hazard auftreten kann.
In der Angabe heißt es nun, dass bei Hazard-gefährdeten Operationen ein Zeitabstand (Stall) gelassen werden soll, in dem der Schreibvorgang erledigt wird, und erst danach darf gelesen werden. Dies ist also nur bedeutend bei Operationen, die zuerst ein bestimmtes Register (R = Register) schreiben und direkt danach auslesen. Wo tritt dies auf?
1) Die Operation ADD schreibt R1, danach wird R1 gepusht. Hierbei kann ein Hazard auftreten, da Push R1 zu früh lesen könnte und dann den falschen Wert auf den Stack pusht.
2) Die Operation SLL ändert den Inhalt von R1 durch einen Shift. Danach wird von SUB R1 gelesen und in R4 geschrieben. Auch hier wird zuerst geschrieben (SLL) und direkt danach gelesen (SUB), wobe ein Hazard auftreten kann.
3) POP holt R2 vom Stack, und DIV überschreibt R2 direkt danach. Hier kann kein Hazard auftreten, da POP keine Datenänderung durchführt.
Was man nun tun muss, ist die einzelnen Instruktionen abzuarbeiten (= in die Kasteln eintragen), wobei bei kritischen Operationen ein wenig Platz gelassen werden muss, laut Angabe: "Dabei wird eine Instruktion erst dann in Stufe D verarbeitet, wenn die abhängige Instruktion Stufe S abgeschlossen hat".
Das bedeutet, eine Instruktion muss warten, wenn eine sogenannte Datenabhängigkeit (Schreib- und Lesevorgang direkt hintereinander) besteht. Das Ergebnis sieht so aus:
F D E S
1 i1 - - -
2 i2 i1 - -
3 i3 i2 i1 -
4 i3 i3 - i1
5 i3 i2 - -
6 i4 i3 i2 -
7 i5 i4 i3 i2
8 i6 i5 i4 i3
9 i6 i5 - i4
10 i6 i5 - -
11 i7 i6 i5 -
12 - i7 i6 i5
13 - - i7 i6
14 - - - i7
15 - - - -
16 - - - -
WICHTIG: es heißt, eine Instruktion wird erst in D abgearbeitet, wenn die vorige S verlassen hat. Das bedeutet, man muss die Instruktion zwar in die Spalte D eintragen, aber sie bleibt dort und wird NICHT verarbeitet (auch wenn sie drin steht). Erst wenn die vorige Instruktion S verlassen hat (also nicht mehr in der Zeile steht, wandert die nachfolgende Instruktion in die nächste Spalte E.
Zum Beispiel: es besteht eine Datenabhängigkeit zwischen i1 und i2. i1 wird Schritt für Schritt abgearbeitet, bis es in S drin steht. Danach verschwindet sie aus der Pipeline. Die nachfolgende i2 kommt in die Spalte D, bevor i1 aus S verschwunden ist, deshalb muss sie in D warten, bis i1 verschwunden ist. Dies ist erst beim Zeitpunkt 5 der Fall, das heißt zu diesem Zeitpunkt wird i2 in D verarbeitet (= noch mal in D reinschreiben) und danach in die weiteren Stufen schreiben.
b) Die CPU benötigt zur Abarbeitung der Befehlsfolge (= i1 bis i7) offenbar 14 Takte (= Zeilen 1 bis 14 sind mit Instruktionen befüllt).
c) Der Durchsatz berechnet sich durch Anzahl der Instruktionen / Sekunden die für die Abarbeitung benötigt werden. Hier sind das 7 Instruktionen in 14 Nanosekunden oder 700 000 000 Instruktionen in 1.4 Sekunden.
Beispiel 7)
Hier reicht ein einfaches Bild:
Beispiel 8)
Polling bezeichnet in der Informatik die Methode, den Status eines Geräts aus Hard- oder Software oder das Ereignis einer Wertänderungen mittels zyklischem Abfragen zu ermitteln
Das Gegenstück heißt Pushing:
Das Push-Model ist ein Pattern zur Datenübertragung bei dem der Datenlieferant die Daten überwacht. Erkennt dieser Änderungen sendet er die geänderten Werte an den Datenempfänger. Der Empfänger verhält sich passiv und wartet, nachdem er sich nach dem Publish-Subscribe Pattern angemeldet hat, auf neue Werte
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 a - - - - - - - - - - - x b x - - - - x c - - - - - - - x d x x x x - - - - - - x e x x x x f - - - - x x
Beispiel 9)
Die Exzessdarstellung ist eine Art der Zahlendarstellung im Computer im binären Format. Hierbei wird ein Zahlenbereich so dargestellt, dass negative Zahlen VOR positiven Zahlen gereiht werden. Dazu ist es nötig, einen Exzess zu jeder Zahl zu addieren, wodurch positive Zahlen größer werden und negative Zahlen positiv oder mindestens 0. Das bedeutet, der Exzess ist für alle Zahlen eines Zahlenbereiches gleich, und immer gleich mit der kleinsten negativen Zahl.
Im Beispiel haben wir einen Zahlenbereich von (-195)10 bis (+60)10. Die Zahlen haben 8 Bit.
a)
Der Exzess entspricht dem Betrag der kleinsten negative Zahl (immer). Dies ist 195. Der Exzess wird zu jeder Zahl addiert, wodurch sich die Zahlenwerte ändern:
Ohne Exzess | Mit Exzess (in Dezimal)
-195 0
-194 1
-193 2
...
-2 193
-1 194
0 195
1 196
2 197
...
59 254
60 255
Nun heißt es, man soll den Exzess in Binärdarstellung angeben, das ist einfach (195)10 als Binärzahl: (11000011)2
b)
Die Zahl 0 wird bei der Exzessdarstellung mit dem Wert des Exzesses gleichgesetzt, ist hier also (195)10 oder (11000011)2
c)
Die Zahl (-191)10 soll binär dargestellt werden. Dazu wird der Exzess (195)10 dazuaddiert, was (4)10 ergibt. Dies als Binärzahl dargestellt ist (0000 0101)2
ACHTUNG: alle Zahlen sollen mit 8Bit dargestellt werden, also ggf. mit Nullen auffüllen, bis die Zahl 8 Stellen hat.
Beispiel 6)
Ein 4-way Set-Associative Cache ist ein Cache, der aus Sets zu je 4 Blöcken besteht. Jeder dieser Blöcke hat laut Angabe 16 Byte
Man kann sich dies als Zeilen mit 4 Blöcken vorstellen, wie im Bild. Dies wird gemacht, um schneller parallel den Speicher verarbeiten zu können. Die Speicheradressen werden hierbei nacheinander in die einzelnen Cache-Blöcke gelegt, und zwar Adresse 1 in Block 1, Adresse 2 in Block 2 usw. Durch die parallele Arbeit gewinnt man an Performance.
a)
Ein Cache-Set ist also eine Zeile des Caches, bei einem 4-way Cache sind das 4 Blöcke. Laut Angabe hat der gesamte Cache 16Kbyte, ein Block hat 16Byte. Der gesamte Cache hat also 1024 (16KByte = 16384Byte / 16 Byte) Blöcke. Wenn in einer Zeile 4 Blöcke drin sind, sind das 256 Zeilen.
b) Hier wirds etwas komplizierter:
Wir wissen bereits, dass ein Cache-Block 16Byte groß ist. Daraus ergibt sich der Offset, der ist nämlich so groß, dass 16Byte einzeln (pro Byte) adressiert werden können. Das heißt, er ist 4Bit (2^4 = 16) groß.
Die Länge des Tags lässt sich anhand der Tabelle in c) ablesen. Hier sind als Tag etwa "DE0", "003", "3FF" und "7E8" aufgeführt. Dies sind offensichtlich HEX-Ziffern. Nun muss man wissen dass eine HEX-Ziffer immer 4Bit (2^4 = 16) Wertebereich hat, da sie ja 16 Zustände annehmen kann (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F). 3 HEX-Ziffern hintereinander sind also 4Bit + 4Bit + 4Bit = 12Bit. Das Tag ist 12Bit lang.
Der Index ist damit nun der verbleibende Teil der Adresse. Laut Angabe sind die Adressen 24Bit lang, der Tag 12Bit und der Offset 4Bit. Damit muss der Index 8Bit (24-12-4) lang sein.
d) fehlt
e)
Hierbei rechnet man die Anzahl der Adressen (24Bit) durch die Anzahl der Zeilen des Caches. Es gibt 2^24 Adressen und 256 Zeilen, das sind also 16777216 / 256 = 65536 oder 2^24 / 2^8 = 2^16
Last edited by wHat_Ev3r; 02-07-2012 at 18:53.
Beispiel 3)
Hier muss man beachten, welche Informationen der Angabe für die Lösung von Bedeutung sind. Bei normalem Scheduling benötigt man als Zustände NUR Ready und Running, der Rest ist EGAL. Blocked und Suspended sind nur von Bedeutung, wenn externe Ereignisse auftreten können, etwa wenn Semaphore im Spiel sind. Hierbei interessiert uns das nicht. Würde man bei diesem Beispiel an irgendeiner Stelle B oder S eintragen, wäre dies falsch.
Im Wesentlichen muss man hier zu jedem Zeitpunkt neu entscheiden, welcher Prozess an die Reihe kommt. Das Scheduling ist preemptive, das bedeutet die CPU kann einem Prozess im Status Running entzogen werden. Non-preemptive bedeutet, der Prozess nutzt die CPU solange er möchte, die kann ihm nicht von außen weggenommen werden.
Zusätzlich haben die Prozesse hier eine Priorität, wobei eine hohe Ziffer eine hohe Priorität bedeutet. Man betrachtet also einzeln jeden Zeitpunkt (=Spalte) und überlegt sich:
- Welche Prozesse sind bereits gestartet?
- Welche Prozesse sind noch nicht fertig abgearbeitet?
- Welcher dieser Prozesse hat die höchste Priorität?
Der Prozess mit der höchsten Priorität bekommt ein X, alle anderen zu diesem Zeitpunkt ein -.
Wichtig: man muss zu jedem Zeitpunkt neu beurteilen, welcher Prozess an die Reihe kommt, da wir es mit preemptive Scheduling zu tun haben.
Beispiel 2 ist falsch, du kannst zum Beispiel in der dritten Zeile PUSH bis zu D laufen lassen.
Außerdem musst du um eins länger warten, bis du nachrücken kannst.
"The only way to get rid of a temptation is to yield to it."
- Oscar Wilde
Beispiel 4)
Wir haben ein System mit 4096 Byte großen Pages und Frames, adressiert wird byteweise.
a) Wieviel Byte physischer Speicher sind im System vorhanden?
Aus der Page-Table kann man ablesen, dass im System 4 Frames existieren, da 2 Bits zum Codieren verwendet werden.
4 Frames á 4096 Byte macht 4 * 4096 = 16384 Byte physischen Speicher.
b) Auf welche Page greift die Adresse (534D)16 zu?
Aus der Page-Table erkennt man auch, dass im System 8 Pages existieren, sprich wir haben 8 * 4096 = 32768 Byte virtuellen Speicher.
Um 32768 Byte adressieren zu können brauchen wir 15 Bit, also sind unsere Adressen 15 Bit (nicht 16!) lang.
(534D)16 = (101|....)2, die Adresse greift also auf die Page 101 zu.
Wenn man sich das für alle gegebenen Adressen aufschreibt, sieht man auch, wie die dargestellte Page-Table zu Stande gekommen ist
c) Wie lautet die entsprechende physische Adresse zur (virtuellen) Adresse (534D)16?
Die physischen Adressen sind 14 Bit lang (ergibt sich aus der Größe des physischen Speichers), in der (aktuellen) Page-Table wird die Page 101 auf den Frame 00 gemapped.
Der Offset wird einfach von der virtuellen in die physische Adresse mitgenommen:
(00|0011 0100 1101)2
d) Wie verändert sich die Page-Table durch die folgenden beiden Adresszugriffe (Ersetzungsstrategie = FIFO):
(32EA)16 - (2CAC)16
(32EA)16 = (011|....)2, die Adresse greift also auf die Page 011 zu.
In der Page-Table steht aber für Page 011 und Frame 01 das Present-Bit auf 1, die Daten sind also schon da, und es passiert erstmal nichts.
Dann kommt der nächste Zugriff:
(2CAC)16 = (010|....)16
Der Eintrag für die Page 010 hat beim Present-Bit einen 0er stehen, die Daten müssen also nachgeladen werden.
Jetzt kommt die Ersetzungsstrategie zum Tragen (FIFO):
Durch die Einfügeoperationen zu Beginn des Beispiels wurden nacheinander die Frames 00, 01, 10, 11 und wieder 00 befüllt, sprich der nächste zu ersetzende Frame ist 01.
Dort liegt aber gerade unsere Page 011, für diese müssen wir also das Present-Bit auf 0 setzen und die Page-Table in Summe wie folgt anschreiben:
Page-Nr
Frame-Nr
Present-Bit
010 01 1 011 01 0
Last edited by alexhauer; 02-07-2012 at 19:35.
Die Antwort ist korrekt, aber ich bin mal so frei und löse es nochmal in etwas einfacheren Worten ;DBeispiel 6)
Ein 4-way Set-Associative Cache ist ein Cache, der aus Sets zu je 4 Blöcken besteht. Jeder dieser Blöcke hat laut Angabe 16 Byte
Man kann sich dies als Zeilen mit 4 Blöcken vorstellen, wie im Bild. Dies wird gemacht, um schneller parallel den Speicher verarbeiten zu können. Die Speicheradressen werden hierbei nacheinander in die einzelnen Cache-Blöcke gelegt, und zwar Adresse 1 in Block 1, Adresse 2 in Block 2 usw. Durch die parallele Arbeit gewinnt man an Performance.
a)
Ein Cache-Set ist also eine Zeile des Caches, bei einem 4-way Cache sind das 4 Blöcke. Laut Angabe hat der gesamte Cache 16Kbyte, ein Block hat 16Byte. Der gesamte Cache hat also 1024 (16KByte = 16384Byte / 16 Byte) Blöcke. Wenn in einer Zeile 4 Blöcke drin sind, sind das 256 Zeilen.
b) Hier wirds etwas komplizierter:
Wir wissen bereits, dass ein Cache-Block 16Byte groß ist. Daraus ergibt sich der Offset, der ist nämlich so groß, dass 16Byte einzeln (pro Byte) adressiert werden können. Das heißt, er ist 4Bit (2^4 = 16) groß.
Die Länge des Tags lässt sich anhand der Tabelle in c) ablesen. Hier sind als Tag etwa "DE0", "003", "3FF" und "7E8" aufgeführt. Dies sind offensichtlich HEX-Ziffern. Nun muss man wissen dass eine HEX-Ziffer immer 4Bit (2^4 = 16) Wertebereich hat, da sie ja 16 Zustände annehmen kann (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F). 3 HEX-Ziffern hintereinander sind also 4Bit + 4Bit + 4Bit = 12Bit. Das Tag ist 12Bit lang.
Der Index ist damit nun der verbleibende Teil der Adresse. Laut Angabe sind die Adressen 24Bit lang, der Tag 12Bit und der Offset 4Bit. Damit muss der Index 8Bit (24-12-4) lang sein.
d) fehlt
e)
Hierbei rechnet man die Anzahl der Adressen (24Bit) durch die Anzahl der Zeilen des Caches. Es gibt 2^24 Adressen und 256 Zeilen, das sind also 16777216 / 256 = 65536 oder 2^24 / 2^8 = 2^16
a.)4-Way Set bedeutet pro Set 4 Blöcke. Wir wissen, dass dein Block 16 Byte groß ist -> Setgröße = 16 Byte * 4
Wieviele Sets? Der Cache ist 16kB groß --> 16k/16*4 -> 1k/4 -> 256 Sets
b) Adresslänge 24 Bit.
Jeder Cache-Block ist 16Byte groß -> wir brauchen 4 Offset Bits (2^4=16) um jedes Byte Adressieren zu können.
Wir haben 256 Sets und müssen jedes davon adressieren -> (2^8= 256) -> 8 Index Bits.
also gehen von 24 Bit 4 für den Offset und 8 für den Index drauf, bleiben noch 12 restliche, diese sind dann der Tag.
c) Leider sieht man unten die Fragen Zwecks Hit/Miss nicht, aber auch das kann ich schnell erklären:
Wir können aus der Angabe herauslesen das es um Cache Set 8C geht. Der Offset ist uns egal --> Die ersten 3 LS(B?) der HEX Zahlen müssen so aussehen 8Cx (x... dont Care). Jetzt müssen wir nur die restlichen Teile mit unserer Tabelle vergleichen.
Hierbei gilt: Valid Bit muss auf 1 stehen. Das Dirty Bit bedeutet nur, dass etwas im Cache verändert wurde, was im Hauptspeicher noch nicht übernommen wurde. (Sollte dieser CacheBlock ausgelagert werden, werden diese Änderungen zuvor noch im Hauptspeicher durchgeführt) --> ein Zugriff auf 0038Cx wäre ein Hit.
d) Hier musste man herauslesen wie sie der Cache bei schreibzugriffen Verhält, richtige Antwort wäre CB (Copy Back), was man anhand des DirtyBits erkennt
e) Hier muss man eigentlich garnicht groß Nachdenken: Die Größte Tags gibt uns Auskunft darüber, wieviele unterschiedliche Cache Blöcke in einem Set landen können. Gefragt wurde jedoch nach der Anzahl der Adressen, also haben wir 2^12 Blöcke mal einer Größe von 2^4 -> 2^12*2^4 = 2^16
Last edited by Reaso; 02-07-2012 at 20:30.
Wer andauernd begreift, was er tut, bleibt unter seinem Niveau
ich hatte beim test bis zum sll alles richtig und daher passt es so wie es ist. man kann allerdings push auch ins d laufen lassen. im prinzip wäre ein zwischenzustand notwendig.
EDIT:
Beispiel 6 c und d durfte ich nicht fotografieren weil das MC fragen waren
Last edited by Philipp H.; 02-07-2012 at 19:35.
Beispiel 4)
Hierbei gehts um virtuelle Speicherverwaltung. Dieses System hat man eingeführt, um den gesamten Speicher eines Computers, der aus verschiedenen Geräten bestehen kann (zB Festplatten, Bandlaufwerke etc) für Programme wie einen großer Speicher aussehen zu lassen, damit sich Programmierer nicht um die genaue Adressierung kümmern müssen.
Bei der virtuellen Speicherverwaltung gibt es virtuelle und physische Adressen. Virtuelle Adressen bestehen aus (Page-Teil) und (Offset), physische Adressen aus (Frame-Teil) und (Offset). Der Offset ist bei einer virtuellen und der zugehörigen physischen Adresse GLEICH. Der Page-Teil der virtuellen Adresse wird mithilfe der Seitentabelle (=Pagetable) in den Frame-Teil der physischen Adresse umgewandelt.
Um zu wissen, wie sich eine virtuelle Adresse in Page und Offset teilt, muss man etwas herumrechnen. Zunächst der Offset: Im Beispiel ist die Page-Größe mit 4096 Byte angegeben. 1 Byte ist die kleinste Einheit, somit lässt sich der Offset direkt berechnen: 4096 = 2^12 = 12 Bit.
Bei manchen Beispielen ist die Länge der Adressen gegeben, da müsste man jetzt einfach nur noch den Offset von der Adresslänge abziehen und hätte Page-Teil oder Frame-Teil. Bei diesem Beispiel ist diese Information nicht gegeben, aber wir haben ein paar virtuelle Adressen gegeben:
(7CAD), (3252), (4341), (02A5), (534D)
Diese Adressen sind aus HEX-Ziffern zusammengesetzt. Eine Hex-Ziffer hat im Binärformat immer 4 Bit, wenn wir jetzt bereits wissen, dass der Offset 12 Bit lang ist, müssen wir nun nur noch die Anzahl der HEX-Ziffern berechnen, die darin Platz finden: 12Bit / 4Bit = 3. Das bedeutet, von einer gegebenen virtuellen Adresse sind die LETZTEN 3 Ziffern der Offset. Damit bleibt für den Page-Teil nur noch die vordere HEX-Ziffer oder im binären 4Bit.
a)
Der physische Speicher im System muss mit den physischen Adressen adressierbar sein. Die physische Adresse besteht aus Frame-Teil und Offset. Der Offset ist 12Bit (siehe oben). Der Frame-Teil lässt sich aus der Tabelle auslesen, er hat immer 2 binäre Ziffern (00, 01, 10, 11), also 2 Bit. Dadurch ergibt sich die Länge der physischen Adressen: 2Bit Frame-Teil + 12Bit Offset = 14Bit, weshalb sich 2^14 Byte (kleinste adressierbare Einheit) Speicher adressieren lassen.
b)
Wie bereits oben erklärt besteht eine virtuelle Adresse hier aus einer HEX-Ziffer Page-Teil und 3 Hex-Ziffern Offset. Die gegebene Adresse greift also auf Page Nummer (5)16 = (101)2 zu.
c)
Die Physische Adresse setzt sich aus dem Frame-Teil + Offset der virtuellen Adresse zusammen. Die Frame Nummer der Page (101)2 ist (00)2 oder (0)16, der Offset ist und bleibt (34D)16. Die physische Adresse ist (034D)16.
d)
Die Tabelle nach den Zugriffen:
Page Frame Present
010 | 01 | 1
011 | 01 | 0
Last edited by wHat_Ev3r; 02-07-2012 at 20:05.
Alles klarhat mich nur gewundert. Aber dass die letzte Spalte 1x "leer" sein muss bevor man mit dem Teil nachrückt, das abhängig ist, stimmt schon oder? (Hast du eh gemacht)
"The only way to get rid of a temptation is to yield to it."
- Oscar Wilde
a) 4096 Byte ist ein Frame Groß, laut Page Table 2 Bit für Frame Nr -> 2^2 * 4096 Byte= 16kByteBeispiel 4)
a) Wieviel Byte physischer Speicher sind im System vorhanden?
b) Auf welche Page greift die Adresse (534D)16 zu?
c) Wie lautet die Physikalische Adresse
d) Wie verändert sich die Page-Table durch die folgenden beiden Adresszugriffe (Ersetzungsstrategie = FIFO):
b) 4096 = 2^12 -> die Ersten 12 Bit (entspricht den ersten 3 HexZahlen) sind Quasi der Offset! Page Nr = 3 Bit -> 12+3 = 15 Bit
Wenn man 5 jetzt Binär darstellt und sich das erste Bit wegdenkt kommt man zum Erg 101 -> Page 101
c)Darstellung bei Pages ist immer PageNr + Offset. Damit man zu Physikalischen Addresse kommt muss man nur die Page Nr durch die Frame Nr ersetzen. -> 101 wäre Frame Nr 00-> 034D
d) Zugriff auf Page 3 -> Hit wir müssen also nichts ändern. Zugriff auf Page 5 führt zu einem Page fault -> Wir müssen oben in der Angabe schauen, was von den Vorhanden Pages zuletzt eingefügt wurde. 7 Ist momentan nicht Present, 3 ist allerdings Present. Nach Fifo würde jetzt Pages 3 ausgelagert werden (Valid Bit auf 0 setzen) und Page an der Stelle 01 eingefügt werden
Last edited by Reaso; 02-07-2012 at 19:39.
Wer andauernd begreift, was er tut, bleibt unter seinem Niveau
Hier stimme ich dir nicht zu. Die Reihenfolge war:
7CAD -> MISS -> 00
3252 -> MISS -> 01
4341 -> MISS -> 10
02A5 -> MISS -> 11
534D -> MISS -> 00 // 7CAD wurde ersetzt
----
32EA -> HIT -> 01
2CAC -> MISS -> 01 // in der aktuellen Table am längsten drinnen. 00 ist das neueste Frame wegen 534D
richtig wäre:
010 | 01 | 1
011 | 01 | 0
Beispiel 5)
Hier waren ein Speicherbereich und einige Befehle gegeben.
Adresse F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF Wert F1 10 D9 21 4F A2 F0 0 12 1E 99 78 25 11 10 16
1 SP <= FF
2 R1 <= F5
3 mem[FA] <= R1
4 mem[-SP] <= R1
5 R1 <= mem[mem[F6]]
6 R0 <= mem[SP+]
7 R1 <= mem[R0]
8 mem[R0+6] <= R1
Hier muss man zunächst mal beachten, dass es Register und den Speicher gibt. Register werden mit RX (x ... 0 oder 1) angesprochen, der Speicher immer mit memory[] oder hier mem[]. Die linke Seite einer Anweisung wird geschrieben, die Rechte gelesen, erkennbar an der Pfeilrichtung.
Schritt für Schritt:
1) SP wird mit dem WERT (nicht dem Speicher) FF überschrieben.
2) Register 1 (R1) wird mit dem Wert F5 überschrieben
3) der Speicher wird an der Stelle FA mit dem Inhalt von Register 1 überschrieben
4) der Speicher wird an der dekrementierten Stelle von SP mit Register 1 überschrieben. Achtung: Hier wird SP zwar um eins heruntergesetzt, diese Änderung wird in SP aber erst einen Zyklus später wirksam. Der Speicherzugriff ist auf (FE), SP ist in Zeile 4 aber immer noch FF, erst in Zeile 5 FE.
5) Register 1 wird überschrieben mit dem inhalt von mem[mem[F6]]. in mem[F6] steht F0 drin, und in mem[F0] steht F1 drin. In R1 steht also danach F1 drin.
6) R0 wird mit dem inkrementierten SP überschrieben. SP war an dieser Stelle FE, inkrementiert FF. Im Speicher an der Stelle FF steht F5, damit wird R0 zu F5.
7) R1 wird mit dem Speicherwert bei F5 überschrieben, das ist A2
8) Der Speicher wird an der Stelle (R0+6) mit dem Inhalt von R1 überschrieben. R0 war hier F5, 6 dazuaddiert ergibt FB, R1 hatte den Wert A2. Damit ist mem[FB] = A2.
Der resultierende Speicher:
Adresse F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF Wert F1 10 D9 21 4F A2 F0 0 12 1E F5 A2 25 11 10 F5
Die ausgefüllte Tabelle:
Befehl SP R0 R1 Speicher 1 FF 2 FF F5 3 FF F5 FA 4 FE F5 FE 5 FE F1 F6,F0 6 FF F5 F1 FF 7 FF F5 A2 F5 8 FF F5 A2 FB
Hoffe dass alles richtig ist, bei Fehlern bitte um Korrekturhinweise...
Last edited by wHat_Ev3r; 02-07-2012 at 20:07. Reason: Korrektur
müsste in Zeile 4 nicht bereits bei SP FE stehen?
jeder macht mal Fehler ;-)
stimmt, ich hatte FF und das wurde durchgestrichen, also ist es FE
ich fürchte, 2^12 stimmt nicht. mir wurde vom matiasch gesagt, dass es 2^16 ist, und so stands auch auf der musterlösung... kann mich zwar irren, bin mir dabei aber ziemlich sicher, weil ichs mir bei der einsicht noch extra notiert hatte...
Mhm ich war nicht bei der Einsichtnahme, aber wenn ich genauer darüber Nachdenke, wird die Antwort von What Ever wahrscheinlich doch stimmen, da die 2^12 Ja nur die Anzahl der Unterschiedlichen Blöcke sind die in einem Set landen und gefragt wurde nach der Anzahl der Adressen... Also sorry What_Ever hat doch gestimmt, ich hab das Beispiel nur schnell überflogenich editiere es gleich mal raus und danke für den Hinweis
Wer andauernd begreift, was er tut, bleibt unter seinem Niveau
Soweit korrekt, der Wert von R1 wird im Speicher unter der Adresse FE abgelegt.
In FF steht aber immer noch 10, in FE steht F5 (siehe Schritt 4), demnach müsste man hier doch eigentlich auf FE zugreifen, oder? Ich glaub' der Post-Dekrement Operator ist dazu da, dass man noch den alten Wert für den Speicherzugriff verwendet und dann erst den Wert erhöht (analog zum Pre-Dekrement Operator in Schritt 4).
Hatte das beim Test zumindest so und es hat gepasst.
ihr verwechselt hier virtuellem mit physischem Speicher! der physische Speicher beträgt 2^14 und setzt sich zusammen aus 12bit Offset + 2bit für die Addressierung der frames!
Foliensatz 21 Seite 27
... Ja Tut er, der Offset ist beim Virtuellen und beim Physikalischen Speicher gleich. Ich versteh deinen Einwand nicht so ganz? Bei diesem Beispiel ist die Frage: Auf welche Page greift die Adresse (534D)16 zu?
Nachdem die ersten 12 Bit (die ersten 3 Hexzahlen) mit obriger Begründung den Offset bilden, kann für die PageNr nur noch die 5 Stehen.... Und falls das dein Einwand war, es kann sich hier Offensichtlich NUR um eine Virtuelle Adresse handeln, da du die 5 mit 2 Bit ja garnicht darstellen kannst.
Man wählt beim Paging immer die Darstellungs Form : PageNr + Offset aus einem sehr einfachen Grund: Wenn man zur Physikalischen Adresse möchte, muss man nur die PageNr durch die FrameNr ersetzen. Die Frage bei diesem Beispiel war allerdings noch nicht die Physikalische Adresse sondern nur auf welche der 8 Pages zugegriffen wird.
Last edited by Reaso; 03-07-2012 at 09:05.
Wer andauernd begreift, was er tut, bleibt unter seinem Niveau
hab deine Argumentation weiter oben falsch interpretiert, da dort 2^15 gestanden ist. habe gedacht du beziehst die 2^15 auf den physischen Speicher.
ah, shit... hier stand blödsinn, aber jetzt habe ich etwas anders to sagen/fragen.
ad Bsp 6)
Ein set assoziative cache verwendet keinen index. Es verwendet nur [[Tag][Set][Offset]] (nach folien).
Ein cache set wird immer durchgesucht für ein tag und es ist auch notwendig ein Replacement Algorithmus zu implementieren.
wie kann ein Indexlänge > 0 gerechnet werden?
Last edited by TLM; 03-07-2012 at 14:26.
The Laughing Man
mit index ist wsl set gemeint....
Richtig, der Index gibt bei einem Direct Mapped Cache den Block und bei einem n-way Set Associative Cache das Set an, mit Ausnahme eines Full-Associative Cache, dort gibt's nämlich nur ein Set und man braucht keinen Index (gibt also nur Tag und Offset).
mit 4 sets braucht man nur 2 bits um die sets zu codieren.
Ich habe 2 hingeschrieben, und keine punkte dafür bekommen.
The Laughing Man
4-way bedeutet dass jedes set 4 Blöcke enthält
Wer andauernd begreift, was er tut, bleibt unter seinem Niveau
ich habe bei dem befehl 6 die adressierung/speicher F5 ,da es ein postinkrement ist und wird erst beim naechsten befehl um 1 erhöht .
kann jemand das bestaetigen?
Last edited by mrbadmad; 20-01-2013 at 13:46.
Posting Permissions
Reply With Quote
Bookmarks