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. 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.
[...]
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
2.4.2 Kooperatives Scheduling
Kooperatives Scheduling verfolgt den Ansatz, dass ein Prozess, wenn er zum Laufen kommt, die CPU so lange zugeteilt bekommt, wie er sie benötigt - er sie also freiwillig wieder abgibt. Dieser Ansatz wurde vor allem in den frühen Tagen insbesondere auf Batch-Systemen verfolgt. Auf Time-Sharing Systemen ist der Gedanke, dass ein Prozess die CPU gar Stunden für sich allein beanspruchen kann, nicht nur unangebracht, sondern steht gar dem Ansatz, dass mehrere Benutzer quasi gleichzeitig eine Recheneinheit nutzen können, diametral gegenüber.
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.
- Arbeit zitieren
- Diplom-Informatiker (FH) Alexander Zschach (Autor:in), 2004, Funktionsweise und Performancemessungen des LINUX O(1)-Schedulers, München, GRIN Verlag, https://www.grin.com/document/70285
