Kapitel 6

Technische Informatik 1
6 – Speicherhierarchie
© Lothar Thiele
Computer Engineering and Networks Laboratory
Arbeitsprinzipien
6 ‐ 2
Übersicht Speicherhierarchie
Ziele:
 Dem Benutzer möglichst viel Speicherkapazität zur Verfügung stellen.
 Möglichst kleine Zugriffszeit.
 Möglichst kostengünstig.
SSD (solid state drive)
HDD (hard disk drive)
Zugriffszeit 0.25‐0.5ns 0.5‐2.5ns 50‐70ns 0.1‐20ms
Grösse
~ 1kByte ~ 16MByte ~ 32GByte ~ 1000GByte
Kosten/Mbyte
0.5 – 1.0$ 0.01–0.02$ 0.00005–0.0005$
6 ‐ 3
Plattenspeicher (Hard Disk Drive)
6 ‐ 4
DRAM Architektur
DRAM
(dynamisch)
SRAM (statisch)
6 ‐ 5
Technologische Trends
DRAM (dynamic random access memory) Speicherbausteine:
 Zugriffszeit sinkt mit etwa 6% pro Jahr
 Speicherkapazität steigt mit etwa 45% pro Jahr
6 ‐ 6
Technologische Trends
Zugriffszeit DRAM vs. Zykluszeit Prozessor
Lücke
6 ‐ 7
Ebenen der Speicherhierarchie
verantwortlich für Übertragung
Blockgrösse
Zugriffszeit
Cache Architektur
schneller
Programm, Compiler
1‐8 Bytes, 1 Taktzyklus
Cache Steuerung (Hardware)
16‐128 Bytes, 10‐1000 Taktzyklen
Hauptspeicher
Betriebssystem (Software)
4000 ‐ 64000 Bytes, 10M‐100 M Taktzyklen
sekundärer Speicher
Anwendungsprogramm (Software)
Mbytes, ‐
virtueller Speicher
CD/DVD/Magnetband
grösser
6 ‐ 8
Lokalität
Die Effizienz der hierarchischen Speicherarchitektur basiert auf dem Prinzip der Lokalität:
 Programme greifen in einem kleinen Zeitintervall auf einen relativ kleinen, noch nicht referenzierten Teil des Adressraumes zu. Dies gilt sowohl für Instruktionen als auch für Daten.
 Es werden zwei unterschiedliche Arten der Lokalität unterschieden:
 Zeitliche Lokalität: Falls ein Datum oder eine Instruktion referenziert wird, so wird sie bald wieder referenziert.
 Örtliche Lokalität: Falls ein Datum oder eine Instruktion referenziert wird, werden bald Daten oder Instruktionen mit nahgelegenen Adressen referenziert.
6 ‐ 9
Lokalität
 Zeitliche Lokalität: Falls ein Datum oder eine Instruktion referenziert wird, so wird sie bald wieder referenziert. Speichern von kürzlich benutzten Informationen näher am Prozessor, d.h. in einer oberen Ebene.
 Örtliche Lokalität: Falls ein Datum oder eine Instruktion referenziert wird, werden bald Daten oder Instruktionen mit nahgelegenen Adressen referenziert.
Bewege Blöcke aus aufeinanderfolgenden Daten näher zum Prozessor, falls eines von Ihnen benutzt wird.
6 ‐ 10
Arbeitsprinzipien
 Daten werden nur zwischen aufeinanderfolgenden Ebenen kopiert.
 Übertragungseinheit oder Blockgrösse (z.B. Datenblock, Seite): Die kleinste Informationseinheit, die in den zwei benachbarten Hierarchieebenen vorhanden oder nicht vorhanden sein kann.
 Beispiel: Cache / Hauptspeicher
Adresse
Prozessor
Daten (schreiben)
Daten (lesen)
6 ‐ 11
Arbeitsprinzipien
1. Datenanfrage an die obere Ebene.
2. Feststellen in der oberen Ebene, ob die gesuchten Daten vorhanden sind


Treffer (hit): Daten sind in der oberen Ebene vorhanden
Fehlzugriff (miss): Daten müssen durch eine Datenanfrage aus der nächst unteren Ebene besorgt werden.
3. Weiterleiten der gesuchten Daten an die anfragende Ebene.
Cache
virtueller Speicher
6 ‐ 12
Terminologie
 Hit‐Rate: Relativer Anteil der Speicherzugriffe, die in der oberen Ebene erfolgreich sind.
 Hit‐Zeit: Zugriffszeit zur oberen Ebene:
Hit_Zeit = Zugriffszeit + Zeit_zur_Bestimmung_von_hit_miss
 Miss‐Rate: Relativer Anteil der Speicherzugriffe, die in der oberen Ebene nicht erfolgreich sind:
Miss_Rate = 1 ‐ (Hit_Rate)
 Miss‐Strafe:
Miss_Strafe = Zeit_zum_Finden_eines_Blocks_in_der_unteren_Ebene
+ Zeit_zum_Übertragen_zur_oberen_Ebene
 Mittlere Zugriffszeit: Mittlere_Zugriffszeit = Hit_Zeit + Miss_Strafe ∙ Miss_Rate
6 ‐ 13
Implementierungsalternativen
Wo kann ein Block platziert werden, wie wird er gefunden ?
 direkte Abbildung
 teilassoziativ
 vollassoziativ
Welcher Block sollte bei einem Miss ersetzt werden ?
 zufällig
 am längsten unbenutzt
Was geschieht beim Schreiben eines Blocks ?
 durchgängiges Schreiben
 zurückkopieren
