Erklärung

III

Vorwort

Die Beschäftigung mit Schedulingmechanismen und die Verbesserung der bestehenden Realisierungen trat zu Beginn der 90er Jahre stark in den Hintergrund und machte anderen Themen Platz - bspw. der Forschung und Entwicklung von und um JAVA ¹ und dessen Komponenten. Die anerkannte 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] dieser 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 gewachsen. 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 musste einen Weg beschreiten, der in der Hemisphäre der Softwarentwicklungswelt der freien Betriebssysteme nicht selten in die Katastrophe führte - stabile Realisierungen sollten innheralb kürzester Zeit komplett neuen Implementationen weichen, ohne dass sich die neuen Entwürfe ausgiebig im realen Betrieb bewähren konnten und einzelne Änderungen über einen langen Zeitraum sich einer “natürlichen Auslese” unterwerfen mussten. Der Gefahr, fehlerträchtige Betriebssystemkerne 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 werden und im vierten Kapitel der O(1)-Scheduler und dessen Konzepte und Realisierung betrachtet werden.

¹ JAVA ist ein eingetragenes Warenzeichen der SUN Inc.

Abschließend wird derO(1)-Scheduler einer eingängigen Prüfung in seinem Laufzeitverhalten unter Symmetrischem Multiprocessing unterzogen und die Testergebnisse detailliert erläutert. Abschließ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 vergangenen 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 Schnebel, 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

1.2  Batchsysteme  2

1.3  Resident Monitor  2

1.4  Multiprogrammed Batched Systeme  3

1.5  Time-Sharing Systeme  4

2  Grundlagen  5

2.1  Prozesse und Programme  5

2.2  Threads und Prozesse  6

2.2.1  Multithreadingmodelle  8

2.2.2  Symmetric Multi-Threading (SMT)  10

2.2.3  Symmetrisches Multiprocessing (SMP)  14

2.2.4  Prozessoraffinität  16

2.2.5  NUMA  17

2.3  Prozessverwaltung  18

2.3.1  Prozesstatus  18

2.3.2  Prozesskontrollblock  20

2.3.3  Prioritätenmodel  22

2.4  Scheduling  24

2.4.1  Anforderungen an Scheduling  24

2.4.2  Kooperatives Scheduling  25

2.4.3  Preemptives Scheduling  26

2.4.4  Schedulingalgorithmen  26

2.5  Dispatching  36

3  4BSD und Derivate  41

3.1  Einführung in den 4BSD-Scheduler  41

3.2  Prozessverwaltung  42

3.2.1  Prozesskontrollblock  42

3.2.2  Prozesslisten  44

Inhaltsverzeichnis II

3.3  Prioritäten  46

3.4  Scheduling  49

3.4.1  Zeitscheiben  49

3.4.2  Prozessauswahl und Kontextwechsel  49

3.5  SMP Unterstützung  51

4  Linux 2.6 - (O1)-Scheduler  53

4.1  Einführung  53

4.2  Grundfunktionen und -verhalten des (O1)-Schedulers  54

4.2.1  likely und unlikely  54

4.2.2  Prozess- und Kernelpreemption  54

4.2.3  Bestimmung der Quanten  55

4.3  Prozesse und Threads  56

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

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

4.3.3  Symmetric Multithreading  59

4.4  Prozessverwaltung  61

4.4.1  Prozesszustände  61

4.4.2  Runqueue  62

4.4.3  Prozesskontrollblock  64

4.4.4  De- und Enqueue-Funktionen der Prozessverwaltung  66

4.5  Prioritäten  68

4.5.1  Prioritätsbereich- und Aufteilung  68

4.5.2  Effektive Priorität  69

4.5.3  Prioritätsarrays  71

4.6  Scheduling  72

4.6.1  Periodisches Scheduling  73

4.6.2  Hauptscheduler  76

4.7  Symmetrisches Multiprocessing  80

4.7.1  Ausbalancieren der Runqueues unter SMP  80

4.7.2  Implizite Prozessoraffinität  82

4.8  Echtzeitprozesse  82

5  Messwerte und Testergebnisse  85

5.1  Einführung  85

5.2  Schedulerverhalten  86

5.2.1  Kern- und Benutzerbereich  86

5.2.2  Kontextwechsel  87

5.2.3  Systemcalls  90

5.2.4  Prozessoraffinität  92

