Funktionsweise und Performancemessungen des LINUX O(1)-Schedulers

II

Erklärung

Hiermit erkläre ich, dass ich diese Diplomarbeit selbständig verfasst, noch nicht anderweitig für Prüfungszwecke vorgelegt, keine anderen als die angegebenen Quellen oder Hilfsmittel verwendet, sowie wörtliche und sinngemäße Zitate als solche gekennzeichnet habe.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alexander Zschach (Mannheim, den 31. August 2004)

III

Vorwort

Die Beschäftigung mit Schedulingmechanismen und die Verbesserung der bestehenden Realisie- rungen trat zu Beginn der 90er Jahre stark in den Hintergrund und machte anderen Themen Platz

- bspw. der Forschung und Entwicklung von und um JAVA 1 und dessen Komponenten. Die aner- kannte Fachwelt war der Meinung, es sei alles zu diesem Thema gesagt und geschrieben worden. Andrew S. Tanenbaum widmete in seinem Standardwerk zum Thema Betriebssysteme[Tan02] die- ser Thematik ein ausführliches Kapitel und nahm einzelne Strategien und Implementationen unter die Lupe.

Zum Beginn des neuen Jahrtausends rächte sich die Vernachlässigung der Thematik “Scheduler”. Den Architekturänderungen der neuen Prozessorgenerationen und gestiegenen Anforderungen an das Laufzeitverhalten von Betriebssystemen schienen die erprobten Mechanismen nicht mehr ge- wachsen. Linux und die BSD-Derivate waren nur eingeschränkt auf den Siegeszug von Multipro- zessormaschinen als High-End-Server in Hochleistungsnetzen vorbereitet und unterschätzten die Entwicklung weg vom Prozesskonzept hin in einen Threadkontext.

Neue Konzepte mussten gefunden, erprobte verworfen werden. Die Open Source Community mus- ste einen Weg beschreiten, der in der Hemisphäre der Softwarentwicklungswelt der freien Be- triebssysteme nicht selten in die Katastrophe führte - stabile Realisierungen sollten innheralb kür- zester Zeit komplett neuen Implementationen weichen, ohne dass sich die neuen Entwürfe ausgie- big im realen Betrieb bewähren konnten und einzelne Änderungen über einen langen Zeitraum sich einer “natürlichen Auslese” unterwerfen mussten. Der Gefahr, fehlerträchtige Betriebssy- stemkerne freizugeben, sah man ins Auge und heraus kamen Scheduler, deren Leistungsvermö- gen heutigen Prozessoren und aktuellen Anforderungen mehr als gerecht werden und alte Mankos ausbügeln.

Die vorliegende Diplomarbeit widmet sich in der Einführung den Anfängen der computerisierten Welt bis hin zur Entwicklung der ersten Time-Sharing Systeme um dann im zweiten Kapitel die Grundlagen für und von Scheduling im Allgemeinen detailliert zu beleuchten. Darauf folgend soll der 4BSD-Scheduler als Basis für eine ganze Generation an Schedulern detailliert beschrieben wer- den und im vierten Kapitel der O(1)-Scheduler und dessen Konzepte und Realisierung betrachtet werden.

1 JAVA ist ein eingetragenes Warenzeichen der SUN Inc.

IV

Abschließend wird derO(1)-Scheduler einer eingängigen Prüfung in seinem Laufzeitverhalten un- ter Symmetrischem Multiprocessing unterzogen und die Testergebnisse detailliert erläutert. Ab- schließend soll die vorliegende Arbeit ein Fazit ziehen und einen möglichen Ausblick auf die Welt der Scheduler von morgen geben.

Danksagung

Besonders danken möchte ich meinen Eltern, Ulrich und Birgit Zschach, die mir auf meinen ver- gangenen Wegen, in ruhigen wie turbulenten Zeiten, immer zur Seite standen und mich in all meinen Entscheidungen immer unterstützten und mir so das das Studium und diese Diplomarbeit erst ermöglichten. Außerdem danke ich meiner Schwester Annett Zschach-Keßler und meinem Schwager Frank Keßler.

Auch ganz besonders danken möchte ich Irina Haas, die mich in den vergangenen Wochen und Monaten unterstützte und aufbaute und auch ertrug, wenn es mal wieder eine Tiefphase gab, mir mit Rat und Tat zur Seite stand, mich motivierte, mir auch hin und wieder einen nötigen Schubs in die richtige Richtung gab und für mich da war.

Susanne Ullrich, weil sie diese Arbeit etliche male lesen durfte, obwohl sie von der Thematik nichts verstand, mir aber trotzdem Hinweise gab, wo ich etwas besser oder anders machen konnte.

Ich danke der Firma iCADA GmbH, weil sie mir die berufliche Möglichkeit gab, überhaupt bis zum Ende meines Studiums durchzuhalten und mir eine Perspektive nach dem Studium eröffnete.

Weiterhin danke ich (in alphabetischer Reihenfolge) Eva Autor, Thomas Forster, Volker Gratzka, Rita Grübel, Jens Heptaskin, Dirk Heuer, Misel Janosevic, Sven Johann, Gabriele John, Michael Keller, Mario Kiem, Michael Luz, Richard Mücke, Jan Naumann, Karina Ryschka, Peter Schne- bel, Johannes Schneider, Katrin Schneider, Stephan Schneider, Wjatscheslaw Wächter, Torsten Wegmann, Stephanie Weirauch und Kristina Wilhelm. Ihr ward mir treue und teure Wegbegleiter in den vergangenen Jahren.

Inhaltsverzeichnis I

Inhaltsverzeichnis

1 Einführung 1

1.1 Programmierer und Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Batchsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Resident Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Multiprogrammed Batched Systeme . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Time-Sharing Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Grundlagen 5

2.1 Prozesse und Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Threads und Prozesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 Multithreadingmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 Symmetric Multi-Threading (SMT) . . . . . . . . . . . . . . . . . . . .

2.2.3 Symmetrisches Multiprocessing (SMP) . . . . . . . . . . . . . . . . . .

2.2.4 Prozessoraffinität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.5 NUMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Prozessverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1 Prozesstatus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2 Prozesskontrollblock . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.3 Prioritätenmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1 Anforderungen an Scheduling . . . . . . . . . . . . . . . . . . . . . . .

2.4.2 Kooperatives Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.3 Preemptives Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.4 Schedulingalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Dispatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 4BSD und Derivate 41

3.1 Einführung in den 4BSD-Scheduler . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Prozessverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1 Prozesskontrollblock . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.2 Prozesslisten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Inhaltsverzeichnis II

3.3 Prioritäten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1 Zeitscheiben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Prozessauswahl und Kontextwechsel . . . . . . . . . . . . . . . . . . . .

3.5 SMP Unterstützung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4 Linux 2.6 - O(1)-Scheduler

4.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Grundfunktionen und -verhalten des O(1)-Schedulers . . . . . . . . . . . . . . .