6 ‐ 14
Cache Architekturen
6 ‐ 15
Direkte Abbildung
5 Bit lange Speicheradresse [4 … 0] : 32 Daten im Hauptspeicher
Teiladresse [2 … 0] : Cache Index (Adresse im Cache Speicher)
Teiladresse [4 … 3] : Cache Tag (Marke zur Identifikation der Datenadresse)
6 ‐ 16
Direkte Abbildung
6 ‐ 17
Beispiele direkte Abbildung
Cachegrösse:
 Wie gross ist ein direkter Cache für 64 kByte Nutzdaten, Blockgrösse = 1 Wort = 4 Byte, byteweise Adressierung, Adresslänge 32 Bit?
 64 kByte = 216 Byte = 214 Worte
Cachegrösse = 214 (32 + (32 ‐ 2 ‐ 14) + 1) Bit = 803 kBit  100 kByte
Beispiel: Zugriffssequenz (8 Cacheblöcke, 32 Speicherblöcke):
6 ‐ 18
Beispiele direkte Abbildung
6 ‐ 19
Vergrösserung der Blockgrösse
Cacheblock: Cachedaten, die ihren eigenen Tag besitzen.
Vergrösserung der Blockgrösse:
 Vorteile: Ausnutzung der örtlichen Lokalität sowie effizientere Speicherung.
 Nachteile: weniger unabhängige Cacheblöcke im Cache und höhere Miss‐Strafe (Zeit zum Ersetzen eines Blocks ist grösser)
Speichergrösse:
 L Bit breite Adresse, byteweise Adressierung, Cache mit 2N Byte Nutzdaten, 2M Byte pro Block
 Teiladressen: [L‐1 … N] Tag, [N‐1 … M] Cache Index, [M‐1 … 0] Block+Byte offset
 Cachegrösse: (1 + (L‐N) + 82M)  2(N‐M) Bit = 2N Byte + (1 + L – N)  2(N‐M) Bit
6 ‐ 20
Vergrösserung der Blockgrösse
Diagramm eines Caches mit direkter Abbildung, 16 kByte Nutzdaten, Blockgrösse 16 Worte, byteweise Adressierung, 32 Bit Adresslänge: 6 ‐ 21
Vergrösserung der Blockgrösse: Vorteile und Nachteile
Grosse Blöcke nutzen die örtliche Lokalität besser. Auf der anderen Seite gibt es bei grossen Blockgrösse nur wenige Blöcke im Cache. Programme arbeiten nicht nur auf nebeneinanderliegenden Daten (Datencache) und springen auch zwischen verschiedenen Softwarekomponenten (Instruktionscache).
6 ‐ 22
Assoziativer Cache
Probleme bei direkter Abbildung:
 Häufiger Miss aufgrund eines Konfliktes (mehrere Speicherblöcke werden auf einen Cacheindex abgebildet).  Ungünstige festgelegte Ersetzungsstrategie bei einem Miss.
 Abhilfe: grösserer Cache oder mehrere Einträge pro Index (assoziativer Cache).
Assoziativer Cache:
 K Einträge pro Index (K‐fache Assoziativität), K direkte Caches arbeiten parallel
 Der Cacheindex selektiert eine Menge von Blöcken, die Tags werden mit dem entsprechenden Adressanteil parallel verglichen, die Daten werden entsprechend dem Resultat des Vergleiches selektiert.
6 ‐ 23
Vergleich von Cachestrukturen
1‐fach assoziativ
2‐fach assoziativ
4‐fach assoziativ
8‐fach assoziativ
vollassoziativ
6 ‐ 24
Diagramm eines teilassoziativen Caches
6 ‐ 25
Vorteil der Assoziativität
6 ‐ 26
Ersetzungstrategien
Direkte Abbildung:
 Jeder Speicherblock kann nur auf einen Cacheblock abgebildet werden ‐> keine Auswahl möglich
Assoziativer Cache:
 Jeder Speicherblock kann auf einen von K Cacheblöcken abgebildet werden; bei vollassoziativem Cache: in irgendeinen Cacheblock.
Einige Ersetzungsstrategien:
 Zufällige Auswahl des zu ersetzenden Blocks.
 Der am längsten unbenutzte Block wird ersetzt. Hardware speichert die jeweiligen Zugriffszeiten und ermittelt den ältesten Block (aufwändig).
6 ‐ 27
Schreibalternativen
Was passiert beim Schreiben vom Cache? Wie werden Informationen im Cache und im Hauptspeicher konsistent gehalten?
Zurückkopieren („write back“):  Prozessor schreibt nur in den Cache; falls der Block bei einem Miss ersetzt wird, wird er in den Hauptspeicher kopiert.
 Ein “dirty bit” für jeden Cacheblock zeigt an, ob der Block zurückkopiert werden muss.
 Aufwändige Steuerung aber kleiner Bandbreitenbedarf zwischen Hauptspeicher und Cache.
 Schreibgeschwindigkeit richtet sich nach der des Caches und nicht des Hauptspeichers.
 Cache und Hauptspeicher können für lange Zeit inkonsistent sein (problematisch für Ein/Ausgabe von Daten und Mehrprozessor‐ und Multicoresysteme).
6 ‐ 28
Schreibalternativen
Durchgängiges Schreiben („write through“):  Mit jedem Schreibvorgang wird auch der Hauptspeicher beschreiben.
 Verlieren wir nicht den Vorteil eines Caches?
 Verwendung eines Pufferspeichers zwischen Prozessor und Speicher: Prozessor schreibt in Cache und Pufferspeicher; Pufferspeicher wird kontinuierlich in den Hauptspeicher übertragen.
 Voraussetzung: mittlere_Speicherrate < 1/Hautpspeicher_Schreibzykluszeit
