Systeme 1 Kapitel 8.3 Betriebssystemaufgaben Kapitel 9.1 Betriebssysteme auf aktueller Hardware WS 2009/101

1

Systeme 1

Kapitel 8.3 Betriebssystemaufgaben

Kapitel 9.1Betriebssysteme

auf aktueller HardwareWS 2009/10

2

Letzte VorlesungVergleich Seitenersetzungsstrategien

WS 2009/10

Algorithmus Bewertung

Optimal Unrealisierbar, gedacht für Vergleiche

NRU (Not Recently Used) Sehr primitiv

FIFO (First-In, First-Out) Wichtige Seiten können entfernt werden.

Second Chance Enorme Verbesserung gegenüber FIFO

Clock Realistisch

LRU (Least Recently Used) Exzellent, schwierig zu implementieren

NFU (Not Frequently Used) Unoptimiert mit LRU vergleichbar

Aging Optimierter Algorithmus, der fast LRU erreicht.

Working set Etwas aufwändig in der Implementierung

WSClock Guter und effizienter Algorithmus

In der Realität wird insbesondere WSClock eingesetzt.

3

Letzte VorlesungBeladys Anomalie: Beispiel LRU• Zusammenfassung

– Wenn auf eine Seite zugegriffen wird, wird sie nach oben geschoben.– Wenn die Seite vorher schon in M war, verschieben sich alle Einträge

über ihr um eine Zeile nach unten. Die Einträge unterhalb bleiben unverändert.

WS 2009/10

0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 10 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1

0 2 1 3 5 4 6 3 7 4 7 7 3 3 5 3 3 3 1 7 1 3 40 2 1 3 5 4 6 3 3 4 4 7 7 7 5 5 5 3 3 7 1 3

0 2 1 3 5 4 6 6 6 6 4 4 4 7 7 7 5 5 5 7 70 2 1 1 5 5 5 5 5 6 6 6 4 4 4 4 4 4 5 5

0 2 2 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 60 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0P P P P P P P P P P P

4

Keller-Algorithmen• Der LRU Algorithmus aus dem vorherigen Beispiel zeigte eine besondere

Eigenschaft:

– wobei m die Anzahl der verfügbaren Seitenrahmen,– und r der Index der Referenzkette ist.

• D.h., wenn das Programm ein zweites Mal auf einem Interpreter mit m + 1 Seitenrahmen gestartet wird, so sind zu jedem Zeitpunkt alle Seiten im Speicher, die beim ersten Durchlauf im Speicher waren und zusätzlich eine weitere.

• Eine ganze Klasse von Algorithmen erfüllt diese Eigenschaften, die sogenannten Keller-Algorithmen (Stack-Algorithmen).

• Diese Klasse von Algorithmen ist nicht anfällig für die Belady Anomalie!