4.2.1 likely und unlikely . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2 Prozess- und Kernelpreemption . . . . . . . . . . . . . . . . . . . . . .

4.2.3 Bestimmung der Quanten . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Prozesse und Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1 Entscheidung für m:n- oder 1:1-Threading-Modell . . . . . . . . . . . .

4.3.2 Thread Local Storage (TLS) und Global Descriptor Table (GDT) . . . . .

4.3.3 Symmetric Multithreading . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Prozessverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.1 Prozesszustände . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.2 Runqueue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.3 Prozesskontrollblock . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.4 De- und Enqueue-Funktionen der Prozessverwaltung . . . . . . . . . . .

4.5 Prioritäten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5.1 Prioritätsbereich- und Aufteilung . . . . . . . . . . . . . . . . . . . . .

4.5.2 Effektive Priorität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5.3 Prioritätsarrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.1 Periodisches Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.2 Hauptscheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.7 Symmetrisches Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . .

4.7.1 Ausbalancieren der Runqueues unter SMP . . . . . . . . . . . . . . . . .

4.7.2 Implizite Prozessoraffinität . . . . . . . . . . . . . . . . . . . . . . . . .

4.8 Echtzeitprozesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5 Messwerte und Testergebnisse 85

5.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Schedulerverhalten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.1 Kern- und Benutzerbereich . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2 Kontextwechsel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.3 Systemcalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.4 Prozessoraffinität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Prozessverhalten auf Betriebssystemebene . . . . . . . . . . . . . . . . . . . . . 95

Inhaltsverzeichnis III

5.3.1 Prozesserzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.3.2 Interprozesskommunikation . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Applikationen im Vergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.1 Apache2-Webserver mit dynamischen und statischem Inhalt . . . . . . .

5.4.2 Datenbank-Performance . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6 Schlusswort 101

6.1 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

A Benchmarkquelltexte, -Tools und -System 104

A.1 Systembeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

A.2 Verwendete externe Tools und Aufrufe . . . . . . . . . . . . . . . . . . . . . . . 105

A.3 Vorgenommene Änderungen an den Vanilla-Kerneln . . . . . . . . . . . . . . . 105

A.3.1 Implementation eines Systemaufrufs unter 2.6.7 . . . . . . . . . . . . . 105

A.3.2 Implementation eines Systemaufrufs unter 2.4.27 . . . . . . . . . . . . . 106

A.4 Quelltexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

A.4.1 Globale Makros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

A.4.2 Benchmark Prozessverdrängungs-Latenzen . . . . . . . . . . . . . . . . 108

A.4.3 Benchmark Prozesserzeugung . . . . . . . . . . . . . . . . . . . . . . . 109

A.4.4 Benchmark Prozessor-Affinität . . . . . . . . . . . . . . . . . . . . . . . 114

B Abkürzungsverzeichnis 121

C Literaturverzeichnis 123

Abbildungsverzeichnis IV

Abbildungsverzeichnis

2.1 Unterschied zwischen Prozessen und Threads . . . . . . . . . . . . . . . . . . . 6

2.2 Exemplarische Erzeugung von Userthreads . . . . . . . . . . . . . . . . . . . .

2.3 Exemplarische Erzeugung von Kernelthreads . . . . . . . . . . . . . . . . . . .

2.4 m:1 Multithreadingmodell mit drei Userthreads und einem Kernthread . . . . . .

2.5 1:1 Multithreadingmodell mit drei Userthreads und drei Kernthreads . . . . . . .

2.6 1:1 Multithreadingmodell mit drei Userthreads und zwei Kernthreads . . . . . .

2.7 CPU Architektur herkömmlicher und SMT-fähiger Prozessoren . . . . . . . . . .

2.8 Fetch/Decode-Einheit eines Intel x86-Prozessors [Int98] . . . . . . . . . . . . .

2.9 Dispatch/Execution-Einheit eines Intel x86-Prozessors [Int98] . . . . . . . . . .

2.10 Semaphoren bei bedingt kritischen Kernregionen . . . . . . . . . . . . . . . . .

2.11 Symmetrisches Multiprocessing mit Master-Slave-Prinzip . . . . . . . . . . . . .

2.12 Darstellung eines lose gekoppelten Multiprozessorsystems (NUMA) . . . . . . .

2.13 Diagramm einzelner Prozesszustände . . . . . . . . . . . . . . . . . . . . . . .

2.14 Darstellung eines beispielhaften Prozesskontrollblocks [S + 00] . . . . . . . . . .

2.15 Unterschiede zwischen CPU- und I/O gebundenen Prozessen . . . . . . . . . . .

2.16 Verdeutlichung kooperatives und preemptives Scheduling . . . . . . . . . . . . .

2.17 FCFS-Scheduling Ablauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.18 Gantcharts eines Beispielhaften FCFS Verhaltens . . . . . . . . . . . . . . . . .

2.19 Shortest Job First Scheduling-Algorithmus . . . . . . . . . . . . . . . . . . . . .

2.20 Darstellung des exponentiellen Durchschnitts (Gewichtung α)[SG94] . . . . . .

2.21 Gantchart eines Beispielhaften Shortest Job First Szenarios . . . . . . . . . . . .

2.22 Gantchart eines beispielhaften Round-Robin Szenarios . . . . . . . . . . . . . .

2.23 Multilevel-Feedback Queue Algorithmus . . . . . . . . . . . . . . . . . . . . .

2.24 Exemplarischer Kontextwechsel zweier Prozesses [SG94] . . . . . . . . . . . . .

2.25 Speicherung der Registersätze in Hauptspeicher . . . . . . . . . . . . . . . . . . 38

3.1 Einfluß des Decay-Filters auf die Schedulerpriorität eines Prozesses . . . . . . . 49

4.1 Verhalten der Quantengröße zur statischen Priorität [Mau04] . . . . . . . . . . .

4.2 Vereinfachter Aufbau der CPU eigenen GDT-Datenstruktur . . . . . . . . . . . .

4.3 Abgleichen der TLS- und GDT-Threadeinträge . . . . . . . . . . . . . . . . . . 58

Abbildungsverzeichnis V

4.4 Ausgeglichene und unausgeglichene SMT-Einheiten eines Dual-Prozessorsystems 60

4.5 Verkettete Top-Down Prozessverwaltung unter Linux . . . . . . . . . . . . . . . 61

4.6 Prioritätskala unter Linux 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.7 Bonusberechnung in Abhängigkeit von p->sleep_avg[Mau04] . . . . . . . . .

4.8 Prioritätsbitmap des Active-Arrays zur Auswahl des nächsten Prozesses . . . . .

5.1 Dauer der Kern- und Benutzerbereichsausführung . . . . . . . . . . . . . . . . .

5.2 Anzahl der Kontextwechsel je Messung . . . . . . . . . . . . . . . . . . . . . .

5.3 Durchschnittliche Anzahl Kontextwechsel . . . . . . . . . . . . . . . . . . . . .

5.4 Kontextwechsel-Latenzen unter Linux 2.6 . . . . . . . . . . . . . . . . . . . . .