Prozessor
Cache
Hauptspeicher
Puffer
6 ‐ 29
Cache Architekturen ‐ Leistungsberechnungen
6 ‐ 30
Leistungsberechnungen
Grundlegende Gleichungen:
CPU_Zeit = (CPU_Instruktionszyklen + CPU_Wartezyklen)∙Taktperiode
CPU_Wartezyklen = Lese_Wartezyklen + Schreib_Wartezyklen
Lese_Wartezyklen = Leseinstruktionen/Programm ∙ Lese_Miss_Rate ∙ Lese_Miss_Strafe/Taktperiode
Schreib_Wartezyklen = (Schreibinstruktionen/Programm ∙ Schreib_Miss_Rate ∙ Schreib_Miss_Strafe/Taktperiode) + Schreibpuffer_Wartezyklen
Vereinfachte Gleichung:
CPU_Wartezyklen = Speicherinstruktionen/Programm ∙ Miss_Rate ∙ Miss_Strafe/Taktperiode + Instruktionen/Programm ∙ Miss/Instruktion ∙ Miss_Strafe/Taktperiode
Datencache
Instruktionscache
6 ‐ 31
Beispiel
Gegeben:
Für ein bestimmtes Programm sind 33% aller Instruktionen Speicherinstruktionen, Miss‐Rate bei Instruktionen 5%, Miss‐Rate bei Daten 10%, CPIperfekt = 4, Miss_Strafe/Taktperiode 12 Zyklen.
Frage: Um wieviel schneller wäre ein Rechner mit perfektem Cache?
Antwort:
Instruktions_Wartezyklen = Instruktionen ∙ 5% ∙ 12 = 0.6 ∙ Instruktionen
Daten_Wartezyklen = Instruktionen∙33%∙10% ∙ 12 = 0.4 ∙ Instruktionen
Wartezyklen = 1.0 ∙ Instruktionen
CPIwarten = (4 + 1) Zyklen/Instruktion
CPU‐Zeit mit perfektem Cache ist um Faktor 5/4 besser.
6 ‐ 32
Beispiel
Gegeben sind die gleichen Randbedingungen wie zuvor.
Frage:
Wie steigt die Leistung des Rechners bei K‐facher Taktrate.
Annahme: Speicher wird nicht schneller.
Antwort:
Wartezyklen = K ∙ 1.0 ∙ Instruktionen = K Instruktionen
CPIschnell = (4 + K) Zyklen/Instruktion
CPU_Zeitlangsam / CPU_Zeitschnell =
(Instruktionen∙CPIwarten∙Taktrate) / (Instruktionen∙CPIschnell∙Taktrate / K)
= K ∙ 5/ (4 + K)
Beispiel: K = 6, Beschleunigungsfaktor = 3
6 ‐ 33
Mehrere Cacheebenen
L1 Cache:
 klein,  schnell, möglichst kleine Hit_Time
L2 Cache:
 behandelt Misses vom L1 Cache
 grösser als L1, langsamer als L1, schneller als Hautspeicher
 möglichst kleine Miss_Rate um Hauptspeicherzugriff zu vermeiden
L3 Cache:
 findet sich vor allem in Multicore‐Prozessoren
6 ‐ 34
Mehrere Cacheebenen
Berechnungsbeispiel:
 nur Instruktions‐Cache (in diesem Beispiel)
Taktrate 4 GHz; CPI = 1 (mit perfekten Caches); L1 Miss_Rate = 2%
Zugriffszeit L2 Cache = 5ns ; L2 Miss_Rate = 10 %
Zugriffszeit Hauptspeicher = 100ns
 Mit L1 Cache:  Miss_Strafe/Taktperiode = 100ns/0.25ns = 400 Zyklen
 CPI = 1 + 0.02 ∙ 400 = 9
 Mit L1 und L2 Cache:
 L1 Miss mit L2 Hit: Miss_Strafe/Taktperiode = 5ns / 0.25ns = 20 Zyklen
 L1 Miss mit L2 Miss: Miss_Strafe/Taktperiode = 105ns / 0.25ns = 420 Zyklen
 CPI = 1 + 0.02 ∙ 0.9 ∙ 20 + 0.02 ∙ 0.1 ∙ 420 = 2.2
6 ‐ 35
Speicher und Bus
Die Kombination von Speicherarchitektur und Bussystem kann die Systemleistung stark beeinflussen.
6 ‐ 36
Speicher und Bus
Annahmen:
 1 Buszyklus zum Übertragen der Adresse
 15 Buszyklen für jeden Hauptspeicherzugriff
 1 Buszyklus pro Datentransfer
Beispiel 1 (Organisation a.):
 Blockgrösse 4 Worte, Speicher‐ und Busbreite 1 Wort
 Miss_Strafe = (1 + 4 ∙ 15 + 1) Buszyklen = 62 Buszyklen
•15 Zyklen
•15 Zyklen
•15 Zyklen
•15 Zyklen
 Bandbreite = [(4 ∙ 4) / 62] Bytes/Zyklus = 0.258 Bytes/Zyklus
Zeit
6 ‐ 37
Speicher und Bus
Beispiel 2 (Organisation b.):
 Blockgrösse 4 Worte, Speicher‐ und Bus‐Breite 4 Worte
 Miss_Strafe = (1 + 15 + 1) Buszyklen = 17 Buszyklen
 Bandbreite = (4 ∙ 4) / 17 Bytes/Zyklus = 0.94 Bytes/Zyklus
Beispiel 3 (Organisation c.):
 Blockgrösse 4 Worte, 4 Speicherbänke mit einer Breite von je einem Wort, Busbreite 1 Wort
 Miss_Strafe = (1 + 15 + 4) Buszyklen = 20 Buszyklen
 Bandbreite = (4 ∙ 4) / 20 Bytes/Zyklus
