Kapitel 6

Planen von Aktivitäten (Scheduling)

IN DIESEM KAPITEL

• erfahren Sie, warum es nötig ist, Aktivitäten zu planen,
• lernen Sie Methoden kennen, wie man Abarbeitungspläne entweder im Voraus (offline) oder zur Laufzeit des Systems (online) generiert.

Im Allgemeinen existiert in einem Rechensystem eine (große) Menge an Prozessen oder anderen Aktivitäten, die auf eine (kleine) Menge an Prozessoren abgebildet werden müssen. Das System muss festlegen, wer (welche Aktivität), wann (zu welchem Zeitpunkt), wie lange (für welchen Zeitabschnitt), wo (auf welchem Prozessor oder Core) abgearbeitet wird. Dieser Vorgang wird Prozessorzuteilung oder Scheduling genannt; die verantwortliche Komponente im Betriebssystem ist der Scheduler.

Wozu benötigt man einen Scheduler?

Je nach Zweck des Systems versucht man durch den Einsatz verschiedener Verfahren, bestimmte Leistungskennwerte zu optimieren. Solche Ziele können sein:

• Maximierung der CPU-Auslastung. Dies ist häufig das Ziel bei sehr teurer Hardware, wie beispielsweise Clusterrechnern mit vielen Zehn- oder Hunderttausenden Prozessoren. Infolge des sehr hohen Energiebedarfs solcher Systeme sind jegliche Arbeitspausen zu vermeiden.
• Maximierung des Durchsatzes. Unter dem Begriff »Durchsatz« versteht man verarbeitetes Datenvolumen pro Zeit. Systeme, die Datenströme erzeugen und verarbeiten wie Streaming-Server oder Systeme zur digitalen Signalverarbeitung, fallen in diese Kategorie. Im Gegensatz zur Betrachtung der reinen CPU-Auslastung muss hier das Zusammenspiel zwischen CPU, Haupt- und Massenspeicher sowie Netzwerkschnittstelle besonders gut funktionieren.
• Minimierung der mittleren Reaktionszeit. Dieses Kriterium ist für alle interaktiven Systeme wichtig, denn die Nutzer akzeptieren bei der Arbeit nur geringe Verzögerungen bei der Reaktion des Systems auf ihre Eingaben; das Arbeiten an zügig reagierenden Systemen wird als angenehmer empfunden als das an trägen. Später im Kapitel lernen Sie, warum die Optimierung dieses Parameters eine Verschlechterung von CPU-Auslastung und Durchsatz nach sich zieht (und umgekehrt).
• Garantie einer maximalen Reaktionszeit. Im Gegensatz zum vorangehenden Kriterium, bei dem versucht wird, Reaktionszeiten klein zu halten, geht es hier um die Zusicherung, dass eine bestimmte Reaktionszeit niemals überschritten wird. Dies ist sehr häufig beim Betrieb von industriellen Steuerungen sowie Fahrer- und Pilotenassistenzsystemen notwendig, für die sich der Begriff Automotive Systems eingebürgert hat. Entsprechende Rechensysteme nennt man Echtzeitsysteme, und diese wiederum nutzen ganz andere Planungsverfahren als Universalbetriebssysteme.
• Fairness. Eine recht einleuchtendes Ziel, das interessanterweise dem Gedanken der Reaktionszeitgarantie widerspricht, ist die gleichmäßige Aufteilung der CPU und gegebenenfalls weiterer Ressourcen unter allen Nutzern. Arbeiten allgemein Nutzer gleichzeitig an einem System, dann sollte jeder ungefähr 1/n der Rechenzeit des Systems zugeteilt bekommen. Das in einem späteren Abschnitt vorgestellte Round-Robin-Verfahren verwirklicht dies.

Da sich verschiedene Optimierungsziele widersprechen, also die Verbesserung eines Kennwertes meist die Verschlechterung anderer Parameter nach sich zieht, sucht man bei Auswahl und Implementierung des Schedulers häufig einen Kompromiss.

Scheduling im engeren Sinne betrifft die Zuordnung des Prozessors zu Aktivitäten. Weitere planbare Ressourcen sind der virtuelle Speicher (Kapitel 9) sowie Aufträge an den Massenspeicher (Kapitel 10). Auch Bandbreite bei der Kommunikation kann geplant werden, dies verlässt allerdings den Kontext dieses Buches.

Planst du noch, oder arbeitest du schon?

Ein wesentlicher Punkt ist die Frage, wann der Plan erstellt wird.

Ein naheliegender Vorschlag ist, dies bei der Entwicklung des Systems zu tun. Wenn man die erforderlichen Aktivitäten und deren Rechenzeitbedarf kennt, kann man darangehen, einen Abarbeitungsplan zu erstellen. Der entstehende Plan muss dann in einer geeigneten Datenstruktur abgelegt werden und wird nach dem Systemstart befolgt. Diese Vorgehensweise wird Offline-Scheduling genannt. In diesem Sinne arbeitet beispielsweise auch der Stundenplanbauer in der Schule: Er kennt alle Aktivitäten (die Klassen) und Ressourcen (Klassenräume, Turnhalle …) sowie den (Rechen-)Zeitbedarf in Form der Stundentafeln für jede Klassenstufe. Das Ergebnis ist der erarbeitete Plan, der zur »Laufzeit« des Systems durch das Stunden- und Pausenklingeln durchgesetzt wird.

Vorteilhaft ist dabei die Tatsache, dass man fast beliebig viel Zeit in die Erstellung des Planes investieren kann. Die meisten Schedulingprobleme sind nämlich schwierig; es gibt für sie keine Algorithmen, die in polynomieller Zeit zu einem Ergebnis führen. Statt den »besten« Plan für eine gegebene Menge von Prozessen zu finden, müssen wir uns oft mit Näherungslösungen oder suboptimalen Ergebnissen begnügen. Insofern ist es durchaus von Vorteil, wenn man genügend Rechenzeit in das Scheduling investieren kann.

Auf der anderen Seite birgt das Offline-Scheduling auch ein Problem: Nicht immer ist im Voraus bekannt, welche Prozesse im System laufen sollen. Ein normaler Büro-PC kann einfach nicht wissen, ob der Nutzer im Laufe des Tages weiter am geplanten Buch arbeiten möchte oder lieber ein Spiel lädt. Für interaktive Systeme oder, präziser, immer dann, wenn kein vollständiges Wissen über die abzuarbeitenden Aktivitäten vorliegt, muss zur alternativen Kategorie des Online-Schedulings gegriffen werden.