5.5 Latenzen einzelner Kontextwechsel bei n Prozessen . . . . . . . . . . . . . . . .

5.6 Durchschnittliche Dauer eines Systemaufrufs . . . . . . . . . . . . . . . . . . .

5.7 Durchschnittliche implizte Prozessoraffinität . . . . . . . . . . . . . . . . . . . .

5.8 Kosten für Prozesserzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.9 Interprozesskommunikation zwischen n Prozessen . . . . . . . . . . . . . . . . .

5.10 Apache2 Requests pro Sekunde . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.11 MySQL Select-Requests pro Sekunde . . . . . . . . . . . . . . . . . . . . . . . 100

5.12 Update/Select-Requests pro Sekunde . . . . . . . . . . . . . . . . . . . . . . . . 100

Tabellenverzeichnis VI

Tabellenverzeichnis

2.2 Im TSS zu sichernde Register des Motorola 680x0 . . . . . . . . . . . . . . . . . 38

3.1 Kernelprioritäten für Prozesse unter 4BSD . . . . . . . . . . . . . . . . . . . . . 47

Listings VII

Listings

2.1 TSS Beispielstruktur unter Motorola 680x0 . . . . . . . . . . . . . . . . . . . . 38

2.2 Beispielhafter Kontextwechsel in einer Motorola 680x0 Umgebung und Assembler 39

3.1 Darstellung des 4BSD Prozesskontrollblocks . . . . . . . . . . . . . . . . . . . . 42

3.2 Auswahl eines ablauffähigen Prozesses in vax/locore.s für eine VAX . . . . .

3.3 Sichern und Laden des Maschinenstatus in den PCBs für eine VAX . . . . . . . .

4.1 Definition der Codeoptimierungs-Makros likely und unlikely . . . . . . . . .

4.2 Deklaration der Frequenzkonstanten F (HZ) in include/asm/param.h . . . . . .

4.3 Runqueue Linux 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Linux task_struct Auszug aus linux/sched.h . . . . . . . . . . . . . . . . .

4.5 Einhängen eines Prozesskontrollblocks in ein Prioritätsarray . . . . . . . . . . .

4.6 Ausketten eines Prozesskontrollblocks in ein Prioritätsarray . . . . . . . . . . . .

4.7 Makros für die Zuordnung der Prioritätswerte in include/linux/sched.h . . .

4.8 Macros zur Bonusberechnung in kernel/sched.c . . . . . . . . . . . . . . . .

4.9 Definition der maximalen Benutzerpriorität in include/linux/sched.h . . . .

4.10 Prioritätsarray aus kernel/sched.c . . . . . . . . . . . . . . . . . . . . . . . .

4.11 Berechnung der Bitmapgröße des Prioritätsbitmaps in kernel/sched.c . . . . .

4.12 Parameterinitialisierung in der Funktion scheduler_tick() . . . . . . . . . . .

4.13 Schedulerverhalten bei einer Idle-CPU . . . . . . . . . . . . . . . . . . . . . . .

4.14 Signalisierung der Verdrängung des aktuellen Tasks . . . . . . . . . . . . . . . .

4.15 Behandlung von Realtime-Prozessen durch sched_tick() . . . . . . . . . . . .

4.16 Verdrängung eines Prozesses, der sein Quantum aufgebraucht hat . . . . . . . . .

4.17 Setzen des expired-Zeitstempels der Runqueue . . . . . . . . . . . . . . . . . .

4.18 Entscheidung über die Taskliste, in welcher ein Task eingehängt wird . . . . . .

4.19 Verhinderung der CPU-Monopolisierung durch einen Task . . . . . . . . . . . .

4.20 Verlassen eines bedingt kritischen Kernel-Bereichs . . . . . . . . . . . . . . . .

4.21 Variablendeklaration in schedule() . . . . . . . . . . . . . . . . . . . . . . . .

4.22 need_resched-Label in schedule() . . . . . . . . . . . . . . . . . . . . . . .

4.23 Ausbalancieren der Runqueues im Hauptscheduler . . . . . . . . . . . . . . . .

4.24 Austauschen des active- und expired-Arrays . . . . . . . . . . . . . . . . . .

4.25 Auswahl des nachfolgenden Prozesses . . . . . . . . . . . . . . . . . . . . . . .

4.26 Aufruf der Funktion dependent_sleeper() . . . . . . . . . . . . . . . . . . . 78

Listings VIII

4.27 Überprüfung auf Neuberechnung der Priorität . . . . . . . . . . . . . . . . . . . 78

4.28 Vorbereiten des Low-Level Kontextwechsels . . . . . . . . . . . . . . . . . . . . 4.29 Aufruf des Low-Level Kontextwechsels . . . . . . . . . . . . . . . . . . . . . . 4.30 Verlassen des Hauptschedulers . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.31 Bestimmung der Cache-Lastigkeit eines Tasks . . . . . . . . . . . . . . . . . . . 4.32 Behandlung von Echtzeitprozessen in effective_prio() . . . . . . . . . . . .

A.1 Erweiterung der 2.6.7 linux/sched.c . . . . . . . . . . . . . . . . . . . . . . . 105 A.2 Erweiterung der 2.6.7 arch/i386/kernel/entry.S . . . . . . . . . . . . . . . 106 A.3 Erweiterung der 2.6.7 include/asm/unistd.h . . . . . . . . . . . . . . . . . . 106 A.4 Erweiterung der 2.4.27 kernel/sched.c . . . . . . . . . . . . . . . . . . . . . 106 A.5 Erweiterung der 2.4.27 arch/i386/kernel/entry.S . . . . . . . . . . . . . . 107 A.6 Globale Makros von mehrere Quellen verwendet . . . . . . . . . . . . . . . . . 107 A.7 Quelltext des Testprogramms loop_yield . . . . . . . . . . . . . . . . . . . . . . 108 A.8 Kompilierungsaufruf für das Benchmarkprogramm loop_yield . . . . . . . . . . 109 A.9 Aufruf des Benchmarkprogramms loop_yield . . . . . . . . . . . . . . . . . . . 109 A.10 Aufruf Systemprogramms vmstat . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.11 Headerdatei für fork_pipe.c . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.12 Quelltextdatei fork_pipe.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 A.13 Kompilierungsaufruf für das Benchmarkprogramm fork_pipe . . . . . . . . . . . 114 A.14 Aufruf des Benchmarkprogramms fork_pipe . . . . . . . . . . . . . . . . . . . . 114 A.15 Headerdatei sched_aff.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 A.16 Quelltextdatei sched_aff.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 A.17 Kompilierungsaufruf für das Benchmarkprogramm sched_aff . . . . . . . . . . . 120 A.18 Aufruf des Benchmarkprogramms sched_aff . . . . . . . . . . . . . . . . . . . . 120

1

Kapitel 1

Einführung

“Those who cannot remember the past

1.1 Programmierer und Operator