•15 Zyklen
= 0.8 Bytes/Zyklus
•15 Zyklen
•15 Zyklen
•15 Zyklen
6 ‐ 38
Speicherhierarchie Beispiel
Intel i7 920 Prozessor:  Grösse 13.5 x 19.6 mm, 731 Millionen Transistoren.  4 Prozessorkerne mit jeweils  32 KB L1 Instruktions‐ und 32 KB L1 Daten‐Cache  sowie einem 512 KB L2 Cache.  Die 4 Prozessorkerne teilen sich einen gemeinsamen 8 MB L3 Cache.
6 ‐ 39
Speicherhierarchie Beispiel
6 ‐ 40
Cache Kohärenz
6 ‐ 41
Cache Kohärenz
Inkohärente Daten in Caches und Hauptspeicher:
 Problem bei Multiprozessorsystemen mit gemeinsamem Speicher, z.B. Multicoresystemen.
6 ‐ 42
Cache Kohärenz
6 ‐ 43
Cache Kohärenz
6 ‐ 44
Cache Kohärenz
1. Falls ein Prozessor P den Inhalt einer Speicherzelle X liest, nachdem er sie mit dem Wert w beschrieben hat, dann ist der gelesene Wert w, sofern die Speicherzelle in der Zwischenzeit nicht durch einen anderen Prozessor beschrieben wurde.
2. Falls ein Prozessor P den Inhalt einer Speicherzelle X zur Zeit t1 liest, nachdem ein anderer Prozessor die Speicherzelle mit dem Wert w zur Zeit t0 beschrieben hat, dann ist der gelesene Wert w, sofern t1‐t0 genügend gross ist, und die Speicherzelle in der Zeit zwischen t0 und t1 nicht neu beschrieben wurde.
3. Alle Prozessoren beobachten die gleiche Reihenfolge zweier Schreibbefehle auf die gleiche Speicherposition.
6 ‐ 45
Cache Kohärenz: Snooping Protokoll
Alle Prozessoren beobachten Datenübertragungen zwischen jedem Cache und dem gemeinsamen Speicher.
6 ‐ 46
Cache Kohärenz: Snooping Protokolle
 Erweiterung der Status‐Bits jeder Cachezeile.
 Zusätzliche Cache‐Controller, die das jeweilige Cachekohärenz‐Protokoll implementieren.
 Zur Vermeidung von Zugriffskonflikten zwischen CPU und Bus werden Adressen‐
Tags und Status‐Bits dupliziert (Snoop tag).
 Protokolle werden üblicherweise durch endliche Automaten dargestellt. Die Zustände sind den Cachezeilen zugeordnet und repräsentieren die aktuelle Situation.
 Protokollbeispiele:  Write invalidate für „write through“
 Write invalidate für „write back“
 MESI (Modified, Exclusive, Shared Invalid) für „write back“
6 ‐ 47
Cache Kohärenz: Write invalidate/Write through  Das Zustandsdiagramm ist auf eine Cachezeile von Prozessor P bezogen. Speicherung des Zustands durch ein Bit pro Cachezeile.
RM
verursacht durch
Zugriff auf einen
anderen Cache
(remote cache)
invalid
RH
WM
RM
valid
RH: RM: WH: WM: SHW: Read Hit
Read Miss
Write Hit
Write Miss
Snoop Hit on Write
Cache Line Fill
Write Cache and Memory SHW
WH
WM
Auffüllen der Cachezeile
aus dem Hauptspeicher
Speichern in die Cachezeile
und in den Hauptspeicher
Block, in den von einem anderem
Prozessor geschrieben wird,
ist in der Cachezeile
6 ‐ 48
Cache Kohärenz: MESI
Weit verbreitetes Write Invalidate Protokoll für Zurückkopieren (write back): MESI (Modified, Exclusive, Shared, Invalid).
 Modified: Es gibt nur eine Cachekopie mit Schreibberechtigung, Cacheinhalt stimmt nicht mit Hauptspeicher überein.
 Exclusive: Es gibt nur eine Cachekopie mit Schreibberechtigung, Cacheinhalt stimmt mit Hauptspeicher überein.
 Shared: Kein Prozessor hat Schreibberechtigung, Cacheinhalt stimmt mit Hauptspeicher überein.
 Invalid: Jeder Zugriff führt zu einem Miss.
6 ‐ 49
Cache Kohärenz : MESI
 Zustände einer Cachezeile:
6 ‐ 50
Cache Kohärenz : MESI
 Read Hit: Lokale Operation
 Read Miss: Prozessor signalisiert Read Miss auf dem Bus und initiiert einen Lesevorgang aus dem Hauptspeicher.
 Falls der Block in einem anderen Prozessor exclusive ist, wird er in beiden Prozessoren zu shared.
 Falls der Block in anderen Prozessoren shared ist, wird er in allen diesen Prozessoren zu shared.
 Falls der Block in einem anderen Prozessor modified ist, wird er zunächst in den Hauptspeicher geschrieben und dann in beiden Prozessoren zu shared.
 Falls der Block in keinem anderen Prozessor ist, wird er zu exclusive. 6 ‐ 51
Cache Kohärenz : MESI
 Write Hit:
 Falls der Block shared ist, geht er in modified über. Hierzu signalisiert er „intent‐to‐
modify“ und alle Prozessoren invalidieren den Block.
 Falls der Block exclusive ist, wird der Cache beschrieben und auf modified
geändert.
 Falls der Block modified ist, wird der Cache beschrieben.
 Write Miss:  Der Prozessor signalisiert zunächst „intent‐to‐modify“.
 Falls der Block in einem anderen Prozessor modified ist, wird er von ihm zunächst in den Hauptspeicher geschrieben und dann zu invalid.
 Falls der Block in anderen Prozessoren shared oder exclusiv ist, wird er in diesen Caches zu invalid.
 Anschliessend wird der Block in den Cache geschrieben und zu modified.