Hierbei wird der Plan nicht im Vorhinein ermittelt, sondern gewissermaßen »live« während das System arbeitet. Immer dann, wenn ein Prozess den Aktiv-Zustand verlässt, entscheidet das System, welcher Prozess als Nächstes bearbeitet wird. Es leuchtet ein, dass für diese Entscheidung nicht allzu viel Zeit zur Verfügung steht, sodass ein vergleichsweise suboptimaler Plan resultiert. Vorteilhaft ist jedoch die viel größere Flexibilität: Das System kann auf sich ändernde Anforderungen reagieren und den Plan geeignet anpassen. In den meisten Rechensystemen nutzt man Online-Verfahren, die Flexibilität überwiegt also den Optimalitätsverlust. Aus diesem Grunde erlernen Sie in diesem Kapitel entsprechende Verfahren.

Außer Informatikern befassen sich auch Wirtschaftswissenschaftler, Produktionsplaner und Logistiker mit Fragen des Schedulings. Hierbei wird jedoch stets offline geplant, und der Zeitmaßstab ist einige Zehnerpotenzen größer. Auch der Stundenplanbau in der Schule kann kaum online erfolgen. Das hätte zur Folge, dass kein Stundenplan an die Schüler verteilt wird, sondern bei jedem Pausenklingeln würde der Planer ad hoc allen Klassen die nächsten Räume zuweisen. Kein beneidenswerter Job!

Unterbrechungen und, wenn ja, wie viele

Ein weiteres wichtiges Kriterium ist der Zeitpunkt, wann eine Aktivität unterbrochen wird, um den Scheduler zu aktivieren und gegebenenfalls einen anderen Prozess abzuarbeiten.

Im einfachsten Falle ist dies jederzeit möglich. Das Betriebssystem kann zu jedem beliebigen Zeitpunkt die Bearbeitung des gegenwärtig aktiven Prozesses unterbrechen. Umgekehrt muss ein Prozess damit rechnen, dass er an beliebiger Stelle in seinem Anweisungsstrom unterbrochen wird. Dies nennt man präemptives Scheduling. (Im Englischen nennt man die Unterbrechung und spätere Fortsetzung eines Prozesses »preemption«, daher der etwas sperrige Begriff; er hat nichts mit Prävention zu tun.) Die meisten modernen Universalbetriebssysteme (Windows, UNIX und verwandte) sind auf diese Weise realisiert. Vorteilhaft an dieser Lösung ist, dass das Betriebssystem stets die Herrschaft über alle Prozesse besitzt, keiner kann die CPU okkupieren, Prozesse können jederzeit beendet werden.

Eine zweite Realisierungsform ist das sogenannte kooperative Scheduling. Betriebssysteme dieses Typs sind gerade nicht in der Lage, den aktiven Prozess ohne dessen Mithilfe (Kooperation!) zu unterbrechen. Stattdessen muss der Prozess selbst aktiv den Prozessor zurückgeben. Dies geschieht durch die Nutzung von Systemrufen. Sobald der Prozess einen Systemruf ausführt, wird in den Kernel Mode der CPU geschaltet, und das Betriebssystem hat automatisch wieder die Kontrolle. Es kann sich nun entscheiden, den unterbrochenen Prozess zu suspendieren und anschließend mittels des Schedulers einen anderen Prozess zur Abarbeitung auszuwählen, bis dieser wieder einen Systemruf ausführt und das Spiel von Neuem beginnt. Genauso ist es möglich, dass der unterbrochene Prozess weiter bearbeitet wird.

Was geschieht aber, wenn der betreffende Prozess keinen Systemruf benötigt und er zum Beispiel eine langwierige Berechnung anstellt? Für diesen Fall gibt es einen Dummy-Systemruf, der keine Funktionalität besitzt, außer dem Betriebssystem die Möglichkeit zu geben, die Kontrolle zu erlangen. Die Positionen dieses Dummy-Systemrufs im Code werden Preemption Points, Unterbrechungspunkte, genannt. Natürlich ist der Programmierer dafür verantwortlich, Unterbrechungspunkte regelmäßig in »systemrufarmen« Programmcode einzustreuen. Vergisst er dies, dann okkupiert der Prozess die CPU, was alle anderen Prozesse benachteiligt. Im Kontext konkurrierender Nutzer ist ein solches Schema kaum sinnvoll einzusetzen. Es bietet jedoch einen gravierenden Vorteil: Da die Prozesse nicht mehr an beliebiger Stelle unterbrochen werden können, gibt es keine oder kaum kritische Abschnitte. Entsprechend ist der Bedarf an Synchronisation weitaus kleiner, was zu weniger Overhead, weniger zeitabhängigen Fehlern wie Deadlocks und einfacherer Codestruktur führt. Die (historischen) Windows-Varianten vor Windows 95 boten diese Form des Schedulings. Ebenso wird es in Spezialbetriebssystemen eingesetzt, und User-Level-Thread-Packages nutzen es ebenfalls.

Der Vollständigkeit halber sei noch eine dritte Form erwähnt: Bestimmte Systeme erlauben gar keine Unterbrechung. Eine einmal begonnene Aktivität wird bis zu ihrem Ende (oder ihrer Blockierung) ausgeführt. Dies wird Run-to-completion genannt und kommt in Jobsystemen zum Einsatz, bei denen es nicht auf quasigleichzeitige Ausführung ankommt. Durch die entfallenden Prozessumschaltungen reduziert sich der Overhead, sämtliche Prozessorleistung kommt den Prozessen zugute.

Zeit- und Ereignissteuerung

Widmen wir uns noch etwas dem präemptiven Scheduling. Sie wissen bereits, dass das Betriebssystem jederzeit die Kontrolle übernehmen kann. Dies wirft die Frage auf, in welchem grundsätzlichen Rhythmus dies geschieht.

Besonders einfach strukturiert sind zeitgesteuerte Systeme. Hierbei wird jeglicher Ablauf im System durch einen einheitlichen Takt vorgegeben. Stellen Sie sich eine antike Rudergaleere vor. Damit alle Ruderer im gleichen Takt arbeiteten, saß im Bug ein Aufseher, der eine große Trommel schlug und damit den Rhythmus aller Ruderer vorgab. Ein Abweichen von diesem Takt war unmöglich.

Ganz ähnlich funktioniert ein zeitgesteuertes Rechensystem. In der CPU programmiert man dafür einen Timer, der periodisch einen Interrupt generiert. Durch dessen Behandlung landet man nach Ablauf einer Timerperiode stets im Betriebssystem und kann den Scheduler zur Auswahl des nächsten Prozesses aufrufen oder einfach den nächsten Prozess, der sich im (offline generierten) Plan befindet, aktivieren.