In den 50er Jahren des vergangenen Jahrhunderts wurden Rechner von nur einer Person sowohl programmiert, als auch bedient. Der Programmierer griff über eine Konsole auf den Rechner zu, welche die einzige interaktive Schnittstelle zwischen dem Rechner und seiner Außenwelt darstell- te.

Um einen Job erfolgreich abarbeiten zu können, waren mehrere Arbeitsschritte notwendig. Zum Ersten musste die zu erledigende Aufgabe programmiert und ausgeführt werden. Der Programmie- rer schrieb also das Programm, lud das notwendige Übersetzungsprogramm in den Arbeitsspeicher des Rechners, um den Quelltext in Maschinensprache zu kompilieren 2 und führte das übersetzte Programm aus. Traten bei der Ausführung des Jobs Fehler auf, so stoppte der Programmierer den Prozess und kümmerte sich um die Fehlerbeseitigung. Konnte der Fehler behoben werden, startete er den Prozess erneut.

Bei diesem Vorgehen wurde jedoch ein Problem signifikant - die wenigste Zeit, die ein Rech- ner belegt war, kam der Abarbeitung eines Jobs zugute. Die meiste Zeit jedoch wurde für das Programmieren, das Einbinden von Festspeichermedien (bspw. Bandlaufwerke), das Laden von Übersetzern, das Neuladen von Jobs und für das Debugging verbraucht. Während der Program- mierung der Maschine oder im Falle eines Fehlers stand die CPU still - sie verharrte im Leerlauf.

2 Anfangs wurde einzig in Assembler programmiert. Assembler ist aufgrund seiner Nähe zur Maschinensprache eine äußerst komplexe und fehlerträchtige Sprache. Später kamen Hochsprachen, wie FORTRAN oder COBOL hinzu.

1.2. BATCHSYSTEME 2

Aufgrund der Preise für Rechner zu dieser Zeit war dieser Leerlauf jedoch eine sehr kostspieli- ge Angelegenheit. Es bestand ein immenses Interesse daran, die tatsächliche Rechnerauslastung durch die Ausführung von Jobs zu optimieren.

Diesem Dilemma wurde begegnet, indem die Bedienung der Rechner von der Programmierung losgelöst wurde. Die Bedienung übernahmen Operatoren, die einzig die Programme übersetzten und abarbeiten ließen. Kam es zu Fehlern, so stoppte der Operator den Job und übergab dem Pro- grammierer einen Fehlerbericht mit den relevanten Auszügen aus dem Speicher und den Registern.

In der Zeit, in der der Programmierer sich nun um die Fehlerbeseitigung kümmerte, konnte der Operator den nächsten Job ausführen. Diese Aufgabenteilung führte zu einer höheren Auslastung der Rechner und steigerte die Produktivität des Computers immens.

1.2 Batchsysteme

Nach der Einführung der ersten Hochsprachen, wie COBOL oder FORTRAN wurde die Ausfüh- rung einzelner Jobs durch das ständige Neuladen der jeweiligen Compiler weiter verzögert. Für jeden auszuführenden Job musste zuerst der Übersetzer geladen werden um das Programm in eine ausführbare Einheit zu übersetzen. Diesem Problem konnte begegnet werden, indem semantisch gleiche Aufgabe gesammelt und zu Stapeln zusammengefasst wurden.

Lag eine ausreichende Anzahl an Jobs auf dem Stapel, so wurde der Compiler einmal geladen und der Jobstapel in das notwendige Binärformat übersetzt - die so übersetzten Programme wurden danach auf Lochkarten oder später auf Magnetbändern oder Magnetkernspeichern abgespeichert um sie dann Stapelweise auszuführen. Auf diese Weise sparte man sich das ständig erneute La- den der Übersetzer und konnte durch die sequentielle Ausführung der übersetzten Programme die Leistungsfähigkeit der Rechner weiter ausreizen.

1.3 Resident Monitor

Den entscheidenden Schritt jedoch ging man mit der Entwicklung des Resident Monitor und des automatic job sequencing. Der Resident Monitor wurde zum Rechnerstart einmal geladen und von da an fest im Speicher gehalten.

Dem Rechner wurde nun der Stapel Programme übergeben und der Resident Monitor übergab der Reihe nach die CPU an den nächsten Job. Stoppte der aktive Prozess, so nahm sich der Resident Monitor die Kontrolle zurück und ließ den nachfolgenden Job laufen. Mit dem Resident Monitor und dem automatic job sequencing schuf man quasi das erste rudimentäre Betriebssystem [SG94].

1.4. MULTIPROGRAMMED BATCHED SYSTEME 3

1.4 Multiprogrammed Batched Systeme

Ein weiterer Faktor, der eine höhere Auslastung der CPU verhinderte war die Beeinträchtigung des Laufzeitverhaltens der Jobs durch Ein- und Ausgabe auf sequentiell beschriebene Medien. Ein Job musste für eine Ein- oder Ausgabe auf ein externes Medium unterbrechen, darauf warten, dass die Daten geschrieben oder geladen wurden um dann fortzufahren. In dieser Zeit verweilte die CPU im Stillstand.

Beeinträchtigt wurde dies nicht nur dadurch, dass externe Medien langsamer waren, als die CPU, sondern vor allem durch die Latenzen und Zugriffszeiten der damaligen Festspeicher. Sollten Da- ten bspw. von einem Magnetband geladen werden, so musste dieses erst an die entsprechende Stelle gespult werden um die benötigten Daten zu lesen. Folgte dem ein Schreibvorgang, musste das Band erst wieder an die nächste freie Stelle spulen um die Daten fassen zu können.

Diesem Kostenfaktor konnte durch die Entwicklung und Einführung von Speichern mit direktem Zugriff und sequentiellen 3 bzw. zufälligen 4 Speicherpunkten und entsprechend stark verringerten Zugriffszeiten begegnet werden.

Die Steuerung dieser Medien übernahm nun nicht mehr die CPU direkt, sondern spezielle Control- ler für diese Medien. Die Einführung der Hardwarecontroller für externe Speicher schuf die Mög- lichkeit, Rechen- und Medienzugriffsoperationen von einander zu trennen (Off-Line-Processing). Das Blockieren eines Prozesses wegen einer Ein- oder Ausgabeoperation blockierte nun nicht mehr das ganze System, bis die I/O-Operation ausgeführt war. Der blockierte Job wurde auf die Seite “geschoben”, bis die benötigten Daten eingetroffen oder geschrieben waren. In der Zwi- schenzeit konnte die CPU einem anderen Prozess aus der Warteschlange zugeteilt werden.

Nach erfolgter I/O-Operation des blockierten Prozesses war dieser nun wieder bereit, die Kontrolle über die CPU zurückzuerlangen und er wurde vom System am Ende der Warteschlange wieder eingereiht.

