Studiengang Informatik FHDW
Vorlesung:
Betriebssysteme I
Scheduling
3. Quartal 2012
Vorlesung: 1 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling
Was ist das denn?
Haben Sie eine Idee für die grundsätzlichen
Verfahren?
Welche Kriterien würden Sie für SchedulingVerfahren verwenden?
Was denken Sie, welche Verfahren bei der
Umsetzung aktueller BS in der Praxis
Anwendung finden?
Vorlesung: 2 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling
Ein (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, die die
zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt.
Prozess-Scheduler kann man grob in unterbrechende (preemptive) und
nicht unterbrechende (non preemptive, auch kooperativ genannt)
aufteilen. Nicht unterbrechende Scheduler lassen einen Prozess,
nachdem ihm die CPU einmal zugeteilt wurde, solange laufen, bis dieser
diese von sich aus wieder freigibt oder bis er blockiert. Unterbrechende
Scheduler teilen die CPU von vornherein nur für eine bestimmte
Zeitspanne zu und entziehen dem Prozess diese daraufhin wieder.
Weiter ist eine Unterscheidung in "work-conserving" und "non workconserving" Strategien möglich. Eine Scheduler-Strategie arbeitet "workconserving", wenn das Umschalten zwischen Prozessen nur eine
vernachlässigbar geringe Zeit in Anspruch nimmt.[1] Man kann
verschiedene Systeme unterscheiden, in welchen jeweils verschiedene
Anforderungen an den Scheduler gestellt werden:
Stapelverarbeitungssysteme
interaktive Systeme
Echtzeitsysteme
Vorlesung: 3 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Ziele
Die Zuteilung der CPU an die Prozesse sollte
bestmöglich erfolgen, wobei (abhängig vom
ausführenden System) allerdings unterschiedliche
Ziele verfolgt werden können:
Allgemein
Fairness: Kein Prozess sollte unverhältnismäßig
lange warten müssen, während ein anderer
bevorzugt wird.
Balance: Die Prozesse sollten der CPU auf eine
Weise zugeteilt werden, dass auch andere
Ressourcen wie Festplatte, Netzwerk-Schnittstelle
u.a. ausgelastet sind.
Einhaltung der Systemregeln
Vorlesung: 4 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Ziele
Stapelverarbeitungssysteme
CPU-Auslastung: Die CPU sollte zu jeder Zeit
ausgelastet sein. Es soll nicht vorkommen, dass die
CPU sich im Leerlauf befindet, nur weil ein Prozess
auf Daten von der Festplatte wartet.
Durchsatz: Die Anzahl beendeter Aufgaben pro
Zeiteinheit sollte maximiert werden. Dies ergibt eine
ähnliche Strategie wie die Auslastung, betrachtet
aber mehr das tatsächliche Ergebnis.
kurze Turnaroundzeit (Durchlaufzeit): Die Zeit, die
von der Ankunft eines Prozesses bis zu seiner
vollständigen Beendigung vergeht, sollte minimiert
werden.
Vorlesung: 5 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Ziele
Interaktive Systeme (Dialogsysteme)
Schnelle Antwortzeiten: Die Wartezeiten des
Benutzers (oder anderer Systeme) sollten minimiert
werden. Prozesse, die eine Interaktion mit dem
Benutzer erfordern, sollten also bevorzugt werden
vor solchen, die im Hintergrund stattfinden können.
Proportionalität: Die Antwortzeiten verschiedener
Prozesse sollten den Erwartungen des Benutzers
entsprechen. Werden Prozesse (wie z.B. das
Schließen einer Anwendung) vom Benutzer als
simpel betrachtet, sollten diese auch schnell
ausgeführt werden.
Vorlesung: 6 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Ziele
Echtzeitsysteme
Deadlines einhalten
Vorhersagbarkeit: Wichtig für MultimediaAnwendungen (da sonst z.B.
Verschlechterung der Tonqualität droht)
Vorlesung: 7 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Strategien
Das größte Problem des Schedulers ist die
Tatsache, dass die benötigten Betriebsmittel
für die einzelnen Prozesse nicht im Vorfeld
bekannt sind. Es lässt sich also im
Allgemeinen keine optimale Planung
erstellen, sondern der Scheduler muss
dynamisch auf geänderte Anforderungen
reagieren. Dabei können (abhängig vom
Scheduler) verschiedene
Zuteilungsstrategien zum Einsatz kommen.
Unter anderem:
Vorlesung: 8 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
First-Come First-Served (FCFS, FIFO): Hierbei
werden alle Prozesse in der Reihenfolge ihres
Eingangs bearbeitet. Eine Neuzuteilung der
Prozesse findet erst statt, wenn der laufende
Prozess zu warten beginnt oder seine Ausführung
beendet ist.Diese Strategie erzielt eine gute
Auslastung bezüglich der CPU, allerdings nicht
bezüglich Ressourcen, die längere Zeit für eine
Anforderung benötigen können, wie z. B. Ein/Ausgabe oder Massenspeicher. Für
Mehrbenutzersysteme ist die Strategie darüber
hinaus wenig geeignet, da einzelne Benutzer so
ggf. für längere Zeit (nämlich bei aufwendigen
Prozessen anderer Benutzer) ausgeschlossen
werden.
Vorlesung: 9 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Shortest Job First (SJF, SPT) ist ein
weiteres Verfahren, das nicht für
Mehrbenutzersysteme geeignet ist. SJF lässt
sich in Fällen einsetzen, in denen die
benötigte Rechenzeit für einzelne Aufgaben
aus Erfahrungswerten gut vorhergesagt
werden kann. Ein Nachteil ist, dass große
Prozesse u. U. niemals die CPU zugeteilt
bekommen, wenn sich immer kürzere Jobs
vordrängeln.
Vorlesung: 10 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Shortest-Remaining-Time, ShortestRemaining-Processing-Time entspricht
dem SPT-Verfahren. Anders als beim SPTVerfahren wird hier ein Prozesswechsel
durchgeführt, wenn ein neu ankommender
Prozess eine kürzere Ausführungszeit
aufweist, als die verbleibende des aktuellen
Prozesses.
Vorlesung: 11 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Round Robin (Zeitscheibenverfahren):
Einem Prozess wird die CPU für eine
bestimmte (kurze) Zeitspanne zugeteilt.
Danach wird der Prozess wieder hinten in die
Warteschlange eingereiht.
Vorlesung: 12 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Earliest Due Date: Bei dieser Strategie
werden diejenigen Prozesse zuerst
ausgeführt, welche die geringste Deadline
haben. Voraussetzung dafür sind statische
Deadlines und gleichzeitiges Eintreffen von
einander unabhängiger Tasks. Dieses
nichtunterbrechende Verfahren ist ideal, um
die maximale Verspätung zu minimieren.
Vorlesung: 13 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Prioritätsscheduling: Bei dieser Strategie wird jedem
Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt
dann in der Reihenfolge der Prioritäten. Da es sich dann
(innerhalb der gleichen Prioritäten) um eine Strategie der
Eingangsreihenfolge handelt, wird diesem Verfahren
meistens noch ein Zeitscheibenverfahren untergeordnet
(diese nennt man dann u.a. auch Multilevel Feedback
Queue Scheduling, Shortest-Elapsed-Time (SET) ), um
trotzdem eine schnelle Antwortzeit zu ermöglichen.
Zusätzlich wird in den verbreiteten Schedulern mit
dynamischen Prioritäten gearbeitet, wobei sich die Priorität
eines Prozesses mit der Zeit erhöht, damit auch niedrig
priorisierte Prozesse irgendwann bearbeitet werden und
nicht ständig von höher priorisierten Prozessen verdrängt
werden.
Vorlesung: 14 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Strategien:
Terminabhängige Ablaufplanung: Diese
Strategie kommt hauptsächlich in
Echtzeitsystemen vor. Dabei werden die
Prozesse bevorzugt verarbeitet, die als
erstes beendet sein müssen. Damit ist es
möglich, eine definierte Antwortzeit für
bestimmte Prozesse zu garantieren.
Vorlesung: 15 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Verfahren:
Scheduling-Verfahren I
Completely Fair Scheduler (CFS), neuester Scheduler von
Linux seit 2.6.23
Coscheduling
COVERT (Cost Over Time)
Deadline Monotonic Scheduling (DMS)
Earliest Deadline First (EDF) (Planen nach Fristen)
Fair-Share-Scheduling
First Come First Serve (FCFS) bzw. First In – First Out
(FIFO)
Generalized Processor Sharing (GPS)
Gruppenscheduling
Highest Response Ratio Next (HRRN)
Least Laxity First (Planen nach Spielraum)
Least recently used (LRU)
Vorlesung: 16 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling Verfahren:
Scheduling-Verfahren II
Lotterie-Scheduling
Multilevel Feedback Queue
Planen durch Suchen
Prioritätsscheduling (PS)
Priority Exchange Server
Rate Monotonic Scheduling (RMS) (Planen nach monotonen Raten)
Round-Robin-Strategie
Shortest-Job-First
Shortest-Process-Next (SPN)
Shortest-Remaining-Time (SRT)
Soft_affinity (SA)
Sporadic Scheduling
Three-Level-Scheduling
Weighted Round Robin (WRR)
Vorlesung: 17 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Scheduling-Verfahren
Completely Fair Scheduler (CFS) (Scheduler für Linux seit 2.6.23 )
Der Completely Fair Scheduler (kurz CFS) ist ein Prozess-Scheduler
in der Informatik. Solche Scheduler werden verwendet, um die Priorität
von Programmabläufen auf Kernelebene von Betriebssystemen zu
verwalten. CFS wurde von Ingo Molnár entwickelt und ersetzte mit der
Linux-Kernelversion 2.6.23 im Oktober 2007 den zuvor implementierten
O(1)-Scheduler.
Der CFS garantiert eine faire Aufteilung der Prozessorzeit. Er verzichtet
im Gegensatz zum O(1)-Scheduler auf Heuristiken und Statistiken. Im
Idealfall läuft beim CFS jeder Task quasiparallel in gleicher
Geschwindigkeit. Der CFS kennt keine Runqueue, keine Timeslices und
kein Array-Switching, weil es kein expired-Array gibt. Stattdessen ist
jedem Prozess ein wait_runtime-Wert zugeordnet, der auf
Nanosekunden genau bestimmt ist, und eine Aussage darüber macht,
wie lange der Prozess auf seine Ausführung wartet. Derjenige Prozess
mit höchster wait_runtime wird gewählt. Als Struktur wird dafür ein nach
der wait_runtime sortierter Rot-Schwarz-Baum verwendet.[1]
Vorlesung: 18 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Prozess-Scheduling
Grundsätzliches Verfahren
Kriterien für Scheduling-Verfahren
Round-Robin-Scheduling
Prioritäts-Scheduling
Mehrere Schlangen
Shortest-Job-First
Garantiertes Scheduling
Zweistufiges Scheduling
Umsetzung bei den aktuellen BS in der
Praxis
Vorlesung: 19 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Scheduling
Detaillierte Diskussion der Scheduling-Verfahren
Verschiedene Kriterien
Vor- und Nachteile der unterschiedlichen Verfahren
Round-Robin-Scheduling
Prioritäts-Scheduling
Zweistufiges Scheduling
Umsetzung bei den aktuellen BS in der Praxis
Beispiel Windows NT 4.0
Aufbau und Architektur von Windows-NT 4.0 (siehe
auch White-Paper)
Vorlesung: 20 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Speicherverw.
Speicherverwaltung
Aufgaben der Speicherverwaltung
Einfache Speicherverwaltung
Fragmentierung (interne / externe)
Verschiebbarkeit (Relocation)
Organisationsformen (Bitmap, verkettete
Listen..)
Virtueller Speicher
Segmente, Seiten, Seitenrahmen
Vorlesung: 21 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Speicherverw.
Allgemeine Speicherverwaltung
Virtuelle Speicherverwaltung
Paging / Demand Paging
Caching
Swapping
Verschiedene Realisierungen bei aktuellen
Betriebssystem-Varianten
Translation LookAside Buffer (TLAB)
Thrashing
Lokalitätsprinzip
Working Set
Vorlesung: 22 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Wg. Betriebssysteme: Speicherverw.
Speicherverwaltung am Beispiel von Linux
Paging
Das Virtuelle Speichermodell
Die Page Table im Detail
Page Allocation und Page Deallocation
Memory Mapping & Demand Paging
Caching
Die verschiedenen Caches
Swapping
Auslagern von Speicherseiten
Der Kernel Swap Demon (kswapd)
Freimachen von Speicherseiten
Vorlesung: 23 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Wg. Betriebssysteme: Speicherverw.
Speicherverwaltung bei Linux
Paging, Caching, Swapping
Ein- /Ausgabe-System
Anforderungen
Physisches Ein- /Ausgabe-System
Aufgaben eines Gerätetreibers
Polling / Interrupt
Logisches Ein- /Ausgabe-System
Dateiverwaltung
Dateikonzept (Datei, Dateisystem)
Vorlesung: 24 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Dateiverwaltung
Dateiverwaltung
Dateikonzept (Datei, Dateisystem)
Dateiorganisation logische Struktur
Zugriffsformen
Sequentieller Zugriff
Wahlfreier Zugriff
Indexsequentieller Zugriff
Speicherplatzzuordnung und -Verwaltung
Verzeichnisse
Datenträger- Organisation
Beispiel: Virtuelle Maschinen und Dateisysteme
Vorlesung: 25 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Dateiverwaltung
Datenträger-Organisation
Sicherheit und Zugriffsschutz
Leistungsverbesserungen
Systemdienste zur Dateiverwaltung
Praktische Beispiele für den Einsatz von
Dateisystemen (MS-DOS, NTFS, ext2...)
Vorlesung: 26 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Betriebssysteme: Aktuelles
Nach der kurzen Wiederholung der
wichtigsten Begrifflichkeiten und
Zusammenhänge werden aktuelle
Entwicklungen und Tendenzen im Umfeld
der Betriebssysteme und Netzwerke zur
Motivation gegeben.
Wovon haben Sie gehört?
Was wird benötigt?
Verschiedene Anwendungs /Einsatzbereiche
Kosten- /Nutzen Betrachtungen
Praktische Beispiele und Ausblick
Vorlesung: 27 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
ENDE
Fragen?
Vorlesung: 28 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg
Quellen
Tannenbaum, Andrew, Moderne Betriebssysteme
M. Weber, Foliensatz Universität Ulm
Microsoft Whitepapers
Novell Brainshare 2004
Novell Papers 2003 / 2004
Novell Tour 2004
Präsentation Oracle 2004
Präsentation Targosoft 2004
Präsentation Matsushita 2004
Quelle Wikipedia aktuell aus Februar 2011
Vorlesung: 29 Betriebssysteme / Netze I
2012 Prof. Dr. G. Hellberg

Foliensatz Scheduling