Funktionsweise und Performancemessungen des LINUX O(1)-Schedulers

Inhaltsverzeichnis

1 Einführung

1.1 Programmierer und Operator

1.2 Batchsysteme

1.3 Resident Monitor

1.4 Multiprogrammed Batched Systeme

1.5 Time-Sharing Systeme

2 Grundlagen

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

3 4BSD und Derivate

3.1 Einführung in den 4BSD-Scheduler

3.2 Prozessverwaltung

3.2.1 Prozesskontrollblock

3.2.2 Prozesslisten

3.3 Prioritäten

3.4 Scheduling

3.4.1 Zeitscheiben

3.4.2 Prozessauswahl und Kontextwechsel

3.5 SMP Unterstützung

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

5 Messwerte und Testergebnisse

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

5.3.1 Prozesserzeugung

5.3.2 Interprozesskommunikation

5.4 Applikationen im Vergleich

5.4.1 Apache2-Webserver mit dynamischen und statischem Inhalt

5.4.2 Datenbank-Performance

6 Schlusswort

6.1 Fazit

6.2 Ausblick

A Benchmarkquelltexte, -Tools und -System

A.1 Systembeschreibung

A.2 Verwendete externe Tools und Aufrufe

A.3 Vorgenommene Änderungen an den Vanilla-Kerneln

A.3.1 Implementation eines Systemaufrufs unter 2.6.7

A.3.2 Implementation eines Systemaufrufs unter 2.4.27

A.4 Quelltexte

A.4.1 Globale Makros

A.4.2 Benchmark Prozessverdrängungs-Latenzen

A.4.3 Benchmark Prozesserzeugung

A.4.4 Benchmark Prozessor-Affinität

Zielsetzung & Themen

Die Diplomarbeit untersucht die Funktionsweise und das Laufzeitverhalten des Linux O(1)-Schedulers, wobei ein besonderer Fokus auf dessen Skalierbarkeit und Effizienz im Vergleich zu Vorgängerversionen und anderen Unix-Derivaten liegt. Die Forschungsfrage zielt darauf ab, zu belegen, inwiefern der O(1)-Scheduler die Systemlast minimiert und die Performance bei einer großen Anzahl von Prozessen sowie unter Symmetrischem Multiprocessing (SMP) steigert.

• Grundlagen von Prozessen, Threads und Scheduling-Mechanismen
• Analyse des 4BSD-Schedulers als historischer Referenzpunkt
• Detaillierte Untersuchung der Konzepte und Architektur des Linux O(1)-Schedulers
• Vergleichende Performancemessungen zwischen Linux 2.4 und Linux 2.6
• Einfluss von Prozessoraffinität und SMT auf das Scheduler-Verhalten

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Einführung: Überblick über die historische Entwicklung von Batch-Systemen bis hin zu frühen Time-Sharing Systemen.

2 Grundlagen: Erläuterung elementarer Konzepte wie Prozesse, Threads, Multithreadingmodelle sowie die Prozessverwaltung und die Funktionsweise von Scheduling-Algorithmen.

3 4BSD und Derivate: Detaillierte Betrachtung des klassischen 4BSD-Schedulers und dessen Prozessverwaltung und SMP-Unterstützung als Grundlage für moderne Systeme.

4 Linux 2.6 - O(1)-Scheduler: Tiefgehende Analyse der Architektur, Prioritätenberechnung und Scheduling-Strategien des Linux O(1)-Schedulers inklusive Kernelpreemption und SMT-Unterstützung.

5 Messwerte und Testergebnisse: Empirische Evaluation und Vergleich des Laufzeitverhaltens zwischen dem Linux 2.4- und dem Linux 2.6-Kernel anhand diverser Benchmarks.

6 Schlusswort: Fazit zur Notwendigkeit des Wechsels zum O(1)-Scheduler und ein Ausblick auf zukünftige Anforderungen an Betriebssystem-Scheduler.

Schlüsselwörter

Linux, O(1)-Scheduler, Scheduling, Kernel, Multiprocessing, SMP, Prozessverwaltung, Prozessoraffinität, Threading, NPTL, Performance-Messung, Latenz, SMT, Kontextwechsel, Durchsatz

Häufig gestellte Fragen

Worum geht es in dieser Arbeit grundsätzlich?

Die Arbeit befasst sich mit der Architektur und Leistungsfähigkeit des Linux O(1)-Schedulers, der in Linux 2.6 eingeführt wurde, um die Skalierbarkeit gegenüber älteren Implementierungen zu verbessern.

Was sind die zentralen Themenfelder?

Die zentralen Themen sind Scheduling-Theorie, Prozess- und Threadmanagement in Unix-ähnlichen Systemen, die Funktionsweise von SMP-Unterstützung und detaillierte Performance-Benchmarks.

Was ist das primäre Ziel oder die Forschungsfrage?

Das primäre Ziel ist es, nachzuweisen, dass der O(1)-Scheduler durch seine Algorithmen einen geringeren Systemoverhead verursacht und eine wesentlich bessere Skalierbarkeit bei steigender Prozessanzahl bietet als sein Vorgänger.

Welche wissenschaftliche Methode wird verwendet?

Es handelt sich um eine systemnahe Informatik-Arbeit, die Theorie und Praxis kombiniert: Neben der theoretischen Analyse von Quellcode und Betriebssystemkonzepten werden Benchmarks durchgeführt, um Performance-Daten zu vergleichen.

Was wird im Hauptteil behandelt?

Im Hauptteil werden der 4BSD-Scheduler, die Architektur des O(1)-Schedulers (Runqueues, Prioritätsarrays, Kernelpreemption) sowie die praktischen Auswirkungen der Architekturänderungen durch Messungen detailliert beschrieben.

Welche Schlüsselwörter charakterisieren die Arbeit?

Die wichtigsten Begriffe sind Scheduling, O(1)-Algorithmus, Performance, Linux-Kernel, SMT, SMP und Prozessoraffinität.

Was ist der wesentliche Unterschied zwischen kooperativem und preemptivem Scheduling?

Beim kooperativen Scheduling gibt ein Prozess die CPU freiwillig ab, während beim preemptiven Scheduling das Betriebssystem den Prozess nach Ablauf einer Zeitscheibe zwangsweise unterbrechen und verdrängen kann.

Wie beeinflusst Prozessoraffinität das Systemverhalten?

Prozessoraffinität versucht, Prozesse möglichst auf derselben CPU auszuführen, um von bestehenden Cache-Inhalten zu profitieren und so Cache-Misses zu reduzieren, was die Performance signifikant steigert.