Durch diese Aufteilung und die Einführung neuer Festspeicher und entsprechender Controller ließ sich mit wachsender Größe der Hauptspeicher Multiprogramming und Job Scheduling etablie- ren und die Leerlaufzeiten der Recheneinheiten weiter senken. Die größeren Hauptspeicher spielen hierbei eine zentrale Rolle. Multiprogramming ist nur dann möglich, wenn man die Möglichkeit hat, mehrere Programme parallel im Hauptspeicher zu halten. Nur so kann ein blockierender Pro- zess durch einen anderen ersetzt werden.

3 Direct Access Memory (DAM). Bei diesen Speichermedien werden die Daten sequentiell gespeichert (vgl. Bandlauf- werke), auf das Medium jedoch wird direkt zugegriffen (detailliert beschrieben in [TG01]).

4 Random Access Memory (RAM). Die Daten werden hierbei an unterschiedlichen, nicht vordefinierten Punkten ge- speichert und der Zugriff ist, wie bei DAMs auch, direkt. RAM jedoch ist kein Synonym für Lese/Schreib-Speicher, wie den Hauptspeicher; Nur-Lese-Speicher (ROM) sind auch Random Access Memorys (detailliert beschrieben in [TG01]).

1.5. TIME-SHARING SYSTEME 4

1.5 Time-Sharing Systeme

Time-Sharing Systeme stellen die logische Weiterentwicklung von Multiprogrammed Batch Sy- stemen dar. Zwar erreichte man mit Multiprogramming eine hohe Effektivität in der Auslastung der Computerressourcen, jedoch war keine Interaktion von Benutzern mit den Rechnern möglich. Um dies zu erreichen benötigte man eine Quasiparallelität (auch virtuelle Parallelität genannt) von laufenden Prozessen - Multitasking.

Multitasking ermöglicht das Interagieren eines oder mehrerer Benutzer über Tastatur und Maus mit dem Betriebssystem selbst. Multitasking heißt, dass zwischen den laufenden Prozessen in- nerhalb kurzer Zeit hin- und hergeschalten werden muss. Diese Quasiparallelität und die kurzen Antwortzeiten gaukeln so den Benutzern eines Time-Sharing Systems vor, sie griffen als einzige auf den Rechner zu.

Die Krux hinter Time-Sharing ist nun, die vorhandene CPU-Zeit so zwischen den Benutzeranfor- derungen aufzuteilen, dass keiner zu kurz kommt, jedoch die Antwortzeiten auf Benutzereingaben innerhalb eines vertretbaren Zeitraums geschehen. Um dies zu erreichen bedient man sich dem Scheduling und Multiprogramming.

In den frühen 60er Jahren entwickelte das Massachusettes Institute of Technologie das Compatible Time-Sharing System (CTSS) welches aber aus den unterschiedlichsten Gründen kein besonde- rer Erfolg war. Hauptsächlich lag dieser Misserfolg darin begründet, dass Time-Sharing Systeme komplexe Gebilde sind, die neben einem effizienten Scheduling auch u. a. ein gutes Speichermana- gement (mit virtuellem Speicher und Swappingfunktion), Benutzerrechten und Schutzfunktionen zwischen Kernel- und Benutzermodus bzw. innerhalb der Benutzermodi, etc. benötigen. All diese Anforderungen an Time-Sharing Systeme trieben die Kosten für das CTSS zu stark in die Höhe, was sich nachteilig auf den Verkauf des CTSS auswirkte.

Gegen Ende der 60er Jahre entwickelte das M. I. T. in Zusammenarbeit mit General Electrics und den Bell Laboratories den UNIX-Vorläufer 5 MULTICS 6 . MULTICS wurde zwar nie fertig gestellt, doch durch die weite Verbreitung der MULTICS-Quellen unter den ursprünglichen Entwicklern bei AT&T fanden die Grundfunktionen später Einzug in den ersten AT&T-Unixes und wurden so über BSD-Unix bis hin zu POSIX und System V verbreitet.

5 Der Name UNIX leitet sich aus UNICS ab - UNified Information Computing System

6 MULTiplexed Information and Computing System. Die Geschichte von MULTICS und UNIX kann u. a. in [Ray03] detailliert nachgelesen werden.

5

Kapitel 2

Grundlagen

2.1 Prozesse und Programme

Ein Prozess ist definiert als ein Programm in Ausführung. Hieraus ist ersichtlich, dass zwischen einem Prozess und einem Programm ein elementarer Unterschied besteht. Ein Prozess benötigt Sy- stemressourcen, wie Hauptspeicher, Rechenzeit, I/O Zugriffe, etc. um seine Aufgabe zu erfüllen. Prozesse sind aktive Einheiten wohingegen Programme passiv auf einem sekundären Speicherme- dium darauf warten, ausgeführt zu werden.

Weiterhin können von einem Programm mehrere Prozesse im Hauptspeicher auf Zuteilung zur CPU warten. Dies kann dadurch zustande kommen, dass

I ein Prozess ein oder mehrere Unterprozesse (Kindprozesse) erzeugt (fork) oder

I Benutzer ein Programm mehrfach aufrufen (bspw. eine Shell)

Die Inhalte der Prozessvariablen werden an unterschiedlicher Stelle aufbewahrt - die Inhalte der lokalen Variablen verweilen im Prozesstack, wohingegen die globalen Variablen des Jobs in der Data Section aufbewahrt werden.

2.2. THREADS UND PROZESSE 6

2.2 Threads und Prozesse

Threads sind die kleinste ausführbare Einheit eines Prozesses - jeder Prozess kontrolliert wenig- stens einen Thread, der auf dem Prozessor zur Ausführung kommt. Jeder Thread besitzt eine ThreadID, einen Programmzähler (program counter - PC), einen Registersatz und einen Stack.

Mit moderneren Betriebssystemen und insbesondere der Einführung und Etablierung von JAVA und der zugehörigen JAVA Virtual Machine (JVM) wurde dieses traditionelle Singlethreading um Multithreading erweitert - ein Prozess kann nun also einen oder mehrere Threads kontrollieren. Multithreading ermöglicht es - wie Multiprocessing - mehrere Aufgaben eines Prozesses neben- läufig erledigen zu lassen. Außerdem ermöglicht Multithreading das Verteilen mehrerer Aufgaben eines Prozesses auf mehrere CPUs in einem Multiprozessorsystem.

(a) Drei Prozesse mit je einem Thread

(b) Drei Prozesse mit Multithreads

Abbildung 2.1: Unterschied zwischen Prozessen und Threads

Der Vorteil gegenüber Multiprocessing liegt jedoch in einer erheblichen Kostenreduktion. Jedem neuzuerstellenden Prozess muss das Betriebssystem eigene Betriebsmittel zuweisen, was mit ei- nem erheblichen Overhead einhergeht. Threads hingegen müssen bei der Erstellung keine weiteren Betriebsmittel zugewiesen werden, da Threads auf die Betriebsmittel des erzeugenden Prozesses zugreifen - alle Threads eines Prozesses liegen im selben Speicheradressraum.

2.2. THREADS UND PROZESSE 7

