Speicherkonzepte PDF

Preview

Summary

Zusammenfassung zu Speicherkonzepten aus dem Kurs....

Description

Speicherkonzepte

Ziele der virtuellen Speicherverwaltung (VSS)      

Großer Adressraum virtueller Adressen auf relativ kleinen Adressraum physischer Adressen zur Verfügung stellen Transparent d.h. Anwender soll nicht merken, dass Adressen nur virtuell existieren Schneller Programmstart, da nicht alle Code- und Datenbereiche zu Programmbeginn im Hauptspeicher vorhanden sein müssen Einfache Relozierbarkeit (Verschiebbarkeit im Hauptspeicher) Unterstützung von Schutzbits (keine unerlaubten Zugriffe) Automatische Verwaltung des Haupt-/Sekundärspeichers

Folgende Fragestellungen sind von Bedeutung:     

Wo kann ein Speicherblock im Hauptspeicher platziert werden? Welcher Speicherblock sollte bei einem Fehlzugriff ersetzt werden? Wann muss ein verdrängter Speicherblock in den Sekundärspeicher zurückgeschrieben werden? Wie wird ein Speicherblock aufgefunden, der sich in einer höheren Hierarchiestufe befindet? Welche Seitengröße sollte gewählt werden?

Grundprinzip der VSS 

Entkopplung zwischen den Adressen, die das auf dem Prozessor ablaufende Programm benutzt (logische/virtuelle Adressen) und den tatsächlichen Adressen im Speicher (physikalische Adressen)





   



Logische Adresse (vom Anwender sichtbare und benutzte Adresse) wird von der VSS zuerst in virtuelle Adresse (vom Prozessor benutzt) dann in physikalische Adresse transformiert VSS unterteilt physikalischen Speicher in Speicherblöcke (organisiert in Seiten mit fester Größe und/oder Segmenten mit variabler Größe) und bindet diese an im Rechner ablaufende Prozesse Virtueller und physikalischer Adressraum wird in gleichgroße Abschnitte (Seiten) aufgeteilt. Abschnitt im Hauptspeicher auf dem eine Seite abgelegt werden kann heißt Seitenrahmen Typische Seitengrößen von 512 – 4096 Byte aber immer Größe 2n Seitenübersetzung = Virtuelle Adresse in zwei Teile zerlegt: Seitennummer und Adresse innerhalb der Seite (Verschiebung bzw. Offset)

Seitennummer = Zeiger innerhalb einer Seitentabelle (zu jeder Seitennummer die dazugehörige physikalische Anfangsadresse der Seite)

Beispiel Speicherseitenverwaltung: Geg.:   

Prozessor mit 16 Bit breiten Adressbus = virtueller Adressraum besteht aus 2 16 = 65536 Adressen = Adressen von 0 bis 65535 Byte-adressierter Speicher und Seitengröße 4096 = 16 Seiten (65536/4096) Hauptspeicher = 32KByte mit 8 Seitenrahmen



Aufteilung der 16-Bit-Adresse in 4-Bit-Seitennummer und 12-Bit-Adresse

Thrasing: bei zu kleinem Hauptspeicher werden zuletzt geladene Seiten von anderen benötigten Seiten verdrängt. Anzahl der Seitenfehler stagniert auf hohem Niveau. Ausführungszeit des Programms steigt im Vergleich zu größerem Hauptspeicher stark an.

Dynamische Speicherverwaltung   

Da virtueller Speicherbereich > physikalischer Speicher  Zugriff auf Seiten, welche momentan nicht im Hauptspeicher sind = Seitenfehler (Page-Fault) Referentielle Lokalität: Konzentrierung von hohen Zugriffswahrscheinlichkeiten auf bestimmte Stellen im Programm  Auslagern nur dieser Bereiche Welche Seite wird bei einem Seitenfehler aus dem HSP verdrängt?: o LRU-Verfahren (least recently used): Seite welche am weitesten zurückliegende Aktivität hat wird ersetzt o FIFO (First-In-First-Out): zuerst geladene Seite wird verdrängt (evtl. dadurch sogar mehr Seitenfehler – Beladys Anomalie) o OPT: theoretisches optimale, praktisch jedoch nicht realisierbare Ersetzungsstrategie. Erfordert vollständiges Wissen über alle zukünftigen Seitenzugriffe