Wichtig ist, dass alle Aktivitäten sich diesem Takt unterordnen. Hat eine Aktivität gerade nichts zu tun, dann steht ihr trotzdem immer eine Taktzeit (Slot) zur Verfügung, die sie aktiv »verbummeln« muss. In einem zeitgesteuerten System gibt es außer diesem Takt keine extern induzierten Ereignisse, die direkt Reaktionen auslösen. Peripheriegeräte wie die Netzwerkschnittstelle oder die Tastatur müssen aktiv abgefragt werden (sogenannter Pollingbetrieb), da sie keine Ereignisse auslösen können. Abbildung 6.1 zeigt ein einfaches Beispiel. Es gibt vier Prozesse, hellgrau, dunkelgrau, schwarz und weiß; diese werden im globalen Takt hintereinander für jeweils eine Taktzeit aktiviert. Es ist somit unmöglich, dass ein Prozess mehr als die Dauer eines Slots auf einmal erhält oder ausgelassen wird, weil er gerade nichts zu tun hat.

Abbildung 6.1: Prinzip der Zeitsteuerung

Die gegenteilige Kategorie sind ereignisgesteuerte Systeme. Hierbei reagiert das System auf alle möglichen externen Einflüsse. Wenn die Peripheriegeräte eines Systems die CPU benötigen (beispielsweise nach der Betätigung einer Taste oder dem Empfang eines Datenpaketes), dann lösen sie ein Ereignis in Form eines Interrupts aus. Die CPU unterbricht ihre gegenwärtige Arbeit, reagiert auf das Ereignis (liest den Tastaturpuffer aus oder transferiert das empfangene Datenpaket in den Hauptspeicher) und setzt nach der Interruptbehandlung die Programmausführung fort. Vorteilhaft an diesem Verfahren ist dessen Ökonomie: Die CPU wird nur unterbrochen, wenn Handlungsbedarf besteht. In einem zeitgesteuerten System muss die Tastatur regelmäßig aktiv abgefragt werden, egal, ob der Nutzer eine Taste betätigte oder nicht. Andererseits besteht hierbei potenziell eine Überlastgefahr, die es im zeitgesteuerten System nicht gibt. Es gibt keine Möglichkeit, die Anzahl der Ereignisse zu beschränken. Somit könnte die Peripherie die CPU mit Interrupts »überfluten«, Letztere käme nicht mehr zur eigentlichen Nutzarbeit. Diese Gefahr besteht in einem zeitgesteuerten System nicht.

Ein oder mehrere Prozessoren?

Schedulingverfahren kann man nach der Anzahl betrachteter Prozessoren im System in Uni- und Multiprozessorverfahren klassifizieren. Uniprozessorverfahren sind historisch älter, besonders gut untersucht und deutlich einfacher zu analysieren. Die Unterstützung mehrerer Prozessoren ist eine relativ neue Entwicklung. Sie wurde durch die breite Verfügbarkeit von Multicore-Plattformen etwa ab dem Jahr 2000 notwendig.

Prioritäten

Im einführenden Abschnitt dieses Kapitels haben Sie gelernt, dass man durch das Schedulingverfahren bestimmte Parameter des Rechensystems optimieren möchte. Zu diesem Zweck erhält jeder Prozess oder jede Aktivität einen Parameter zugeordnet, der seine oder ihre »Wichtigkeit« repräsentiert. Dieser wird Priorität genannt.

Wenn ein neuer Prozess zur Aktivierung ansteht, vergleicht der Scheduler die Prioritäten aller bereiten Prozesse und aktiviert den zu diesem Zeitpunkt höchstpriorisierten Prozess. Sind mehrere Prozessoren frei, so werden analog die höchstpriorisierten Prozesse zur Bearbeitung ausgewählt.

Man unterscheidet zum einen externe Prioritäten, wobei die Prioritäten willkürlich durch den Nutzer oder den Entwickler des Systems, gewissermaßen »von außen«, vergeben werden. Im Kontrast dazu stehen interne Prioritäten, die aus Parametern des Systems selbst abgeleitet werden.

Des Weiteren gibt es statische und dynamische Prioritäten. Im ersten Fall ist die Priorität konstant, im zweiten Fall ändert sie sich. Konstante Prioritäten sind einfacher zu realisieren und die zugehörigen Verfahren leichter zu analysieren. Dynamische Prioritäten erlauben die Adaptierung an wechselnde Wichtigkeiten der Prozesse und bieten somit mehr Flexibilität. Dynamische Priorisierung kommt bei interaktiven Systemen zum Einsatz, während statische Prioritäten beispielsweise gern in eingebetteten Systemen genutzt werden, da sich in Letzteren die Wichtigkeit der einzelnen Aktivitäten kaum ändert.

Ein beliebtes Schedulingverfahren für echtzeitfähige Systeme ist das Ratenmonotone Scheduling (RMS). Es basiert auf einem einfachen periodischen Taskmodell. Jede Ausführungseinheit oder Task besitzt zwei Parameter, eine Periode sowie eine Ausführungszeit und wird notiert . bedeutet, dass die Task Nummer 1 alle 30 Zeiteinheiten genau 5 Zeiteinheiten für ihre Bearbeitung benötigt (man verzichtet meist auf die Angabe der absoluten Dauer; typisch sind Millisekunden).

RMS ist ein Online-Verfahren für Einprozessorsysteme und funktioniert folgendermaßen: Die Priorität jeder Task ergibt sich aus ihrer Periode. Je kleiner die Periode, desto größer die Priorität. Es handelt sich also um eine statische Priorisierung, denn die einzelnen Perioden sind konstant. Es wird präemptiv geplant und stets die höchstpriorisierte Task abgearbeitet, bis sie ihre Ausführungszeit innerhalb ihrer Periode erhalten hat oder durch eine höher priorisierte Task unterbrochen wird.

Abbildung 6.2 zeigt einen Plan nach RMS für die Tasks , und im Zeitintervall von 0 bis 20. Die Jobs von haben die höchste, die von die niedrigste Priorität.

Abbildung 6.2: Resultierender Plan nach RMS für einen Prozessor und , und

Zu , und wird der aktive Job jeweils unterbrochen, da ein höher priorisierter anderer Job bereit wird. Dieses Verfahren ist besonders gut untersucht; es gibt beispielsweise Algorithmen, die für beliebige Taskmengen entscheiden können, ob alle Jobs innerhalb ihrer Periode komplettiert werden können oder ob (und, wenn ja, welche) Jobs »Verspätung« erleiden.