6 ‐ 52
Cache Kohärenz : MESI
•Lokale Cache Operationen
RMS
RMS
RH
Block ist in keinem
anderen Cache
shared
invalid
RME
RME
WH
RMS
WM
WM
RMS
RME
exclusive
RH:
RMS:
RME:
WH:
WM:
SHW:
SHRM:
Block ist in einem anderen
Cache “exclusive”, “modified”
oder “shared”.
Read Hit
Read Miss Shared
Read Miss Exclusive
Write Hit
Write Miss
Snoop Hit on Intent-to-Modify
Snoop Hit on Read Miss
Cache Line Fill
Line Copyback
Intent-to-Modify
WH
WM
WM
modified
WH
RH
RH
RME
6 ‐ 53
Cache Kohärenz : MESI
•Remote Cache Operationen
SHW
shared
invalid
SHW
SHRM
SHRM
SHW
exclusive
RH:
RMS:
RME:
WH:
WM:
SHW:
SHRM:
Read Hit
Read Miss Shared
Read Miss Exclusive
Write Hit
Write Miss
Snoop Hit on Intent-to-Modify
Snoop Hit on Read Miss
Cache Line Fill
Line Copyback
Intent-to-Modify
modified
6 ‐ 54
Virtueller Speicher
6 ‐ 55
Prozess
«Prozess»: Die Instanz eines Programms (oder eines Teils davon), die vom Prozessor zu einem gewissen Zeitpunkt mit konkreten Eingabedaten ausgeführt wird. Ein Prozess besteht aus dem zugehörigen Programm‐Code sowie dem
derzeitigen Zustand.
7FFF FFFFhex
Stack Eigenschaften:
 Ein Prozess hat seinen eigenen privaten Adressraum.
 Zu seinem Zustand gehören zum Beispiel die Prozessor‐Register, der Programmzähler und Daten.
 In Kapitel 7 werden wir uns genauer mit der (quasi)‐parallelen Abarbeitung
mehrerer Prozesse beschäftigen.
Dynamic data
Static data
0000 0000hex
Text typischer Adressraum eines Prozesses
6 ‐ 56
Gründe für die Verwendung virtueller Speicher
1. Manche Prozesse passen einschliesslich ihrer Daten nicht in den Hauptspeicher. 2. Viele Betriebssysteme erlauben die (quasi) gleichzeitige Ausführung mehrerer unabhängiger Prozesse, die jeweils ihren eigenen Adressraum (Bereich der Speicheradressen, auf die der Prozess zugreifen kann) haben.  Falls nur ein Prozess den Hauptspeicher besetzt, kann ein Prozesswechsel zu erheblichen Startzeiten (Zeit, bis die erste Instruktion ausgeführt wird) führen.
 Damit alle Prozesse in den Hauptspeicher passen, müsste er sehr gross sein.
 Der Adressraum eines Prozesses sollte vom Zugriff anderer Prozesse geschützt werden (unabhängige Adressräume).
6 ‐ 57
Virtueller Speicher ‐ Grundprinzipien
6 ‐ 58
Grundprinzip
Adressraum
aus der Sicht
eines Prozesses
virtuelle
Seite
Adressraum aus der Sicht
von Hauptspeicher und
sekundärem Speicher
Jeder Prozess hat
seine eigene, private
Adressübersetzung
physikalische
Seite
6 ‐ 59
Virtueller Speicher vs. Cache
Cache
 Die verschiedenen Cacheblöcke gehören üblicherweise zum gleichen Prozess.
 Cache‐Misses werden von der Hardware gelöst.
Virtueller Speicher
 Ein Speicherblock wird als Seite (page) bezeichnet, ein Miss als Seitenfehler (page
fault).
 Ein Prozess kann quasi gleichzeitig mit anderen Prozessen ausgeführt werden. Prozesse haben voneinander unabhängige virtuelle Speicherbereiche.
 Die Adressumsetzung (virtueller auf physikalischer Adressraum) erfolgt durch Hardware und Software.
 Seitenfehler werden über Software gelöst.
6 ‐ 60
Adressabbildung
Abbildung von virtueller Seite
auf physikalische
Seite.
Seitengrösse 212 Byte = 4 KByte
maximale Zahl physikalischer Seiten 218
maximale Zahl virtueller Seiten 220;
Adressierung innerhalb
einer Seite
adressierbarer physikalischer Speicher 1 GByte
Grösse des virtuellen Adressraums 4 GByte
6 ‐ 61
Implementierungsalternativen
Wo kann ein Block platziert werden, wie wird er gefunden ?
 Üblicherweise vollassoziative Platzierung da die Kosten zur Beseitigung eines Seitenfehlers sehr hoch sind (10 – 100 Millionen Taktzyklen).
 Auffinden einer Seite im Hauptspeicher erfolgt üblicherweise über eine Tabelle (Seitentabelle), die virtuelle auf physikalische Adressen abbildet.
 Jeder Prozess besitzt seine eigene Seitentabelle.
Welcher Block sollte bei einem Miss ersetzt werden ?
 Üblicherweise LRU (least recently used, am längsten unbenutzt) oder eine Annäherung mit weniger Speicher‐ und Rechenaufwand.
Was geschieht beim Schreiben eines Blocks ?
 Zurückkopieren, da das Schreiben in den sekundären Speicher zu lange dauert und zudem Seitenfehler im Vergleich zu Cache‐Misses selten sind.
