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
B Abkürzungsverzeichnis
C Literaturverzeichnis
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)
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 JAVA1 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 gewachsen. Linux und die BSD-Derivate waren nur eingeschränkt auf den Siegeszug von Multiprozessormaschinen 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.
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 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.
Mannheim im August 2004
Alexander Zschach
Abbildungsverzeichnis
2.1 Unterschied zwischen Prozessen und Threads
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
3.1 Einfluß des Decay-Filters auf die Schedulerpriorität eines Prozesses .
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
4.4 Ausgeglichene und unausgeglichene SMT-Einheiten eines Dual-Prozessorsystems
4.5 Verkettete Top-Down Prozessverwaltung unter Linux
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
5.12 Update/Select-Requests pro Sekunde
Tabellenverzeichnis
2.2 Im TSS zu sichernde Register des Motorola 680x0
3.1 Kernelprioritäten für Prozesse unter 4BSD
Listings
2.1 TSS Beispielstruktur unter Motorola 680x0
2.2 Beispielhafter Kontextwechsel in einer Motorola 680x0 Umgebung und Assembler
3.1 Darstellung des 4BSD Prozesskontrollblocks
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()
4.27 Überprüfung auf Neuberechnung der Priorität
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
A.2 Erweiterung der 2.6.7 arch/i386/kernel/entry.S
A.3 Erweiterung der 2.6.7 include/asm/unistd.h
A.4 Erweiterung der 2.4.27 kernel/sched.c
A.5 Erweiterung der 2.4.27 arch/i386/kernel/entry.S
A.6 Globale Makros von mehrere Quellen verwendet
A.7 Quelltext des Testprogramms loop_yield
A.8 Kompilierungsaufruf für das Benchmarkprogramm loop_yield
A.9 Aufruf des Benchmarkprogramms loop_yield
A.10 Aufruf Systemprogramms vmstat
A.11 Headerdatei für fork_pipe.c
A.12 Quelltextdatei fork_pipe.c
A.13 Kompilierungsaufruf für das Benchmarkprogramm fork_pipe .
A.14 Aufruf des Benchmarkprogramms fork_pipe
A.15 Headerdatei sched_aff.h
A.16 Quelltextdatei sched_aff.c
A.17 Kompilierungsaufruf für das Benchmarkprogramm sched_aff .
A.18 Aufruf des Benchmarkprogramms sched_aff
Kapitel Einführung
“Those who cannot remember the past are condemned to repeat it.”
- George Santayana (The Life of Reason)
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 kompilieren2 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.
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 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ü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
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 sequentiellen3 bzw. zufälligen4 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 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.
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
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 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 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äufer5 MULTICS6. 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.
Kapitel 2 Grundlagen
“To explain what Linux is, you got to explain what an operating system is ...”
- Linus Benedict Torvalds (in “RevolutionOS”, 2003)
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
- ein Prozess ein oder mehrere Unterprozesse (Kindprozesse) erzeugt (fork) oder
- 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
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 nebenläufig erledigen zu lassen. Außerdem ermöglicht Multithreading das Verteilen mehrerer Aufgaben eines Prozesses auf mehrere CPUs in einem Multiprozessorsystem.
Abbildung in dieser Leseprobe nicht enthalten
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 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.
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 Blockiergrundes, trotzdem nicht zum Zuge.
Abbildung in dieser Leseprobe nicht enthalten
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.
Abbildung in dieser Leseprobe nicht enthalten
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 Multiprozessorfä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 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.
Abbildung in dieser Leseprobe nicht enthalten
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 in dieser Leseprobe nicht enthalten
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. LinuxThreads7 ).
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 in dieser Leseprobe nicht enthalten
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 SMT8 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 mit- gibt oder die vorhandenen dediziert zwischen den logischen Einheiten aufgeteilt, für jede virtu-
Abbildung in dieser Leseprobe nicht enthalten
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]:
- 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.
- 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.
- 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- einheiten und ihre Instruktions-Scheduler und der SMT-Technik zugrundeliegende Prinzip der Out-Of-Order (OOO)-Instruktionsabarbeitung9.
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 dekodiert10 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 Engine11.
Abbildung in dieser Leseprobe nicht enthalten
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 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.
Abbildung in dieser Leseprobe nicht enthalten
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 bekommen12, 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.
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 Einheiten13 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 Performanceeinbuß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]:
- Es werden die Regionen bei Aufruf gesperrt, die Kerndaten verändern und die Sperre wird beim Verlassen des Codeabschnitts wieder entfernt (Semaphoren-Modell)
- Es wird eine CPU definiert, die Kerncode ausführen kann. Alle anderen CPUs können Tasks nur im Usermodus bedienen (sog. Master-Slave Prinzip)
- 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,
die Datenintegrität und -konsistenz zu sichern, wenn der Kern in die Ausführung eines kritischen Bereichs tritt.
Abbildung in dieser Leseprobe nicht enthalten
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 SlaveCPUs 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-
Abbildung in dieser Leseprobe nicht enthalten
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 Verwaltungsarrays14 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.
Implizite Prozessoraffinität
Die implizite Affinität umschreibt das Verhalten des Schedulers, der versucht ist, einen Task mög- lichst immer der gleichen CPU zuzuordnen. Dieses Verhalten ist unter der Betrachtung der immer größeren CPU-Caches sinnvoll. Ein Task, der zuvor auf der ersten von bspw. vier CPUs gelaufen ist, dann verdrängt wurde und nun wieder am Zuge ist, hält u. U. noch Daten im CPU-Cache, auf die er mit niedrigeren Latenzen zugreifen kann. Würde der Task einer anderen CPU zuge- teilt, müssten die Daten auf jedenfall erst aus dem Hauptspeicher geholt werden was in größeren Verzögerungen resultiert.
Es ist nicht sichergestellt, dass die Daten des Tasks noch im CPU-Cache verweilen, jedoch besteht die Möglichkeit, die es gilt zu nutzen. Aus der impliziten Prozessoraffinität resultiert eine höhere Performance für Tasks.
2.2.5 NUMA
NUMA - None Uniform Memory Architecture - steht als Synonym für lose gekoppelte Multipro- zessorsysteme (siehe Abbildung 2.12) und somit ist diese Architektur die logische Weiterentwick- lung von Symmetrischem Multiprocessing. Zusammengefasst ergibt eine CPU und ihr zugehöriger Speicher einen Knoten. Auch wenn die Knoten in sich autonom arbeiten, so stehen sie trotzdem in Kommunikation miteinander. Daraus resultiert die Möglichkeit, dass ein Prozess zwischen zwei Knoten verschoben wird und noch Daten aus dem Speicher seines vorherigen Knotens benötigt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.12: Darstellung eines lose gekoppelten Multiprozessorsystems (NUMA)
Da die Wege zwischen den Speichern unterschiedlich und ggf. sogar über mehrere unabhängige Busse realisiert sind, führt dies zu unterschieden in den Speicherzugriffszeiten und bedarf mehrerer Schutzmechanismen, die Speicher konsistent zu halten.
Scheduler, die Unterstützung für NUMA bereitstellen, versuchen möglichst die Wege zwischen Speicher und Prozessoren zu minimieren und somit die Zugriffszeiten zu reduzieren, in dem sie Prozesse der CPU zuordnen, von der die Prozesszugriffe auf den Speicher am geringsten sind und nur der fairnesshalber auf andere Knoten ausweichen.
2.3 Prozessverwaltung
Neben der Entscheidung ob und wann ein Prozess eine CPU zugeteilt bekommt, muss der Scheduler die neu gestarteten, lauffähigen und blockierten Prozesse verwalten. Prozessverwaltung selbst ist lediglich mit einem Bedarf an Hauptspeicher verbunden, in welchem die Seitentabellen und Prozesskontrollblöcke resistent gehalten werden. Jedoch kann die Suche des Schedulers nach dem nächsten auszuwählenden Prozess auf Systemen mit einer enormen Menge an laufenden und lauffähigen Prozessen eine hohe Systemlast erzeugen. Es gilt also, je überdachter ein System seine Prozesse verwaltet, desto weniger Overhead wird für das Scheduling selbst beansprucht, desto mehr Prozessorzeit steht den Prozessen zur Verfügung.
2.3.1 Prozesstatus
Während der “Lebenszeit” eines Prozesses wechselt dieser zwischen verschiedenen Status (siehe Abbildung 2.13 auf der nächsten Seite), egal ob es sich beim zugrundeliegendem Prozessmanagement um preemptive oder kooperative Mechanismen15 handelt. Der Zustand eines Prozesses ergibt sich aus seiner momentanen Aktivität:
- Neu
Der Prozess wurde neu erzeugt und noch nicht in die Bereit-Liste eingefügt
- Bereit
Der Prozess ist bereit, die CPU zu übernehmen und wartet darauf, vom Scheduler ausgewählt zu werden und durch den Dispatcher die Kontrolle über die CPU zu erlangen
- Aktiv
Der Prozess hat die Kontrolle über die CPU
- Blockiert
Der Prozess wartet auf die Aktivität einer externen Ressource (bspw. sekundärer Speicher) oder auf das Eintreten eines Ereignisses
- Beendet
Der Prozess hat seine Aufgabe erledigt und wartet darauf, vom Betriebssystem entfernt zu werden
Für jeden dieser Status verwaltet das Betriebssystem (je nach Implementierung) eine oder mehrere Listen, deren Komplexität von einfach verketteten Listen bis hin zu komplexen Bäumen reicht.
Kommt nun ein Programm zur Ausführung, so benötigt der daraus resultierende Prozess zunächst die notwendigen Betriebsmittel. Zentrale Ressource ist hierbei der Hauptspeicher, in den der Pro- zess geladen wird und von wo aus er die CPU übernehmen kann, sobald er an der Reihe ist.
Konnte der Prozess erfolgreich in den Hauptspeicher geladen und ihm alle notwendigen Ressourcen zugeteilt werden, so ist er bereit, die Kontrolle über den Prozessor zu übernehmen - er befindet sich im Status “Ready” und wird in die Ready-Queue (wie auch immer diese organisiert ist) eingehängt. Die in der “Ready-Queue” verwalteten Prozesse sind also bereit, jederzeit die Kontrolle über die CPU zu erlangen, sobald sie vom Scheduler dafür ausgewählt und durch den Dispatcher durch einen Kontextwechsel16 dem Prozessor zugeteilt werden.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.13: Diagramm einzelner Prozesszustände
Je nachdem, ob es sich beim zugrundeliegenden Modell um einen preemptiven oder kooperativen Mechanismus handelt, kann ein Prozess also
- seine Aufgabe während der zugeteilten Rechenphase abschließen und terminieren. Er wech- selt dann vom Status aktiv in den Status beendet.
- blockieren, weil er auf ein Ereignis (bspw. eine Benutzereingabe) oder eine externe Res- source (bspw. Festplattenzugriff) wartet. Der Prozess wechselt aus dem Status aktiv in den Status blockiert
- nach Beseitigung des Blockiergrundes (der Benutzer hat mit einer Eingabe reagiert oder die benötigten Daten wurden vom Festplattencontroller an das Betriebssystem übergeben) möchte der Prozess die CPU wieder zugeteilt bekommen um seine Aufgabe zu erledigen. Hierzu wechselt er aus dem Status blockiert erneut in den Status bereit und wartet darauf, den Prozessor zugeteilt zu bekommen.
- durch das Betriebssystem von der CPU verdrängt werden, weil das System einen Interrupt erhalten hat, den es abarbeiten muss. In diesem Fall wechselt der Prozess aus dem aktiven Status (Running) zurück nach Ready.
- bei der Verwendung von preemptiven Schedulingstrategien während der Abarbeitung von der CPU verdrängt und durch einen anderen Prozess ersetzt werden. Der Prozess wechselt dann aus dem Status aktiv zurück in den Status bereit und wartet in der Ready-Queue darauf, erneut die Kontrolle über die CPU zu erlangen.
Jeder Statuswechsel zieht also eine Reorganisation der Verwaltungslisten nach sich. Wechselt bspw. ein Prozess aus dem Status Running in den Status Waiting, so muss er aus der korrespondie- renden Liste entfernt und in die Liste des aktuellen Status eingehängt werden. All diese Operatio- nen sind neben dem eigentlichen Kontextwechsel - also dem Entfernen eines Prozesses und neu Zuweisen eines weiteren Prozesses zur CPU - äußerst kostenintensiv und es bedarf daher einiger Überlegungen, wie man die Status- und Kontextwechsel bzw. die Reorganisation der Listen so gestalten kann, dass die Prozessverwaltung die Prozessabarbeitung nicht zu sehr beeinflusst.
2.3.2 Prozesskontrollblock
Jeder Prozess wird im System durch den Prozesskontrollblock (Processcontrolblock - PCB - oder auch Taskcontrolblock genannt) repräsentiert. Über diesen verwaltet das System alle notwendigen Informationen einen Prozess betreffend. Dazu gehören bspw. ein Abbild des Prozessstacks, die Adressen der zugewiesenen Speichersegmente, geöffnete Dateideskriptoren, etc.
Neben diesen Informationen enthält der PCB Felder, in welchen die Abbilder der Registersätze abgespeichert werden, wenn der Prozess von der CPU verdrängt wird und der Prozessor einem anderen Prozess zugewiesen wird. Nur so ist es möglich, einen Prozess während seiner Arbeit zu unterbrechen und ihn später an exakt dieser Stelle fortfahren zu lassen.
Das tatsächliche Aussehen des PCB ist abhängig vom System bzw. der Implementation. So besitzt ein Motorola 680x0 Prozessor andere Registerstätze, als eine Intel x86 CPU. Weiterhin verwaltet bspw. SUN Solaris den physischen und virtuellen Speicher anders, als dies eines der BSD-Derivate macht. All diese Faktoren wirken sich auf den tatsächlichen Aufbau des PCB aus, weshalb an dieser Stelle nur ein beispielhafter PCB erläutert wird.
- Prozessstatus
Das Statusfeld enthält die Information über den aktuellen Zustand des Prozesses, also ob er neu, bereit, aktiv, blockiert oder beendet ist.
- Prozesszeiten
Die Prozesszeitenfelder verwalten taskspezifische Informationen über die Zeit, die der Prozess bisher real die CPU belegt hatte, Zeitlimits- und ggf. die Zeitscheiben, etc.
- Programmzähler
Ähnlich dem Programmzähler (Programcounter - PC) des Prozessors gibt dieses Feld die Adresse der nächsten auszuführenden Instruktion des Prozesses an.
- CPU Register
Die Felder für die CPU Register enthalten die Inhalte (Abbilder) der CPU-Registersätze.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.14: Darstellung eines beispielhaften Prozesskontrollblocks [S+00]
Diese variieren je nach Prozessorarchitektur, enthalten aber in allen Fällen den Stand des Stackpointers, den jede CPU (ggf. in unterschiedlicher Breite) besitzt. Die Sicherung der Register und des Programmzählers ist notwendig um einen Prozess zu unterbrechen und um ihn später an der gleichen Stelle fortfahren zu lassen.
- Schedulerinformationen
Unter die Schedulerinformationen fällt alles, was der Scheduler benötigt, um den Prozess verwalten und auswählen zu können. Dazu gehören u. a. die aktuelle Priorität des Prozesses, Zeiger auf die Schedulingqueues, welchen der Prozess zugeordnet ist, ggf. Timerinforma- tionen, etc.
- Speichermanagement
Alle Informationen das Speichermanagement betreffend, werden auch im PCB verwaltet. Dazu gehören u. a. die Adressen der Speicherseiten, die dem Prozess durch das Betriebssystem zugewiesen wurden, etc. Das tatsächliche Aussehen dieses Bereichs des PCB hängt vom Aufbau des Speichermanagement des Betriebssystems ab.
- I/O Statusinformationen
In diesem Bereich sichert der PCB alle für das Betriebssystem notwendigen Informationen über I/O-Geräte, die dem Task zugeordnet sind, geöffnete Dateideskriptoren, etc.
2.3.3 Prioritätenmodel
Rechen- und I/O-Intensive Jobs
Prozesse haben im Allgemeinen unterschiedliche Aufgaben, was signifikant für ihr Laufzeitverhalten ist. Grundsätzlich können Prozesse in zwei Kategorien unterschieden werden:
- CPU gebunden
- I/O gebunden.
CPU gebundene Prozesse (CPU-bound17 processes) sind eher rechenintensive Prozesse und ver- bringen die meiste Zeit im laufenden (rechnenden) Zustand. Ihr Interesse ist es, die CPU so oft und so lange wie nur möglich zu erhalten. Auf der anderen Seite kann ein CPU gebundener Prozess eher von der CPU verdrängt werden, sofern seine Aufgabe nicht Realzeitverhalten18 erfordert.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.15: Unterschiede zwischen CPU- und I/O gebundenen Prozessen
Im Gegensatz zu CPU gebundenen Prozessen stehen die I/O gebundenen Prozesse (I/O-bound). Diese werden auch als interaktive Prozesse bezeichnet, weil ihr Laufzeitverhalten stark an eine Interaktion mit Benutzern oder anderen Betriebsmitteln gekoppelt ist. I/O gebundene Prozesse weißen eine starke Affinität zu kurzen aber intensiven Prozessornutzungen (CPU Burst) auf, weshalb I/O gebundene Tasks ein Interesse daran haben, mit möglichst niedrigen Latenzen während des CPU Bursts die Kontrolle über die CPU zu erlangen.
Der Scheduler muss nun versuchen, diesen gegensätzlichen Interessen beider Kategorien mög- lichst fair Rechnung zu tragen. Würde das Betriebssystem beide Kategorien gleich behandeln, hieße dass, rechenintensive Prozesse erhielten die CPU gleich lang wie die weniger rechenintensi- ven, interaktiven Prozesse, die aber nur kurze Rechenzyklen aufweisen. Die interaktiven Prozesse würde während ihrer Zeitscheiben die CPU hauptsächlich im Leerlauf verharren lassen, weil sie noch auf ein Ereignis warten. Eine solche Gleichbehandlung beider Prozesskategorien käme einer Verschwendung von Rechenzeit gleich.
Die Lösung liegt darin, dass rechenintensive Prozesse die CPU belegen dürfen, wenn kein inter- aktiver Prozess die CPU benötigt. Das Betriebssystem favorisiert jedoch interaktive Prozesse mit ihren kurzen CPU-Bursts gegenüber den CPU gebundenen Prozessen. In anderen Worten heißt das, je häufiger ein Prozess die CPU verlangt, desto niedriger stuft der Scheduler seine Priorität ein.
Dynamische und statische Prioritäten
Um auszuschließen, dass hochpriorisierte Prozesse die CPU ganz allein für sich in Anspruch nehmen können (und so niedriger priorisierte Tasks nie zum Zuge kommen), unterteilt man Prioritäten in zwei Kategorien
- statische Prioritäten
Diese Priorität wird dem Prozess durch den Benutzer oder das System zugewiesen und verändert sich nur explizit während der Laufzeit des Tasks (bspw. weißt ein Benutzer dem laufenden Task eine andere Priorität zu). Im Allgemeinen kann aber davon ausgegangen werden, dass die meisten Prozesse mit der anfänglichen statischen Priorität arbeiten und bis zum Ende ihrer Laufzeit diese beibehalten.
- dynamische Prioritäten
Prioritätenbasiertes Scheduling führt zu dem zuvor beschriebenen Effekt, dass hochpriori- sierte Prozesse im schlechtesten Fall verhindern, dass Tasks mit niedrigerer Priorität je zum Laufen kommen oder zumindest sehr lange auf die Zuteilung zur CPU warten müssen. Um diesem Umstand zu begegnen bedient man sich Prioritäten, die während der Laufzeit eines Prozesses ständig ihren Wert ändern. Diese “Dringlichkeitsstufe” eines Tasks lässt sich in zwei Richtungen anpassen. Zum einen kann man wartenden Tasks, je nach verstrichener Zeit ohne Prozessorkontrolle, eine höhere Priorität zuweisen, bis diese über den Prioritäten der laufenden Tasks liegt und der Prozess so zum Zuge kommt. Im zweiten Fall wird die Priorität in Abhängigkeit von CPU Nutzung verringert, bis diese unter den Prioritäten der wartenden Tasks liegt.
Real bedient man sicher beider Varianten - die “Dringlichkeitsstufe” wartender Tasks wird erhöht, die der rechnenden verringert.
Die Priorität, die nun ein Prozess besitzt und darüber entscheidet, vor und nach welchen Tasks er zum Laufen kommt, setzt sich zusammen aus beidem - dynamischer und statischer Priorität. Welche Prioritätsstufen und welche Unterscheidungen es hierbei gibt, ist wiederrum abhängig von der jeweiligen Implementation19.
2.4 Scheduling
Der Scheduler eines Betriebssystems koordiniert den Ablauf von Prozessen - er wählt die Tasks aus, die die CPU benutzen dürfen und entscheidet wann, welcher Task zum Zuge kommt. Auf Multiprozessorsystemen kommt dem noch die Entscheidung hinzu, auf welcher CPU ein ausge- wählter Task laufen soll. Die Arten, wie er dies macht wird in Kapitel 2.4.2 und Kapitel 2.4.3 erläutert.
2.4.1 Anforderungen an Scheduling
Da die Anforderungen an ein System äußerst unterschiedlich sein können, kann es keinen “besten Algorithmus” geben. Es gibt eine Bandbreite an Algorithmen und Möglichkeiten, die Taskabarbeitung zu strukturieren und jede dieser Möglichkeiten hat Vor- und Nachteile, bzw. favorisiert bestimmte, unterschiedliche Tasktypen.
Die Ziele, auf die Schedulingalgorithmen optimiert sind und an welchem Verhalten ihre Effizienz gemessen wird, sind [Ben90]
- CPU Auslastung (CPU utilization)
Vorrangiges Ziel des Scheduling ist es, vorhandene Rechenkapazititäten so gut wie möglich auszuloten, also den oder die Prozessoren so lang wie möglich in Beschäftigung zu halten. Die Dringlichkeit dieses Ziels hat sich in den letzten Jahren ein wenig entschärft - die Preise für Prozessoren liegen heute nur noch bei einem Bruchteil dessen, was vor wenigen Jahren noch gängig war. Die CPU kann somit heute nicht mehr als das “teuerste” Betriebsmittel eines Rechners angesehen werden (der Fokus hat sich zugunsten von Netzwerktechnologi- en und Festspeichermedien ein wenig verschoben) - jedoch ist die CPU nach wie vor das Zentrale Betriebsmittel, ohne das kein computerisiertes Werkzeug Arbeit verrichten kann.
- Turnaroundzeiten
Aus Sicht eines Prozesses ist es ein wichtiges Kriterium, wie lange er für die Erledigung seiner Aufgabe benötigt. Die Zeit, die der Prozess vom Start bis zur Beendigung braucht, wird als Turnaroundzeit bezeichnet. Die Turnaroundzeit ist also die tatsächlich verstrichene Zeit, also die Summe aus Spawntime, Warte-, Blockier- und Rechenzeit.
- Prozessdurchsatz (throughput)
Ziel bei der Optimierung des Prozessdurchsatzes ist es, innerhalb eines Zeitraumes t eine maximale Menge n Prozesse durcharbeiten zu lassen. Der wünschenswerte Prozessdurch- satz bestimmt sich nach der durchschnittlichen Rechenzeit der Prozesse. Auf Systemen mit hauptsächlich länger rechnenden (laufenden) Prozessen20 beenden weniger Prozesse ihre Arbeit innerhalb des Zeitraums t, als auf Systemen mit kürzer rechnenden (laufenden) Pro- zessen, woraus folgt, dass ein Durchsatzwert kein vergleichbares Kriterium ist und indivi- duell bestimmt werden muss, ob ein System einen guten throughput besitzt.
- Wartezeiten von Tasks
Als Wartezeit eines Prozesses ist der Zeitraum t zu betrachten, den ein Prozess zwischen CPU Zuweisungen in der “Readyqueue” verbringt. Blockierzeiten eines Prozesses wirken sich auf diese Wartezeit nicht aus, da diese vom Scheduler nicht beeinflusst werden können.
- Antwortzeiten von Tasks
Auf interaktiven Systemen gibt es neben der Turnaroundzeit eines Prozesses noch das Kri- terium der Antwortzeit dieses Prozesses auf eine Benutzereingabe. Als Antwortzeit wird hierbei die Zeit bezeichnet, die benötigt wird von der Eingabe einer Anforderung an den Prozess und der Antwort des Prozesses (CPU Burst). Wichtig ist jedoch, dass als Antwort nicht die Ausgabe auf dem Monitor gemeint ist, da die Bildschirmausgabe wiederrum von der Leistungsfähigkeit des Ausgabegeräts abhängt (bspw. ist die Antwort auf einer Unix- konsole weniger aufwendig, als unter einer grafischen Benutzeroberfläche).
Wünschenswert ist es, für ein bestimmtes Problem oder Systemverhalten einen Algorithmus zu finden, der
- CPU Auslastung und throughput maximiert und
- Turnaround-, Warte- und Antwortzeit minimiert.
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.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.16: Verdeutlichung kooperatives und preemptives Scheduling
2.4.3 Preemptives Scheduling
Time-Sharing Systeme müssen dem Anspruch genügen, dass mehrere Benutzer das System quasi parallel beanspruchen können und es dem einzelnen Benutzer so vorkommt, als würde die CPU einzig ihm zur Verfügung stehen. Die CPU wird den Prozessen so zugeteilt, dass kein Benutzer zu kurz kommt. Dies ist nur dann möglich, wenn das Betriebssystem - als übergeordnete Instanz - die Möglichkeit besitzt, einen laufenden Prozess von der CPU zu verdrängen und diese einem anderen Job zuzuweisen.
2.4.4 Schedulingalgorithmen
First-Come First-Served
Die wohl trivialste Methode einer strukturierten Prozessabarbeitung ist die First-Come FirstServed-Strategie21 (FCFS). Trivial ist die Methode daher, weil jeder neu ankommende Prozess einfach an das Ende der Warteliste eingereiht und zwischen den Prozessen und deren Anforderung keine Unterscheidung getroffen wird. Wer zuerst in der Warteschlange ankommt, bekommt auch als erstes die Kontrolle über die CPU.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.17: FCFS-Scheduling Ablauf
Die mittlere Turnaroundzeit je Task errechnet sich aus:
Abbildung in dieser Leseprobe nicht enthalten
und die durchschnittliche Wartezeit je Prozess aus:
Abbildung in dieser Leseprobe nicht enthalten
Entscheidend für die mittlere Wartezeit ist die Reihenfolge, in der die Prozesse bei dieser Strategie zur Ausführung kommen. Um dies zu verdeutlichen untersuchen wir zwei Szenarien (mit je vier Prozessen und jeweils gleichen Burstzeiten):
Abbildung in dieser Leseprobe nicht enthalten
In der Reihenfolge P3, P1, P2 und P4 (im Beispielszenario 1) und P4, P1, P3 und P2 (im Beispielszenario 2) ergeben sich folgende Wartenzeiten für die Prozesse:
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.18: Gantcharts eines Beispielhaften FCFS Verhaltens
und nach Formel 2.2 auf der vorherigen Seite folgt für beide Szenarien eine durchschnittliche Wartezeit twaiting von:
Abbildung in dieser Leseprobe nicht enthalten
Aus diesen beiden Beispielen wird ersichtlich, dass beim FCFS-Prinzip die Ankunft der Prozesse in der Warteschlange erhebliche Auswirkungen auf die durchschnittliche Wartezeit hat. Je größer die Unterschiede zwischen den Burstzeiten der Prozesse, desto mehr Einfluss hat die Reihenfolge, in der die Prozesse zur Abarbeitung übergeben werden auf die durchschnittliche Wartezeit.
Shortest Job First
Bei der Shortest Job First-Strategie (SJF) wird der Job zuerst bedient, der die (geschätzt) gering- ste Gesamtlaufzeit hat. Im Vordergrund steht, die Turnaroundzeit je Prozess und den Einfluss, den die Turnaroundzeit eines Prozesses auf die Wartezeit der anderen Prozesse im FIFO-Verfahren hat, zu minimieren. Jedesmal, wenn ein neuer Prozess zur Ausführung kommt, muss der Scheduler die Warteliste gemäß den (geschätzten) Laufzeiten neu sortieren.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.19: Shortest Job First Scheduling-Algorithmus
Die mittlere Ausführungszeit für die einzelnen Ausführungszeiten ti1 , ti2 , . . ., tin errechnet sich aus:
Abbildung in dieser Leseprobe nicht enthalten
wobei dies nur dann minimal ist, wenn für diese n Prozesse ti1 ≤ ti2 ≤ . . . ≤ tin gilt.
Problematisch beim SJF-Algorithmus ist, dass dieser nicht fair ist. Auf Systemen mit einer hohen Rate an neu erzeugten Jobs besteht die Gefahr, dass Tasks mit hoher Rechenzeit verhungern, also nie zur Ausführung kommen.
Ein weiterer Nachteil ist, dass sich der SJF-Algorithmus nur auf der Basis von Long-Term-Sched- uling realisieren lässt. Dies geschieht dadurch, dass bspw. ein Benutzer eines Batchsystems zum Programmstart sagen kann, wie lange in etwa der Task laufen wird. Für Short-Term-Scheduling ist SJF vollkommen ungeeignet, da es nicht möglich ist, vorherzusehen, wie lange der nächste CPU-Burst eines Jobs dauern wird.
Wenn jedoch keine Möglichkeit besteht, die Dauer des nächsten CPU-Bursts zu wissen, so besteht jedoch die Möglichkeit, diese Dauer zu schätzen und den SJF-Algorithmus so preemptiv-fähig22 werden zu lassen. Die Grundlage für diese Schätzung ist die Annahme, dass CPU-Bursts je Prozess in etwa gleich sind, also dass die Dauer des kommenden CPU-Bursts in etwa genausolange dauert, wie die zuvor erfolgten CPU-Bursts.
tn sei die Dauer des nten CPU-Bursts für den Prozess P1 und α sei die Gewichtung der vorange- gangenen CPU-Bursts mit 0 ≤ α ≤ 1, dann ergibt sich für die Dauer des nächsten CPU-Bursts [Abbildung in dieser Leseprobe nicht enthalten]
[...]
1 JAVA ist ein eingetragenes Warenzeichen der SUN Inc.
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.
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.
7 siehe Kapitel 4.3.1 auf Seite 57
8 Intel bietet mit dem Northwood-Prozessor Kern einen Prozessorkern, der SMT unterstützt und nennt diese Technologie Hyperthreading
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
12 vgl. Abschnitt 2.4.4
13 vgl. Kapitel 2.2.2 auf Seite 10
14 Siehe Abschnitt 4.5.3 auf Seite 71
15 siehe Kapitel 2.4.2 auf Seite 25, ff.
16 siehe Abschnitt 2.5 auf Seite 36
17 “Bound” heißt in diesem Zusammenhang nicht “beschränkt” oder “begrenzt”, sondern “gebunden”. Das Verhalten eines “I/O bound” Prozesses ist an Ein-/Ausgabe gebunden und korreliert bspw. bei viel Festplattenzugriff mit den Zugriffs- und Antwortzeiten der Festplatte. In Fachbüchern aus dem englischen ins deutsche übersetzt, liest man jedoch häufig von “Beschränkungen”, was nur bedingt richtig ist.
18 siehe Abschnitt 2.4.4 auf Seite 35
19 siehe Kapitel 3.3 auf Seite 46 und 4.5 auf Seite 68
20 Die Rechenzeit eines Prozesses, die sich auf den Throughput auswirkt darf nicht verwechselt werden mit der Tur- naroundzeit des Prozesses
21 Die First-Come First-Served-Strategie wird auch häufig First-In First-Out-Strategie (FIFO) genannt
22 Die preemptive Variante des SJF-Algorithmus ist auch bekannt als Shortest Time Remaining Next-Algorithmus
- Quote paper
- Diplom-Informatiker (FH) Alexander Zschach (Author), 2004, Funktionsweise und Performancemessungen des LINUX O(1)-Schedulers, Munich, GRIN Verlag, https://www.grin.com/document/70285
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.