Man könnte auf die Idee kommen und diesen Algorithmus auch für Multiprozessorsysteme nutzen, indem man einfach die höchstpriorisierten Tasks ausführt. Dies funktioniert jedoch für bestimmte Taskmengen erstaunlich schlecht. Näheres finden Sie in der Spezialliteratur über Echtzeitsysteme unter dem Stichwort »Dhalls Effekt« [9].

Offline-Planung

In diesem Abschnitt soll anhand eines einfachen Beispiels das Planen vor der Laufzeit des Systems erläutert werden. Ein (nicht näher spezifiziertes) Rechensystem bestehe aus drei Prozessen , die wiederum aus verschiedenen Teilprozessen bestehen. Um einen Plan aufstellen zu können, muss man wissen, welche Rechenzeit jeder Teilprozess benötigt; diese ist in Klammern angegeben, wobei auf die Angabe einer konkreten physikalischen Einheit verzichtet wird. Für diese sogenannte Ausführungszeit (execution time) nutzen wir ab sofort das Symbol .

Häufig gibt es bei der Planung die Situation, dass ein Teilprozess erst ablaufen darf, wenn ein anderer Teilprozess bereits komplettiert wurde. Dies ist beispielsweise immer dann der Fall, wenn einer der beiden Ausgabedaten erzeugt, die der andere als Eingabedaten weiterverarbeitet. Diese Abhängigkeiten werden Präzedenzen genannt.

Für die Beispielprozessmenge sollen die folgenden Präzedenzen gelten:

vor , vor , vor , vor , vor .

Da diese textuelle Darstellung nicht besonders übersichtlich ist, kann man einen sogenannten Präzedenzgraphen ableiten, der aus Kreisen (den Knoten) und Pfeilen zwischen ihnen (Kanten) besteht. Jeder Knoten repräsentiert einen Teilprozess, und eine Kante zwischen zwei Knoten und existiert genau dann, wenn erst gestartet werden darf, wenn komplettiert wurde (also eine Präzedenz zwischen und existiert). Abbildung 6.3 zeigt den Präzedenzgraphen für die Prozessmenge des Beispiels.

Abbildung 6.3: Präzedenzgraph für die Beispielprozessmenge

Es gibt übrigens auch noch die impliziten Präzedenzen der Prozesse. So muss beispielsweise vor , dieses vor und dieses vor liegen. Es ist klar, dass das Ende eines Programms nicht vor dessen Anfang abgearbeitet werden kann.

Nun geht es ans eigentliche Planen. Zunächst soll ein Uniprozessorsystem, also für einen Prozessor, geplant werden. Folgendermaßen geht man dabei vor:

1. Aus der Menge aller Prozesse müssen diejenigen ausgewählt werden, die potenziell abgearbeitet werden können (Bildung der Bereit-Menge ).
2. Auswahl eines Prozesses aus . Hier unterscheiden sich die einzelnen Verfahren.
3. Planung des ausgewählten Prozesses entweder für eine Zeiteinheit (wenn präemptiv geplant wird) oder für seine gesamte Zeitdauer (wenn keine Unterbrechungen vorgesehen sind).
4. Falls noch nicht alle Prozesse komplettiert sind Goto 1.
5. Stop.

Im oben eingeführten Beispiel besteht die Bereitmenge zu Beginn () aus den Teilprozessen und . Alle anderen Teilprozesse sind von vor ihnen liegenden anderen Teilprozessen abhängig. Wenn mehr als ein Teilprozess bereit ist, soll der Scheduler im Schritt 2 den jeweils kürzesten auswählen. Da drei Zeiteinheiten benötigt und fünf Einheiten lang ist, wird zunächst abgearbeitet, danach folgt (es soll keine Unterbrechungen der Teilprozesse geben). Der Plan ist damit schon bis ermittelt. Durch die Komplettierung der ersten beiden Teilprozesse wird gewissermaßen »freigeschaltet« – seine beiden Präzedenzen sind erfüllt, und er wird von bis abgearbeitet. Nun wandern und in . Aufgrund seiner Kürze ist zuerst an der Reihe. Da zu komplettiert ist, werden in die Teilprozesse und aufgenommen, außerdem ist immer noch enthalten. Dieser muss infolge seiner Größe aber weiter warten. Da und gleich lang sind, ist es egal, wer von beiden Vorrang hat; wichtig ist nur, dass der Scheduler die Gleichwertigkeit erkennt und auflöst. Im Beispiel soll der kleinere Index »gewinnen«, also läuft von bis und anschließend bis . Der einzig bereite Teilprozess ist nun , der damit bis abgearbeitet wird. Letzter verbliebener Teilprozess ist , der erzwungenermaßen auf die Komplettierung seiner drei Präzedenzen warten muss und schließlich von bis zum Zuge kommt. Damit ist der Plan offline erstellt (Abbildung 6.4; die Teilprozesse, die gemeinsam einen Prozess konstituieren, sind identisch eingefärbt).

Abbildung 6.4: Offline generierter Plan für einen Prozessor

Für ein Multiprozessorsystem verläuft das Scheduling ganz ähnlich. Im Schritt 2 wird nun nicht ein Prozess ausgewählt, sondern so viele, wie es freie Prozessoren gibt. Dabei kann es passieren, dass Prozessoren frei bleiben müssen, weil es gar nicht genügend bereite Teilprozesse gibt. In Tabelle 6.1 finden Sie für zwei Prozessoren die entsprechenden Bereitmengen und die zur Abarbeitung ausgewählten Prozesse.

t		Auswahl
0
3	()	()
5
7
9
14
19

Tabelle 6.1: Schedulingzeitpunkte und Bereitmengen für zwei Prozessoren

Die Parallelisierung führt zu einer deutlichen Verkürzung der Gesamtabarbeitung um ungefähr ein Drittel. Andererseits gibt es infolge der Präzedenzen Phasen, in denen Prozessoren nichts zu tun haben (idle time; in der Abbildung weiß dargestellt), beispielsweise zwischen und auf CPU Nummer 1.

Abbildung 6.5: Offline generierter Plan für zwei Prozessoren

Damit ist der prinzipielle Ablauf beim Offline-Scheduling erklärt. In der Praxis hat man es meist mit viel größeren Taskmengen zu tun, und die Ermittlung der Pläne erfolgt nicht mehr ad hoc wie in oben stehendem Beispiel, sondern rechnergestützt.

Einfache Online-Verfahren für Jobsysteme

Besonders gut untersucht sind Planungsverfahren für sogenannte Jobsysteme. Die zu planenden Aktivitäten nennen wir Jobs oder Aufträge, und meist sind gewisse Parameter wie die Bearbeitungsdauer a priori bekannt (in interaktiven Systemen ist das typischerweise nicht der Fall!). Es gibt keine Unterbrechung; die Jobs werden, einmal angefangen, in einem Rutsch durchgezogen.