Threads, die auf Betriebssystemebene unterstützt und von diesem direkt verwaltet werden, werden als Kernelthreads bezeichnet. Vom Betriebssystem nicht verwaltete Threads bezeichnet man als Userthreads.

Userthreads

Werden Threads nicht auf der Ebene des Betriebssystems direkt unterstützt, so spricht man von Userthreads. Das Betriebssystem ist hierbei nicht fähig, Threads zu schedulen, sondern verwal- tet nach wie vor die traditionellen Prozesse. Dies bedeutet, dass wenn ein Thread blockiert, so blockiert der gesamte zugehörige Prozess. Besitzt der nun blockierte Prozess noch weitere Th- reads, die eigentlich ausgeführt werden könnten, so kommen diese bis zur Beseitigung des Bloc- kiergrundes, trotzdem nicht zum Zuge.

Abbildung 2.2: Exemplarische Erzeugung von Userthreads

Der Vorteil von Userthreads ist, dass diese einfach und kostengünstig zu erzeugen sind, da sie nicht vom Betriebssystem verwaltet werden müssen.

Kernelthreads

Betriebssysteme, die Threading direkt unterstützen haben sich vom traditionellen Prozesskonzept verabschiedet. Die Prozessverwaltung (sic!) kennt hierbei keine Prozesse mehr, sondern nur noch Threads. Da ja, wie zuvor beschrieben, jeder Prozess mindestens einen Thread kontrolliert, wird ein Prozess von seinem darunter liegendem Thread im Betriebssystem repräsentiert.

Blockiert ein Kernelthread eines Prozesses, so beeinträchtigt dies nicht mehr die Lauffähigkeit an- derer Threads des Prozesses - sind sie im Status “Ready”, so können sie trotzdem zur Ausführung kommen.

2.2. THREADS UND PROZESSE 8

Abbildung 2.3: Exemplarische Erzeugung von Kernelthreads

2.2.1 Multithreadingmodelle

Die meisten modernen Betriebssystemkerne unterstützen beides - User- und Kernelthreads. Auf diese Weise ist es möglich, die Vorteile beider Varianten - geringe Erzeugungskosten und Mul- tiprozessorfähigkeit - auszukosten und durch unterschiedliche Modellimplementationen den Ein- fluss des jeweils nachteiligen Verhaltens zu minimieren.

Modellimplementation bezeichnet hierbei die Art, wie die Threads im Kern repräsentiert werden. Es werden drei Arten von Multithreadingmodellen unterschieden.

n:1 Modell

Beim n:1 Modell wird jedem Kernelthread mehrere Userthreads zugewiesen. Programme mit mehreren Threads erzeugen diese jedoch nicht auf Kern-, sondern auf Benutzerebene (Userth- reads) und das Betriebssystem übernimmt die Zuweisung zu den Kernelthreads. Hierin liegt die Stärke des n:1 Modells - es nutzt die kostengünstige Erzeugung von Benutzerthreads und mini- miert die Kosten für Kernelthreads.

Nachteilig jedoch ist, dass die Lauffähigkeit der Benutzerthreads die einem Kernelthread zugeord- net sind, voneinander abhängt. Blockiert in einem Kernthread ein Job, so blockiert der gesamte Kernthread (und alle ihm zugeordneten Jobs). Außerdem ist im n:1 Modell nur eine eingeschränk- te parallele Verarbeitung von Jobs auf System mit mehreren Prozessoren möglich, da immer nur Kernthreads der CPU zugeteilt werden und weitere Threads dieses Kernthreads nicht auf einer an- deren CPU zum Zuge kommen können. Alle weiteren Threads in diesem Kernthread müssen auf die Freigabe der CPU warten. Letztlich schwächt dieser Nachteil auf Multiprozessorsystemen die Vorteile dieses Modells über die Maßen.

2.2. THREADS UND PROZESSE 9

Abbildung 2.4: m:1 Multithreadingmodell mit drei Userthreads und einem Kernthread

1:1 Modell

Bei diesem Modell wird jeder Benutzerthread einem Kernelthread zugeordnet. Dies ermöglicht, dass ein blockierender Thread die Ausführbarkeit keines anderen Threads beeinträchtigt und echte Parallelität der Threadabarbeitung auf Multiprozessorcomputern erreicht wird.

Abbildung 2.5: 1:1 Multithreadingmodell mit drei Userthreads und drei Kernthreads

Jedoch muss man bei der Implementierung des 1:1 Modells einen entsprechenden Overhead zur Erzeugung und Verwaltung von gleich vielen Kernelthreads, wie Userthreads existieren, in Kauf nehmen und kann nicht von der kostengünstigen Verwaltung auf Benutzerebene profitieren. Der resultierende Overhead kann derart gewaltig sein, dass die Performance einer Anwendung nicht zu vertretende Einbußen hinnehmen muss. Aus diesem Grund limitieren die meisten Systeme, die dieses Modell realisieren, die maximale Anzahl an Threads (bspw. LinuxThreads 7 ).

7 siehe Kapitel 4.3.1 auf Seite 57

2.2. THREADS UND PROZESSE 10

n:n Modell

Das n:n-Modell versucht den Nachteil der mangelnden Multiprozessorfähigkeit des n:1-Modells und die hohen Kosten für die Kernelthreaderzeugung des 1:1-Modells zu kompensieren, in dem es einer Menge Kernelthreads mehrere oder gleichviele Userthreads zuweist. Die Anzahl der Userthreads je Kernelthread variiert nach Anwendung oder Maschine. So werden die Userthreads einer Anwendung auf einer Multiprozessormaschine eher mehreren Kernelthreads zugewiesen, als auf einer Uniprozessormaschine.

Abbildung 2.6: 1:1 Multithreadingmodell mit drei Userthreads und zwei Kernthreads

Die Menge an Kernelthreads bzw. die Menge an Userthreads, die einem Kernelthread zugewiesen werden muss nicht festgelegt sein. Es ist möglich, diese Modell so zu implementieren, dass mit steigender Anzahl an Userthreads, die Kernelthreads eine größere Menge Benutzerthreads aufneh- men um den Systemoverhead durch die kostenintensive Kernelthread-Erzeugung zu minimieren.

Durch eine überdachte Zuteilung mehrerer Benutzerthreads einer Applikation zu verschiedenen Kernelthreads kann nahezu echte Nebenläufigkeit auf einem Uniprozessorsystem oder volle echte Nebenläufigkeit auf einem Multiprozessorsystem realisiert werden. Blockiert dabei ein Thread einer Anwendung, kann der Scheduler einen anderen Thread der gleichen Multithreadanwendung zur CPU-Zuteilung auswählen.

2.2.2 Symmetric Multi-Threading (SMT)

Bei SMT 8 handelt es sich um ein von Prozessen losgelöstes Konzept. SMT wird auf Hardwaree- bene realisiert, in dem eine physische CPU in logische (oder virtuelle) Einheiten gesplittet wird und so vorgibt, das System besitze mehrere Prozessoren, statt nur eines einzigen.

