Upload
lamkhuong
View
219
Download
0
Embed Size (px)
Citation preview
Segmentierung – Motivation
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 59
Bisher haben wir feste Blockgrößen betrachtet. Ziel: Paging stellt dem Anwender einen großen (eindimensionalen) Speicher von 0 bis 2b‐1 (b = Bit‐Tiefe) bereit.
Annahme Programm benötigt mehrere Speicherbereiche deren Längen im Programmablauf variabel sind. Beispiel Compiler:
Für solche Anwendungsfälle ist es besser dem Anwender sichtbar mehrere unabhängige Speicherbereiche zur Verfügung zu stellen.
Symbol‐tabelle
Source‐Code
Kon‐stanten
Parse‐Tree Call‐Stack
0 … A … B … C … D … E … 2b‐1
Segmentierung ‐ Grundidee
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 60
Voriges Beispiel Compiler:
Dieses Konzept mit variablen Blockgrößen nenn man Segmentierung.
Im Gegensatz zu Paging: explizit sichtbare zweidimensionale Adressierung (n,k) mit Segment‐Nummer n und Segment‐Offset k
• Anfang kann auf einen beliebigen Startpunkt im Speicher zeigen.• Die physikalische Adresse ergibt sich aus Anfang + Offset.• Segmente können beliebig lang sein; benötigt auch „Bounds‐Check“.
Segmentierung ermöglicht auch einfaches Sharing von Code (und natürlich auch Daten) zwischen Prozessen. Alle können die gleiche Adresse (n,k) verwenden. Protection kann explizit erfolgen. [Paging: virtueller Adressbereich muss verfügbar sein; Protection implizit]
Symbol‐Tabelle Source‐
CodeKon‐
stanten
Parse‐Tree Call‐
Stack
0K
4K
8K
12K
16K
20K
24K
0K
4K
8K
12K
16K
0K
4K
0K
4K
8K
12K
16K
20K
0K
4K
8K
12K
Implementierung über Segment‐Tabelle
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 61
Segment‐Nummer(Selector) Offset
Basis‐Adresse
Limit
Andere Felder (z.B. Priviledge, Protection,…)
Adressierung im virtuellen Addressraum
Eintrag in Segmenttab
elle
Segmenttabelle
+
N‐Bit lineare Adresse
Damit geeigneter Zugriff auf physikalischen Speicher
Segmentierung versus Paging
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 62
Paging Segmentierung
Für den Programmierer sichtbar Nein Ja
Anzahl verfügbarer linearerAdressbereiche
1 Viele
Mehr als der physikalische Speicherbereich verfügbar
Ja Ja
Trennung von Programm und Daten mit unterschiedlichem Protection möglich
Nein Ja
Unterstützung mehrererSpeicherbereiche mit dynamischer Größe
Nein Ja
Unterstützung von Code‐Sharing Nein Ja
Motivation für die Einführung/Verwendung
Bereitstellung eines großen Adressraumes bei limitiertem physikalischem Speicher
Trennung von Programm und Daten in logische unabhängige Adressbereiche. Unterstützung von Sharing und Protection
Pure Segmentierung: Jedes Segment belegt ab einer Basisadresse einen aufeinander‐folgenden physikalischen Speicherbereich. (z.B. Ausgangspunkt (a))Mit der Zeit entsteht eine sog. externe Fragmentierung (z.B. (b), (c), (d))Mögliche Lösung: Compactation (z.B. (e))
Problem mit purer Segmentierung
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 63
Segment 0(4K)
Segment 1(8K)
Segment 2(5K)
Segment 3(8K)
Segment 4(7K)
Segment 0(4K)
Segment 7(5K)
Segment 2(5K)
Segment 3(8K)
Segment 4(7K)
Segment 0(4K)
Segment 2(5K)
Segment 3(8K)
Segment 5(4K)
(3K)
(3K)
Segment 7(5K)
(3K)
Segment 0(4K)
Segment 2(5K)
Segment 6(4K)
Segment 5(4K)
(3K)
Segment 7(5K)
(3K)
(4K)
Segment 0(4K)
Segment 2(5K)
Segment 6(4K)
Segment 5(4K)
(10K)
Segment 7(5K)
(a) (b) (c) (d) (e)
Lösung: Segmentierung mit Paging (1)
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 64
Beispiel Intel Pentium:• Es gibt zwei Segment‐Tabellen (mit 8K+8K Einträgen)
• GDT (Global Descriptor Table) – eine globale Tabelle für alle Prozesse
• LDT (Local Descriptor Table) – für jeden Prozess eine individuelle Tabelle
• Es gibt 6 sog. Segment‐Register(u.a. CS als Selector für Code und DS als Selector für Daten)
• Selector‐Format 16‐Bit
• Mittels Index: Zugriff auf Segment‐Descriptor in LDT oder GDT(Privilege‐Level gleich)
Index 0=GDT1=LDT
Privilege‐Level (0‐3)
15 14 … 3 2 1 0
Lösung: Segmentierung mit Paging (2)
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 65
Beispiel Intel Pentium:• Aufbau eines Segment‐Descriptors (8 Bytes)
• Base: 32‐Bit‐Basis‐Adresse des Segments (Format bzgl. Base und Limit ist Downward‐Kompatibilität mit 24‐Bit‐Base des 286 geschuldet)
• (Privilege Level, Segement‐Type und Protection siehe gleich)• Limit: mittels Granularity‐Bit entweder in Bytes (max. Segmentgröße 220=1MB) oder in
4K‐Pages (max. Segmentgröße 4K*220=4GB)• Damit zunächst also: Zugriff auf physikalischen Speicher mittels Basis‐Adresse plus
Offset (Segemente dürfen sogar überlappen)• Wo ist denn Paging als Lösung angewendet???
Bildquelle: Andrew S. Tanenbaum, „Modern Operating Systems“, Second Edition, 2001
Lösung: Segmentierung mit Paging (3)
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 66
Beispiel Intel Pentium:• Bit in globalem Control‐Register kann man Paging dazuschalten• Lineare Adresse wird dann nicht direkt als physikalische Adresse verwendet• Stattdessen wird die Adresse als virtuelle Adresse des Pagings verwendet• Virtuelle 32‐Bit‐Adresse: es wird zweistufiges Paging verwendet
• Bemerkung: Pentium verwendet selbstverständlich TLB zwecks Performancesteigerung• Bemerkung: Pentium erlaubt auch nur Paging ohne Segmentierung (setze alle
Segmentregister auf denselben Segment‐Selector, Descriptor Base=0 und Limit=max)
Dir Page Offset
Lineare Adresse
Bildquelle: Andrew S. Tanenbaum, „Modern Operating Systems“, Second Edition, 2001
Zum Abschluss: Protection
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 67
Beispiel Intel Pentium:• Vier Protection Level (0 bis 3; Level 0 hat höchste Privilegien) • Zu jedem Zeitpunkt befindet sich ein Programm in einem der Level• Jedes Segment ist ebenfalls einem Level zugeordnet.• Unmittelbarer Zugriff auf Segment nur aus gleichem Level oder aus Level mit höheren
Privilegien möglich; ansonsten Trap/Exception!• Aufruf von Prozeduren ist aber auf kontrollierte Weise über call‐Instruktion möglich
• call verwendet anstatt Adresse einen Segment‐Selector
• Dieser beschreibt einen sogenanntencall‐Gate (welcher die Aufrufadressefestlegt)
• Damit Sprung an beliebige Stelle nichtmöglich; nur offizielle Eintrittspunktekönnen verwendet werden
• Typisches Beispiel (siehe Grafik)• Type‐Feld wird zur Unterscheidung
zwischen Code‐Segment, Daten‐Segmentund verschiedene Typen von Gatesverwendet
Bildquelle: Andrew S. Tanenbaum, „Modern Operating Systems“, Second Edition, 2001
Parallelität und Caches
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 68
Cache‐Kohärenz‐Problem
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 69
CPU 1 (oder Core 1)
Cache
CPU 2 (oder Core 2)
Cache
Speicher
Zeitschritt Event Cache‐Inhalt für CPU A
Cache‐Inhalt für CPU B
Speicherinhalt für Adresse X
0 0
1 CPU 1 liest X 0 0
2 CPU 2 liest X 0 0 0
3 CPU 1 speichert 1 nach X
1 0 1
Wann gilt ein Cache als kohärent?
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 70
1. Lesen von Speicherstelle X nach schreiben in Speicherstelle X sollte den geschriebenen Wert zurück geben, wenn kein weiterer Prozess auf die Stelle X geschrieben hat.
2. Nachdem ein Prozess in Speicherstelle X geschrieben hat, sollte „nach einer gewissen Zeit“ jeder Prozess den geschriebenen Wert in X vorfinden.
3. Zwei Schreiboperationen von zwei Prozessen in die Speicherstelle X sollte von jedem Prozess in der gleichen Reihenfolge gesehen werden. (Schreiben ist serialisiert)
Wie erreicht man Kohärenz?
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 71
Write‐Invalidate‐Protokoll: Wenn ein Prozess in einen Speicherstelle schreibt wird die Speicherstelle in den Caches aller anderen Prozesse invalidiert.
Wie wird das Invalidieren technisch erreicht? Snooping: Jeder Cache‐Controller überwacht den gemeinsamen Bus, ob auf einen eigenen gecachten Inhalt geschrieben wird.
Prozessor‐aktivität
Busaktivität Inhalt des Caches von CPU A
Inhalt des Caches von CPU B
Speicher‐inhalt für X
0
CPU A liest X Cache‐Miss für X 0 0
CPU B liest X Cache‐Miss für X 0 0 0
CPU A schreibt 1 nach X
Cache‐Invalidierung für X
1 1
CPU B liest X Cache‐Miss für X 1 1 1
Ergänzung: RAM und ROM
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 72
Speichern eines Bits versus viele MB
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 73
Wir wissen wie wir einzelne Bits speichern können (Erinnerung: Latches, Flip‐Flops)
CK
D Q
Mehrere solcher Bausteine können zu Register zusammengebaut werden
Wie baut man daraus aber komplexe RAM‐Bausteine?
Bildquelle: Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 2006
Beispiel: Speicherbaustein mit Adressierung
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 74
Dateneingänge (3 Bit): I0, I1, I2Datenausgänge (3 Bit): O1, O2, O3Adressleitungen (4 „Wörter“): A0, A1Kontrollleitungen:• CS = Chip‐Select• RD = Read (=1) / Write (=0)• OE = Output Enable
Lesen und Schreiben am Beispiel…
Wenn man entweder liest oder schreibt können I0, I1, I2 und O1, O2, O3 auch dieselben Leitungen sein (das spart Pins und Busleitungen). Dies erfordert aber, dass beim Schreiben die Ausgabe getrennt wird.Baustein hierfür: noninverting und invertingBuffer:
(sog. Tri‐State‐Device: Ausgabe 0/1 oder „none“ (d.h. open circuit))
Bildquelle: Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 2006
Erweiterung von Adressraum und Bit‐Tiefe
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 75
Erweiterung des vorigen Beispiels ist offensichtlich:• Vergrößerung des Adressraums (in der
Größenordnung 2n): Füge eine Adressleitung hinzu und verdoppele die Anzahl Zeilen
• Vergrößerung der Bit‐Tiefe (beliebig): Füge in jede Zeile eine/mehrere Spalte/n hinzu
Zwei‐dimensionales sich wiederholendes Muster:• lässt sich gut mit dem Konzept von
integrierten Schaltung vereinen(z.B. kein Anwachsen von Leitungsüberkreuzungen)
• Speicherkapazität ist nur direkt an Chip‐Integrationsdichte gekoppelt
Bildquelle: Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 2006
Verschiedene Chip‐Organisationsformen möglich. Beispiel für zwei 4Mbit‐Chip‐Varianten:
Variante (a): wie eben nur größerVariante (b):• 2048x2048 Matrix mit 1‐Bit‐Zellen• Adressierung ist zweistufig (z.B. erst Row
Address Strobe (RAS) und dann ColumnAddress Strobe (CAS))
Organisation als Matrix
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 76
n x n‐Matrix‐Konzept des vorigen Beispiels allgemein:• Geeignet für große Speicher‐Chips• Reduziert die Anzahl Pins• Adressierung dauert aber doppelt so lang• Mögliche Optimierung:
• Teile zuerst die Row‐Adresse mit• Anschließend können innerhalb dieser Row mit einer Sequenz von Column‐
Adressen Speichereinträge erreicht werden
Mehrere n x n ‐ 1‐Bit‐Bausteine lassen sich auch parallel zu größerer Bit‐Tiefe zusammenbringen, z.B. Tiefe 8‐Bit
Matrix‐Organisation eines Einzelbausteins nicht auf Bit‐Einträge begrenztBeispielsweise: 4‐, 8‐, oder 16‐Bit‐Breiten möglich; daraus lassen sich mit weniger Einzel‐Chips größere RAM‐Bausteine zusammenbauen (z.B. Anstatt 32‐Bit‐Tiefe mit vier 8‐Bit‐Bausteinen anstatt mit 32 1‐Bit‐Bausteinen)
Bildquelle: Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 2006
Weitere Aspekte
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 77
Matrix muss nicht Quadratisch sein (z.B. 13 Rows und 10 Columns)Zusätzlich kann Speicher noch in Bänken organisiert sein (z.B. 4 Bänke mit je 128Mbit ergibt 512 Mbit)
Zwei Beispiele eines 512Mbit‐Chips:
• Vier interne Bänke a 128MBit (d.h. zwei Bank‐Select‐Leitungen)• Variante (a): 32M x 16 Design mit 13‐Bit‐RAS und 10‐Bit‐CAS => 213+10+2 = 225 interne
16‐Bit‐Zellen• Variante (b): 128M x 4 Design mit13‐Bit‐RAS und 12‐Bit‐CAS => 213+12+2 = 227 interne
4‐Bit‐ZellenBildquelle: Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 2006
SRAM und DRAM
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 78
Zwei RAM‐Varianten: SRAM und DRAM
Static RAM (SRAM)• Aufgebaut mit Schaltungen wie die diskutierten Flip‐Flops• Zustand bleibt erhalten solange Strom anliegt• Sehr schneller Speicher (Zugriffszeit wenige nsec)
Dynamic RAM (DRAM)• Nutzt keine Flip‐Flops sondern Array von Zellen mit je einem Transistor und
einem winzigen Kondensator pro Bit• Ladezustand des Kondensator (aufgeladen/entladen) stellt 1‐Bit‐Information
dar• Kondensator entladen sich => damit periodischer „Refresh“ notwendig (alle
paar Millisekunden)• Vorteil: hohe Dichte bzgl. Bit pro Chip (Transistor+Kondensator anstatt 6
Transistoren für den Flip‐Flop) => große RAM‐Speicher damit realisierbar• Nachteil: wesentlich langsamer (mehrere 10 nsec)• Guter Kompromiss: DRAM‐Baustein mit SRAM‐Cache
FPM, EDO, SDRAM und DDR
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 79
DRAM‐Varianten: z.B. FPM und EDO
Fast Page Mode (FPM) DRAM• Matrix zur Adressierung von Bit• Eine Row‐Adresse und anschließend aufeinander folgende Column‐Adressen• RAM läuft unabhängig (asynchron) vom Haupt‐Systemtakt
Extended Data Putput (EDO) DRAM• Nächste Speicherreferenz ist möglich bevor die vorige beendet wurde (vgl. Pipelining‐Prinzip)• Erhöht nicht die individuelle Speicherzugriffzeit aber den Speicherdurchsatz
Synchronous DRAM (SDRAM)• Hybrid aus dynamischem und statischem DRAM durch den Haupt‐Systemtakt getriggert• Keine Kontrollnachrichten zwischen Prozessor und RAM wie bei asynchronem RAM erforderlich• Wesentlich schneller
Double Data Rate (DDR) SDRAM• Output bei fallender und steigender Clock‐Flanke => verdoppelt die Datenrate
ROM
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 80
Read Only Memory (ROM) – Zum Chipherstellungsprozess wird das Bitmuster festgelegt; besonders billiger Speicher
Programmable ROM (PROM) – kann einmalig Programmiert werden; Meist ein Feld von Column‐Row‐Adressierbaren Knotenpunkten die über einen Eingangs‐Pin einmalig auf einen Bit‐Wert gesetzt werden können
Erasable PROM (EPROM) – Belichtung des Quartz‐Fenster mit starkem UV‐Licht für 15 Minuten setzt alle Bit‐Werte zurück auf 1. Erneutes Setzen der Bits damit möglich
EEPROM – Löschen mittels elektrischer Impulse; Re‐Programmierung direkt am Chip möglich (anstatt wie bei EPROM in spezieller Apparatur)
Diskussion:EEPROMS typischerweise wesentlich kleiner als EPROMS und nur halb so schnellEEPROMS wesentlich langsamer kleiner und teurer als DRAM und SRAMNur dann sinnvoll, wenn Werte einmalig festgelegt sein sollen
Aktueller als EEPROMs sind Flash‐Speicher (auf NAND‐Basis)Unterschied: Block‐Erasable/Rewritable anstatt Byte‐Erasable/Rewritable
Flash‐Speicher
SS 2012 Grundlagen der Rechnerarchitektur ‐ Ein‐ und Ausgabe 81
Flash‐Speicher: nichtvolatiler Halbleiterspeicher.
Vorteile gegenüber Disks:• Latenz ist 100 bis 1000 fach schneller• Kleiner• Größere Leistungseffizienz• Größere Shock‐Resistenz
Nachteile gegenüber Disks:• Höherer Preis pro GB• Flash‐Speicher‐Bits sind nach vielem Überschreiben nicht mehr
verwendbar (Wear‐Out).
Flash‐Speicher muss ein entsprechendes Wear‐Levelingdurchführen.
NOR‐ und NAND‐Flash‐Speicher
SS 2012 Grundlagen der Rechnerarchitektur ‐ Ein‐ und Ausgabe 82Bildquelle: David A. Patterson und John L. Hennessy, „Computer Organization and Design“, Fourth Edition, 2012
Zusammengefasst
SS 2012 Grundlagen der Rechnerarchitektur ‐ Speicher 83
Typ Kategorie Löschen Volatil Typische Anwendung
SRAM R/W Elektr. Ja Level1/2 Cache
DRAM R/W Elektr. Ja Hauptspeicher (alt)
SDRAM R/W Elektr. Ja Hauptspeicher (neuer)
ROM Read‐Only
Nicht möglich
Nein Produkte großer Stückzahl
PROM Read‐Only
Nicht möglich
Nein Produkte kleinerer Stückzahl
EPROM Read‐Mostly
UV‐Licht Nein Prototyping
EEPROM Read‐Mostly
Elektr. Nein Prototyping
Flash R/W Elektr. Nein Sekundärer Speicher
Zusammenfassung und Literatur
Grundlagen der Rechnerarchitektur ‐ Speicher 84SS 2012
Zusammenfassung• Cache‐Ziel: Speicher so groß wie auf unterstem Level aber annähernd so schnell wie auf höchstem Level.
• Warum funktionieren Caches überhaupt so gut? Lokalitätsprinzip.
• Virtueller Speicher ist prinzipiell das selbe wie ein Cache. Auch hier gelten dieselben Cache‐Prinzipien (z.B. Lokalität)
• Insgesamt ergibt sich eine Hierarchie von Caches.• Caches sind prinzipiell vor der Software unsichtbar. Dennoch ist es sinnvoll diese in der Software zu beachten (z.B. Speicherblöcke in Schleifen Cache‐günstig durchlaufen, Prefetching)
Grundlagen der Rechnerarchitektur ‐ Speicher 85SS 2012
Literatur[PattersonHennessy2012] David A. Patterson und John L. Hennessy, „Computer Organization and Design“, Fourth Edition, 20125.1 Introduction5.2 The Basics of Caches5.3 Measuring and Improving Cache Performance5.4 Virtual Memory5.8 Parallelism and Memory Hierarchies: Cache Coherence6.4 Flash‐Storage
[Tanenbaum2001] Andrew S. Tanenbaum, „Modern Operating Systems“, Second Edition, 20014.8 Segmentation
[Tanenbaum2006] Andrew S. Tanenbaum, „Structured Computer Organization“, Fifth Edition, 20063.3 Memory
Grundlagen der Rechnerarchitektur ‐ Speicher 86SS 2012