6 ‐ 62
Seitentabelle
Zeiger auf die Seitentabelle des
derzeit ausgeführten Prozesses.
zumindest ist
noch ein “dirty bit” notwendig
Jeder Prozess besitzt seine eigene
Seitentabelle. Zunächst gehen wir davon aus, dass die Seitentabellen im Hauptspeicher
gespeichert sind.
Im Beispiel besitzt eine Seitentabelle
220 Einträge.
Eine Zeile der Seitentabelle enthält
üblicherweise noch Bits, die
Informationen über Zugriffsrechte
enthalten.
6 ‐ 63
Seitenfehler
Wie wird ein Seitenfehler erkannt?
 Das Valid‐Bit in der Seitentabelle ist ‘0’.
 Eine Unterbrechung des Prozessablaufs wird erzeugt und die Kontrolle an das Betriebssystem übergeben. Es ist verantwortlich für die gesamte Prozessorganisation und somit auch für die Organisation des virtuellen Speichers.
Wo ist die Seite im sekundären Speicher?
 Betriebssystem unterhält eine Datenstruktur, in der diese Information enthalten ist. Diese Information kann auch in die Seitentabelle integriert sein.
Welche Seite im Hauptspeicher wird ersetzt?
 Üblicherweise wird eine Annäherung an LRU (least recently used) benutzt: Ein Referenz‐Bit für eine Seite wird auf ‘1’ gesetzt, falls die Seite benutzt wird (genaue Erklärung folgt später).
Wann wird die Seite vom Hauptspeicher in den sekundären Speicher kopiert?
 Falls in die Seite geschrieben wurde; dies wird durch ein Dirty‐Bit signalisiert.
6 ‐ 64
Seitenfehler
Eine Seite wird in den sekundären Speicher
geschrieben, falls sie ersetzt wird und sie zuvor beschrieben wurde (Dirty =‘1’).
Bei einem Seitenfehler wird eine gültige Seite
(Valid = ‘1’) mit Ref = ‘0’ ersetzt.
6 ‐ 65
Performanz ‐ Seitenfehler
Annahmen:
 Die Architektur besitzt keinen Cache.
 Falls der Zugriff auf die Seitentabelle zu einem Seitenfehler führt, dann wird er zunächst behoben und dann erfolgt ein neuer Zugriff auf die Seitentabelle.
 Seitenfehler‐Rate: p mit 0  p  1 . Falls p == 0 dann gibt es keine Seitenfehler; falls p==1 dann ist jeder Zugriff ein Seitenfehler.
 Mittlere Zugriffszeit zum Hauptspeicher: h
 Mittlere Seitenfehler‐Bearbeitungszeit: f
Effektive Speicherzugriffszeit (Effective Access Time EAT):
erster Zugriff auf die Seitentabelle (Fehler
EAT = 2 • h + p • (h + f) wird danach festgestellt) sowie Beheben des Fehlers.
in jedem Fall erfolgt der Zugriff auf die Seitentabelle (im
Hauptspeicher) und der Zugriff auf die gesuchten Daten.
6 ‐ 66
Rechenbeispiel – Performanz Seitenfehler
Speicherzugriffszeit Mittlere Seitenfehler‐Bearbeitungszeit Seitenfehler‐Rate 200 Nanosekunden
8 Millisekunden
10‐3
Wie hoch ist die effektive Speicherzugriffszeit?
EAT = 2 • 200 ns + p • (8 ms + 200 ns) = 400 ns + 8000 ns + 0.2 ns = 8400.2 ns
 Für p = 10‐3 beträgt die EAT also etwa 8.4 µs.
 Dies ist eine Verlangsamung etwa um den Faktor 42 gegenüber einem direkten
Speicherzugriff.
6 ‐ 67
Problem 1: Grösse der Seitentabelle
Beispiel für einen Prozess:  32 Bit virtueller Adressraum, Seitengrösse 212 Byte, 4 Bytes pro Tabelleneintrag:
Zahl der Einträge = 232 / 212 = 220 ; Grösse der Tabelle = 220 * 22 Bytes = 4 Mbyte  Eigentlich müssten die Seitentabellen aller Prozesse im Hauptspeicher liegen.
Möglichkeiten der Abhilfe:
 Durch geeignete Datenstrukturen werden entweder nur die Einträge der tatsächlich verwendeten virtuellen Seiten gespeichert oder die Grösse der Tabelle entspricht der maximalen Zahl an Seiten im Hauptspeicher (wird in der Vorlesung nicht weiter behandelt).
 Die Verwaltung aller Tabellen wird in einem Prozess ausgeführt, der Teil des Betriebssystems ist. Dieser Prozess verwendet ebenfalls einen virtuellen Adressraum, d.h. die Seitentabellen sind ihrerseits auf virtuelle Seiten aufgeteilt und können im sekundären Speicher liegen.
6 ‐ 68
Hierarchischer Aufbau einer Seitentabelle
 Die Seitentabelle wird in Teiltabellen (innere Seitentabellen) aufgeteilt.
 Ziel: Es werden lediglich diejenigen inneren Seitentabellen (inner page table) gespeichert, die tatsächlich genutzten virtuellen Speicherbereichen zugeordnet sind.
 Die äussere Seitentabelle enthält Einträge, die auf die inneren Seitentabellen zeigen.
•outer page •table
•inner page •table
inner page
tables
 Vorteil: Für ungenutzte virtuelle Speicherbereiche ist nicht notwendigerweise eine innere Seitentabelle erforderlich.
6 ‐ 69
Beispiel – Zweistufige Seitentabelle
210 Zeilen
210 Zeilen
Annahmen: • Seitengrösse 4kB
• 4 Bytes pro Eintrag in der «inner page table»
physikalische
Seite: 4 kB
6 ‐ 70
Problem 2: Aufwändige Ersetzungsstrategie
Welche Seite soll ersetzt werden, falls keine freie physikalische Seite verfügbar ist?
 Ziel: Algorithmus mit minimaler Zahl von Seitenfehlern.
 Problem: LRU (least recently used) ist aufwendig, da jeweils die physikalische Seite bestimmt werden muss, die am längsten unbenutzt ist.
 Eine mögliche Lösung: Approximation mittels Referenz‐Bit («second chance»):
 Jede Seite erhält ein Referenz‐Bit. Falls eine Seite benutzt wird, wird Ref=‘1’ gesetzt.
 Ein Zeiger auf die physikalischen Seiten wird definiert.
 Die folgende Schritt wird bei jedem Seitenfehler so oft durchgeführt, bis eine Seite ersetzt wird:
 Falls der Zeiger auf eine Seite mit ‘0’ zeigt, dann diese Seite ersetzen und den Zeiger inkrementieren (auf die nächste Seite zeigen, zirkulär). Falls der Zeiger auf eine Seite mit ‘1’ zeigt, dann das Referenz‐Bit auf ‘0’ setzen und den Zeiger inkrementieren (auf die nächste Seite zeigen, zirkulär).