Ein Analogon zu Jobsystemen sind die Schlangen an den Kassen im Supermarkt. Die Kassen entsprechen den Prozessoren, und der »Füllgrad« der Einkaufswagen determiniert die Bearbeitungsdauer (durch die Kassiererin, die die Rolle der CPU übernimmt). Wenn nun ein Mitarbeiter die wartenden Kunden umsortieren würde, übernähme er die Funktion des Schedulers.

FCFS: Wer zuerst kommt, mahlt zuerst

Bleiben wir gleich beim Beispiel des Supermarktes. Die dort tatsächlich angewandte Strategie heißt: First Come First Serve (FCFS) oder auch First In First Out. Sie ist äußerst einfach zu implementieren, denn alle Jobs werden in der Reihenfolge ihres Eintreffens in eine Warteschlange eingeordnet und diese wird sukzessive bearbeitet. Ein zweiter Vorteil dieses Verfahrens liegt in dessen Fairness: Kein Job wird benachteiligt, und somit ist garantiert, dass jeder nach endlicher Wartezeit bedient wird. Eine Optimierung im engeren Sinne erfolgt natürlich nicht.

Der Grund, warum Sie dieses Verfahren trotzdem in jedem Buch zur Betriebssystemtheorie finden, ist seine einfache Analysierbarkeit. Es gibt ein Teilgebiet der Mathematik, die Warteschlangentheorie, mit deren Hilfe man bei bestimmten Annahmen über die Verteilung der Bedienzeiten und die Rate des Eintreffens der Jobs genau ausrechnen kann, wie lang die Warteschlange im Mittel ist und wie lange jeder Job im System verweilt. Dies sprengt jedoch den Rahmen dieses Buches.

SJN - Shortest Job Next

Eine zweite Strategie besteht in der Priorisierung nach der geforderten Bearbeitungsdauer der Jobs: Je kürzer diese ist, desto höher ist die Priorität. In abgeschwächter Form gibt es diese auch im Supermarkt. Wenn Sie nur zwei, drei Artikel in der Hand halten, dann kann es passieren, dass die nette Oma mit einem vollständig gefüllten Einkaufswagen unmittelbar vor Ihnen Sie zum Überholen in der Warteschlange auffordert. Der Grund ist klar: Sie müssten sehr lange in der Schlange warten, während die Oma mit der ohnehin langen Abarbeitungszeit eine kurze zusätzliche Wartezeit tolerieren kann.

In einem Rechensystem sollte das Scheduling natürlich nicht vom guten Willen einzelner Nutzer abhängen, sondern das Verfahren strikt angewandt werden. Der Lohn besteht in der Minimierung der mittleren Wartezeit (und damit auch der Verweilzeit) aller Jobs!

Sehen Sie sich dazu die folgende Jobmenge an (das Symbol repräsentiert die benötigte Ausführungszeit):

Job	A	B	C	D	E
	5	2	7	3	1

Die Abbildung 6.6 zeigt die resultierenden Pläne für die Verfahren FCFS (die Jobs sollen in der Reihenfolge A B C D E das System betreten haben) und SJN.

Die Verweilzeit eines Jobs erhält man durch Addition seiner Wartezeit und seiner Ausführungszeit, die mittlere Verweilzeit durch Addition aller individueller Verweilzeiten und Division durch die Anzahl der Jobs.

Der Unterschied ist ziemlich beträchtlich!

Abbildung 6.6: Resultierende Pläne für FCFS und SJN

SJN birgt aber auch ein Risiko: Wenn immer wieder sehr kurze Jobs im System neu eintreffen, dann haben diese alle eine verhältnismäßig hohe Priorität, sie »drängeln sich vor«. Gibt es dazu noch Jobs mit sehr großer Abarbeitungszeit, dann kann es passieren, dass einige von diesen gar nicht zur Bearbeitung kommen. In der englischen Literatur hat sich dafür der unschöne Begriff »Starvation« (Verhungern) eingebürgert. Bei SJN müssen also gegebenenfalls Maßnahmen gegen das Verhungern einzelner Jobs vorgesehen werden.

Shortest Remaining Time (SRT)

Eine mögliche Gegenmaßnahme gegen das Verhungern langer Prozesse wäre, wenn man nicht die gesamte Abarbeitungszeit zur Ermittlung der Priorität nutzen würde, sondern die noch verbleibende. Der Prozess mit der geringsten noch verbleibenden Abarbeitungszeit wird abgearbeitet. Ein solches Verfahren hat nur Sinn, wenn man präemptiv plant, die Prozesse also zu beliebiger Zeit unterbrochen werden können.

Nachteilig ist, dass nun protokolliert werden muss, wie viel Rechenzeit jeder Prozess bekommen hat, um seine Priorität zu ermitteln. Das Verfahren arbeitet offenbar mit dynamischen Prioritäten, denn die Priorität des gerade abgearbeiteten Jobs erhöht sich, während die der wartenden Prozesse konstant bleibt. Ein langer Prozess, der kurz vor seiner Komplettierung steht, kann nun nicht mehr so schnell durch neu hinzukommende kürzere Prozesse blockiert werden. Tabelle 6.2 führt die Parameter einer beispielhaften Prozessmenge auf, und Abbildung 6.7 zeigt den zugehörigen Plan nach SRT. Dabei kommt ein neuer Parameter ins Spiel. Bislang sind wir stillschweigend davon ausgegangen, dass alle Prozesse bereits zu Beginn abarbeitungsbereit sind. Es kann aber auch sein, dass Prozesse erst nach Verstreichen einer gewissen Zeitspanne zur Ausführung zur Verfügung stehen, beispielsweise wenn sie erst im Laufe der Arbeit des Systems erzeugt werden. Dies wird mit dem Parameter Bereitzeit (ready time) und dem Symbol ausgedrückt. In der Prozessmenge von Tabelle 6.2 gilt dies für die Prozesse D, E und F.

Prozess
A	4	0
B	6	0
C	2	0
D	3	2
E	1	3
F	3	3

Tabelle 6.2: Beispielprozessmenge für SRT und HRRN

Abbildung 6.7: Resultierender Plan nach SRT für die Prozesse aus Tabelle 6.2

Wie Sie sehen, werden kurze Prozesse immer noch stark bevorteilt. Zu geschieht etwas Besonderes: Der eigentlich mit drei Zeiteinheiten schon recht kurze Prozess D wird unterbrochen, weil mit E ein noch deutlich kürzerer Prozess ins System kommt. Dieser Vorgang wird Preemption, das bedeutet »vorzeitige Unterbrechung«, genannt. Nachdem der so wichtige, weil sehr kurze Prozess E komplettiert wurde, wird D an der Unterbrechungsstelle fortgesetzt.