WS 2009/10

),1(),( rmMrmM

5

Distanzkette

• Abstraktere Art der Repräsentation einer Referenzkette• Eine Distanzkette ist definiert als

– Abstand einer Seite zum oberen Tabellenende bei deren Zugriff.– Ist eine Seite noch nicht in M, so ist ihr Abstand ∞.

WS 2009/10

0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 10 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1

0 2 1 3 5 4 6 3 7 4 7 7 3 3 5 3 3 3 1 7 1 3 40 2 1 3 5 4 6 3 3 4 4 7 7 7 5 5 5 3 3 7 1 3

0 2 1 3 5 4 6 6 6 6 4 4 4 7 7 7 5 5 5 7 70 2 1 1 5 5 5 5 5 6 6 6 4 4 4 4 4 4 5 5

0 2 2 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 60 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0P P P P P P P P P P P

∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ 4 2 3 1 5 1 2 6 1 1 4 2 3 5 3

Distanzkettefür M

6

Distanzkette

• Eine Distanzkette wird verwendet, um die Anzahl der Seitenfehler für verschiedene Speichergrößen vorherzusagen.

• Dazu wird die Distanzkette durchlaufen und das Vorkommnis jedes auftretenden Abstands gezählt.

WS 2009/10

0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 10 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1

0 2 1 3 5 4 6 3 7 4 7 7 3 3 5 3 3 3 1 7 1 3 40 2 1 3 5 4 6 3 3 4 4 7 7 7 5 5 5 3 3 7 1 3

0 2 1 3 5 4 6 6 6 6 4 4 4 7 7 7 5 5 5 7 70 2 1 1 5 5 5 5 5 6 6 6 4 4 4 4 4 4 5 5

0 2 2 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 60 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0P P P P P P P P P P P

∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ 4 2 3 1 5 1 2 6 1 1 4 2 3 5 3

Abstand Anzahl1 42 33 34 35 26 27 0∞ 8

7

Distanzkette

• Die Formel

– beschreibt dann die Anzahl der Seitenfehler Fm einer gegebenen Distanzkette,

– wobei Di die Häufigkeit des Abstands i bezeichnet,– n die Anzahl der virtuellen Seiten und– m die Anzahl der verfügbaren Seitenrahmen ist.

• Beispiel:

WS 2009/10

F1 F2 F3 F4 F5 F6 F7 F∞20 17 16 11 9 8 8 8

8

Lokale und Globale Strategien

• Seitenersetzungsalgorithmen wurden bisher nur für einzelne Prozesse betrachtet (lokale Strategien).

• In der Praxis laufen jedoch meist mehrere Programme (quasi-)parallel.

• D.h. der zur Verfügung stehende physikalische Speicher, muss unter den Prozessen aufgeteilt werden:– Bekommt beispielsweise ein Prozess für die komplette Laufzeit

eine feste Speichergröße zugeordnet, die kleiner als die maximal benötigte ist, so erzeugt der Prozess ständig Seitenfehler, obwohl u.U. noch freie Seitenrahmen auf dem System zur Verfügung stehen.

– D.h. eine dynamische Aufteilung des Speichers wird notwendig.

WS 2009/10

9

Globale Paging Strategien

• Eine globale Paging Strategie sollte den Prozess mit einer sinnvollen Speichergröße ausstatten und diese während der Ausführung dynamisch anpassen.

• Beispiel: Der Page Fault Frequency (PFF) Algorithmus:– Dieser Algorithmus misst die Anzahl der Seitenfehler eines

Prozesses in einem Zeitintervall.– Ist die Seitenfehlerrate eines Prozesses

• über Whigh, bekommt der Prozess einen zusätzlichen Seitenrahmen.

• unter Wlow, verliert der Prozess einen Seitenrahmen.

– Der Prozess nutzt dabei die Eigenschaften der Keller-Algorithmen (monoton fallende Seitenfehlerrate bei zusätzlichen Speicherrahmen).

WS 2009/10

10

Gemeinsame Seiten

• Führen zwei Prozesse das selbe Programm aus, ist es effizienter, Seiten gemeinsam zu nutzen, als mehrere Kopien der selben Seite im Speicher zu halten.

• Seiten auf die nur lesend zugegriffen wird, können gemeinsam genutzt werden.

• Seiten auf die auch schreibend zugegriffen wird, ist eine gemeinsame Nutzung in der Regel nicht möglich.

• Einfache Lösung: Zwei getrennte Adressräume für Daten und Programmcode. – Zwei getrennte Seitentabellen pro Prozess. – Gemeinsame Nutzung von Programmcode recht einfach möglich.

WS 2009/10

11

Gemeinsame Seiten• Gemeinsame Nutzung von Datenseiten ebenfalls möglich aber

komplizierter.• Beispiel: UNIX-Befehl fork()

– fork() erstellt eine exakte Kopie eines laufenden Prozesses.– Beide Prozesse verfügen über eine eigene Seitentabelle, deren Einträge

zeigen zunächst auf die selben Seitenrahmen. D.h. es werden zunächst keine Daten kopiert.

– Alle Datenseiten werden als READ_ONLY markiert.– Sobald ein Prozess schreibend auf eine Seite zugreift, wird eine

Schutzverletzung erkannt und diese Seite kopiert. Das READ_ONLY Flag gelöscht.

– Dieses Verfahren wird copy-on-write genannt und erhöht die Systemleistung, da in der Regel weniger Seiten kopiert werden müssen.

WS 2009/10

12

Systeme 1

Kapitel 9.1Betriebssysteme

auf aktueller Hardware

WS 2009/10

13

Zukünftige Bedeutung von NUMA-Hardware

Interview J. Goslin, Java Magazin, Februar 2008 „ … es ist ziemlich eindeutig, dass Moore‘s Law nicht mehr die

Taktrate sondern die Zahl der Kerne misst. Es scheint so, als ob sich die Anzahl der Kerne alle paar Jahre verdoppelt. In zehn Jahren etwa werden wir bei 128 CPUs liegen. In so einer Umgebung muss man ganz anders über Programmierung an sich denken.“

WS 2009/10

Konsequenz:• Forschung- und Entwicklungsschwerpunkt von

allgemeinen Betriebssystemen verlagert sich.• Betriebssysteme werden spezifischer auf

Hardware mit einer großen Zahl von Prozessorkernen angepasst.

James Goslin, Sun MicrosystemsErfinder der Programmiersprache Java

14

Moore‘s Gesetz

• Das Mooresche Gesetz (Moore, 1965, 1975 Korrektur)– Die Komplexität integrierter Schaltkreise (mit minimalen

Komponentenkosten) verdoppelt sich etwa alle zwei Jahre.– Komplexitätsmaß: Zahl elementarer Schaltkreise auf Chip

(auch pro Fläche)– Moore, 2007 (Intel Forum): Gesetz hat wahrscheinlich

noch 10 bis 15 Jahre Bestand, bevor fundamentale Grenze erreicht ist.

WS 2009/10

Gordon MooreIntel Mitbegründer

15

Moore‘s Gesetz

WS 2009/10

16

Moore‘s Law und Multiprozessor-Systeme

• Während Moores Gesetz mit enormen Geschwindigkeitszuwächsen für Computersysteme im allgemeinen einherging, konnten Multiprozessor-Systeme nur begrenzt davon profitieren:– Elektrische Effekte begrenzen die Geschwindigkeiten zwischen den

CPUs und erhöhen die Latenz zwischen CPU und Speicher.– Größerer Hauptspeicher erhöht die Komplexität für die Umsetzung

von logischen in physikalische Adressen und erhöht damit die Zugriffszeit auf Speicher.

– Speicherlatenz kann von manchen Prozessoren mit „out-of-order“ bzw. spekulativer Ausführung von Befehlen kompensiert werden. Auf Shared Memory Multiprocessor Systemen SMMP muss aber ein streng sequentieller Ablauf garantiert werden.

WS 2009/10

17

Aufbau eines modernen PCs

• PC-Architektur wurde an immer höhere Taktraten angepasst– Northbridge liegt zwischen CPU und Southbridge und

kommuniziert mit RAM.– Southbridge kommuniziert mit Northbridge und externen Devices

mit Schnittstellen, z.B.• PCI, PCI-Express, USB, SATA.

– Bei Mehrkern Prozessoren (z.B. Dualcore) mehrere Memory Controller

– Intel: Northbridge mit Memory-Crtl. , AMD: CPU mit lokalem Speicher

WS 2009/10

CPU

Northbridge

Southbridge

RAM

PCI-ESATAUSB

CPU

Northbridge

Southbridge

MC1

PCI-ESATAUSB

MC2

MC3

MC4

CPU

RAMRAM

RAMRAM

18

Aufbau eines modernen PCs• Verschiedene Ansätze reduzieren den sogenannten Flaschenhals,

die Transferzeiten z.B. zwischen RAM u. CPU– Mehrere Memory-Controller kommunizieren mit Northbridge.– Jede CPU kommuniziert direkt mit einem Memory Controller.

• Nachteil: jede CPU sieht nur ihren Speicherausschnitt, Transfers CPU<->CPU nötig

• Bezeichnung dieser Architekturen: NUMA– non-uniform memory architecture– Einige Speicherbereiche liegen physikalisch an anderen Bussen, daher

gibt es unterschiedliche Zugriffskosten.• NUMA-Factor: Kommunikationskosten einer Architektur• Spezielle NUMA-Hardware muss vom OS geeignet behandelt

werden.WS 2009/10

19

NUMA – Hardware und ihre OS-Integration

• Betriebssystemunterstützung von NUMA-Hardware– CPU mit lokalem RAM sollte möglichst Prozesse auf lokalem RAM ausführen

• Das Code-Segment (Text-Segment, enthält auszuführende Maschineninstruktionen) wird von mehreren CPUs verwendet

• Lösung: Spiegelung des Code-Segmentes in den lokalen RAM-Bereich jeder CPU

– Prozess-Migration• Ein Prozess sollte möglichst nicht auf eine andere CPU migriert werden (Transfer-

Kosten).

– Falls Migration nötig: • Wahl eines Prozessors mit geringerer Last• Wahl eines Prozessors mit niedrigen RAM-Zugriffs-/Transferkosten (z.B. Nachbar-CPU)

– Größe des lokalen Speicherbereich • Kann – bei unterschiedlichem Prozessbedarf – variieren• Der Speicherbedarf jeder CPU muss dynamisch angepasst werden.

WS 2009/10

20

Probleme beim konkurrierenden Speicherzugriff

Beim Design entsprechender Datenstrukturen müssen folgende Eigenschaften berücksichtigt werden:1. Nebenläufigkeit (Concurrency)2. Performanz3. Korrektheit4. SkalierbarkeitWS 2009/10

Shared-memory multiprocessors(SMMP) können nebenläufig mehrere Threadsausführen, die mit Datenstrukturen im gemeinsam genutzten Speicher (sharedmemory) kommunizieren und synchroni-siert werden müssen.

P1 P2 P3

Concurrent data structures

Shared Memory

Thread1 Thread2 Thread3

21

Beispiel: Datenstruktur shared counter

• Operation fetch-and-inc– Ein Wert wird aus einer Speicherzelle gelesen und um 1 erhöht.– Beispielszenario Threads T1, T2 (verschiedene CPUs)

WS 2009/10

Sequentielles fetch-and-incoldval = X;X = oldval+1;return oldval;

Lock-basiertes fetch-and-incaquire(lock(X));oldval = X; X = oldval+1;release(lock(X));return oldval;

Richtige Ergebnisse, jedoch• Sequentieller Flaschenhals• Blockierung• Contention

(Konkurrenzsituation)00

11

T1

0+1

Return 0

T20+1

Return 0

00

12

T1

0+1

Release LockReturn 0

T2

1+1Release lockReturn 1

Require lockRejected lock

Fehler: beide liefern 0!Schlechtes Interleaving

22

Probleme einfacher lock-basierter shared counter

1. Sequentielles Flaschenhalsproblem – zunächst: der IdealfallDie Beschleunigung skalierbarer Datenstrukturen steigt mit P

WS 2009/10

Beispiel: Applikation benötigt 1 s auf einem ProzessorAuf 10 Prozessoren benötigt diese 0.1 sec.Die Beschleunigung ist B=1 sec / 0.1 sec = 10

23

Sequentielles Flaschenhalsproblem

Amdahls Gesetz:Sei b der prozentuelle Anteil eines Programms, der nur sequentiell ausgeführt werden kann (seq. bottleneck). Die Beschleunigung B bei P Prozessoren ist:

Beispiel:b=10%, P=10

Es wird also wegen b=10% nur etwa die Hälfte der möglicher Maschinenkapazität genutzt.

WS 2009/10

Pb

bB

11

3.5

10%90

%10

1

B

24

Probleme einfacher lock-basierter shared counter

Steigerung der Performance durch:I. Reduzierung Länge des sequentiell bottlenecksII. Reduzierung der LockgranularitätIII. Reduzierung der Anzahl der Locks

Weitere Probleme:2. (Memory-) Contention: Ein Overhead im Datenaustausch der

zugrundeliegenden Hardware, da viele Threads nebenläufig z.B. auf die selbe Speicheradresse zugreifen. (auch Cache-Probleme).

3. Blockierung (Lock-Contention): Wenn der Thread, der gegenwärtig einen Lock hält, verzögert wird, werden alle anderen Threads, die versuchen auf dieselbe Ressource zuzugreifen ebenfalls verzögert.

WS 2009/10

25

Nichtblockierende Techniken mit Operationen

Der einfache Lock-freie shared Counter hat das Problem, dass bei ungünstigem Interleaving unkorrekte Ergebnisse entstehen können.

Lösung mit Operation CAS (Compare And Swap): Hardware Operation, die atomar das Laden und Speichern kombiniert.

WS 2009/10

Bool CAS(L, E, N){ // L Speicheradresse, E Referenzwert, N neuer Wert atomically { if (*L == E) { // Vergl. Wert an Adresse L mit E *L = N; // Zuweisung: Wert an Adresse L jetzt N return true; } else return false; }}

CAS-Operation im Pseudocode:

26

Umsetzung nicht-blockierender Counter mit CAS

Einfache Umsetzung Counter jeweils T1, T2:while (!CAS(X,*X,X+1));

• Lockfreie Alternative für fetch-and-inc• Herlihy 1991:

– Operationen, wie CAS oder LL/SC (load-linked/ stored-conditional) sind universell.

– Jede nebenläufige Datenstruktur kann wait-free realisiert werden, falls ein System diese Operationen unterstützt.

• wait-free bedeutet: eine Operation terminiert - ungeachtet dem Zeitverhalten andere Operationen - garantiert nach endlich vielen Schritten.

WS 2009/10

27

Nichtblockierende Synchronisation

• Aufbauend auf primitiven Operationen wie z.B. CAS, können auch Algorithmen für komplexere Datenstrukturen entwickelt werden.

• Diese Algorithmen nutzen die selben Strategien, um nichtblockierende Synchronisation zu gewährleisten.

• Beispiel:– Soll ein Prozess eine globale Datenstruktur verändern, so erstellt er

zunächst eine Kopie dieser. Anschließend verändert er die Kopie. – Haben sich die Originaldaten in dieser Zeit nicht verändert, so wird

diese Kopie zur neuen globalen Datenstruktur.– Haben sich die Daten verändert, verwirft der Prozess seine

geänderte Kopie und versucht es erneut.

WS 2009/10

28


• Ausgangspunkt– Zwei Prozesse– Eine globale Liste mit den Elementen A,B,C– Prozess 1 möchte Element D einfügen– Prozess 2 möchte Element B löschen

WS 2009/10

A B CPointer

29


• Prozess 1 und Prozess 2 erzeugen jeweils eine private Kopie der Liste

WS 2009/10

A B CPointer

A B CProcess 1

A CProcess 2

D

30


• Prozess 1 ist schneller fertig und seine Änderung wird wirksam.

WS 2009/10

A B CPointer

A B CProcess 1

A CProcess 2

D

31


• Prozess 2 muss seine Änderung verwerfen und erneut beginnen.

WS 2009/10

A B CPointer

A C DProcess 2

A BPointer

D

C D

A C DProcess 2

32


• Fokus auf Lock-Contention– Schwerpunkt um 1990 (u.A. Herlihy). Speicherlatenz

spielte noch keine so große Rolle.• Zwar können solche nichtblockierenden Techniken

ohne explizite Locks auskommen, jedoch bleibt– erhöhter Kommunikationsaufwand zwischen den

CPUs– erhöhte Speicherlatenz.

• Einführung einer neuen Art von Overhead durch wiederholte Versuche.

WS 2009/10

33

Speicherlatenz: Beispiel

Ein Programm mit zwei Variablen. Beide sind zunächst im Hauptspeicher.

WS 2009/10

CPU 0

Cache

CPU 1

Cache

MemoryA B

34

Speicherlatenz: Beispiel

CPU 1 lädt Variable A und modifiziert diese. CPU 2 lädt Variable B und modifiziert diese.Beide CPUs besitzen nun jeweils eine Kopie des Wertes in ihrem lokalen Cache.

WS 2009/10

CPU 0

Cache

CPU 1

Cache

MemoryA B

A B

35

Speicherlatenz: BeispielCPU 0 greift jetzt lesend auf Variable B zu. Beide CPUs haben jetzt jeweils eine Kopie von B in ihrem Cache. In dieser Situation muss jedes Mal, wenn CPU 1 den Wert von B ändert, CPU 0 gezwungen werden, den Wert von B zu validieren.

WS 2009/10

CPU 0

Cache

CPU 1

Cache

MemoryA B

A B

CPU 0

Cache

CPU 1

Cache

MemoryA B

A BB B

36

Speicherbarrieren

• Die Reihenfolge von Lese- und Schreibzugriffen kann von der Hardware / CPU bei Bedarf geändert werden.– „Weak Memory-Consistency Semantics“– Erhöht im Normalfall die Systemleistung– Erschwert die Synchronisation von SMMP

• CPUs besitzen Spezielle Befehle zum Unterbinden dieses Verhaltens.– Memory Barriers– Kosten Performance, insbesondere bei langen CPU-

Pipelines.

WS 2009/10

37

Asymmetrische Synchronisation

• Für bestimmte Fälle kann man die Speichersynchronisation vereinfachen

• Beispiel: „split-counter“– Nutze Kommutativgesetz der Addition: Ein Zähler kann

über mehrere CPUs unabhängig (ohne Synchronisation) erhöht werden.

– Synchronisationsoverhead wird auf Lesezugriff verschoben:• Dann müssen von allen CPUs die Werte zu einem Wert

zusammengezählt werden:

– Jedoch nur sehr begrenzte Einsatzmöglichkeiten:• Zum Beispiel: Statistiken (TCP/IP Paketzähler etc…)

WS 2009/10

38

Beispiel: Hash-Tabelle

Ausgangspunkt: Bereits gefüllte Hash-Tabelle. Potentiell (seltene) Updates.

WS 2009/10

Eintrag 0

Eintrag 1

Eintrag 30

Eintrag 31

…

Elemente

Elemente

Elemente

Elemente

Vorgehen:1.) Sichere exklusiven Zugriff2.) Berechne Hash Wert3.) Suche Element4.) Freigabe

39

Beispiel: Hash-TabelleBei diesem einfachen Beispiel hat das Hinzufügen von weiteren CPUs sogar negative Effekte.

In diesem Beispiel wird hauptsächlich lesend auf die Tabelle zugegriffen, dennoch muss dieser Zugriff vor potentiell (seltenen) schreibenden Zugriffen geschützt werden.

Frage: Wie kann man solche Zugriffsmuster ausnutzen ?

WS 2009/10

01 2 3 4

5

10

15

20

25

30

35

Has

h Ta

ble

Sear

ches

per

Mic

rose

cond

# CPUs

„ideal“„global“

Quelle: Paul E. McKenney„Exploiting Deferred Destruction: An Analysis of Read-Copy-Updates Techniquesin Operating System Kernels“, Dissertation Oregon State University, July 2004.

Documents

Systeme 1 Kapitel 8.3 Betriebssystemaufgaben Kapitel 9.1 Betriebssysteme auf aktueller Hardware WS 2009/101