Beispiel Ein Computersystem habe 16 Seiten virtuellen Adressraum, aber nur 4 Seitenrahmen. Die Zugriffsfolge der virtuellen Seiten betrage: 0,7,2,7,5,8,9,2,4,5,9. Wieviele Seitenfehler entstehen bei OPT, LRU und FIFO Strategie?

Maßnahmen zur Reduktion von Seitenfehlern: Vergrößerung des HSP: Ja  mehr Seiten im HSP  Höhere Wahrscheinlichkeit, dass aktuell gesuchte Seite im HSP Vergrößerung des SSP: Nein  Seitenfehler wird nur durch Fehlzugriff auf HSP erzeugt Verbesserung der Verdrängungsstrategie: Ja  Wahrscheinlichkeit, dass sich demnächst benötigte Seite im HSP befindet wird erhöht  Senkung der Wahrscheinlichkeit eines Seitenfehlers

Fragmentierung des Speichers  

Teil des Speichers bleibt ungenutzt, weil Programme und Daten nicht genau den Seitenrahmen füllen Reduzierung durch kleine Seitengrößen  Anzahl Seitenrahmen steigt  Größe Seitentabelle steigt  Längere Suche

Speichersegmentierung    

Durch parallele Bearbeitung muss virtueller Adressraum Struktur erhalten Jedem Prozess i kann ein eigener Adressraum von 0 bis ni zugewiesen werden (logische Adressen) Einzelner Datenbereich oder logischer Adressraum wird als Segment bezeichnet Jeder Prozess hat eigenen Segmentzeiger da z.B. virtuelle Adresse 0 mehrmals auftreten kann

Adressübersetzungspuffer (TLB)    

Hardwaretabelle, welche wichtigste Adressumsetzungen enthält Enthält in der Regel 32 bis 128 Einträge für die zuletzt durchgeführten Adressumsetzungen Auslösung einer Unterbrechung bei einem TLB-Fehlzugriff TLB-Eintrag besteht aus Tag (Etikett, enthält Teil der virtuellen Adresse), Datenanteil mit einer physikalischen Seitennummer und weiteren Verwaltungs- und Schutzbits

Speicherplatzzuweisung Um für jedes neu angeforderte Segment einen unbenutzten Bereich erforderlicher Größe zu finden gibt es mehrere Möglichkeiten: 1. First Fit: der Bereich, der als erster mit ausreichender Größe gefunden wird, wird gewählt. Suchzeit minimal 2. Best Fit: der kleinstmögliche Bereich mit ausreichender Größe wird benutzt. Es entstehen noch kleinere ungenutzte Bereiche 3. Worts Fit: der größte freie Block wird verwendet. Reststücke bleiben in ausreichender Größe vorhanden. Sehr große Anfragen können evtl. nicht bedient werden da keine sehr großen Bereiche bleiben 4. Zusammenpacken von kleinen ungenutzten Bereichen zu großen Bereichen

Aufbau und Funktion von Cache-Speichern Ziel:  

Neutralisierung langsamer Hauptspeicher durch einen kleinen, schnellen Pufferspeicher Ausnutzen der zeitlichen und räumlichen Lokalität

Cache-Parameter: Cache-Treffer (Hit): angefordertes Speicherwort ist im Cache-Speicher enthalten Cache-Fehlzugriff (Miss): angefordertes Speicherwort steht nur im HSP Cache-Zugriffszeit (tHit): Anzahl Takte um Speicherwort im Cache zu identifizieren, die Verfügbarkeit und Gültigkeit zu prüfen und zur Verfügung zu stellen Fehlzugriffsrate (Miss-Rate): Verhältnis von Fehlzugriffen zu allen Anfragen Trefferrate (Hit-Rate): Anteil von Treffern bezogen auf alle Anfragen Fehlzugriffsaufwand (Miss-Penalty, tMiss): Zeit, welche benötigt wird, um Cache-Block von tiefer gelegenen Hierarchiestufe in den Cache zu laden und dem Prozessor zur Verfügung zu stellen Zugriffszeit (access-time): Abhängig von Latenz zu unteren Hierarchiestufen Übertragungszeit (transfer-time): Zeit um Block zu übertragen Effektive Zugriffszeit (Teff):