6 ‐ 71
Problem 2: Aufwändige Ersetzungsstrategie
Seitenfehler:
diese Seite
wird
ersetzt
6 ‐ 72
Virtueller Speicher –
Translation Lookaside Buffer (TLB)
6 ‐ 73
Problem 3: Zugriffsgeschwindigkeit
Jeder Speicherzugriff besteht nun aus zwei Zugriffen: Bestimmung der physikalischen Adresse sowie Datenzugriff.
Abhilfe:
 Spezieller Hardware‐Cache für die Seitentabelle: Translation Lookaside Buffer (TLB).
 Damit gibt es zwei Klassen von Misses: TLB‐ Miss sowie Seitenfehler.
 TLBs verwenden üblicherweise «Zurückkopieren» (write back), da Misses selten sind.
6 ‐ 74
TLB als Cache für die Seitentabellen
voll‐assoziativ
oder auch
teil‐assoziativ
6 ‐ 75
Überblick Cache ‐ TLB
Datenpfad und
Kontrollpfad
translation lookaside
buffer (TLB)
1. Cache‐Ebene
2. Cache‐Ebene
Bus: Verbindung zwischen Komponenten
Hauptspeicher
6 ‐ 76
Beispiel: Cache – TLB
voll‐assoziativer TLB
Cache mit direkter Abbildung
getrennter Tag‐ und Daten‐Zugriff
im Cache (kein Multiplexer)
6 ‐ 77
Verarbeitung von Lesen und durchgängigem Schreiben
Write Access Bit schützt gewisse Seiten vor dem Schreibzugriff; Teil des Speicher‐Schutzes (später mehr dazu …)
Annahme: Der Cache ist «physikalisch» organisiert
(Tags und Indizes). Er könnte auch virtuell organisiert sein (Indizes und eventuell auch Tags);
dies wird hier nicht weiter ausgeführt.
6 ‐ 78
Performanz – TLB Miss ohne Seitenfehler
Annahmen:
 Die Architektur besitzt keinen Cache. Es tritt kein Seitenfehler auf.
 Falls der Zugriff auf den TLB zu einem Miss führt, dann wird er zunächst behoben und dann erfolgt ein erneuter Zugriff auf den TLB.
 Zugriffs‐ und Suchzeit im assoziativen TLB: s
 Miss‐Rate: m mit 0  m  1  Mittlere Zugriffszeit zum Hauptspeicher: h
 Mittlere TLB Miss‐Bearbeitungszeit: o
Effektive Speicherzugriffszeit (Effective Access Time EAT):
EAT = (s + h) + m • (s + o)
6 ‐ 79
Virtueller Speicher – TLB Miss und Seitenfehler
6 ‐ 80
Seitenfehler und TLB Miss
Auflösen von TLB Miss und Seitenfehler: Der gesamte Vorgang ist komplex und stellt hohe Anforderungen an die Hardware‐ und Softwarearchitektur, z.B. exakte Unterbrechungen von Instruktionen sowie Unterbrechungen der Betriebssystemprozesse. Es folgt eine von vielen Möglichkeiten:
TLB Miss
 Ein TLB Miss führt zu einer Programmunterbrechung (Ausnahmefehler).
 Die Kontrolle wird an das Betriebssystem übergeben, das folgende Aktionen ausführt:
 Eine Zeile im TLB wird ausgewählt, die ersetzt werden soll.  Aus der Adresse der fehlenden virtuellen Seite sowie der Basisadresse der derzeit gültigen Seitentabelle wird der im TLB fehlende Adresseintrag in der Seitentabelle ermittelt.
 Dieser fehlende Eintrag wird in die freie Zeile im TLB übertragen.
 Zurückkehren zum unterbrochenen Prozess.
6 ‐ 81
Seitenfehler und TLB Miss
Seitenfehler (page fault)