Highest Response Ratio Next (HRRN)

Ein letztes in diesem Rahmen diskutiertes Verfahren wird Highest Response Ratio Next (HRRN) genannt. Es ist wieder ein bisschen komplexer als die bislang vorgestellten.

Die Priorität jedes Jobs errechnet sich so:

wobei die bisherige Wartezeit und wiederum die Bedienzeitforderung des Jobs repräsentieren. Auch dieses Verfahren bevorzugt kurze Jobs, denn ein kleinerer Nenner führt zu größerer Priorität. Zusätzlich bekämpft HRRN jedoch das Phänomen des Verhungerns: Je größer die Wartezeit eines Jobs ist, desto größer wird auch seine Priorität, da sich der Zähler des Bruches vergrößert. Bei mehreren gleich langen Jobs gewinnt derjenige, der bislang am längsten gewartet hat. Weisen alle Jobs die gleiche Wartezeit auf, wie im vorletzten Beispiel, dann degeneriert HRRN zu SJN. Somit beugt HRRN dem Verhungern der Jobs auf Kosten einer gegenüber SJN leicht erhöhten mittleren Verweilzeit vor.

Da sich die Wartezeit aller nicht abgearbeiteten Jobs permanent ändert, ändert sich deren Priorität. Somit müssen die Prioritäten in gewissen Zeitabständen neu berechnet werden, was den Aufwand gegenüber statischer Priorisierung erhöht.

Zur Veranschaulichung soll wiederum die Prozessmenge aus Tabelle 6.2 dienen. Es ist günstig, zunächst für jeden Zeitschritt die Prozessprioritäten zu ermitteln. Dies geschieht in Tabelle 6.3. Die jeweils höchste Priorität zu jedem Zeitpunkt ist durch Fettdruck hervorgehoben. Sobald ein Prozess bereit ist, startet er mit Priorität 1. Falls er nicht abgearbeitet wird, erhält er auf seine Priorität addiert. Bei identischen Prioritäten (wie zu oder ) kann ein beliebiger Prozess gewählt werden.

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13–19
A	1
B	1
C	1	1
D	-	-	1
E	-	-	-	1	2
F	-	-	-	1

Tabelle 6.3: Entwicklung der Prioritäten bei HRRN für die Prozesse der Beispielmenge

Den resultierenden Plan finden Sie in Abbildung 6.8. Auf den ersten Blick erkennbar ist, dass im Vergleich zu den bisher diskutierten Verfahren viel mehr Kontextwechsel nötig sind. Alle Prozesse bis auf B werden im Grunde nach jedem Zeitschritt unterbrochen. In realen Systemen sind jedoch die Ausführungszeiten viel größer, was im Vergleich zum Beispiel zu subtileren Prioritätsänderungen führt.

Abbildung 6.8: Resultierender Plan nach HRRN für die Prozesse aus Tabelle 6.2

Es existiert eine ganze Reihe weiterer Verfahren zum Jobscheduling, die Sie weiterführender Literatur entnehmen können. In den nächsten Abschnitten widmen wir uns lieber Algorithmen, die interessant für Universalbetriebssysteme sind.

Verfahren für Universalbetriebssysteme

Universalbetriebssysteme wie Windows oder Linux versuchen beim Scheduling, einen Kompromiss zwischen verschiedenen Leistungskenngrößen zu erzielen. Es überrascht daher kaum, dass diese ähnliche Konzepte beim Scheduling nutzen. Diese lernen Sie im folgenden Abschnitt kennen.

Zeit, scheibchenweise

Ein wichtiger Bestandteil vieler moderner Schedulingverfahren ist das sogenannte Zeitscheibenverfahren. In der englischen Literatur haben sich die Begriffe Time Slicing beziehungsweise Round Robin eingebürgert. Letzterer Begriff deutet an, dass alle Prozesse gleich oft an die Reihe kommen, denn hier geht es in erster Linie um Fairness.

Alle Prozesse im System erhalten reihum den Prozessor für eine gewisse Zeitspanne, das sogenannte Quantum, zugeteilt. Man spricht auch von einer »Zeitscheibe« (timeslice), da man sich mit etwas Fantasie die Prozessorzeit als unendliche Wurst vorstellen kann. Nach Ablauf des Quantums für einen Prozess wird dieser unterbrochen, und der nächste Prozess kommt an die Reihe. Es findet also ein Kontextwechsel zwischen diesen beiden Prozessen statt. Dieses Verfahren hat offenbar nur einen Sinn, wenn die Prozesse zu beliebigen Zeitpunkten unterbrochen werden können, es muss also präemptiv geplant werden. Aber, Moment mal: Wird denn hier überhaupt geplant? Es handelt sich offenbar um ein Online-Verfahren, der Plan wird also während der Laufzeit des Systems quasi nebenbei fortgeschrieben. Vorteilhaft ist, dass zur Laufzeit Prozesse hinzukommen und auch das System verlassen können, wie es bei interaktiver Arbeitsweise die Regel ist.

Prioritäten kennt das reine Zeitscheibenverfahren zunächst nicht; gibt es Prozesse, so erhält jeder der Prozessorzeit, allerdings in kleinen »Portionen«.

Ein kritischer Parameter ist die »Dicke« der Zeitscheibe . Wird sie zu groß gewählt, so dauert es vergleichsweise lange, bis ein Prozess wieder an die Reihe kommt. Dies kann zum Beispiel eine lange Reaktionszeit auf externe Ereignisse bewirken. Wird die Zeitscheibe zu klein gewählt, so wird die Rechenzeit sehr feingranular auf die einzelnen Prozesse aufgeteilt. Jedoch verbraucht das System anteilig besonders viel Zeit für den Kontextwechsel, da sehr viel umgeschaltet wird. Somit steht weniger Zeit für die Nutzerprozesse zur Verfügung.

Während im originalen UNIX die Länge von eine Sekunde betrug, liegt das Quantum heutiger Systeme etwa zwischen zehn und 150 Millisekunden.

In Abbildung 6.9 sind die wesentlichen zeitlichen Parameter dargestellt. Das Quantum haben Sie bereits kennengelernt. Die Dauer des Kontextwechsels (context switch) ist nicht maßstäblich; sie ist viel kleiner als das Quantum. Sie hängt wesentlich davon ab, wie viele Register die CPU besitzt, denn beim Kontextwechsel müssen diese einmal in den Hauptspeicher geschrieben und einmal aus diesem gelesen werden.