Beispiel: Trefferrate h = 0 ≤ h ≤ 1 THS = Zugriffszeit des HSP TCA=Zugriffszeit auf Cache 1. Möglichkeit: Sequentieller Zugriff Zugriff auf Cache. Wenn Fehlzugriff, dann danach Zugriff auf HSP

Treffer im Cache

Zugriffsversuch Cache  Fehlzugriff  Zugriff HSP

2. Möglichkeit: Paralleler Zugriff Unabhängig, ob sich Datum im Cache befindet wird vorsichtshalber auf HSP zugegriffen

Speedup (S): effektive Beschleunigung, Verhältnis von bisheriger Zugriffszeit zur Zugriffszeit mit Cache

Funktionsweise des Caches Blockrahmen: eine Anzahl von Speicherplätzen, dazu ein Adressetikett und Statusbits Cache-Block: Speicherportion die in einen Blockrahmen passt (2 n Speicherzellen) Blocklänge: auch Blockgröße, Anzahl der Speicherplätze in einem Blockrahmen mit 2#rByte mit 2 ≤ #r ≤ 6 (immer als Zweierpotenzen). Typische Blocklängen sind 16 oder 32 Byte

Lesezugriffe: Bei jedem Lesezugriff des Prozessors auf eine Speicherzelle im HSP wird gleichzeitig auch im Cache nachgeschaut, ob diese Speicherzelle dort abgelegt wurde: Read Hit  gesuchte Wort wird aus Cache entnommen und bleibt für weitere Zugriffe erhalten Read-Miss  Datenwort wird von HSP in Prozessor geladen. HSP-Speicherzelle wird in Cache-Speicherzelle übertragen. In der Regel wird ein älterer nicht mehr benötigter Block verdrängt Schreibzugriffe: Write Hit  Speicherzelle bereits im Cache enthalten  Aktualisierung im Cache  Tag bleibt erhalten  Zelle im HSP veraltet und unbrauchbar  Inkonsistenz zwischen Cache und HSP Write-Miss  Speicherzelle im Cache nicht erhalten  Datenspeicher und Tag werden aktualisiert  Inkonsistenz zwischen Cache und HSP Schreibstrategien, um Inkonsistenzen zu vermeiden Durchschreibestrategie (Write-Through-Verfahren): Speicherwort vom Prozessor wird immer gleichzeitig in Cache und Hauptspeicher geschrieben. Problem: schneller Prozessor und langsame HSP  Verlust an Verarbeitungsgeschwindigkeit. Abhilfe schafft Schreibpuffer (nimmt Speicherwörter temporär auf und schreibt diese allmählich in HSP)  gepufferte Durchschreibestrategie (buffered write-through) Rückschreibestrategie: Speicherwort wird nur in Cache geschrieben und nicht in HSP. Transport vom Cache zum HSP erfolgt später. Durch ein sog. Dirty-Bit wird eine Markierung gesetzt die anzeigt, dass HSP an dieser Stelle noch nicht aktualisiert wurde.

Fehlzugriffe beim Schreiben Bei einem Write-Miss gibt es zwei unterschiedliche Strategien:  

Write-Allocation: gesuchte Speicherzelle wird mit entspr. Cache-Block aus dem HSP in Cache geladen. Speicherzelle wird neu beschrieben und das Dirty-Bit gesetzt. Write-Around: Speicherzelle im Cache wird nicht gesucht und eingetragen

Organisation von Cache-Speichern    

Menge an Block –bzw. speicherrahmen wird in sog. Sätze unterteilt Anzahl der Blockrahmen n in einem Satz wird als Assoziativität bezeichnet Jeder Datenblock aus dem HSP kann im Cache nur in einem bestimmten Satz, aber innerhalb des Satzes in einem beliebigen Blockrahmen gespeichert werden Gesamtzahl c der Blockrahmen = Produkt aus Anzahl s der Sätze und der Assoziativität n  c = s • n

Cache mit direkter Zuordnung (Direct-Mapped-Cache)     

Anzahl Sätze = Anzahl Blöcke Eins-Zu-Eins-Abbildung von HSP-Blöcken zu Blockrahmen im Cache Inhalt einer Adresse des HSP kann nur an einer einzigen Position im Cache liegen Aus Indexteil der HSP-Adresse ergibt sich direkt der Blockrahmen im Cache Größe ergibt sich: o C=Cachegröße=Anzahl Blöcke • Blockgröße = 2#q • 2#r = 2#q+#r...