5.3  Prozessverhalten auf Betriebssystemebene  95

Inhaltsverzeichnis III

5.3.1  Prozesserzeugung  95

5.3.2  Interprozesskommunikation  96

5.4  Applikationen im Vergleich  97

5.4.1  Apache2-Webserver mit dynamischen und statischem Inhalt  98

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  7

2.3  Exemplarische Erzeugung von Kernelthreads  8

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

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

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

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

2.8  Fetch/Decode-Einheit eines Intel x86-Prozessors Int98  12

2.9  Dispatch/Execution-Einheit eines Intel x86-Prozessors Int98  13

2.10  Semaphoren bei bedingt kritischen Kernregionen  15

2.11  Symmetrisches Multiprocessing mit Master-Slave-Prinzip  16

2.12  Darstellung eines lose gekoppelten Multiprozessorsystems (NUMA)  17

2.13  Diagramm einzelner Prozesszustände  19

2.14  Darstellung eines beispielhaften Prozesskontrollblocks S 00  21

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

2.16  Verdeutlichung kooperatives und preemptives Scheduling  26

2.17  FCFS-Scheduling Ablauf  27

2.18  Gantcharts eines Beispielhaften FCFS Verhaltens  28

2.19  Shortest Job First Scheduling-Algorithmus  29

2.20  Darstellung des exponentiellen Durchschnitts (Gewichtung α) SG94  30

2.21  Gantchart eines Beispielhaften Shortest Job First Szenarios  30

2.22  Gantchart eines beispielhaften Round-Robin Szenarios  32

2.23  Multilevel-Feedback Queue Algorithmus  34

2.24  Exemplarischer Kontextwechsel zweier Prozesses SG94  37

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  56

4.2  Vereinfachter Aufbau der CPU eigenen GDT-Datenstruktur  58

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  68

4.7  Bonusberechnung in Abhängigkeit von p- sleep avg Mau04  70

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

5.1  Dauer der Kern- und Benutzerbereichsausführung  86

5.2  Anzahl der Kontextwechsel je Messung  88

5.3  Durchschnittliche Anzahl Kontextwechsel  89

5.4  Kontextwechsel-Latenzen unter Linux 2.6  90

5.5  Latenzen einzelner Kontextwechsel bei n Prozessen  91

5.6  Durchschnittliche Dauer eines Systemaufrufs  92

5.7  Durchschnittliche implizte Prozessoraffinität  94

5.8  Kosten für Prozesserzeugung  96

5.9  Interprozesskommunikation zwischen n Prozessen  97

5.10  Apache2 Requests pro Sekunde  99

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  50

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

4.1  Definition der Codeoptimierungs-Makros likely und unlikely  54

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

4.3  Runqueue Linux 2.6  62

4.4  Linux task struct Auszug aus linux/sched.h  64

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

4.6  Ausketten eines Prozesskontrollblocks in ein Prioritätsarray  67

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

4.8  Macros zur Bonusberechnung in kernel/sched.c  69

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

4.10  Prioritätsarray aus kernel/sched.c  71

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

4.12  Parameterinitialisierung in der Funktion scheduler tick()  73

4.13  Schedulerverhalten bei einer Idle-CPU  73

4.14  Signalisierung der Verdrängung des aktuellen Tasks  74

4.15  Behandlung von Realtime-Prozessen durch sched tick()  74

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

4.17  Setzen des expired-Zeitstempels der Runqueue  75

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

4.19  Verhinderung der CPU-Monopolisierung durch einen Task  75

4.20  Verlassen eines bedingt kritischen Kernel-Bereichs  76

4.21  Variablendeklaration in schedule()  76

4.22  need resched-Label in schedule()  77

4.23  Ausbalancieren der Runqueues im Hauptscheduler  77

4.24  Austauschen des active- und expired-Arrays  77

4.25  Auswahl des nachfolgenden Prozesses  78

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  79

4.29  Aufruf des Low-Level Kontextwechsels  79

4.30  Verlassen des Hauptschedulers  80

4.31  Bestimmung der Cache-Lastigkeit eines Tasks  82

4.32  Behandlung von Echtzeitprozessen in effective prio()  83

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

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 darstellte.

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 Programmierer schrieb also das Programm, lud das notwendige Übersetzungsprogramm in den Arbeitsspeicher des Rechners, um den Quelltext in Maschinensprache zu kompilieren ² 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 Rechner 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 Programmierung der Maschine oder im Falle eines Fehlers stand die CPU still - sie verharrte im Leerlauf.