Diese Trennung erreicht man, in dem man entweder dem Prozessor dedizierte Registersätze mit- gibt oder die vorhandenen dediziert zwischen den logischen Einheiten aufgeteilt, für jede virtu-

8 Intel bietet mit dem Northwood-Prozessor Kern einen Prozessorkern, der SMT unterstützt und nennt diese Techno- logie Hyperthreading

2.2. THREADS UND PROZESSE 11

Abbildung 2.7: CPU Architektur herkömmlicher und SMT-fähiger Prozessoren

elle CPU einen eigenen Interrupt-Controller schafft und die virtuellen Prozessoren sich weitere Ressourcen, wie Caches, Queues oder Key-Buffer teilen. Jedoch müssen nicht zwingend weite- re Arithmetic Logical Units (ALU) dem Prozessorkern hinzugefügt werden, da heutige, moderne CPUs bereits über mehr als eine ALU verfügen.

Die vorhandenen CPU-Ressourcen und deren Aufteilung in SMT-fähigen Prozessorkernen kann in drei Teile gegliedert werden[Sto02]:

I replizierten Ressourcen (replicated ressources):

Auch wenn es sich um zwei virtuelle Prozessoren handelt, muss es möglich sein, auf jeder dieser virtuellen Einheiten einen vollen Programmkontext darstellen und ablaufen zu lassen. Um dies zu bewerkstelligen, müssen bestimmte Prozessorressourcen für jede Einheit dedi- ziert zur Verfügung stehen. Hierzu zählen zum Beispiel der Instruction Pointer (IP), die Register Allocation Tables (RATs) welche für das Mapping der physischen Interger- und Fließkommaregister auf die logischen Einheiten zuständig ist.

I aufgeteilten Ressourcen (partitioned ressources):

Zu den aufteilten Ressourcen zählen sämtliche Prozessorkern-Internen Puffer und Listen, die für den Ablauf von Programmen notwendig sind. Diese Listen und Puffer werden sta- tisch zwischen den virtuellen Einheiten aufgeteilt, also bei bspw. zwei Einheiten werden die vorhandenen Reorder Buffer durch zwei geteilt und in gleicher Weise den Einheiten zur Verfügung gestellt.

I geteilten Ressourcen (shared ressources):

Im Gegensatz zu den partitioned ressources stehen die shared ressources den virtuellen Einheiten in gleicher Weise zur Verfügung und werden nicht zwischen ihnen aufgeteilt. Zu den shared ressources zählen bspw. die L1-, L2- und L3-Caches, die Mikroarchitektur- Register oder die Ausführungseinheiten (Integer-, Floating-Point- und Load-Store-Unit).

Das Herzstück der SMT-Technologie sind die shared Ressources oder genauer die Ausführungs-

2.2. THREADS UND PROZESSE 12

einheiten und ihre Instruktions-Scheduler und der SMT-Technik zugrundeliegende Prinzip der Out-Of-Order (OOO)-Instruktionsabarbeitung 9 .

OOO bedeutet, dass der Prozessor versucht eine Vorreihenfolge der anstehenden Instruktionen un- abhängig von der tatsächlichen linearen Abarbeitungsreihenfolge festzulegen. Nachdem der Pro- zessor eine Reihe der anstehenden Instruktionen dekodiert 10 und in den µ-Operations-Listen oder dem Level 1-Cache als sog. µ-Operationen (µops) zur Verfügung stehen, werden sie durch den Allo- cator den Reorder-Puffer zugewiesen und so den Instruktions-Schedulern zur Verfügung gestellt. Sowohl der Allocator, als auch die Instruktions-Scheduler gehören zur Out-Of-Order Execution Engine 11 .

Abbildung 2.8: Fetch/Decode-Einheit eines Intel x86-Prozessors [Int98]

OOO-fähige Prozessoren besitzen interne Scheduler (und für SMT sind diese Scheduler unver- zichtbar), welche die dekodierten Instruktionen (µops) den Ausführungseinheiten möglichst fair zuteilen. Unter SMT müssen die Instruktions-Scheduler und die Ausführungseinheiten nichts da- von wissen, von welcher logischen Einheit nun die auszuführende Instruktion stammt - eine In- struktion ist eine Instruktion, ob diese vom virtuellen Prozessor A oder B stammt, ist dabei uner- heblich.

Intels I32-Architektur besitzt fünf dieser internen Instruktions-Scheduler, die jeweils für verschie- dene Typen von µ-Instruktionen zuständig sind. Diese fünf Instruktions-Scheduler arbeiten parallel und wählen mit jedem Clock-Tick des Prozessors neue µops aus, die sie den Ausführungseinheiten parallel zur Verfügung stellen.

9 Ein detaillierter Überblick über die Funktionsweise der Out-Of-Order Execution ist u. a. in [M + 02] zu finden 10 Die komplexen I32-Instruktionen werden über das Microcode-ROM in µ-Operationen dekodiert und in den µ- Operation-Listen abgelegt.

11 Siehe Abbildung 2.8

2.2. THREADS UND PROZESSE 13

Abbildung 2.9: Dispatch/Execution-Einheit eines Intel x86-Prozessors [Int98]

Die Funktionsweise und die daraus resultierenden Vor- und Nachteile seien an einem Beispiel deutlich gemacht. Ein System mit einer physischen SMT-CPU führe zwei Prozesse auf den beiden logischen Einheiten aus. Mit einem neuen Clock-Tick teilen die fünf Instruktions-Scheduler von der Einheit A zwei µops und von der Einheit B eine µop der Ausführungseinheit zu. Im nächsten Clock-Cycle würden die drei Instruktionen parallel abgearbeitet.

Jedoch birgt genau dieses Vorgehen einen Nachteil. Würden bspw. zwei rechenintensiven Tasks mit vielen Fließkommaoperationen parallel auf den virtuellen CPUs laufen, so bestünde die Mög- lichkeit, dass einer von beiden beginne, die Ausführungseinheiten für seine Fließkommaoperatio- nen zu monopolisieren, während der andere Task nicht zum Zuge käme - seine Instruktionen wären zwar dekodiert, jedoch würden die Instruktionsscheduler äußerst selten Instruktionen dediziert von ihm auswählen.

Hätten nun beide Tasks vom Betriebssystem-Scheduler die gleichen Zeitscheiben zugewiesen be- kommen 12 , könnte der erste Task viele Operationen während eines Zeitschlitzes abarbeiten, wäh- rend der andere wenige bis gar keine Operationen während seines Zeitschlitzes zur Ausführung bringen könnte. Besäße der Scheduler des Betriebssystems keine Kenntnis davon, dass dem Sy- stem zwei logische CPUs zur Verfügung stehen, würde er beide Prozesse nach Ablauf ihres Quan- tums verdrängen und wäre somit unfair gegenüber dem zweiten Prozess.