Abbildung 6.9: Parameter bei Round Robin

Unter der Antwortzeit (response time) versteht man die Zeit zwischen zwei Aktivierungen ein und desselben Prozesses, da innerhalb dieser Zeitspanne garantiert werden kann, dass der betreffende Prozess auf ein von außen eintreffendes Datum reagiert hat. Die Antwortzeit hängt offenbar von der Dauer des Kontextwechsels, von der Dauer der Zeitscheibe und der Anzahl der Prozesse im System ab, und es gilt:

Meist wird Round Robin mit Prioritäten kombiniert. Ein Beispiel dafür ist das Scheduling in Windows. Hier gibt es 32 Prioritätsstufen, wie Abbildung 6.10 verdeutlicht.

Die allerunterste Stufe 0 wird ausschließlich durch einen besonderen Systemthread, den sogenannten Zero Page Thread, genutzt. Die Stufen 1 bis 15 sind den »normalen« Nutzerthreads vorbehalten. Die Priorität dieser Threads wird durch verschiedene Mechanismen verändert, kann jedoch niemals den Bereich verlassen.

Aus Gründen besserer Vorhersagbarkeit sind die höchsten 16 Stufen, die sogenannten »Real-Time«-Levels, statisch; die Priorität entsprechender Threads kann also nicht verändert werden. Sie stehen auch ausschließlich Systemthreads zur Verfügung; betriebssystemspezifische Aufgaben haben also immer Vorrang. Die Bezeichnung »Real-Time« ist ein bisschen irreführend, denn Windows, genauso wie andere Universalbetriebssysteme, ist für Echtzeitaufgaben denkbar ungeeignet.

Abbildung 6.10: Prioritätsstufen in Windows

Wie arbeitet nun der Windows-Scheduler? Ganz einfach: Es wird stets der Thread mit der höchsten Priorität abgearbeitet und zwar, bis er terminiert oder blockiert (in den Zustand wartend übergeht). Gibt es mehrere Threads in der höchsten Prioritätsstufe, dann wird zwischen ihnen Round Robin ausgeführt. Das bedeutet: Je höher ein Thread priorisiert ist, desto häufiger muss er blockieren, und umso kleiner muss seine Abarbeitungszeit sein, denn sonst werden Threads mit niedrigeren Prioritäten niemals abgearbeitet.

Die Länge des Quantums ist konstant, hängt aber von zwei Faktoren ab:

1. Das Quantum von Editionen, die für Server entwickelt sind, beträgt zwölf »clock intervals«, für Client-Versionen zwei »clock intervals«.
2. Die Länge des »clock interval« beträgt 10 ms für Einprozessor-Systeme (aber solche Plattformen sind historisch zu nennen) und 15 ms für Mehrprozessor-Systeme.

Somit ergeben sich je nach Kombination beider Faktoren mögliche Werte für von 20, 30, 120 und 180 Millisekunden.

Die Priorität in den variablen Levels wird durch sogenannte »Priority Boosts« modifiziert, die zum einen die Reaktionszeit von bestimmten Threads verbessern, zum anderen das Verhungern von Threads verhindern sollen. Eine sehr ausführliche Darstellung des Mechanismus finden Sie in [24].

Klassisches UNIX

Ein-/Ausgabe- und berechnungsbeschränkte Prozesse

In Universalbetriebssystemen kann man zwei Klassen von Prozessen unterscheiden. Zum einen gibt es Prozesse, die vorwiegend mit Geräten interagieren: Dies kann eine direkte Interaktion mit dem Nutzer via Tastatur und Maus sein oder eine indirekte Interaktion über die Netzwerkkarte. Auch Kommunikation mittels eines Terminals oder mittels Browser zählt dazu. Prozesse, die viel mit dem Massenspeicher interagieren, fallen ebenso in diese Kategorie. Da sämtliche Geräte im Vergleich zur CPU sehr langsam arbeiten, muss der auf der CPU abgearbeitete Prozess laufend auf diese Bummelanten warten. Das Vorankommen eines solchen Prozesses hängt also maßgeblich von der Geschwindigkeit des Gerätes ab, deswegen nennt man diese Prozesse »Ein-/Ausgabe-beschränkte« Prozesse (I/O-bound processes).

In der gegenteiligen Kategorie sind Prozesse, die gerade nicht mit Geräten kommunizieren, sondern den Großteil ihrer Zeit ohne Interaktion in reiner Abarbeitung auf der CPU verbringen. Umfangreiche mathematische Berechnungen, das Mining von Bitcoins, aber auch Compilerläufe und Ähnliches zählen dazu. Diese Prozesse nennt man »rechenbeschränkt« (compute-bound), da ihr Fortschritt im Wesentlichen von der Geschwindigkeit der CPU abhängt.

Ein-/Ausgabe-beschränkte Prozesse erkennt man daran, dass sie häufig die ihnen zugeteilte Zeitscheibe nicht voll ausnutzen: Sie arbeiten ein kleines Stückchen und führen dann eine I/O-Operation mit dem betreffenden Gerät aus, meist einen read()- oder write()-Systemruf. Diese Rufe blockieren, bis das Gerät die geforderte Operation ausgeführt hat, und somit geht der Prozess in den Wartezustand, unabhängig davon, wie viel Zeit ihm in seiner Zeitscheibe noch zusteht. Nachdem das Gerät die Operation komplettiert hat, wird der Prozess wieder in die Bereitmenge aufgenommen und erhält eine neue Zeitscheibe, sobald ihn der Scheduler zur Abarbeitung auswählt.

Rechenbeschränkte Prozesse auf der anderen Seite nutzen ihre Zeitscheibe fast immer voll aus.

Natürlich ist diese Unterscheidung sehr grob, und es ist insbesondere auch denkbar, dass ein und derselbe Prozess Merkmale beider Klassen aufweist, indem er phasenweise rechenbeschränkt arbeitet und an anderer Stelle sehr viel I/O-Operationen ausführt. Nichtsdestotrotz hat es sich in allen modernen Systemen bewährt, diese beiden Klassen von Prozessen zu unterscheiden und getrennt zu priorisieren.

Scheduling im UNIX

Im voranstehenden Abschnitt haben Sie den Unterschied zwischen Ein-/Ausgabe-beschränkten und rechenbeschränkten Prozessen kennengelernt. Letztere werden häufig über einen längeren Zeitraum bearbeitet, bei ihnen kommt es nicht auf schnellstmögliche Komplettierung an: Wenn Sie eine fünfstündige Berechnung ausführen, ist es im Allgemeinen egal, ob diese eine oder zwei Minuten länger dauert. Auf der anderen Seite sind Ein-/Ausgabe-beschränkte Prozesse meist mit Interaktion verbunden. Der Nutzer erwartet hier eine schnelle Reaktion; es macht einfach keinen Spaß, an einem träge reagierenden System zu arbeiten.