² 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 kostspielige 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 Programmierer 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ührung 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 Laden 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 Daten 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 ³ bzw. zufälligen ⁴ Speicherpunkten und entsprechend stark verringerten Zugriffszeiten begegnet werden.

Die Steuerung dieser Medien übernahm nun nicht mehr die CPU direkt, sondern spezielle Controller für diese Medien. Die Einführung der Hardwarecontroller für externe Speicher schuf die Möglichkeit, 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 Zwischenzeit 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 etablieren 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 Prozess durch einen anderen ersetzt werden.

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

⁴ Random Access Memory (RAM). Die Daten werden hierbei an unterschiedlichen, nicht vordefinierten Punkten gespeichert 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 Systemen 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 innerhalb 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 Benutzeranforderungen 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 besonderer 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 Speichermanagement (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 ⁵ MULTICS ⁶ . 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.

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

⁶ 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 Systemressourcen, wie Hauptspeicher, Rechenzeit, I/O Zugriffe, etc. um seine Aufgabe zu erfüllen. Prozesse sind aktive Einheiten wohingegen Programme passiv auf einem sekundären Speichermedium 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 wenigstens 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 nebenläufig erledigen zu lassen. Außerdem ermöglicht Multithreading das Verteilen mehrerer Aufgaben eines Prozesses auf mehrere CPUs in einem Multiprozessorsystem.

Der Vorteil gegenüber Multiprocessing liegt jedoch in einer erheblichen Kostenreduktion. Jedem neuzuerstellenden Prozess muss das Betriebssystem eigene Betriebsmittel zuweisen, was mit einem 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 verwaltet 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 Threads, die eigentlich ausgeführt werden könnten, so kommen diese bis zur Beseitigung des Bloc-kiergrundes, trotzdem nicht zum Zuge.

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 anderer Threads des Prozesses - sind sie im Status “Ready”, so können sie trotzdem zur Ausführung kommen.

2.2. THREADS UND PROZESSE 8

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 Einfluss 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 (Userthreads) 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 minimiert die Kosten für Kernelthreads.

Nachteilig jedoch ist, dass die Lauffähigkeit der Benutzerthreads die einem Kernelthread zugeordnet 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änkte 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 anderen 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 ⁷ ).

⁷ 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 aufnehmen 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 ⁸ handelt es sich um ein von Prozessen losgelöstes Konzept. SMT wird auf Hardwareebene 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 mitgibt oder die vorhandenen dediziert zwischen den logischen Einheiten aufgeteilt, für jede virtu-

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

2.2. THREADS UND PROZESSE 11

(b) SMT Dual Prozessor Architektur (a) SMP Dual Prozessor Architektur

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 weitere 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 dediziert 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 statisch 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 ⁹ .

OOO bedeutet, dass der Prozessor versucht eine Vorreihenfolge der anstehenden Instruktionen unabhängig von der tatsächlichen linearen Abarbeitungsreihenfolge festzulegen. Nachdem der Pro-zessor eine Reihe der anstehenden Instruktionen dekodiert ¹⁰ 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 ¹¹ .

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

Intels I32-Architektur besitzt fünf dieser internen Instruktions-Scheduler, die jeweils für verschiedene 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.

⁹ Ein detaillierter Überblick über die Funktionsweise der Out-Of-Order Execution ist u. a. in [M ⁺ 02] zu finden

¹⁰ Die komplexen I32-Instruktionen werden über das Microcode-ROM in µ-Operationen dekodiert und in den µ- Operation-Listenabgelegt.

¹¹ 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öglichkeit, dass einer von beiden beginne, die Ausführungseinheiten für seine Fließkommaoperationen 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 bekommen ¹² , könnte der erste Task viele Operationen während eines Zeitschlitzes abarbeiten, während 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 System zwei logische CPUs zur Verfügung stehen, würde er beide Prozesse nach Ablauf ihres Quantums 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.

¹² 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 ¹³ bestehen, 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 gravierendes 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 gewä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 Korrumpierung 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 Varianten 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,

¹³ 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.

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- CPUsverwalten 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 neuen 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 Abarbeitung 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 ¹⁴ 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.

¹⁴ Siehe Abschnitt 4.5.3 auf Seite 71