Besäße jedoch der Scheduler des OS davon Kenntnis, so würde er den zweiten Prozess länger auf der logischen Einheit verweilen lassen und ihm so die Möglichkeit geben, die zuvor nicht ausführbaren Operationen nun abarbeiten zu können. Nur so ist es möglich, das SMT-System effizient zu nutzen und eine Steigerung des Task-Throughputs durch SMT zu erhalten.

12 vgl. Abschnitt 2.4.4

2.2. THREADS UND PROZESSE 14

2.2.3 Symmetrisches Multiprocessing (SMP)

Symmetrisches Multiprocessing kommt auf Systemen mit mehreren CPUs zum Tragen. Ob diese erkannten CPUs nun mehrere physische Prozessoren sind, oder aus logischen Einheiten 13 beste- hen, spielt für klassisches SMP keine Rolle. Unterstützt ein Kern keine speziellen SMT-Scheduling Strategien, so verwaltet der Prozessor beide Einheiten so, als seien sie physisch - mit all den Per- formanceeinbußen, die dies mit sich bringt.

Auch spielt es in der Betrachtung von reinem SMP keine Rolle, ob es sich beim zugrunde liegenden Multiprozessorsystem um ein lose oder eng gekoppeltes System handelt. Entscheidend allein ist die Tatsache, dass es sich bei dem System um kein Uniprozessorsystem handelt.

Betrachtet man die Arbeitsweise eines SMP-Systems genauer, so stößt man dabei auf ein gravie- rendes Problem: Da Tasks real parallel abgearbeitet werden, könnten die laufenden Tasks auch parallel über Systembefehle im Kernmodus Kerneldaten verändern. Im ungünstigsten Fall werden dadurch Kernstrukturen und -daten inkonsistent. Die Kerndatenkonsistenz ist dann nicht mehr ge- währleistet und kann dazu führen, dass das weitere Verhalten des Betriebssystemkerns nicht mehr vorhersagbar ist, gar weitere seiner kritischen Bereiche beeinflusst und letztlich der Kern instabil wird oder Daten auf sekundären Medien irreparable stört.

Um diesem Dilemma zu begegnen, existieren mehre Möglichkeiten [Bac86]:

I Es werden die Regionen bei Aufruf gesperrt, die Kerndaten verändern und die Sperre wird beim Verlassen des Codeabschnitts wieder entfernt (Semaphoren-Modell)

I Es wird eine CPU definiert, die Kerncode ausführen kann. Alle anderen CPUs können Tasks nur im Usermodus bedienen (sog. Master-Slave Prinzip)

I Man gestaltet die Algorithmen und Datenstrukturen so, dass kein Aufruf die anderen Daten verändern kann

Die Implementierung des letzten Punktes, die Algorithmen so zu gestalten, dass keine Korrum- pierung untereinander möglich ist, stellt sich als nur schwer realisierbar heraus. Daher griffen die Implementierungen SMP-fähiger Kernel in den letzten Jahrzehnten auf eine der ersten beiden Va- rianten zurück, die nachfolgend näher betrachtet werden sollen.

Semaphoren - Sperren kritischer Regionen

Als kritische Regionen werden die Bereiche des Kerns bezeichnet, die Kerninterne Daten und Strukturen derart verändern, dass die Integrität dieser Daten sichergestellt sein muss. Es gilt also,

13 vgl. Kapitel 2.2.2 auf Seite 10

2.2. THREADS UND PROZESSE 15

die Datenintegrität und -konsistenz zu sichern, wenn der Kern in die Ausführung eines kritischen Bereichs tritt.

Abbildung 2.10: Semaphoren bei bedingt kritischen Kernregionen

Um diese Datenkonsistenz sicherzustellen, bedient man sich sogenannter locks und unlocks. Beim Eintritt in eine kritische Region wird also für diesen Bereich eine Sperre gesetzt, die anzeigt, dass auf diesen Bereich und die korrespondierenden Daten gerade zugegriffen wird. Beim Verlassen der Region wird die Sperre wieder entfernt und somit kann von anderer Stelle auf diese Region zugegriffen werden.

Durch diesen Schutzmechanismus verhindert man die parallele Ausführung ein und derselben Region auf mehreren CPUs und serialisiert die Abarbeitung kritischer Regionen.

Master-Slave Prinzip

Beim Master-Slave-Prinzip werden die vorhandenen CPUs kategorisiert. Eine CPU erhält den Status Master und nur diese ist befähigt, Code im Kernelmodus auszuführen. Alle anderen CPUs

- Slaves - dürfen Tasks nur im Benutzermodus ausführen. Da jedoch auch Kernelcode die Slave- CPUs verwalten muss, muss man den Kern um Master- und Slave-Code erweitern. Als Mastercode ist hierbei der gesamte Kern gemeint, wohingegen Slave-Code als Mittler zwischen dem Task auf der Slave-CPU und dem Masterkern fungiert.

Damit der Betriebssystemkern weiß, auf welcher CPU er welchen Task ausführen soll, führt das System im Prozesskontrollblock ein weiteres Feld als Indikator mit sich. Der Einfachheit halber unterscheidet dieses Feld nur zwischen Master und Slave.

Führt ein Task auf einer Slave-CPU nun einen Systembefehl aus, der das Wechseln in den Kern-

2.2. THREADS UND PROZESSE 16

Abbildung 2.11: Symmetrisches Multiprocessing mit Master-Slave-Prinzip

modus bedingt, so setzt der Slave-Kern das CPU-Flag auf den Wert für Master und verdrängt den Prozess von der CPU (und teilt dieser einen anderen Prozess zu). Der Master-Kern findet den neu- en Prozess nun in seiner Prozessliste und - sofern er die nötige Priorität besitzt und kein weiterer Prozess mit einer höheren Priorität vorhanden ist - teilt diesem Prozess die Master-CPU zu. Der Task kann nun seinen Systembefehl absetzen und in den Kernmodus wechseln. Nach der Abarbei- tung des Systembefehls setzt der Master-Kern das CPU-Flag erneut um auf Slave und verdrängt den Prozess wieder von der CPU. Beim nächsten Scheduler-Durchlauf wird er wieder einer der Slave-Prozessoren zugeteilt.

2.2.4 Prozessoraffinität

Unter Prozessoraffinität versteht man das Verhalten, dass ein Task explizit oder implizit einem oder mehreren bestimmten Prozessor(en) zugeordnet wird und (möglichst) nur diesem zugeordnet bleibt.

Explizite Prozessoraffinität

Durch den Systemaufruf sched_setaffinity unter Linux 2.6 lässt sich aus einem Programm heraus über eine Bitmap festlegen, auf welchen Prozessoren der Task ausschließlich ausgeführt werden soll. Für jede vorhandene CPU existiert innerhalb der Bitmaske der Verwaltungsarrays 14 ein Bit, welche zu Beginn für alle CPUs gesetzt sind.

Selbst bei ungleicher Lastverteilung, hält sich der Scheduler an die explizit geforderte CPU- Zuteilung.

14 Siehe Abschnitt 4.5.3 auf Seite 71