Obwohl in UNIX der Begriff der Fairness eine große Rolle spielt und Prozesse typischerweise nach Round Robin geplant werden, nutzt es ebenso wie andere Universalbetriebssysteme Prioritäten. Die genaue Umsetzung der Prioritäten in eine konkrete Abarbeitungsreihenfolge ist erstaunlich kompliziert und differiert sowohl historisch für ein und dieselbe UNIX-Variante als auch für verschiedene UNIX-basierte Betriebssysteme, sodass auf eine detaillierte Beschreibung an dieser Stelle verzichtet wird. Grob kann man festhalten, dass eine höhere Priorität zu einer häufigeren Abarbeitung führt; der betreffende Prozess erhält mehr Zeitscheiben als niedriger priorisierte Prozesse.

Um das Antwortzeitverhalten interaktiver Prozesse zu verbessern, erhöht das Betriebssystem deren Priorität leicht im Vergleich zu rechenbeschränkten Prozessen. Diese erhalten also seltener Zeitscheiben, was ihre Komplettierung verzögert, aber im Allgemeinen akzeptabel ist. Die Diskriminierung zwischen interaktiven und rechenbeschränkten Prozessen erfolgt mittels Überwachung, ob diese die zugeteilten Zeitscheiben vollständig ausnutzen oder nicht, wie im vorangehenden Abschnitt beschrieben wurde.

Nette Prozesse

Die Entwickler von UNIX haben einen Mechanismus vorgesehen, mit dem der Nutzer auf die Priorisierung von Prozessen Einfluss nehmen kann: Mit dem Systemruf nice() (und den Kommandos nice und renice) kann man in beschränktem Maße die Priorität des rufenden Prozesses verändern.

Traditionell darf ein unprivilegierter Nutzerprozess seine eigene Priorität nur vermindern. Er tritt also freiwillig zugunsten anderer Prozesse Rechenzeit ab, er verhält sich nett; being nice würde der Engländer sagen, daher der etwas ungewöhnliche Name des Systemrufs.

Jeder Prozess besitzt einen sogenannten nice-Wert, der beispielsweise beim Kommando top in der Spalte »NI« angezeigt wird. Dieser Wert liegt zwischen +19 und -20, wobei der höhere Wert eine niedrigere Priorität bedeutet; der Parameter gibt sozusagen die »Nettigkeit« des Prozesses an. Der Ausgangswert für den nice-Wert ist 0. Mit root-Rechten ausgestattet, dürfen Sie diesen Wert auch verringern, also den betreffenden Prozess bevorteilen.

Die Abbildung zeigt einen Ausschnitt der Ausgabe des Kommandos top auf einem Vier-Kern-System, nachdem auf diesem acht identische rechenbeschränkte Prozesse (»a.out«) gestartet wurden. Da nur vier Kerne zur Verfügung stehen, erhält jeder der acht Prozesse ungefähr 50 % der Rechenzeit eines Kerns (Spalte %CPU). Ändert man an dieser Konfiguration nichts, so bleibt dieses Verhältnis bestehen, und die acht Prozesse schreiten gleich schnell voran, was man an der zugeteilten absoluten Rechenzeit sehen kann (Spalte TIME+).

Abbildung 6.11: Acht rechenbeschränkte Prozesse auf Vier-Kern-System, identische nice-Werte

Ändert man den nice-Wert von vier Prozessen mittels des renice-Kommandos auf 5, dann ändert sich das Verhältnis der zugeteilten CPU-Zeit. Die vier höher priorisierten Prozesse erhalten von nun an jeweils drei Viertel, die anderen nur noch ein Viertel der Rechenzeit. Die Prozesse schreiten daher unterschiedlich schnell voran.

Ändert man nun (mit root-Rechten) das nice-Level eines der höher priorisierten Prozesse auf -10, dann bekommt dieser Prozess plötzlich eine CPU für sich allein (er erhält 99,7 % der Rechenzeit eines Cores), die drei verbliebenen auf nice-Wert 0 erhalten ein »mittleres« Kontingent, und die vier niedrigstpriorisierten Prozesse werden weiter benachteiligt.

Das Beispiel illustriert, dass eine (Höher-)Priorisierung von Prozessen immer eine Benachteiligung anderer Prozesse nach sich zieht, denn die verfügbare Rechenzeit ändert sich durch das Priorisierungsschema nicht.

Das genaue Verhältnis der Rechenzeit hängt vom Verhältnis der nice-Werte ab; Linux achtet jedoch darauf, dass jeder Prozess ein Minimum an Rechenzeit erhält, egal, wie niedrig seine Gesamtpriorität ist.

Abbildung 6.12: Acht rechenbeschränkte Prozesse auf Vier-Kern-System, 4 x nice = 0, 4 x nice = 5

Abbildung 6.13: Acht rechenbeschränkte Prozesse auf Vier-Kern-System, 1 x nice = -10, 3 x nice = 0, 4 x nice = 5

Übungsaufgaben

1. Gegeben sei die Prozessmenge wie in diesemKapitel unter der Überschrift »Offline-Planung«. Erstellen Sie Offline-Pläne für drei Prozessoren:

   1. unter Beachtung der gegebenen Präzedenzen,
   2. ohne Beachtung der expliziten Präzedenzen (die Teilprozesse ein und desselben Prozesses sollen immer noch sequenziell aufeinander folgen).

   Um wie viel verkürzt sich die Gesamtbearbeitungszeit in beiden Fällen?

2. Ermitteln Sie für die Prozessmenge aus Tabelle 6.2 den Plan nach präemptivem SJN für einen Prozessor, und vergleichen Sie die mittleren Verweilzeiten für SJN und SRT.
3. In einem Rechensystem werden die Prozesse nach Round Robin geplant. Die Zeit für einen Kontextwechsel betrage 100 µs.
   1. Wie groß darf das Quantum maximal gewählt werden, damit bei 100 Prozessen die Reaktionszeit (die Zeit zwischen zwei aufeinander folgenden Aktivierungen) nicht größer als 1 s wird?
   2. Ermitteln Sie die mittlere Reaktionszeit bei zehn Prozessen und einem Quantum von 5 ms.
4. Experimentieren Sie mit verschiedenen nice-Levels. Wie viel Rechenzeit bekommt ein Prozess, der einen nice-Wert von 20 hat gegenüber Prozessen ohne diese Modifikation?