Der Zugriff auf eine Speicheradresse führt im TLB auf einen Eintrag mit Valid == ‘0’. Eine Unterbrechung des Programmablaufs wird erzwungen und das Betriebssystem führt drei Schritte durch:
1.
2.
3.
Der Eintrag im TLB führt zum Ort der fehlenden Seite im sekundären Speicher.
Eine Seite im Hauptspeicher wird ausgewählt, die ersetzt werden soll. Ist die Seite verändert worden (Dirty == ‘1’), wird sie zunächst in den sekundären Speicher geschrieben und die Einträge in der Seitentabelle und im TLB aktualisiert (Valid = ‘0’).
Die fehlende Seite wird vom sekundären Speicher in den Hauptspeicher kopiert
und die entsprechende Einträge in der Seitentabelle und im TLB werden aktualisiert.
•82
6 ‐ 82
Ablauf einer Seitenfehler‐Behandlung
TLB fault handling
TLB miss exception
Processor
TLB
1. Prozessor sendet virtuelle Adresse (VA) an TLB. Annahme TLB Miss. 2.‐3. Laden des fehlenden Seitentabellen‐Eintrages (PTE) mit der Adresse PTEA in den TLB.
6 ‐ 83
Ablauf einer Seitenfehler‐Behandlung
page fault exception
Processor
TLB
1. Prozessor sendet virtuelle Adresse (VA) an TLB. Annahme TLB Miss. 2.‐3. Laden des fehlenden Seitentabellen‐Eintrages (PTE) mit der Adresse PTEA in den TLB.
4. Annahme Seitenfehler (Valid == ‘0’). Verzweigung zum Programm, das die Ausnahme behandelt.
6 ‐ 84
Ablauf einer Seitenfehler‐Behandlung
page fault exception
Processor
TLB
1. Prozessor sendet virtuelle Adresse (VA) an TLB. Annahme TLB Miss. 2.‐3. Laden des fehlenden Seitentabellen‐Eintrages (PTE) mit der Adresse PTEA in den TLB.
4. Annahme Seitenfehler (Valid == ‘0’). Verzweigung zum Programm, das die Ausnahme behandelt.
5. Fehlerbehandlungsprogramm bestimmt eine Seite im Hauptspeicher, deren Inhalt ersetzt werden soll.
Annahme: sie wurde zuvor nicht beschrieben (Dirty == ‘0’).
6 ‐ 85
Ablauf einer Seitenfehler‐Behandlung
page fault exception
Processor
TLB
1. Prozessor sendet virtuelle Adresse (VA) an TLB. Annahme TLB Miss. 2.‐3. Laden des fehlenden Seitentabellen‐Eintrages (PTE) mit der Adresse PTEA in den TLB.
4. Annahme Seitenfehler (Valid == ‘0’). Verzweigung zum Programm, das die Ausnahme behandelt.
5. Fehlerbehandlungsprogramm bestimmt eine Seite im Hauptspeicher, deren Inhalt ersetzt werden soll.
Annahme: sie wurde zuvor nicht beschrieben (Dirty == ‘0’). 6. Die neue Seite wird in den Hauptspeicher geschrieben.
6 ‐ 86
Ablauf einer Seitenfehler‐Behandlung
page fault exception
TLB
1. Prozessor sendet virtuelle Adresse (VA) an TLB. Annahme TLB Miss. 2.‐3. Laden des fehlenden Seitentabellen‐Eintrages (PTE) mit der Adresse PTEA in den TLB.
4. Annahme Seitenfehler (Valid == ‘0’). Verzweigung zum Programm, das die Ausnahme behandelt.
5. Fehlerbehandlungsprogramm bestimmt eine Seite im Hauptspeicher, deren Inhalt ersetzt werden soll.
Annahme: sie wurde zuvor nicht beschrieben (Dirty == ‘0’). Die neue Seite wird 6. Die neue Seite wird in den Hauptspeicher geschrieben.
7. Der «page fault handler» kehrt zum ursprünglichen Prozess zurück.
6 ‐ 87
Kommunikation zwischen Komponenten
6 ‐ 88
Ein/Ausgabe (Input/Output – I/O)
6 ‐ 89
Befehle vom Prozessor an die E/A‐Einheit
Speicheradressierte Ein/Ausgabe (memory mapped I/O):  Teile des Adressraumes sind den E/A‐Einheiten zugewiesen.
 Schreiben und Lesen zu diesen Adressen bzw. Registern wird als Befehl an die E/A‐
Einheit interpretiert:  Steueradressen veranlassen die E/A‐Einheit zu agieren,
 Statusadressen zeigen die derzeitige Aktivität oder Fehlermeldungen an,
 Datenadressen dienen dem Datentransfer zwischen Prozessor und E/A‐Einheit
 Benutzerprogrammen ist es oft nicht erlaubt, direkt auf E/A‐Adressen zuzugreifen. Sie werden vom Betriebssystem verwaltet (siehe Kapitel 7).
6 ‐ 90
Übersicht speicheradressierte Ein/Ausgabe
Datenpfad und
Kontrollpfad
translation lookaside
buffer (TLB)
1. Cache‐Ebene
2. Cache‐Ebene
Bus: Verbindung zwischen Komponenten
E/A Einheit
Hauptspeicher
6 ‐ 91
Information von der E/A‐Einheit an Prozessor
Ein Prozess muss wissen, wann
 die E/A‐Einheit eine Operation abgeschlossen hat oder  die E/A‐Operation einen Fehler verursacht hat.
Diese Information kann auf zwei Arten übermittelt werden:
 Polling: Die E/A‐Einheit gibt Informationen in ein Statusregister, periodisches Abfragen der Statusadresse.
 E/A Unterbrechung: Falls die E/A‐Einheit Aufmerksamkeit vom Prozessor benötigt, unterbricht sie ihn im laufenden Programm (siehe Kapitel 3).
6 ‐ 92
Datenaustausch zwischen I/O Einheit und Prozessor
Problem:  Belastung des Prozessors mit Datenaustausch zwischen Speicher und anderen Komponenten, z.B. Netzwerkzugang, externer Speicher.
Abhilfe:  spezieller Ein/Ausgabe‐Prozessor, der für die Datenübertragung zuständig ist: DMA (direct memory access).
DMA:  ausserhalb der CPU angesiedelt (logisch, nicht unbedingt physikalisch)
 überträgt Datenblöcke zu oder vom Speicher unabhängig vom Prozessor
 unterbricht den Prozessor, falls der gesamte Datentransfer abgeschlossen ist
6 ‐ 93
DMA
Prinzipieller Aufbau und Ablauf:
Der Prozessor sendet die Startadresse der Daten, das Ziel der Übertragung und die Zahl der Daten zur DMA Komponente.
Bus
Die DMA Komponente liefert die Steuersignale und die fortlaufenden Adressen, die über den Bus zu den beteiligten Komponenten
(z.B. Speicher und Ein/Ausgabe Einheit) geleitet werden.
6 ‐ 94